MATP6600 / DSES6780 Nonlinear Programming

Midterm Exam, Fall 1999

Take Home Due: Beginning of class, Wednesday, 3 November 1999.

This is to be all your own work. You may use any result from class, homeworks, or the books on reserve in the library. Do not consult anybody or anything else. I can dispense hints to help you if you are stuck. You can reach me by email at mitchj@rpi.edu. My phone number is 276-6915. The exam consists of five questions and is worth a total of 100 points. I will have my usual office hours as follows:

	Friday, 29 Oct:	1-1.50pm
	Monday, 1 Nov:	5-6pm

1.

(25 points.) Consider the nonlinear programming problem

$$\begin{array}{lccccr} \min & (x_1+3)^2 & + & (x_2+12)^2 \\... ...(x_2+8)^2 & \geq & 100 \\ & & & x_2 & \geq & 0. \end{array}$$

(a)

(3 points.) Is the feasible region for this problem convex?

(b)

(4 points.) Show that the gradients of the active constraints are linearly independent at any feasible point.

(c)

(3 points.) What are the Karush-Kuhn-Tucker conditions for this problem?

(d)

(3 points.) Verify that the points (6,0) and (-6,0) satisfy the KKT conditions.

(e)

(4 points.) Show that there are no points which satisfy x₁²+(x₂+8)²>100 and also satisfy the KKT conditions.

(f)

(4 points.) Are there any other points which satisfy the KKT conditions?

(g)

(4 points.) Can you find the global minimizer?

2.

(20 points.)

(a)

(10 points.) Let $Y=[y_1 \ldots y_m]$ be an n x m matrix, so y_i is the ith column of Y. Let $u \in {\Re}^m$ with $u \geq 0$ and $\sum_{i=1}^mu_i=1$. The matrix Y and the vector u are given. Show that x=Yu solves

$$\min \sum_i \frac{1}{2} u_i \Vert x-y_i \Vert _2^2.$$

(b)

(10 points.) Suppose you have an algorithm for minimizing a convex quadratic function subject to linear constraints. How could you solve the problem

$$\min_x \max_i \Vert x-y_i \Vert _2^2,$$

where $y_1, \ldots ,y_m$ are distinct given points in ${\Re}^n$? (Note: a quadratic function has the form f(w)=w^TQw+c^Tw+d, where Q is a matrix, c is a vector, and d is a scalar.)

3.

(15 points. Each part is worth 5 points.)
Consider the nonlinear programming problem

$$\begin{array}{lccl} \min & \frac{1}{2}x^TMx \\ \mbox{s.t.} & \frac{1}{2}x^Tx & = & \frac{1}{2}. \end{array}$$

(P)

Assume M is (n x n) and symmetric. Let the eigenvalues of M be $\lambda_1\leq\lambda_2\leq\ldots\leq\lambda_n$. Assume $\lambda_1<0$ and $\lambda_1<\lambda_2$. We saw in Homework 4 that the optimal solutions to this problem are the eigenvectors with eigenvalue $\lambda_1$ and norm $\sqrt{x^Tx}=1$. (Recall: $\lambda$ is an eigenvalue of A if $Ax=\lambda x$ for some nonzero vector x; a nonzero x satisfying this equation for some $\lambda$ is an eigenvector of A with eigenvalue $\lambda$. A is positive definite if and only if all the eigenvalues of A are positive. A is positive semi-definite if and only if all the eigenvalue of A are nonnegative. If A has eigenvalues $\mu_1$,...,$\mu_n$ then A+aI has eigenvalues $\mu_1+a$,...,$\mu_n+a$.)

(a)

What is the Lagrangian dual function $\theta(v)$ for this problem? (Take $X=\Re^n$.)

(b)

Solve the Lagrangian dual problem.

(c)

Let $\hat{v}$ solve the Lagrangian dual problem. Let $X(\hat{v})$ be the set of points in X which achieve the infimum in the definition of $\theta(v)$. Show that $X(\hat{v})$ contains infinitely many points and that one of them solves the primal problem.

4.

(a)

(10 points.)  Consider the two sets of points A={a¹,...,a^k} and B={b¹,...,b^m} in ${\Re}^n$. Show that the two sets of points can be strictly separated if and only if there exists a vector $x\in\Re^n$ and a scalar $\gamma$ satisfying

$$\begin{array}{rcrcll} {a^i}^T x & - & \gamma & \geq & 1, &... ... -{b^j}^T x & + & \gamma & \geq & 1, & j=1,...,m. \end{array}$$

(Here, by strictly separate, I mean that the separating hyperplane does not contain any points in either A or B.)

(b)

(10 points.) The problem in part 4a is a linear programming feasibility problem with variables x and $\gamma$. It can be stated as an optimization problem if we use the objective function $\min 0^Tx+0\gamma$, which is zero for any feasible solution. What is the dual of this linear program? If the dual problem has a feasible nonzero solution, what does that imply about the primal problem given in part 4a? Can you give a geometric meaning for a nonzero solution to the dual problem?

5.

(20 points.) Let $f:{\Re}^n\rightarrow\Re$ be C¹ (ie, the first derivative is continuous).

(a)

(8 points.)  Show that the first order necessary conditions for $\bar{x}$ to be a local minimizer of f over ${\Re}^n_+$ are $\bar{x}\geq{0}$, ${\nabla}f(\bar{x}){\geq}0$, and ${\bar{x}}^T{\nabla}f(\bar{x})=0$. (Note: ${\Re}^n_+ := \{x \in {\Re}^n: x \geq 0\}$.)

(b)

(6 points.)   Let $F:{\Re}^n \rightarrow {\Re}^n$ be strictly monotone. (A function G is strictly monotone if $x\neq y \Rightarrow (G(y)-G(x))^T(y-x) > 0$.) Show that F has at most one zero (an $\bar{x}$ with $F(\bar{x})=0$) and that the nonlinear complementarity problem (find $\bar{x}\geq{0}$ with $F(\bar{x}) \geq 0$ and $\bar{x}^TF(\bar{x})=0$) has at most one solution.

(c)

(6 points.) Using the results of parts 5a and 5b, show that, if f is strictly convex, it has at most one minimizer over ${\Re}^n$ and at most one minimizer over ${\Re}^n_+$. (Hint: We know that f is strictly convex if $x \neq y, \lambda \in (0,1) \Rightarrow f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda) f(y)$. You may assume that f is strictly convex if and only if ${\nabla}f$ is strictly monotone.)