MATP6600 / DSES6780 Nonlinear Programming

Midterm Exam, Fall 2007

Take Home Due: Beginning of class, Friday, 19 October 2007.

This is to be all your own work. You may use any result from class, homeworks, or the books on reserve in the library. I will have my usual office hours on Tuesday from 2-3pm and Wednesday from 11am-noon. Do not consult anybody or anything else. The exam consists of five questions and is worth a total of 100 points.

1. (40 points + 10 points Extra Credit; each part is worth ten points.) A quadratic programming problem can be written in the form:
   
   $$\begin{array}{lrclr} \min_x & \multicolumn{3}{l}{c^Tx + \fra... ...ect to} & Ax & \leq & b & \qquad \qquad \qquad (QP) \end{array}$$
   
   
   Here, $x$ and $c$ are $n$-vectors, $b$ is an $m$-vector, $A$ is an $m \times n$ matrix, and $Q$ is a symmetric $n \times n$ matrix. The variables $x$ and the parameters $b$, $c$, $A$, and $Q$ are all real numbers. The recession cone for this problem is $\mathcal{R}:=\{d \in I\!\!R^n : Ad \leq 0\}$ and the feasible region is $\mathcal{S}:=\{x \in I\!\!R^n: Ax \leq b\}$. Assume $d^TQd \geq 0$ for all $d \in \mathcal{R}$.

   (Hint: Questions 4 and 5 on Homework 3 are examples of problems of this form.)

   1. Assume there exists a feasible point $x$ and a direction $d \in \mathcal{R}$ satisfying $(c+Qx)^Td < 0$ and $d^TQd=0$. Show that the optimal value of $(QP)$ is unbounded below.
   2. Show that if the optimal value of $(QP)$ is unbounded below then there exists a point $x \in \mathcal{S}$ and a direction $d \in \mathcal{R}$ such that $(c+Qx)^Td < 0$ and $d^TQd=0$.
   3. Let $\bar{x}$ be a Karush-Kuhn-Tucker point for $(QP)$. Show that $(c+Q\bar{x})^Td \geq 0$ for any $d \in \mathcal{R}$.
   4. Let $x^1$, ..., $x^k$ be Karush-Kuhn-Tucker points for $(QP)$. Show that the following quadratic progam has a finite optimal value:
      
      $$\begin{array}{lrcrcrclr} \min_{x,\lambda,d} & \multicolumn{7... ... &&& \lambda_i &&& \geq & 0 \; \; \; i=1,\ldots,k. \end{array}$$
      
      
      Here, $x$, $c$, $A$, and $Q$ are as defined before, $d$ is an $n$-vector, and each $\lambda_i$ is a scalar.
   5. (Extra Credit: 10 points.) Either prove that every global optimal solution to $(QPK)$ is a KKT point for $(QP)$ or give a counterexample.

2. In the nonlinear programming problem
   
   $$\begin{array}{lrclr} \min & c^Tx \\ \mbox{subject to} & \fr... ...uad \qquad (NLP) \\ & \frac{1}{2}x^TQx & \leq & q, \end{array}$$
   
   
   $c$ and $x$ are $n$-vectors with $c \neq 0$, $M$ and $Q$ are $n \times n$ symmetric positive definite matrices, and $m$ and $q$ are positive scalars. The Lagrangian is
   
   $$L(x,u) = c^Tx + u_1(\frac{1}{2}x^TMx - m) + u_2 (\frac{1}{2}x^TQx - q)$$
   
   
   where $u_1$ and $u_2$ are scalars and $u^T=(u_1,u_2)$. The Lagrangian dual function $\theta(u)$ is defined in the usual way and the Lagrangian dual problem is to maximize $\theta(u)$ over the nonnegative quadrant.
   1. (5 points.) Show constraint qualification holds for $(NLP)$ at all feasible points.
   2. (5 points.) Show that $\theta(0)=-\infty$.
   3. (10 points.) Give a general expression for $\theta(u)$ for $u \geq 0$, $u \neq 0$.
   4. Now let $c$, $M$, and $Q$ be as follows:
      
      $$c = \left[ \begin{array}{r}2 \\ 2 \end{array} \right], \quad... ...r} 1 & -2 \\ -2 & 5 \end{array} \right], \quad m=8, \quad q=1.$$
      
      
      1. (10 points.) Find $\theta(1,0)$, $\theta(0,1)$, and $\theta(1,1)$, and find the gradients of $\theta(u)$ at these three points.
      2. (5 points.) Hence find upper and lower bounds on the optimal value of the dual problem. (You can use a linear programming package in this part.)

3. Given a symmetric real $n \times n$ matrix $Q$, define the nonlinear program
   
   $$\begin{array}{lrclr} \min & \frac{1}{2}x^T Q x \\ \mbox{sub... ...{2}x^T x & \leq & \frac{1}{2}& \qquad \qquad (NLEV) \end{array}$$
   
   
   where $x$ is an $n$-vector. Assume $Q$ has $n$ different eigenvalues. Since $Q$ is a symmetric matrix, it can be diagonalized; that is, $Q = V^T D V$, where $D$ is a diagonal matrix and the columns of $V$ are eigenvectors of $Q$. The columns of $V$ give an orthonormal basis for $I\!\!R^n$.
   1. (5 points.) Show the optimal solution to $(NLEV)$ is $x=0$ if $Q$ is positive semidefinite.
   2. Now assume $Q$ is not positive semidefinite.
      1. (10 points.) Show that the Karush-Kuhn-Tucker points of $(NLEV)$ are the eigenvectors of $Q$ with nonpositive eigenvalue and with norm one.
      2. (10 points.) Show that the KKT points corresponding to one of the eigenvalues satisfy the second order sufficient conditions, and show that the KKT points corresponding to the other eigenvalues do not satisfy the second order necessary conditions. What do you conclude?