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

{\large\bf C\&O 367 \\ 
Assignment 4 
}
\end{center}
\begin{flushleft}
{\large  Due on Thursday, Nov. 18,~~~~   Instructor H. Wolkowicz
}
\end{flushleft}

\begin{enumerate}

\item
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
Verify the optimal solution $(1,0)^T$ and the 
KT conditions for the following problem:
\begin{equation}
\begin{array}{rl}\ds
	\min_{x,y}	& -x				\\*[5pt]
	\st	& 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}\ds
	\min_x 	& \lp \half x\T Q x -b\T x \rp	\\*[5pt]
	\st	& 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}).  (You may assume that $Q$ is symmetric.
Note that no other assumptions on $A$
or $Q$ are necessary.)
\item
Solve the problem
\begin{equation}
\begin{array}{rl}\ds
	\max	& \lp 14x - x^2 - y^2 + 7 \rp		\\*[5pt]
	\st	& x + y \le 2		\\*[3pt]
		& x + 2y \le 3
\end{array}
\end{equation}
\item
Solve the problem
\begin{equation}
\begin{array}{rl}\ds
	\min	& \exp{-(x+y)}				\\*[5pt]
	\st	& \exp{x} + \exp{y} \le 20		\\*[3pt]
		& x \ge 0
\end{array}
\end{equation}
\item
Find the point on the plane $x + 2y + 3z = 6$ that is closest to the origin.
\item
Find the open rectangular box with fixed surface area $S_0$ that has
the largest volume.
\item
Find the solution $x^*$ and multiplier for the
quadratic programming problem:
\begin{equation} 
\begin{array}{rl}\ds
	\min_x	& \half x\T Q x + b\T x		\\*[10pt]
	\st	& x_1 + 2x_2 + x_3 = 4
\end{array}
\end{equation}
where
\[
Q =
\lb
\begin{array}{rrr}
3 &-1 & 0	\\
-1 & 2 & -1	\\
0 & -1 & 1
\end{array}
\rb
\]
and
\[
	b\T = (1,1,1)
\]
Does $x^*$ solve the QP
\begin{equation} 
\begin{array}{rl}\ds
	\min_x	& \half x\T Q x + b\T x		\\*[10pt]
	\st	& x_1 + 2x_2 + x_3  \ge 4		\\*[5pt]
		& x_1, x_2, x_3 \ge 0.
\end{array}
\end{equation}
\item
Find the point that is closest to the origin (Euclidean Distance) and satisfies the
constraints:
\begin{eqnarray*}
	x + 2y - z & \ge & 4	\\
	-x + y - z & \le & 2
\end{eqnarray*}
\item
Let $Q$ be an $n \times n$ positive definite matrix, and let $A$ be an $m \times n$
matrix of rank $m$.  Determine the optimal value function of the QP
as a function of $b$
\[
\begin{array}{rl}\ds
	\min	&	\half x\T Q x + b\T x	\\*[10pt]
	\st	&	Ax = 0
\end{array}
\]
\item
Use Zoutendijk's feasible direction method to solve the following two
problems.

\begin{enumerate}
\item
\[ \begin{array}{cc}
   \max & -x_1-x_2 \\
\mbox{subject to~} & x_1 - x_1^2  \geq 0 \\
                 & x_2 - x_2^2  \geq 0 
 \end{array}
\]
with initial point $(0,1)^t$.
\item
\[ \begin{array}{ccc}
   \max & -x_1-x_2-x_3 \\
\mbox{subject to~} & -x_1^2 - x_2^2 +2  &\geq 0 \\
                &  -(x_1-2)^2 - (x_2-2)^2 +2  &\geq 0 \\
                 & -x_3^2 + 4x_3  &\geq 0 
 \end{array}
\]
with initial point $(1,1,1)^t$.
\end{enumerate}
\end{enumerate}
\end{document}