\documentclass{amsart}
%\input macros

\pagestyle{empty}
\textwidth 7.5in
\textheight 9.8in
\oddsidemargin -0.5in
\evensidemargin -0.5in
\topmargin -0.7in

\usepackage{amsmath,epsfig,amssymb}

\newcommand{\eps}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rn}{\R^n}
\newcommand{\Rm}{\R^m}
\newcommand{\Rnn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\map}[3]{#1:#2\rightarrow #3}
\newcommand{\grad}{\nabla}
\newcommand{\lam}{\lambda}
\newcommand{\uball}{\mathbb{B}}
\newcommand{\set}[2]{\left\{#1\,\left|\, #2\right.\right\}}
\newcommand{\diag}[1]{\mathrm{diag}(#1)}

\def\bx{{\bar x}}
\def\by{{\bar y}}
\def\bw{{\bar w}}


\begin{document}
\noindent {\Large AMATH/MATH 516 \hfill \\ FIFTH HOMEWORK SET}
\medskip

%\noindent
%Due Wednesday, May 10.
\medskip

\begin{enumerate}
\item  
Let $\map{f}{\Rn}{\R}$ be smooth and $S\subset\Rn$ be a subspace of $\Rn$.
Given $x^0\in\Rn$, show that if $\bx\in\Rn$ is a local solution to
$\min\set{f(x)}{x\in x^0+S}$, then 
\begin{equation}\label{fooc}\tag{$*$}
\nabla f(x)\perp S\ .
\end{equation} 
\item
Let $Q\in\Rnn,\ c\in\Rn,\ A\in\Rmn$, and $b\in\Rm$, with $Q$ symmetric and positive definite, and
consider the optimization problem
\(\min\set{\half x^TQx+c^Tx}{Ax\le b}\)
and its relaxation
\[
\mathcal{R}\qquad\min\set{\half x^TQx+c^Tx-t\sum_{i=1}^n\ln(y_i)}{Ax+y= b}\ ,
\]
where $t>0$ and we define $\ln(\mu)=-\infty$ if $\mu\le 0$.
\begin{enumerate}
\item
Use the optimality condition (\ref{fooc}) to show that the optimality conditions for $\mathcal{R}$
can be written as
\begin{equation}\label{cp}\tag{$**$}
\exists\; y,w\in\Rm_+\ \mbox{  s.t.  }Ax+y=b,\ Qx+A^Tw+c=0\mbox{  and  }
\diag{w}\diag{y}\mathbf{1}=t\mathbf{1}\ ,
\end{equation}
where $\mathbf{1}$ is always the vector of all ones of the appropriate dimension.
\item Show that if $(x^k,y^k,w^k,t_k)$ is a sequence of points satisfying (\ref{cp}) with
$t_k\downarrow 0$, then every cluster point of this sequence $(\bx,\by,\bw,0)$ is such that
$\bx$ solves \(\min\set{\half x^TQx+c^Tx}{Ax\le b}\).
\end{enumerate}
\item
Let $Q\in\Rnn$ be symmetric and positive definite, and let $c\in\Rn$.
%Show that the Lagrangian dual of the 
Consider the optimization problem
\[\min_{0\le x}\half x^TQx+c^Tx\ .\]
\begin{enumerate}
\item What is the Lagrangian function for this problem?
\item Show that the Lagrangian dual
is the problem
\[
\max_{y\le c}-\half y^TQ^{-1}y\qquad =\qquad-\,\min_{y\le c}\,\half y^TQ^{-1}y\ .
\]
\item Show that
if $\bx,\by\in\Rn$ satisfy $\by=-Q\bx$, then
$\bx$ solves the primal problem if and only if $\by$ solves    
the dual problem, and the optimal values in the primal and dual
coincide.
\end{enumerate}
\item 
Let $Q\in\Rnn$ be symmetric and positive definite.
%Show that the Lagrangian dual of the problem
Consider the optimization problem 
\[
\begin{array}{lll}
\mathcal{P}&\mbox{minimize}&\half x^TQx+c^Tx\\
&\mbox{subject to}&\norm{x}_\infty \le 1\ .
\end{array}
\]
\begin{enumerate}
\item Show that this problem is equivalent to the problem
\[
\hat{\mathcal{P}}\begin{array}{lll}
\mbox{minimize}&\half x^TQx+c^Tx\\
\mbox{subject to}&-e\le x \le e\ ,
\end{array}
\]
where $e$ is the vector of all ones.
\item What is the Lagrangian for $\hat{\mathcal{P}}$?
\item Show that the Lagrangian dual for $\hat{\mathcal{P}}$
is the problem
\[
\mathcal{D}\qquad \max\,-\half (y-c)^TQ^{-1}(y-c)-\norm{y}_1\qquad =\qquad 
-\, \min \half (y-c)^TQ^{-1}(y-c)+\norm{y}_1\ .
\]
This is also the Lagrangian dual for $\mathcal{P}$.
\item
Show that if $\bx,\by\in\Rn$ satisfy $\by=Q\bx+c$, then
$\bx$ solves $\mathcal{P}$ if and only if $\by$ solves 
$\mathcal{D}$, and the optimal values in $\mathcal{P}$ and $\mathcal{D}$
coincide.
\end{enumerate}
\item
Let $K\subset\Rm$ be a non-empty closed convex cone.
\begin{enumerate}
\item If $K=\R^s_+\times\{0\}^{m-s}$, show that for every $x\in K$,
$N(x\, |\, K)=\set{y\in\R^m}{0\le y_i, \ y_ix_i=0,\ i=1,\dots,s}$.
\item Show that, in general, $ N(x\, |\, K)=\set{y\in K^\circ}{\langle x,\, y\rangle=0}$.
\item
Show that $\mathrm{dist}\,(x\,|\,K)=[\delta^*(\cdot\,|\,\mathbb{B}^\circ)\,\square\, \delta(\cdot |\, K)](x)$,
that is, $\mathrm{dist}\,(x\,|\,K)$ is the infimal convolution of $\delta^*(\cdot\,|\,\mathbb{B}^\circ)$
and $\delta(\cdot |\, K)$, where $\mathbb{B}$ is the unit ball of the norm defining
$\mathrm{dist}\,(x\,|\,K):=\inf\set{\norm{x-y}}{y\in K}$.
\item
Given $f_1,f_2\in\Gamma(\Rn)$, set $f=f_1\,\square\, f_2$.
Show that $f^*=f_1^*+f_2^*$, where 
\[
[f_1\,\square\, f_2](x):=\inf\set{f_1(x_1)+f_2(x_2)}{x_1+x_2=x}.
\]
\item
Use the previous two parts of this problem to show that 
$\mathrm{dist}\,(x\,|\,K)=\delta^*(x\, |\, \mathrm{B}^\circ\cap K^\circ)$ by using the fact that
$f=f^{**}$ for all $f\in\Gamma(\Rn)$.
\item
Given $x\in K$, show that $\partial \mathrm{dist}\,(x\,|\,K)=\mathrm{B}^\circ \cap N(x\, |\, K)$.
\end{enumerate}




\end{enumerate}
\end{document}
