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