\documentclass{slides} \pagestyle{plain} \newcommand{\F}{\cal F} \newcommand{\Kprod}{\otimes} \newcommand{\Diag}{\rm Diag\,} \newcommand{\Sn}{{\cal S}_n} \newcommand{\tran}{^T} \newcommand{\diag}{\rm diag\,} \newcommand{\tr}{\rm trace\,} \newcommand{\trace}{\rm trace\,} \def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~} \begin{document} %======================= %======================= \begin{slide}{} \begin{center} {\bf Is Lagrangian (SDP) Relaxation Best for Quadratic Optimization? } \end{center} ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ Henry Wolkowicz \\ University of Waterloo\\ ~\\ ~\\ in collaboration with:\\ Kurt Anstreicher, Chen Xin, Ya-xiang Yuan\\ (Yuri Nesterov, Yinyu Ye) \end{slide} \begin{slide}{} Quadratically constrained quadratic programs, QQP. Semidefinite Programming, SDP, yields bounds. SDP bound is equivalent to the Lagrangian relaxation. Theme (or conjecture):\\ {\em Lagrangian duality is best}\\ i.e. tractable bounds are equivalent to Lagrangian relaxation bound of an appropriate problem. In some surprising (nonconvex cases) the Lagrangian Relaxation is exact (zero duality gap). \end{slide} \begin{slide}{} \begin{center} {\bf QQP} \end{center} \[ q_i(x) : = x^TQ_ix+2g_i^Tx +\alpha_i~~Q_i=Q_i^T \] \[ (\mbox{QQP}_x) \begin{array}{rcl} q^*:= & \min & q_0(x)\\ &{\rm subject~to} & q_k(x) \leq 0\\ && k \in {\cal I} :=\{1, \ldots , m\}\\ && x \in \Re^n \end{array} \] Lagrangian of QQP$_x$ \[ L(x,\lambda):= q_0(x) + \sum_{k \in {\cal I} } \lambda_k q_k(x), \] $\lambda=(\lambda_k) \geq 0$ are nonnegative Lagrange multipliers. \end{slide} \begin{slide}{} {\bf Lagrange multipliers can be used in two ways.} 1. Classical: if a CQ holds at optimum $\bar{x}$, then the KKT necessary conditions for optimality hold \begin{eqnarray*} \bar{\lambda} \geq 0, \nabla L(\bar{x},\bar{\lambda})=0\\ \bar{x} \mbox{ feasible }\\ \bar{\lambda}_k q_k(\bar{x})=0, \forall k \in {\cal I} \end{eqnarray*} If the Lagrangian at $\bar{\lambda}$ is also convex in $x$, then KKT is sufficient. 2. Lagrangian Relaxation (duality): \[ q^* \geq d^*:= \max\limits_{\lambda \geq 0} \min_x q_0(x) + \sum_{k \in {\cal I} } \lambda_k q_k(x). \] \end{slide} \begin{slide}{} Zero duality gap holds if $q^*=d^*.$ Strong duality holds if $q^*=d^*$ and also $d^*$ is attained. Moreover, $d^*$ can be efficiently evaluated using SDP. Questions:\\ $\bullet$Can one do better than the Lagrangian relaxation?\\ $\bullet$When does a zero duality gap hold?\\ $\bullet$What redundant constraints can be added to close the duality gap? \end{slide} \begin{slide}{} \begin{center} {\bf Several Different Relaxations of Max-Cut} \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=\{\pm 1\}^n$\\ -------------------------------- 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} \] \end{slide} \begin{slide}{} {\bf Bound 0:} the trivial bound from allowing the 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_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_{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_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_{u} f_2(u) \] and \[ \begin{array}{|c|} \hline\\ \mu^* \leq B_2 :=\min_{Q+\Diag(u) \preceq 0} f_2(u).\\ \hline \end{array} \] \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) \] where \[ \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_{u} f_1^c(u).\\ \hline \end{array} \] Similarly, we get equivalent bounds $B_0^c$ and homogenized bounds for the other models. \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. \[ \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. PW: (without restrictions e.g. $u^Te=0$) \[ \begin{array}{|rcl|} \hline B_0 &=&\min_u \max_x q_u(x)\\ B_1 &=&\min_u \max_{x^Tx=n} q_u(x)\\ B_2 &=&\min_u \max_{-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_u \max_{y^Ty=n+1} q^c_u(y)\\ \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 our theme: \begin{center} \fbox{ $B_L$ equals all above bounds. } \end{center} ref PRW.\\ (The proofs come from exploiting strong Lagrangian duality of TRS) \end{slide} \begin{slide}{} {\bf A Strengthened SDP Bound for MC} (motivated by the strong duality results to follow) lifting procedure \[ X=xx^T\] implies \[X^2=xx^Txx^T=nX.\] equivalent quadratic matrix model for CQ \begin{eqnarray*} \mu^*:=&\max& \tr QX\\ &\mbox{s.t.}&\diag(X)=e\\ &&X^2-nX=0\\ &&X \succeq 0. \end{eqnarray*} \end{slide} \begin{slide}{} {\bf Convex Quadratic Program} \begin{eqnarray*} \mu^*:=&\min& q_0(x)\\ &\mbox{s.t.}& q_k(x) \leq 0,\quad k=1, \ldots m, \end{eqnarray*} where all $q_i(x)$ are convex quadratic functions. The dual is \[ \mbox{DCQP}\qquad \nu^*:= \max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x) + \sum_{k=1}^m \lambda_k q_k(x). \] $\bullet$(KKT) conditions are sufficient for global optimality $\bullet$if the primal value of CQP is bounded then it is attained and there is no duality gap, ref PE and T $\bullet$ the dual may not be attained \end{slide} \begin{slide}{} {\bf Nonconvex Cases} {\bf 1. Rayleigh Quotient} $A=A\tran \in \Sn$ \[ \lambda_{\min} = \min \{x\tran Ax : x\tran x = 1\}. \] tractable (nonconvex) problem no (Lagrangian) duality gap for this nonconvex problem \[ \begin{array}{rcl} \mu^*&:=& \max\limits_{\lambda}\ \min\limits_x\ x\tran Ax -\lambda (x\tran x - 1)\\ &=& \max\limits_{A - \lambda I \succeq 0}\ \min\limits_x\ x\tran (A -\lambda I)x + \lambda\\ &=& \max\limits_{A - \lambda I \succeq 0}\ \lambda\\ &=& \lambda_{\min} \end{array} \] \end{slide} \begin{slide}{} {\bf 2. Trust Region Subproblem} \begin{eqnarray*} &\mu^*:=\min& q_0(x)\\ &\mbox{s.t.}& x\tran x - \delta^2\leq 0 \mbox{ (or } =0). \\ \end{eqnarray*} for ``$\le$," the Lagrangian dual is: \[ \mbox{DTRS}\qquad \nu^*:=\max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x) + \lambda (x\tran x - \delta^2). \] strong duality holds and equivalent to (ref SW) the (concave) nonlinear semidefinite program \begin{eqnarray*} \mbox{DTRS}\qquad &\nu^*:=\max& g_0\tran (Q+\lambda I)^{\dagger} g_0 - \lambda \delta^2\\ &\mbox{s.t.}& Q+\lambda I \succeq 0\\ &&\lambda \geq 0. \end{eqnarray*} theme: tractable problem (ref MS) but strong duality holds. \end{slide} \begin{slide}{} {\bf 3. Two Trust Region Subproblem} TTRS consists in minimizing a (possibly nonconvex) quadratic function subject to a norm and a least squares constraint. ref in SQP methods by CDT. TTRS can have a nonzero duality gap, ref PY and Y. if objective not convex, then the primal may not be attained, ref LZ. TRS can have at most one local and nonglobal optimum, ref M. Still an open problem whether TTRS is an NP-hard or a polynomial time problem. \end{slide} \begin{slide}{} {\bf Orthogonally Constrained Programs with Zero Duality Gaps} \[ \{X: X X\tran =I\} \] Stiefel manifold ref EAS $A$ and $B$ $n\times n$ symmetric matrices \begin{equation} \begin{array}{rcl} {\rm QQP_O}\qquad \mu^O:=&\min& \tr AXBX\tran\\ &{\rm s.t.}& XX\tran=I. \end{array} \end{equation} Tractable problem using classical Hoffman-Wielandt inequality. But, Lagrangian dual has a duality gap, ref ZKRW. \end{slide} \begin{slide}{} The constraints $XX\tran=I$ and $X\tran X=I$ are equivalent. Add redundant constraints. \begin{eqnarray*} {\rm QQP_{OO}}\qquad \mu^O:=&\min& \tr AXBX\tran\\ &{\rm s.t.}& XX\tran=I,\ X\tran X=I. \end{eqnarray*} dual problem is \begin{eqnarray*} {\rm DQQP_{OO}}\\ \mu^O \geq \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} 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\}$ (extension of Hoffman-Wielandt inequality) \end{slide} \begin{slide}{} Concluding Remarks: In each case of a tractable bound for a nonconvex problem, the structure allows for redundant constraints to be added to close the Lagrangian duality gap. What is the correct question about ``best''? Can we close or reduce the duality gap in general? (ref KT) \end{slide} \begin{slide}{} \end{slide} \begin{slide}{} \end{slide} \end{document}