\documentstyle[12pt]{article}
\begin{document}
\begin{center}

{\large\bf C\&O 367 \\ 
Assignment 3 
}
\end{center}
\begin{flushleft}
{\large  Due on Thursday, Mar. 10,~~~~   Instructor H. Wolkowicz
}
\end{flushleft}

\begin{enumerate}
\item
Let $H \in \Re^{n \times n}$ be symmetric and positive definite,
$g \in \Re^{n}$. Prove that
$(g^{t}g)^{2} \leq (g^{t}Hg)(g^{t}H^{-1}g)$. [Hint. Use the Cauchy-Schwartz 
inequality.]

\item
For the steepest descent method with exact line searches, show that 
the search direction $s^{(k+1)}$ is orthogonal to $s^{(k)}$ for all $k$.
Apply the method to the function $f(x) = 10x_{1}^{2} + x_{2}^{2}$ from 
$x_{1} = (1/10,1)^{t}$. It can be shown that in the worst case the
method has linear convergence at a rate $(\lambda_{1}-\lambda_{n})/
(\lambda_{1}+\lambda_{n})$, where $\lambda_{1}$ and $\lambda_{n}$ 
are the largest and smallest eigenvalues of $G^{*}$, the Hessian
at the optimum. Verify numerically that this rate is achieved
in this example. Notice that if $G^{*}$ is sufficiently
ill-conditioned, this rate can be arbitrarily close to unity.

\item
Sketch contours of the function
$$ f(x) = x_{1}^{2}+4x_{2}^{2}-4x_{1}-8x_{2}.$$
Deduce the value $x^{*}$ which minimizes $F$. 
Show that if the method of
steepest descent is started from $x^{(1)}=(0,0)^{t}$, it cannot converge to
$x^{*}$ in a finite number of steps. Are there any values of $x^{(1)}$
for which there will be convergence in a finite number of steps?
\item
Consider the following problem:
\begin{eqnarray*}
Minimize & \frac{4}{3}(x_1^2-x_1x_2+x_2^2)^{\frac{3}{4}} - x_3\\
subject ~ to & -x_1,-x_2,-x_3 \leq 0\\
       & x_3 \leq 2
\end{eqnarray*}
Show that the objective function is convex and that the optimal solution
is attained at the unique point $\overline{x}=(0,0,2)^t$.
Let the initial point be $x_1=(0,a,0)^t$, where $a \leq 1/(2\sqrt{2})$.
\begin{enumerate}
\item
Solve the problem using the matlab function CONSTR. (You may want to
use the lower and upper bounds on the variables option.)
\item
Find a feasible direction $d$ at the current iterate $x_k$ using the program:
\begin{eqnarray*}
Minimize & \nabla f(x_k)^td\\
subject~to &  \hat{A}_kd \leq 0\\
           &   d^td \leq 1
\end{eqnarray*}
where $\hat{A}_1$ is the matrix whose rows are the gradients of the active
constraints at $x_k$. Show that Zoutendijk's method with exact
line search yields the sequence
\begin{eqnarray*}
x_k = \left\{ \begin{array}{ll}
               \left[0,(\frac{1}{2})^{k-1}a,\frac{1}{2}
                   \sum_{j=0}^{k-2}(\frac{a}{2^j})^\frac{1}{2}\right] & 
                                    if~k~is~odd,~k \geq 3 \\
               \left[(\frac{1}{2})^{k-1}a,0,\frac{1}{2}
                   \sum_{j=0}^{k-2}(\frac{a}{2^j})^\frac{1}{2}\right] & 
                                    if~k~is~even
               \end{array}
       \right.
\end{eqnarray*}
Does this sequence converge to the optimum? Why? How would you correct
the problem?
\end{enumerate}

\item
The set $C \subset \Re^n$ is a {\em cone} if
\[ x \in C,~ \alpha \in \Re~ \mbox{implies}~ \alpha x \in C.\]
Let $C$ be a cone.  Prove that $C$ is convex if and only if for every $x,y
\in C$, the vector $x+y\in C$.
\item
Find the optimal solution and verify the 
KKT conditions for the following problem:
\begin{equation}
\begin{array}{rl}
	\min_x	& -x				\\*[5pt]
	\mbox{subject to~}	& x^2 + y^2 \le 1		\\
		& (x-1)^3 - y \le 0
\end{array}
\end{equation}
\item
Consider the quadratic program
\begin{equation} \label{p:quad}
\begin{array}{rl}
	\min_x 	& (\frac 12 x^t Q x -b^t x )	\\*[5pt]
	\mbox{subject to~}	& A x = c
\end{array}
\end{equation}
Show that $x$ is a local minimum of (\ref{p:quad}) if and only if $x$ is a
global minimum of (\ref{p:quad}).  (Note, no assumptions on $A$
or $Q$ are necessary.)

\item
Find the point on the plane $x + 2y + 3z = 6$ that is closest to the origin.
\end{enumerate}
\end{document}