%======================= main.tex ===========================================
\documentclass{slides}
\usepackage{latexsym}
%\usepackage{amsfonts}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\p}{{\cal P}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}
\pagestyle{plain}
\begin{document}
%\bibliographystyle{plain}
%\blackandwhite{example}
%======================= example.tex
%  the file example.tex must exist - it is empty though
%======================= 
%======================= 
\begin{slide}{}
\begin{center}
{\bf DUALITY \\
      FOR \\
    SEMIDEFINITE AND CONVEX PROGRAMMING}
\end{center}
 

~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz\\
University of Waterloo

(work with: Serge Kruk, Levent Tuncel, Motakuri Ramana, Jon
Borwein)

\end{slide}
\begin{slide}{}
\begin{center}
{\bf DUALITY \\
      FOR \\
    SEMIDEFINITE AND CONVEX PROGRAMMING}
\end{center}
 

~~\\
~~\\
~~\\
~~\\
~~\\
\end{slide}
\begin{slide}{}

     \begin{center}
HISTORY
    \end{center}
From various sources, e.g.\\

 article by Harold Kuhn in:\\
 NLP SIAM-AMS Proceedings Volume IX, 1976.


\end{slide}
\begin{slide}{}

\begin{quote}
The Lagrange multiplier method leads to several transformations which
are important both theoretically and practically.

By means of these transformations new problems equivalent to a given
problem can be so formulated that stationary conditions occur
simultaneously in equivalent problems. In this way we are led to
transformations of the problems which are important because of their 
symmetric character. Moreover, for a given maximum problem with maximum 
$M$, we shall
often be able to find an equivalent minimum problem with the same value 
$M$ as minimum; this is a useful tool for 
bounding $M$ from above and below. (Courant and Hilbert)
\end{quote}

\end{slide}
\begin{slide}{}


Von Neumann in 1940's had a duality for LPs which was based on
 using game theory (see collected works);
%\cite{vonNeum:63}

 it formed the basis for Dantzig's simplex method

Later: Gale, Kuhn, Tucker developed a duality theory
for general problems

\end{slide}
\begin{slide}{}

Problem 1:
\begin{quote}
Given three points in the plane, find a
fourth point such that the sum of its distances to the three given
points is minimum.
(17th Century Fermat Problem )
\end{quote}

Problem 2:
\begin{quote}
In the three Sides of an equiangular Field stand three Trees, at the
Distances of 10, 12, and 16 Chains from one another: To find the Content
of the Field, it being the greatest the Data will admit of?
(The Ladies Diary or Woman's Almanack (1755) problem posed by Mr
Tho. Moss (pg 47) )
\end{quote}

\end{slide}
\begin{slide}{}
\begin{quote}
Given any triangle, circumscribe the largest possible equilateral
triangle about it.
(Annales de mathematiques Pures et Appliquees, edited by J.D. Gergonne,
Vol I (1810-11), Problem posed on Page 384)
\end{quote}

\end{slide}
\begin{slide}{}

Solution: 
\begin{quote}
Thus the largest equilateral triangle circumscribing a given triangle
has sides perpendicular to the lines joining the vertices of the given
triangle to the point such that the sum of the distances to these
vertices is a minimum.\\
One can conclude that the altitude of the largest equilateral triangle
that can be circumscribed about a given triangle is equal to the sum of
distances from the vertices of the given triangle to the point at which
the sum of distances is a minimum.
(Rochat, Vecten, Fauguier, and Pilatte in vol II (1811-12)
page 88-93)
\end{quote}


\end{slide}
\begin{slide}{}
More recent references:
\begin{description}
\item 
Duffin paper, 1956
\item 

Convex Programming:\\
Rockafellar books: (i)-Convex Analysis, 1969; (ii)-Conjugate Duality
and Optimization, 1974

\item 
Semi-infinite Programming:\\
Perfect Duality and various duality states (Ben-Israel, Charnes,
Kortanek, 1962,1977)
\item 
Monique Guignard, generalized optimality conditions for abstract
 programming, 1969
\item
BBZ optimality conditions without a CQ, 1977
\item
Borwein and W., Cone programming without CQ, 1979
\end{description}


\end{slide}
\begin{slide}{}
Standard Convex Programming Problem:
\[ \min \{ f(x) : f^k(x) \leq 0, k \in {\cal P} :=\{1,\ldots,m \} \}  \]

${\cal P}^=$ implicit equality constraints

${\cal P}^<$  complement of implicit equality constraints

$D^=_{{\cal P}^=}(x)$ cone of directions of constancy at $x$


\end{slide}
\begin{slide}{}

$f$ is {\em faithfully convex} if: $f$ is affine on a line segment only if it
is affine on the whole line containing that segment. (e.g. analytic convex, 
strictly convex), In which case

$f(x)=h(Ax+b)+a^tx+\alpha,$ $h$ strictly convex

$D^=_f$ is null space of $A$ intersect null space of $a$,
 independent of $x$


\end{slide}
\begin{slide}{}

\[K^+ = \{\phi :  \phi \cdot x \geq 0,~ \forall x \in K \}
\]

$K,L$ closed convex cones, then
\[ (K \cap L)^+ = {\rm cl} (K^+ + L^+)  \]
without closure if ${\rm int}(K) \cap L \neq \emptyset$

\end{slide}
\begin{slide}{}
tangent cone of set $M$ at point $x$ is \\
$T(M,x) = {\rm cl} ({\rm cone} (M-x))$

linearizing cone of an active set of
constraints $\Omega \subset {\cal P}$ is
$C_{\Omega}(x)$ and it equals  
$(-\mbox{cone(gradients)})^+$, $-B_{\Omega}(x)^+$ (by Farkas Lemma).

\end{slide}
\begin{slide}{}

Various ways to derive optimality conditions, e.g.

For $\min\limits_{x \in S}  f(x)$, $x\in S$ is optimal
iff
\[\partial f(x) \cap T^+(S,x) \neq \emptyset.\]

For $S$ feasible set from constraints $f_k$\\
translate the tangent cone to the linearizing cone\\
get GEOMETRIC {\em weakest constraint
qualification} 
 \[ T(S,x) = C_{active}(x)  \]

\end{slide}
\begin{slide}{}
\[ T(S,x) = cl(conv D^=_{{\cal P}^=}(x)) \cap C_{active}(x)
\]

\[ T^+(S,x) = (D^=_{{\cal P}^=}(x))^+ - B_{active}(x)
\]

missing set was added on in order to complete the optimality
conditions

\[
\nabla f(x) + \sum_k \lambda_k \nabla f_k(x) \in  K^+
\]

\end{slide}
\begin{slide}{}
Primal approach: split constraints into two parts

\[ 
\min \{f(x) : f_k(x) \leq 0, ~ k \in {\cal P}^<, x \in T \}  \]

\[ T= \{ x : f_k(x) =0, ~ k \in {\cal P}^=   \}
\]

apply generalized Slater condition with definition of
cone of directions of constancy

------------------------\\
equivalently $F(x) \preceq_{{\cal R}^f} 0$, i.e. change
nonnegative orthant to {\em minimal face} of
nonnegative orthant. AND add set constraint
\[
  x \in F^{-1}( span ~ ({\cal R}^f))
= F^{-1}(  {\cal R}^f-{\cal R}^f)
= F^{-1}(  {\cal R}^f-\Re^m_+)
\]


\end{slide}
\begin{slide}{}

Cone programming: $S$ a closed convex cone induces a
linear partial order (Borwein \& W 1980)
\[ 
\min \{f(x) : g(x) \preceq_S 0, ~  x \in \Omega \}  \]
feasible set $A$

--------------------------\\
rewrite using minimal face $g(A) \subset -S^f$
\[ 
\min \{f(x) : g(x) \preceq_{S^f} 0, ~  x \in \Omega^f\}  \]
where
$\Omega^f 
= \Omega \cap g^{-1} (S^f-S^f)  
= \Omega \cap g^{-1} (S^f-S)  $

--------------------------\\
optimality conditions for some $\Lambda \in (S^f)^+$:
\[ f(x) + \Lambda g(x) \geq \mu^*, ~\forall x \in
\Omega^f \]





\end{slide}
\begin{slide}{}
Special case of linear cone programming, $K,L$ closed
convex cones (W81):

primal:
\[  \mu^*=
\min \{cx : Ax \succeq_K 0, ~  x \succeq_L 0 \}  \]

minimal cones $K^f, L^f$

dual:
\[ \mu^*= \nu^*=
\max \{by : A^*y \preceq_{(L^f)^+} b, ~  
          y \succeq_{(K^f)^+} 0 \}  \]

\end{slide}
\begin{slide}{}

Linear Programming  ($A:\Re^m \rightarrow \Re^n$)

$\Re^n_+$ is a closed convex cone

\[ {\bf (P)}
\begin{array}{cccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & Ax \preceq b&(b-Ax \in \Re^n_+)\\
  && x \in \Re^m
    \end{array}
\]
Lagrangian (payoff function):\\ 
$L(x,U)=c^tx+\left< U,b-Ax \right>$
\[p^*=\max_x \min_{U \succeq 0} L(x,U) \]
(the constraint $U \succeq 0$ is needed to recover\\ 
the hidden constraint $Ax \preceq b$.)
\end{slide}
\begin{slide}{}
The dual is obtained from the optimal strategy of the competing player
\[p^*\leq d^*=\min_{U \succeq 0} \max_x L(x,U) =
   \left< U,b\right> +x^t(c-A^*U)
\]
The hidden constraint $c-A^*U=0$ yields the dual
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=& \inf &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq 0.
    \end{array}
\]
for the primal
\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & Ax \preceq b\\
  && x \in \Re^m
    \end{array}
\]
\end{slide}
\begin{slide}{}
If Slater's condition fails for the primal LP, 
then there are an infinite number of
different dual programs.

The implicit equality constraints are:
  \[  A_ex = b_e  \]
where $A = \left[ \begin{array}{c}   A_l \\ A_e  \end{array} \right]$

\[ {\bf (D)}
\begin{array}{ccc}
    d^*=& \inf &\tr bU \\
 &  \mbox{s.t.} & A_l^*U_l
            +A_e^*U_e = c \\
  && U\in {\cal U}\\
 &&    
           \left\{U:U \succeq 0 \right\} \subset {\cal U} \\
       &&  {\cal U} \subset \left\{U:U_l \succeq 0, U_e ~\mbox{free} \right\}.
    \end{array}
\]
for the equivalent primal program
\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & A_lx \preceq b_l\\
 &  & A_ex = b_e\\
  && x \in \Re^m
    \end{array}
\]
\end{slide}
\begin{slide}{}
\begin{center}
{\bf DUALITY THEOREM}
\end{center}
\begin{enumerate}
\item
If one of the problems is inconsistent, then the other is inconsistent
or unbounded.
\item
{\bf WEAK DUALITY}\\
Let the two problems be consistent, and let $x^0$ be a feasible solution
for P and $U^0$ be a feasible solution for D. Then
\[  c^tx^0 \leq \left< b,U^0\right>. \]
\item
{\bf STRONG DUALITY}\\
If both P and D are consistent, then they have optimal solutions and
their optimal values are equal.
\newpage
\item
{\bf COMPLEMENTARY SLACKNESS}\\
Let $x^0$ and $U^0$ be feasible solutions of P and D, respectively.
Then $x^0$ and $U^0$ are optimal if and only if
\[  \left< U^0,(b-Ax^0)\right>=0. \]
if and only if
\[   U^0 \circ (b-Ax^0)=0. \]
\item
{\bf SADDLE POINT}\\
The vectors $x^0, U^0$ are optimal solutions
of P and D, respectively, if and only if $(x^0,U^0)$ is a saddle
point of the Lagrangian $L(x,U)$ for all (x,U),
\[  L(x,U^0) \leq L(x^0,U^0) \leq  L(x^0,U)    \]
 and then
\[  L(x^0,U^0) = c^tx^0= \left<b,U^0\right>.   \]
\end{enumerate}

\end{slide}
\begin{slide}{}
Characterization of optimality for the\\
   dual pair $x,U$
 \[ 
\begin{array}{cc} 
    Ax \preceq b & \mbox{primal feasibility}\\
~\\
    A^*U = c  & \mbox{dual feasibility}\\
~\\
    U \circ (Ax -b) = 0e & \mbox{complementary slackness}
\end{array}
\]
\[
    U \circ (Ax -b) = \mu e ~~~~~ \mbox{perturbed}
\]

Forms the basis for:\\ ~~\\
primal simplex method\\
dual simplex method\\
interior point methods
\end{slide}
\begin{slide}{}
What is SEMIDEFINITE PROGRAMMING?

Why use it?

Quadratic approximations are better than linear approximations. And, we
can solve relaxations of
quadratic approximations efficiently using semidefinite
programming.
\end{slide}
\begin{slide}{}
How does SDP arise from quadratic approximations?

Let 
\[q_i(y)=\frac 12 y^tQ_iy+y^tb_i + c_i,~y\in \Re^n \]
\[ {\bf (QQP)}
\begin{array}{ccc}
    q^*=  & \min &q_0(y) \\
 &  \mbox{s.t.} & q_i(y)=0\\
     &&  i=1,\ldots m
    \end{array}
\]
Lagrangian:\\
\[ 
\begin{array}{ccc}
  L(y,x) &=& \frac 12 y^t (Q_0 -\sum_{i=1}^m x_iQ_i)y  \\
 &&   +y^t(b_0 -\sum_{i=1}^m x_ib_i)\\
   &&+ (c_0 -\sum_{i=1}^m x_ic_i)
\end{array}
\]

\[q^*=\min_y \max_x L(y,x) \geq d^* = \max_x \min_y L(y,x).
\]
homogenize
\[ y_0y^t(b_0 -\sum_{i=1}^m x_ib_i), ~~ y_0^2=1.  \]
\end{slide}
\begin{slide}{}
\[
\begin{array}{cccc}
  d^* &=& \max_x \min_y &L(y,x)\\
  &=& \max_x \min\limits_{y_0^2=1}& \frac 12 y^t (Q_0 -\sum_{i=1}^m
x_iQ_i)y
                            ~~~(+ty_0^2) \\
 &&&   +y_0y^t(b_0 -\sum_{i=1}^m x_ib_i)\\
   &&&+ (c_0 -\sum_{i=1}^m x_ic_i)
                            ~~~(-t)
\end{array}
\]

The hidden semidefinite constraint yields the semidefinite program,
i.e. we get\\
 $A: \Re^{m+1} \rightarrow {\cal S}_{n+1}$
\[
B=\left( \begin{array}{cc}
      0 & b_0^t \\ b_0 &Q_0
   \end{array}  \right),
A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
   = \left[ \begin{array}{cc}
        -t &  \sum_{i=1}^m x_ib_i^t \\
      \sum_{i=1}^m x_ib_i  & \sum_{i=1}^m x_i Q_i
        \end{array}   \right]
\]

\[
B-A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \succeq 0.
\]
\end{slide}
\begin{slide}{}
The dual program is equivalent to the SDP (with $c_0=0$)
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=  & \mbox{sup} & -\sum_{i=1}^m x_ic_i -t \\
 &  \mbox{s.t.} & A\left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \preceq B\\
  && x \in \Re^m, t \in \Re
    \end{array}
\]
As in linear programming, the dual is obtained from the optimal
strategy of the competing player:
\[ {\bf (DD)}
\begin{array}{ccc}
    d^*=& \inf &\tr BU \\
 &  \mbox{s.t.} & A^*U = \left( \begin{array}{c}
      -1 \\ -c
   \end{array}  \right) \\
  && U \succeq 0.
    \end{array}
\]
\end{slide}
\begin{slide}{}
\underline{Example}

If the primal is
\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{sup} &x_2 \\
 &  \mbox{s. t.} & 
\left[ \begin{array}{ccc}
       x_2 & 0 & 0\\
       0 & x_1 & x_2\\
       0 & x_2 & 0
       \end{array}  \right]
\preceq 
   \left[ \begin{array}{ccc}    
       1 & 0 & 0\\
       0 & 0 & 0\\
       0 & 0 & 0
       \end{array}  \right] 
    \end{array}
\]
$S^f = cone \left\{ 
   \left[ \begin{array}{ccc}
       1 & 0 & 0\\
       0 & 0 & 0\\
       0 & 0 & 0
       \end{array}  \right]
\right\}
$

Then the dual is
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=& \inf & U_{11}\\
 &  \mbox{s. t.} & U_{22}=0  \\
 &   & U_{11}+2U_{23}=1  \\
  && U \succeq 0.
    \end{array}
\]
Then $p^*=0 < d^*=1.$

--------------------------\\
But regularized dual has $ U \succeq_{(S^f)^+} 0,$ i.e. only constraint
is $U_{11} \geq 0.$ So new dual optimal value is 0. (Attained.)
\end{slide}
\begin{slide}{}
\begin{enumerate}
\item[]
What is a proper duality theory?\\
\item[]
Do duality gaps occur in practice?
\item[]
Are there an infinite number of duals if Slater's condition fails?
\end{enumerate}
\end{slide}
\begin{slide}{}
the cone $T
\subset K$ is a {\em face} of the cone $K$, denoted $T \lhd K$, if
\[ x,y \in K,~ x+y \in T \Rightarrow x,y \in T. \]
Each face, $K \lhd \p$, is
characterized by a subspace, $S \subset \Re^n.$
\[
K = \{ X \in \p : \n (X) \supset S \}.
\]
Moreover,
\[
\relint K = \{ X \in \p : \n (X) = S \}.
\]
The complementary face of $K$ is $K^c = K^{\perp} \cap \p$ 
\[
K^c = \{ X \in \p : \n (X) \supset S^{\perp} \}.
\]
Moreover,
\[
\relint K^c = \{ X \in \p : \n (X) = S^{\perp} \}.
\]
\end{slide}
\begin{slide}{}
the face $K$ (respectively, $K^c$)
is determined by the supporting hyperplane corresponding to any $X \in
\relint K^c$ (respectively, $\relint K$); 

and 
\[XY=0, \forall X \in K, Y \in K^c
\]
\end{slide}
\begin{slide}{}

An SDP:
\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{max} &c^tx \\
 &  \mbox{s.t.} & Ax  \preceq_{\p} b \\
  && x \in \Re^m.
    \end{array}
\]

Optimality conditions:
\[
c \in A^* (\p^+)  ~~({\rm closed?})
\]

dual program

\[ {\bf (D)}
\begin{array}{ccc}
    p^*=& \min &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq_{\p^+} 0.
    \end{array}
\]
Optimality conditions:
\[
b \in {\cal R}(A)+ \p^+  ~~({\rm closed?})
\]


\end{slide}
\begin{slide}{}
The {\em minimal cone} of P is defined as
\[
 \p^f = \cap \{ \mbox{faces of~} {\cal P} \mbox{~containing~} (b- A(F))
\}.
\]
Therefore, an equivalent program is
the {\em regularized P program}
\[ {\bf (RP)}
\begin{array}{ccc}
    p^*=  & \mbox{max} &c^tx \\
 &  \mbox{s.t.} & Ax  \preceq_{\p^f} b \\
  && x \in \Re^m.
    \end{array}
\]
there exists $x$ such that $b-Ax \in \relint \p^f.$
(generalized Slater's constraint qualification)\\
strong duality pair is RP and
\[ {\bf (DRP)}
\begin{array}{ccc}
    p^*=& \min &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq_{(\p^f)^+} 0.
    \end{array}
\]
\end{slide}
\begin{slide}{}
Find $\p^f$? Properties?

{\bf LEMMA 1}\\
Suppose $\p^f \lhd K \lhd \p.$ Then the system
\[
 A^*U=0, U \succeq_{K^+} 0, \tr Ub=0
\]
is consistent only if
\[
\mbox{the minimal cone}~ \p^f \subset \{U\}^{\perp} \cap K.
\]
{\bf PROOF}\\ 
Since $\tr U(Ax-b)=0$, for all $x$, we get $A(F)-b \subset
{U}^{\perp},$
i.e. $\p^f \subset \{U\}^{\perp}.$
~~\\
\hspace*{4.5in}  $\Box$
\end{slide}
\begin{slide}{}

{\bf LEMMA 2} (surprising)\\
Suppose that $0\neq K \lhd \p$ (proper face). Then
\[   \p^+ + K^{\perp}
   = cl(\p^+ + span~K^c)
 ~\mbox{is always closed}.
\]
But
 \[   \p^+ + span ~K~ \mbox{is never closed}.
\]

~~\\
\hspace*{4.5in}  $\Box$


\end{slide}
\begin{slide}{}
Define: $\p_0:=\p$ and
\[ \uu_{1} := \{ U \succeq_{(\p_0)^+} 0 :
 A^*U=0,  \tr Ub=0 \}
\]
Choose $U_1 \in \uu_{1} \cap \relint \uu_{1}^f $ (if 0 - {\bf STOP})
\[ \p_1 := \uu_{1}^c = \{ U_1 \}^{\perp} \cap \p_0 \lhd \p_0
\]
-----------------------
\[ {\bf (RP_1)}
\begin{array}{ccc}
    p^*=  & \mbox{max} &c^tx \\
 &  \mbox{s.t.} & Ax  \preceq_{\p_1} b \\
  && x \in \Re^m.
    \end{array}
\]
\begin{center}
------------------
$p^*\leq d_1^* \leq d^*$
-------------------
\end{center}
\[ {\bf (DRP_1)}
\begin{array}{ccc}
    d_1^*=& \min &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq_{(\p_1)^+} 0.
    \end{array}
\]
\begin{center}
-------
$(\p_1)^+=(\p \cap \p_1)^+ = \p + (\p_1)^{\perp}$
-------
\end{center}
\[ {\bf (ELSD_1)}
\begin{array}{ccc}
    d_1^*=& \min &\tr b(U+(W+W^t)) \\
 &  \mbox{s.t.} & A^*(U+(W+W^t)) = c \\
 &  & A^*U_1= 0, \tr U_1 b =0 \\
   &&U \succeq 0,~\left[ \begin{array}{cc}    
       I & W^t \\
       W & U_1
       \end{array}  \right] 
   \succeq 0.
    \end{array}
\]
\end{slide}
\begin{slide}{}
We used
\[
\begin{array}{cc}
\p_1^{\perp}=& \left\{ (W+W^t) : A^*U_1 = 0, \tr U_1 b = 0, \right. \\
& ~~ \left. \left[ \begin{array}{cc}  I & W^t \\
                      W & U_1  \end{array}  \right ]   \succeq 0
                             \right\}
\end{array}
\]
and
\[  \begin{array}{ccc}
U_1 \succeq WW^t  &\mbox{iff} &
  \left[ \begin{array}{cc}  I & W^t \\
                      W & U_1  \end{array}  \right ]   \succeq 0\\
& \mbox{implies}& W=U_1H, \mbox{for some matrix H}
\end{array}
\]
\end{slide}
\begin{slide}{}
\begin{eqnarray*} 
\uu_2& := &\{ U \succeq_{(\p_1)^+} 0 : A^*U=0,  \tr Ub=0 \}\\
       &= &\{ U + Z:  A^*(U+Z)=0,  \tr Ub=0, \\
        &&  ~~~U \succeq_{(\p_0)^+}, Z \in (\p_1)^{\perp}\}
\end{eqnarray*}
Choose $U_2 \in \uu_2 \cap \relint \uu_2^f $ (if 0 - {\bf STOP})
\[ \p_2 := \uu_2^c = \{ U_2 \}^{\perp} \cap \p_1 \lhd \p_1
\]
\end{slide}
\begin{slide}{}
\[ {\bf (RP_2)}
\begin{array}{ccc}
    p^*=  & \mbox{max} &c^tx \\
 &  \mbox{s.t.} & Ax  \preceq_{\p_2} b \\
  && x \in \Re^m.
    \end{array}
\]
\begin{center}
--------------$p^*\leq d_2^*\leq d_1^* \leq d^*$-------------
\end{center}
\[ {\bf (DRP_2)}
\begin{array}{ccc}
    d_2^*=& \min &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq_{(\p_2)^+} 0.
    \end{array}
\]
\begin{center}
--------$(\p_2)^+=(\p  \cap \p_2)^+ = \p + (\p_2)^{\perp}$-------
\end{center}
\[ {\bf (ELSD_2)}
\begin{array}{ccc}
    d_1^*=& \min &\tr b(U+(W+W^t)) \\
 &  \mbox{s.t.} & A^*(U+(W+W^t)) = c \\
 &  & A^*U_1= 0, \tr U_1 b =0 \\
 &  & A^*(U_2+(W_1+W_1^t))= 0, \\
    &&\tr (U_2+(W_1+W_1^t)) b =0 \\
   &&U \succeq 0,~\left[ \begin{array}{cc}    
       I & W_1^t \\
       W_1 & U_1
       \end{array}  \right] 
   \succeq 0\\
   &&\left[ \begin{array}{cc}    
       I & W^t \\
       W & U_2
       \end{array}  \right] 
   \succeq 0.
    \end{array}
\]
\end{slide}
\begin{slide}{}
HOMOGENIZATION\\
Alternate view of optimality conditions  
 \[ {\bf (HP)}
\begin{array}{cccc}
    0=& \max &c^tx+t(-p^*)\\
 &  \mbox{~subject to~} & Ax + t(-b) +Z = 0 \\
  && w \in K=\Re^m  \otimes \Re_+ \otimes \p\\
    \end{array}
\]
This defines the objective, constraints, and variables:
 \[
\begin{array}{cccc}
 (=\left< a,w \right> )\\
(Bw =0)\\
           \left(w= \left( \begin{array}{c}  x\\t\\Z
    \end{array} \right)\right)
    \end{array}
\]
the feasible set is
\[  F_H = \n (B) \cap K,  \]
\[
Bw=0, w \in K ~\mbox{implies~} \left< a,w \right> \leq 0.
\]
\end{slide}
\begin{slide}{}
Optimality conditions:
\[
a =  \left( \begin{array}{c} c\\-p\\0 \end{array} \right) \in
    -( \n (B) \cap K)^+.
\]
\[
 \left( \begin{array}{c} -c\\p\\0 \end{array} \right) \in
    \overline{\ra (B^*) +  K^+},
\]
WCQ - Weakest Constraint Qualification:
\begin{center}
CLOSURE HOLDS
\end{center}
\end{slide}
\begin{slide}{}
Conditions for closure:
\begin{enumerate}
\item[]
If $C,D$ are closed convex sets and the intersection of their recession cones
is empty, then $D-C$ is closed.
\item[]
$cone (F_H-K)$ is the whole space
\item[]
(Slater's) \[ \exists \hat{x} \in F ~\mbox{such that}~ A \hat{x} \prec
b.
\]
\end{enumerate}
FIX: Find sets, $T$,
to add to attain the closure. Equivalently, find sets, $C,~C^+=T$,
to intersect with $K$ to attain the closure since
\[
    (\n (A) \cap  (K \cap C))^+ =
    \overline{\ra (A^*) +  K^+ + C^+}.
\]
\end{slide}
\begin{slide}{}
\end{slide}
%\bibliography{.psd,.master,.publs}
\end{document}

