%======================= main.tex ===========================================
\documentstyle{slides}
\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}
\blackandwhite{example}
%======================= example.tex
%  the file example.tex must exist - it is empty though
%======================= 
%======================= 
\begin{slide}{}
\begin{center}
{\bf STRONG DUALITY FOR SEMIDEFINITE PROGRAMMING}
\end{center}
 
(Linear Programming for the 90's and 00's)

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

(work with Levent Tuncel and Motakuri Ramana)
\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}
\]
then the dual is
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=& \inf &\tr U_{11}\\
 &  \mbox{s. t.} & U_{22}=0  \\
 &   & U_{11}+2U_{23}=1  \\
  && U \succeq 0.
    \end{array}
\]
Then $p^*=0 < d^*=1.$
\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}{}
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$
~~\\
~~\\
{\bf LEMMA 2} (surprising)\\
Suppose that $K \lhd \p.$ Then
\[   \p^+ + K^{\perp} ~\mbox{is 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}
\end{document}

