%======================= 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. \] \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}