%\documentclass{slides} \documentclass[landscape]{seminar} %\documentclass[portrait]{seminar} \usepackage{amssymb} \usepackage{psfig} %\pagestyle{empty} \pagestyle{plain} \newcommand{\F}{{\cal F}} \newcommand{\A}{{\cal A}} \newcommand{\p}{{\cal P}} \newcommand{\Ocal}{{\mathcal O}} \newcommand{\Kprod}{\otimes} \newcommand{\Diag}{\rm Diag\,} \newcommand{\tran}{^T} \newcommand{\diag}{\rm diag\,} \newcommand{\tr}{\rm trace\,} \newcommand{\trace}{\rm trace\,} \newcommand{\beq}{\begin{equation}} \newcommand{\Sn}{{\cal S}^n} \newcommand{\svec}{{\rm svec\,}} \newcommand{\sMat}{{\rm sMat\,}} \newcommand{\hMat}{{\rm hMat\,}} \newcommand{\dsvec}{{\rm dsvec\,}} \newcommand{\sdiag}{{\rm sdiag\,}} \newcommand{\vsMat}{{\rm vsMat\,}} \newcommand{\kvec}{{\rm vec\,}} \newcommand{\kmat}{{\rm Mat\,}} \newcommand{\eeq}{\end{equation}} \newcommand{\nc}{\newcommand} \nc{\Hcal}{{\cal H}} \newcommand{\rank}{{\rm rank\,}} \newcommand{\trian}{{\rm trian\,}} \newcommand{\Trian}{{\rm Trian\,}} \newcommand{\BoDiag}{{\rm B^0Diag\,}} \newcommand{\OoDiag}{{\rm O^0Diag\,}} \newcommand{\arrow}{{\rm arrow\,}} \newcommand{\Arrow}{{\rm Arrow\,}} \newcommand{\bodiag}{{\rm b^0diag\,}} \newcommand{\oodiag}{{\rm o^0diag\,}} \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\,}} %\def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~} \newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~} \begin{document} %======================= %======================= \begin{slide}{} \begin{center} {\bf Semidefinite Relaxations for Hard Combinatorial Problems } \end{center} \vspace{5mm} Henry Wolkowicz \\ \vspace{5mm} Department of Combinatorics \& Optimization \\ University of Waterloo \vspace{10mm} \mbox{ \begin{figure} \psfig{file=UWlogori.ps,height=20mm} \end{figure} } \end{slide} \begin{slide}{} {\bf \begin{center} OUTLINE \end{center} } $\bullet$ Introduction (short) to SDP \\ (geometry, duality, algorithms) $\bullet$ Max-Cut Problem instance\\ (quadratic boolean programming)\\ tractable relaxations versus Lagrangian duality \\ equivalence of various bounds $\bullet$ Other instances, e.g. QAP, GP, ...\\ SDPs equivalent to min-max eigenvalue problems $\bullet$ \underline{Theme:} - Tractable relaxation implies Lagrangian relaxation which can be solved efficiently using SDP. \\ - Advantages of Lagrangian approach (recipe for SDP relaxation). \end{slide} \begin{slide}{} \begin{center} INTRODUCTION \end{center} Semidefinite programming -- SDP\\ extension of linear programming -- LP \[ (P)\quad \begin{array}{rc} \mu^*:= \min & C \bullet X \\ \mbox{s.t.} & \A X = b \\ & X \succeq 0, \end{array} \] $C,X \in \Sn$, space of symmetric $n \times n$ matrices\\ inner product $C \bullet X = \tr CX$\\ $A\succeq B$ if $A-B \succeq 0$ positive semidefinite\\ $ \A :\Sn \rightarrow \Re^m $, linear operator: $(\A X)_i =\tr (A_iX)$ $A_i \in \Sn,~i=1, \ldots m.$ \end{slide} \begin{slide}{} Why use SDP? Many applications: engineering, combinatorial optimization, statistics, matrix completions, approximation theory, nonlinear programming, ... \underline{\hspace{90mm}}\\ Many computationally hard problems can be modelled as quadratic programs. These quadratic programs are themselves hard to solve numerically. But, the Lagrangian relaxation can be solved {\em efficiently using SDP}. \end{slide} \begin{slide}{} \begin{center} {\bf Properties of SDP} \end{center} SDP is a special case of the cone programming problem \[ \begin{array}{cc} \min & f(x) \\ \mbox{s.t.} & g(x) \succeq_K 0, \end{array} \] $K$ is a convex cone \\ $g(x) \succeq_K 0$ is cone partial order, $g(x) \in K.$ very general mathematical program e.g. standard equality and inequality constraints when $K= \Re^n_+ \otimes \Sn_+ \otimes \{0\}.$ \end{slide} \begin{slide}{} \begin{center} {\bf GEOMETRY} \end{center} Much of the elegant geometry of polyhedral sets developed for LP can be extended to SDP. (e.g. Bohnenblust 1948, Barker-Carlson 1975 and more recently Lewis/98 and Pataki/98) similarities to LP:\\ {\em self-polar} \[ \p = \p^+:= \left\{Y: X \bullet Y \geq 0, \forall X \in \p \right\}; \] {\em homogeneous}\\ for any $X,Y \in \mbox{int}(\p)$, there exists an invertible linear operator $\cal A$ that leaves $\p$ invariant and $\A (X)=Y.$ \end{slide} \begin{slide}{} {\em faces} \[ {\cal F} = \left\{Y: {\cal N}(Y) \supset {\cal N}(X) \right\}, \quad X \in \mbox{ relint } {\cal F} \] faces are {\em exposed}\\ ${\cal F} = \p \cap \phi^{\perp}$, where $\phi \in \p \cap {\cal F}^{\perp}$ {\em conjugate face}, (Here $\cdot^{\perp}$ denote orthogonal complement.) But difficulties in duality theory can arise due to: $\p + {\cal F}^{\perp}$ is always closed $\p + \mbox{span}({\cal F})$ is never closed. \end{slide} \begin{slide}{} \begin{center} {\bf Duality Theory, Optimality Conditions} \end{center} Extensions from LP to SDP, e.g. Bellman and Fan 1963, but strong duality theorems require a Slater-type constraint qualification (strict feasibility). (Modified optimality conditions without CQ exit Borwein-Wolkowicz/81 and Ramana/98.) \end{slide} \begin{slide}{} primal program \[ (P)\quad \begin{array}{rc} \mu^*:= \min & C \bullet X \\ \mbox{s.t.} & \A X = b \\ & X \succeq 0, \end{array} \] dual program \[ (D)\qquad \begin{array}{rc} \nu^*:= \max & b^T y \\ \mbox{s.t.} & \A^*y \preceq C \end{array} \] \end{slide} \begin{slide}{} weak duality (using hidden constraints) \begin{eqnarray*} \mu^* &=& \min\limits_{X\succeq 0} \max_y C \bullet X + y^T(b-\A X)\\ &\geq& \max_y \min\limits_{X\succeq 0} y^Tb +\left(C - \A^*y\right) \bullet X\\ &=& \nu^*, \end{eqnarray*} $\A^*$ adjoint operator of $\A$ \[ \A (X) \bullet y = X\bullet \A^* (y), \quad \forall X, \forall y \] \end{slide} \begin{slide}{} The duality theory gives rise to the characterization of optimality \begin{equation} \label{eq:optcond} \begin{array}{cccc} \A^{*}y +Z - C &=& 0 & \mbox{dual feasibility} \\ b - \A(X) &=& 0 & \mbox{primal feasibility} \\ ZX &=& 0 & \mbox{complementary slackness} \\ Z,X \succeq 0. \end{array} \end{equation} $X,(y,Z)$ a primal-dual optimal pair. $Z$ is the (dual) slack variable. \underline{\hspace{90mm}}\\ \[ ZX = \mu I, \quad \mu >0 \] perturbed compl. slack. used for interior-point methods \end{slide} \begin{slide}{} First and second order optimality conditions e.g. Shapiro/94,99 Nondegeneracy and strict complementarity (Theorem of Goldman and Tucker) do not directly follow through from LP to SDP though generic, e.g. Shapiro/99, Pataki-Tuncel/98, Alizadeh-Haeberly-Overton/98. (strict complementarity for SDP translates to $Z+X \succ 0$) Complexity/algorithms: SDP are convex programs and fall into the class of problems that can be approximately solved in polynomial time by int-pt algorithms, Nesterov-Nemirovski/93. \end{slide} \begin{slide}{} \begin{center} {\bf Tractable Relaxations of Max-Cut}\\ (quadratic boolean programming) \end{center} \[ (MCQ)~~~ \begin{array}{c} \mu^*:= \max\limits_{x \in \F} q_0(x) \quad ( : = x^TQx -2 c^Tx). \end{array} \] where $\F=\left\{\pm 1\right\}^n$\\ \underline{\hspace{90mm}}\\ perturbing diagonal of $Q$ on $\F:$ \[ \begin{array}{rcl} q_u(x)& : = &x^T(Q+\Diag(u))x -2 c^Tx - u^Te\\ &~=&q_0(x),~~\forall x \in \F, \end{array} \] where $e$ vector of ones. \end{slide} \begin{slide}{} {\bf Bound 0:} trivial bound from diagonal perturbations: \[ \mu^* \leq f_0 (u) := \max_x q_u(x). \] The function $f_0$ can take on the value $+\infty.$ Let \[S:=\left\{u:u^Te=0, Q+\Diag(u)\preceq 0\right\}. \] Then: \[ \begin{array}{|c|} \hline\\ \mu^* \leq B_0 := \min\limits_u f_0(u) \\ \left(= \min\limits_{u^Te=0} f_0(u), \mbox{ if } S \neq \emptyset \right). \\ ~\\ \hline \end{array} \] Using the hidden semidefinite constraint: \[ \mu^* \leq B_0 = \min\limits_{Q+\Diag(u) \preceq 0} f_0(u). \] \end{slide} \begin{slide}{} {\bf Bound 1:} relax the feasible set to the sphere of radius $\sqrt{n}$ (tractable trust region subproblem, TRS): \[ \mu^* \leq f_1(u):= \max_{|| x ||^2 =n} ~ q_u(x) \] and \[ \begin{array}{|c|} \hline\\ \mu^* \leq B_1 :=\min\limits_u f_1(u).\\ ~~\\ \hline \end{array} \] The inner maximization problem is called a trust region subproblem and is tractable. This bound provides the central tool in the proofs of equivalence. \end{slide} \begin{slide}{} {\bf Bound 2:} box constraint: \[ \mu^* \leq f_2(u):= \max_{| x_i | \leq 1} ~ q_u(x). \] add the semidefinite constraint to make bound tractable. \[ \mu^* \leq \min\limits_{u} f_2(u) \] and \[ \begin{array}{|c|} \hline\\ \mu^* \leq B_2 :=\min\limits_{Q+\Diag(u) \preceq 0} f_2(u).\\ ~~\\ \hline \end{array} \] (adding tractable constraint -- equivalence to other bounds) \end{slide} \begin{slide}{} {\bf Bound $B_1^c$:} lift to eigenvalue bound: \[ Q^c := \left[ \begin{array}{cc} 0 & - c^T \\ - c &Q \end{array} \right] \] \[ q^c_u(y) := y^T( Q^c+\Diag(u))y-u^Te \] \[ \mu^* \leq f_1^c(u) := \max_{||y||^2=n+1} q^c_u(y) \] \[ \max_{||y||^2=n+1} q^c_u(y) = (n+1) \lambda_{\max} (Q^c + \Diag (u) ) - u^Te \] \[ \begin{array}{|c|} \hline\\ \mu^* \leq B_1^c := \min\limits_{u} f_1^c(u).\\ ~~\\ \hline \end{array} \] Similarly, equivalence to bounds $B_0^c$ and other homogenized bounds. \end{slide} \begin{slide}{} {\bf Bound $B_3$:} SDP bound: After homogenization ( $c=0$), use \[ x^TQx = \tr x^TQx = \tr Qxx^T\] and, for $x \in \F,$ $y_{ij} = x_ix_j$ defines a symmetric, rank one, positive semidefinite matrix $Y$ with diagonal elements 1. Relax the rank one condition. \[ \begin{array}{|ccc|} \hline &&\\ B_3 :=&\max &\tr QY \\ & \mbox{~subject to~} &\diag(Y) = e \\ && Y \succeq 0.\\ &&~\\ \hline \end{array} \] \end{slide} \begin{slide}{} Summary: ref. Polyak-Rendl-Wolkowicz (PRW) 1995\\ (without restriction $u^Te=0$) \[ \begin{array}{|rcl|} \hline &&~\\ B_0 &=&\min\limits_u \max\limits_x q_u(x)\\ B_1 &=&\min\limits_u \max\limits_{x^Tx=n} q_u(x)\\ B_2 &=&\min\limits_u \max\limits_{-1 \leq x_i \leq 1} q_u(x)\\ B_3 &=&\max \{\tr Q^cY : \diag(Y) = e,~ Y \succeq 0. \}\\ B_1^c &=&\min\limits_u %\max\limits_{y^Ty=n+1} q^c_u(y)\\ % \max_{||y||^2=n+1} q^c_u(y) = (n+1) \lambda_{\max} (Q^c + \Diag (u) ) - u^Te\\ &&~\\ \hline \end{array} \] \end{slide} \begin{slide}{} Now replace $\pm 1$ constraints with $x_i^2=1, \forall i.$ \[ \begin{array}{ccc} (P_E)&\max & q_0(x)=x^TQx-2c^Tx \\ & \mbox{~subject to~} & x_i^2 = 1,~~i=1, \cdots, n. \\ \end{array} \] $B_L$ denotes Lagrangian relaxation bound. Following theme: \begin{center} \fbox{ {\bf Theorem }(PRW) $B_L$ equals all above bounds. } \end{center} (proofs from -- strong Lagrangian duality of TRS.)\\ (question: which relaxation is best numerically, e.g. SDP in dense case, eigenvalue in large sparse case) \end{slide} \begin{slide}{} \begin{center} {\bf Strengthened SDP Bounds for MC}\\ \end{center} (Anjos-Wolkowicz/99)\\ Illustration of recipe for SDP relaxation.\\ (some parts similar to S-procedure Yakubovich/71, Shor relaxation/87)\\ $\bullet$ replace $Ax=b$ by $||Ax-b||^2=0$ and homogenize\\ $\bullet$ add redundant quadratic constraints\\ $\bullet$ take Lagrangian dual\\ $\bullet$ take dual of Lagrangian dual (use hidden SDP constraint)\\ $\bullet$ eliminate redundant constraints\\ \end{slide} \begin{slide}{} motivation for $||Ax-b||^2=0$:\\ $0=\max \{ x^2 : x=0\}$ primal optimal value \\ $0<\infty= \inf\limits_{\lambda} \max\limits_x x^2 + \lambda x$ Lagrangian dual optimal value BUT:\\ replace linear constraint by $x^2 = 0$\\ Then: Lagrangian dual is \[ 0= \inf_\lambda \max_x x^2 + \lambda x^2 \] \end{slide} \begin{slide}{} the trick \[ \mbox{replace } Ax=b \mbox{ by } ||Ax-b||^2 = 0 \] works in general for most applications\\ {\bf Theorem} (PRW) Let $K \subset \Re^n$ be a {\bf finite set}. Let $q(x) = x^TQx -2 c^Tx$, $A \in \Re^{m \times n}$ and $b \in \Re^n$. Then there exists $\bar{\lambda} \in \Re$ such that $\forall\ \lambda \geq \bar{\lambda}$ \[ \max_{x \in K} \{ q(x) : ||Ax-b||^2 = 0 \} = \max_{x \in K} \{q(x) - \lambda ||Ax-b||^2\}. \] \QED i.e. quadratic penalty function is exact in the case that $K$ is a finite set (no need for e.g. augmented Lagrangian) \end{slide} \begin{slide}{} first lifting procedure \[ X=xx^T, \quad \Diag X = e \] implies second lifting procedure \[X^2=xx^Txx^T=nX.\] and provides an equivalent quadratic matrix model for MC \end{slide} \begin{slide}{} MCQ is equivalent to: \begin{eqnarray*} \mu^*:=&\max& \tr QX\\ &\mbox{s.t.}&\diag(X)=e\\ &&X \succeq 0\\ && X \mbox{ is rank 1}. \end{eqnarray*} which is equivalent to \begin{eqnarray*} \mu^*:=&\max& \tr QX\\ &\mbox{s.t.}&\diag(X)=e\\ &&X^2-nX=0 \end{eqnarray*} Since $X$ and $X^2$ can be mutually diagonalized.\\ \end{slide} \begin{slide}{} Now add redundant constraints;\\ and replace $\diag(X)=e$ with $||\diag(X)-e||^2_F=0$ \begin{eqnarray*} \mu^*:=&\max& \tr QX\\ &\mbox{s.t.}&||\diag(X)-e||^2_F=0\\ &&X^2-nX=0\\ &&X \circ X=E \end{eqnarray*} where $E$ is the matrix of ones. \end{slide} \begin{slide}{} Notation:\\ (Interesting operators and adjoints)\\ $\bullet$ $S \in \Sn, \quad t(n)= \frac {n(n+1)}2$\\ $\bullet$ $s=\svec(S) \in \Re^{t(n)} \quad$ vector formed (columnwise) from $S$\\ \hspace{20mm}(ignoring strictly lower triang.)\\ $\bullet$ $S=\sMat(s) \quad$ inverse of $\svec$\\ $\bullet$ $\hMat (v) \quad$ adjoint of $\svec$, off-diagonal terms {\em divided} by 2\\ $\bullet$ $\dsvec (S) \quad$ adjoint of $\sMat$, off diagonal elements {\em multiplied} by 2\\ $\bullet$ $\sdiag(s):= \diag( \sMat(s))$\\ $\bullet$ $\vsMat(s):=\kvec(\sMat(s))$ \[ \bullet \quad \vsMat^*(s)=\dsvec \left( \left(\kmat(v)+\kmat(v)^T\right)/2 \right). \] \end{slide} \begin{slide}{} Summary: \[ \begin{array}{rcl} \diag^* &=& \Diag \\ \svec^* &=& \hMat \\ \svec^{-1} &=& \sMat \\ \dsvec^* &=& \sMat \\ \vsMat^* &=& \dsvec \left[ \frac 12 \left(\kmat(\cdot)+ \kmat(\cdot)^T\right) \right]. \end{array} \] \end{slide} \begin{slide}{} homogenize $1-y_0^2=0.$\\ use: $X=\sMat(x)$ is a symmetric matrix. \[ \begin{array}{ccc} &\max & \tr \left(Q\, \sMat(x)\right)y_0 \\ &\mbox{s.t.}& \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 + n=0\\ &&\sMat(x) \circ \sMat(x)=E\\ &&\sMat(x)^2-n\, \sMat(x)y_0=0\\ &&1-y_0^2=0. \end{array} \] \end{slide} \begin{slide}{} take the Lagrangian dual; Lagrange multipliers $t,w,T,S$ \[ \begin{array}{rl} \mu^*\leq & \\ \nu_2^*= & \min\limits_{t,w,T,S} \max\limits_{x,y_0} \tr \left(Q\sMat(x)\right)y_0 \\ &~+w( \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 + n)\\ &~~+\tr T(\sMat(x) \circ \sMat(x)-E)\\ &~~+\tr S((\sMat(x))^2-n\, \sMat(x)y_0)\\ &~~~+ t(1-y_0^2). \end{array} \] \end{slide} \begin{slide}{} constant part (no Lagrange multipliers) of Lagrangian Hessian: \[ 2H_c:=2\pmatrix{ 0 & \frac 12 \dsvec(Q)^T\cr \frac 12 \dsvec(Q) & 0\cr }. \] ~~\\ {\em negative} nonconstant part of Lagrangian Hessian \[ \begin{array}{lll} 2\Hcal:= 2\Hcal_1(w) + 2\Hcal_2(T)+ 2\Hcal_3(S) + 2\Hcal_4(t) \\ ~~:=2w\pmatrix{ 0 & (\dsvec \Diag e )^T\cr (\dsvec \Diag e ) & -\sdiag^* \sdiag }\\ ~~~~~+2\pmatrix{ 0 & 0 \cr 0 & \dsvec \left( T \circ \sMat\right) }\\ ~~~~~~~~+2\pmatrix{ 0 & \frac 1n\dsvec(S)^T\cr \frac 1n\dsvec(S) & -\dsvec S \sMat }\\ ~~~~~~~~~~~+2t\pmatrix{ 1 & 0\cr 0 & 0 }.\\ \end{array} \] \end{slide} \begin{slide}{} Use {\bf hidden SDP constraint}\\ Lagrangian dual: \[ {\rm MCDSDP2} \quad \begin{array}{ccc} \nu^*_2 = &\min & nw +\tr ET+\tr 0S +t\\ &\mbox{s.t.}& \Hcal(w,T,S,t) \succeq H_c\\ \end{array} \] Take $T$ sufficiently positive definite and $t$ sufficiently large, then we can guarantee Slater's constraint qualification. \end{slide} \begin{slide}{} take dual of this SDP -- strengthened SDP relaxation of MC: \[ {\rm MCPSDP2} \begin{array}{ccc} \nu_2^* = &\max & \trace H_cY\\ &\mbox{s.t.}& \Hcal_1^*(Y) = n\\ & & \Hcal_2^*(Y) = E\\ & & \Hcal_3^*(Y) = 0\\ & & \Hcal_4^*(Y) = 1\\ && Y \succeq 0. \end{array} \] \end{slide} \begin{slide}{} we need to calculate the adjoint operators and remove redundant constraints in MCPSDP2. we use \[ Y \cong \left( \begin{array}{c}y_0 \\ x \end{array}\right) \left( y_0 ~x^T\right), \quad X = \sMat(x) \] \end{slide} \begin{slide}{} simplified SDP relaxation MCPSDP2 \[ \begin{array}{clc} \nu_2^* =\\ \max & \trace H_c Y\\ \mbox{s.t.}& \diag(Y) = e\\ & Y_{0,t(i)}=1, i=1, \ldots , n\\ & Y_{0,T(i,j)} = \frac{1}{n} \sum\limits_{k=1}^n Y_{T(i,k),T(k,j)}, \,\,\,\forall\, i,j \:{\rm s.t.}\: 1\leq i = 2 \trace AXB h^T + SXIh^T \quad \forall h. \] Therefore $AXBX^T = -S=-S^T$, i.e. $A$ and $XBX^T$ are mutually diagonalizable. The optimal value is then \[ \mu^* = \sum_i \lambda_i(A) \lambda_{n-i+1}(B) \] \end{slide} \begin{slide}{} But, Lagrangian dual can have a duality gap, ref Zhao,Karisch,Rendl,Wolkowicz Lagrangian of $(P)$ $$ L(X,S) = \tr AXBX^T + \tr SXX^T - \tr S. $$ Lagrangian dual is \[ \nu^* = \max_S \min\limits_X L(X,S). \] The hidden constraint (Hessian is psd) yields the dual \[ (D) \begin{array}{ccc} \mu^D = &\max\limits_{\hat{S}=\hat{S}^T} & -\tr \hat{S} \\ & \mbox{~subject to~} & (B \otimes A + I \otimes \hat{S}) \succeq 0. \end{array} \] \end{slide} \begin{slide}{} {\bf A simple $2\times 2$ Example} $\mu^* = 10$ \[ A:= \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right) \quad B:= \left( \begin{array}{cc} 3 & 0 \\ 0 & 4 \end{array} \right) \quad B \otimes A = \left( \begin{array}{cccc} 3 & 0 & 0 & 0 \\ 0 & 6 & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 8 \\ \end{array} \right). \] But $s_{11}\geq -3$ and $s_{22}\geq -6$; to maximize $(D)$, equality must hold, and therefore $-\tr \hat{S} = 9$ in the optimum. However, add redundant constraint $X^TX=I$. Get $T \otimes I$ in Hessian and $-\trace T$ in objective function. $s_{11}\geq -3-t_{11}$ $s_{11}\geq -4-t_{22}$ $s_{22}\geq -6-t_{11}$ $s_{22}\geq -8-t_{22}$. So $t_{22}=-1.$ Duality gap is closed. \end{slide} \begin{slide}{} Add redundant constraints $X^TX=I$. \begin{eqnarray*} {\rm QQP_{OO}}\qquad \mu^O:=&\min& \tr AXBX\tran\\ &{\rm s.t.}& XX\tran=I,\ X\tran X=I. \end{eqnarray*} \begin{eqnarray*} {\rm DQQP_{OO}} \qquad \mu^D:=&\max& \tr S+\tr T\\ &\mbox{s.t.}& (I\Kprod S)+(T\Kprod I)\preceq (B\Kprod A)\\ && S=S\tran,\ T=T\tran. \end{eqnarray*} {\bf Theorem (Anstreicher-Wolkowicz/98)} Strong duality holds for $\rm QQP_{OO}$ and $\rm DQQP_{OO},$ i.e. $\mu^D=\mu^O$ and both primal and dual are attained. \QED Theme again holds. \end{slide} \begin{slide}{} Other applications: Weighted Sums of Eigenvalues; Graph Partitioning Problem; TRS like constraints $\{X: XX\tran \preceq I\}$ (ref Anstreicher-Wolkowicz-Xin-Yuan/99) (extension of Hoffman-Wielandt inequality) \end{slide} \begin{slide}{} add linear constraint to QAP ???? Use equivalence to min-max eig problem after homogenization to get zero duality gap? \end{slide} \begin{slide}{} {\bf Linear Case} $A=B=0.$ \begin{equation} \begin{array}{rcl} {\rm QQPL_{\Ocal}}\qquad \mu_L^\Ocal:=&\min& \tr -2CX^T\\ &{\rm s.t.}& XX^T=I. \end{array} \label{QAPL} \end{equation} Characterize the optimal solution using singular values:\\ {\bf Proposition} Suppose we have the singular value decomposition $C=U\Sigma V^T,$ where the singular values, $\sigma_i,$ are in the diagonal matrix $\Sigma,$ and $U,V$ are orthogonal matrices. Then the optimal value of ${\rm QQPL_{\Ocal}}$ is $\mu_L^\Ocal=-2\tr \Sigma =-2\sum\limits_{i=1}^n \sigma_i.$ The optimal solution is obtained using the orthogonal matrices that yield the decomposition, i.e. $X^*=UV^T.$ \QED \end{slide} \begin{slide}{} dual of pure linear case: (can assume $S,T$ are diagonal) \begin{eqnarray*} {\rm LD}\qquad&\max& e^Ts+e^Tt+w\\ &\mbox{s.t.}&s_j+t_i\leq - \frac 1{|w|} |c_{(j-1)n+i}|^2, \quad i,j=1,\ldots, n. \end{eqnarray*} notice independence of the sign of the individual elements of $C.$ \end{slide} \begin{slide}{} But:\\ {\bf Example} \beq \label{eq:exampC} \begin{array}{ccc} \mu^*:= &\min & \tr -2CX^T\\ & \mbox{~s.t.~} &XX^T = I,~X^TX = I, \end{array} \end{equation} with $2\times 2$ matrix $$ C= \left( \begin{array}{rr} 1 & -1 \\ 1 & 1 \end{array} \right). $$ We then solve this example with the sign changed on -1, i.e. $$ C= \left( \begin{array}{rr} 1 & 1 \\ 1 & 1 \end{array} \right). $$ \end{slide} \begin{slide}{} The dual problem in the second case is \[ (D_{\mathcal O})~~ \begin{array}{cl} \max & \tr S + \tr T +w\\ \mbox{s.t.}& \BoDiag(S) + \OoDiag(T) + wE_{00} \preceq L_Q, \end{array} \] where \beq \label{eq:lq0} L_Q := \left[ \begin{array}{cc} 0 & \begin{array}{rrrr} -1&-1&-1&-1 \end{array} \\ \begin{array}{r} -1\\-1\\-1\\-1 \end{array} & \mbox{\huge{0}} \end{array} \right]. \end{equation} Dual optimal value does not change. But primal does, since the sum of the singular values of the two matrices are: $2\sqrt 2$ in the first instance and just $2$ for the symmetric $C,$ i.e. the optimal values are $-4(\sqrt 2)$ and $-4,$ respectively. (Implies duality gap in second case.) \end{slide} \begin{slide}{} Add redundant variables:\\ {\bf Theorem} Strong duality holds between the pure linear case and its Lagrangian dual if the following equivalent problem for the sum of the singular values is used. \[ {\rm SVD}\qquad \begin{array}{rcl} \sum_i \sigma_i (C) =\max& 2\tr YCX^T \\ {\rm s.t.}& XX^T+YY^T=I. \end{array} \] \end{slide} \end{document}