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

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

{\bf NOTE:} Several exercises are marked: {\bf Do not hand in.}
\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
{\bf (Do not hand in.)}
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
({\bf Do not hand in.}) 
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
({\bf Do not hand in.}) 
Find an elimination factorization for the QP:
\begin{equation} 
\begin{array}{rl}\ds
	\min_x	& x^2 - xy + y^2 -yz + z^2 + 2x - y	\\*[10pt]
	\st	& 3x - y + z = 0		\\*[5pt]
		& 2x - y - z = 0
\end{array}
\end{equation}
Use it to find an optimal solution and corresponding multipliers.
\item
({\bf Do not hand in.}) 
Starting from $x = 0$, illustrate the steps taken by the active set method for solving
the QP:
\begin{equation} 
\begin{array}{rl}\ds
	\min_x & x_1^2 - x_1 x_2 + x_2^2 - 3x_1			\\*[10pt]
	\st	& x_1 + x_2 \le 2				\\*[5pt]
		& x_1,x_2 \ge 0
\end{array}
\end{equation}
\item
({\bf Do not hand in.}) 
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
({\bf Do not hand in.}) 
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}
\]
\end{enumerate}
\end{document}
