Nonlinear Programming, MATP6600/DSES6780
Final Exam, Monday, December 13, 1999.

Please do all five problems. You must show all work to obtain full credit. Results from class or the text may be used if properly stated. No books or calculators allowed. The exam lasts three hours.

In order that I can display grades, please write a 4 digit code number on the front of your solution set. The grades will be available from the course web page.

1.

(15 points)
For given differentiable functions $f_1,\ldots,f_n : I\!\! R\rightarrow I\!\! R$, consider the optimization problem:

$$\begin{array}{lcrcll} \min & f(x) := & \sum_{i=1}^n f_i(x_i)... ... && x_i & \geq & 0 & \mbox{ for all } i=1,\ldots,n \end{array}$$

Let $\bar{x}=(\bar{x}_1,\ldots,\bar{x}_n)$ be a local minimizer for this problem. Show that there is a real number $\alpha$ with

$$\begin{array}{rcll} f'_i(\bar{x}_i) & \geq & \alpha & \mbox{... ... \bar{x}_i & = & 0 & \mbox{ for all } i=1,\ldots,n, \end{array}$$

where $f'_i(\bar{x}_i)$ denotes the derivative of f_i evaluated at $\bar{x}_i$.

2.

(20 points) In this problem, we consider the unconstrained quadratic program $\min \frac{1}{2}x^TAx + c^Tx$, where A is a symmetric n x n matrix, and c and x are n-vectors.

(a)

(5 points) Assume A is positive definite. Show that the optimal solution is x^*=-A^-1c.

(b)

(10 points) Assume A is positive definite. Show that steepest descent with an exact linesearch will find the optimal solution to this problem in one step if it is initialized at x⁽⁰⁾=v-A^-1c, where v is an eigenvector of A.

(c)

(5 points) Now assume A has a negative eigenvalue. Show that the problem has an unbounded optimal value.

3.

(20 points) Consider the constraint x₁²+x₂²=1. Given a point $\bar{x}$, what is the linearized version of this constraint? What do you get for the following choices of $\bar{x}$?

$$\bar{x}=(1,0), \quad \bar{x}=(0,0), \quad \bar{x}=(0,-2), \quad \bar{x}=(0.01,-0.2).$$

4.

(25 points)
Consider the convex optimization problem

$$\begin{array}{llcrcccl} \min & \frac{1}{2}x_1^2 & + & x_2 & ... ...column{5}{l}{X := \{x \in I\!\! R^2: x_2 \geq 0\}.} \end{array}$$

(a)

(5 points) Show that the objective function is convex.

(b)

(4 points) Formulate the Lagrangian dual problem by incorporating the first constraint in the objective with scalar multiplier u.

(c)

(8 points) Compute the value of the dual function and its gradient when u=4. (Hint: $\ln(2)=0.7$, $\ln(3)=1.1$, $\ln(4)=1.4$, $\ln(5)=1.6$, $\ln(6)=1.8$, $\ln(7)=1.9$, $\ln(8)=2.1$, $\ln(9)=2.2$, and $\ln(10)=2.3$.)

(d)

(8 points) When u=0, the Lagrangian is minimized by x=(0,3), with $\theta(0)=-4.4$ and $\frac{d\theta}{du}(0)=4$. When u=6 it is minimized by x=(6,12.7), to one decimal place, with $\theta(6)=-52.6$ and $\frac{d\theta}{du}(6)=-21.4$. Use this information to find upper and lower bounds on the optimal value of the primal problem.

5.

(20 points) Let $f:I\!\! R^n \rightarrow I\!\! R$, $g: I\!\! R^n \rightarrow I\!\! R^m$ be convex and differentiable on $I\!\! R^n$. Let $g(\hat{x})<0$ for some $\hat{x}$. Suppose that $x(\alpha)$ is a solution of the penalty function problem

$$\min_{x \in I\!\! R^n} f(x) + \frac{\alpha}{2} \parallel g(x)_+ \parallel^2_2$$

where $\parallel . \parallel_2$ denotes the usual Euclidean 2-norm, $(g(x)_+))_i = \max \{g_i(x),0\}$, $\alpha$ is a positive number, and $g(x(\alpha)) \not\leq 0$.

(a)

(5 points) Show that $f(\hat{x})$ is an upper bound and $f(x(\alpha)) + \frac{\alpha}{2} \parallel g(x(\alpha))_+ \parallel^2_2$ is a lower bound to $\inf_x \{f(x) \vert g(x) \leq 0\}$.

(b)

(15 points) Give an upper bound to $\inf_x \{f(x) \vert g(x) \leq 0\}$ which depends on both $x(\alpha)$ and $\hat{x}$.