\documentclass{slides} \pagestyle{plain} \usepackage{rotating} \newcommand{\F}{{\cal F}} \newcommand{\p}{{\cal P}} \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] {10pt}{10pt}\par\medskip ~~} \begin{document} %======================= %======================= \begin{slide}{} \begin{center} {\bf Lagrangian and Semidefinite Programming Relaxations for Discrete Optimization Problems } \end{center} ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ Henry Wolkowicz \\ University of Waterloo\\ Dept of Combinatorics and Optimization ~\\ ~\\ \end{slide} \begin{slide}{} \begin{center} {\bf Lagrangian and Semidefinite Programming Relaxations for Numerically Hard Problems } \end{center} ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ ~~\\ Henry Wolkowicz \\ University of Waterloo\\ Dept of Combinatorics and Optimization ~\\ ~\\ \end{slide} \begin{slide}{} {\bf \begin{center} Question \end{center} } \vspace{1in} Bob, what was the title of my last talk here? -------------------------- similar topics relaxations of QAP using generalizations of the trust region subproblem (now called SDP) and strong duality \end{slide} \begin{slide}{} {\bf \begin{center} OUTLINE \end{center} } $\bullet$ quick intro. to SDP $\bullet$ Max-Cut Problem instance (quadratic boolean programming)\\ tractable relaxations versus Lagrangian duality, $\bullet$ Strong Duality: \\ TRS, 2TRS\\ matrix orthogonality (L\"owner) constraints $\bullet$ A strengthened relaxation for max-cut: \\ $\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 (denoted SDP) is an extension of linear programming (LP), e.g. an (linear) SDP is: \[ (P)\quad \begin{array}{rc} \mu^*:= \min & C \bullet X \\ \mbox{s.t.} & {\cal A}X = b \\ & X \succeq 0, \end{array} \] $C,X \in \Sn$, space of symmetric $n \times n$ matrices\\ \underline{\hspace{90mm}}\\ inner product $C \bullet X = \tr CX$\\ \underline{\hspace{90mm}}\\ $A\succeq B$ if $A-B \succeq 0$ positive semidefinite\\ \underline{\hspace{90mm}}\\ \[ {\cal A} :\Sn \rightarrow \Re^m \] linear operator: $({\cal 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 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 Tuncel/98, Lewis/98, 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 ${\cal 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}{} \[ (P)\quad \begin{array}{rc} \mu^*:= \min & C \bullet X \\ \mbox{s.t.} & {\cal A}X = b \\ & X \succeq 0, \end{array} \] \underline{\hspace{90mm}}\\ weak duality (using hidden constraints) \begin{eqnarray*} \mu^* &=& \min\limits_{X\succeq 0} \max_y C \bullet X + y^T(b-{\cal A}X)\\ &\geq& \max_y \min\limits_{X\succeq 0} y^Tb +\left(C - {\cal A}^*y\right) \bullet X\\ &=& \nu^*, \end{eqnarray*} \underline{\hspace{90mm}}\\ ${\cal A}^*$ adjoint operator of ${\cal A}$ \[ {\cal A} (X) \bullet y = X\bullet {\cal A}^* (y), \quad \forall X, \forall y \] \underline{\hspace{90mm}}\\ dual program \[ (D)\qquad \begin{array}{rc} \nu^*:= \max & b^T y \\ \mbox{s.t.} & {\cal A}^*y \preceq C \end{array} \] \end{slide} \begin{slide}{} The duality theory gives rise to the characterization of optimality \[ \begin{array}{cccc} {\cal A}^{*}y +Z - C &=& 0 & \mbox{dual feasibility} \\ b - {\cal A}(X) &=& 0 & \mbox{primal feasibility} \\ ZX &=& 0 & \mbox{complementary slackness} \\ Z,X \succeq 0. \end{array} \] $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. for int-pt methods\\ ($ZX$ is not necessarily symmetric; results in an overdetermined system of optimality conditions) \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:} {\bf 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 {\bf 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:} {\bf 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} \] \end{slide} \begin{slide}{} {\bf Bound $B_1^c$:} {\bf 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\limits_{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$:} {\bf 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 restrictions e.g. $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)\\ &&~\\ \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{ {\bf Theorem } $B_L$ equals all above bounds. } \end{center} ref PR, PRW/95.\\ (The proofs come from exploiting strong Lagrangian duality of TRS.) \end{slide} \begin{slide}{} Other instances: 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*} (more general nonconvex constraints $\alpha \leq q(x) \leq \beta.$)\\ 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). \] (ref Stern-Wolkowicz/95) strong duality holds and is equivalent to the (concave) nonlinear semidefinite program \begin{eqnarray*} \mbox{DTRS}\qquad &\nu^*:=\sup & g_0\tran (Q+\lambda I)^{\dagger} g_0 - \lambda \delta^2\\ &\mbox{s.t.}& Q+\lambda I \succ 0\\ &&\lambda \geq 0. \end{eqnarray*} Again {\bf theme holds}: tractable problem implies strong duality. (numerical efficient algorithm:- ref e.g. More-Sorensen/83) \end{slide} \begin{slide}{} short proof of strong duality (e.g. A. Lewis) WLOG TRS is nonconvex; smallest eigenvalue of $Q_0,$ denoted $\gamma,$ is negative: \[ \begin{array}{lllll} && \mu^* = \\ & =& \min\limits_{x^Tx \leq \delta^2} & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^Tx\\ &= & \min\limits_{x^Tx = \delta^2} & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^tx, \\ &&& \mbox{($Q_0$ is indefinite)}\\ &= & \min\limits_{x^Tx = \delta^2} & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2\\ &= & \min\limits_{x^Tx \leq \delta^2} & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2,\\ &&&\mbox{($Q_0-\gamma I$ is singular)}\\ &=& \max\limits_{\lambda \geq 0} \min\limits_x & x^T(Q_0-\gamma I)x-2c_0^tx + \lambda(x^Tx-\delta^2) \\ &&& + \gamma \delta^2 \mbox{(convex case)}\\ &=& \max\limits_{\lambda \geq 0} \min\limits_x & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)\\ &\leq & \max\limits_{\lambda \geq \gamma} \min\limits_x & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)\\ &&& \mbox{($\gamma < 0$)}\\ &=& \nu^* \leq \mu^*. \end{array} \] \end{slide} \begin{slide}{} {\bf 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 Celis-Dennis-Tapia. TTRS can have a nonzero duality gap, ref Peng-Yuan. if objective not convex, then the primal may not be attained, ref Luo-Zhang. TRS can have at most one local and nonglobal optimum, ref Martinez. Still an open problem whether TTRS is an NP-hard or a polynomial time problem. \end{slide} \begin{slide}{} Note: a quadratic constraint can be written as \[ y^tPy \leq \delta \] after the homogenization. This is lifted to \[ \trace PY \leq \delta. \] Second lifting: \[ YPY \preceq \delta Y. \] This strictly strengthens the SDP relaxation. \end{slide} \begin{slide}{} {\bf Orthogonally Constrained Programs with Zero Duality Gaps} permutation matrices are a subset of orthogonal matrices \[ \Pi \subset {\cal O} := \{X: X X\tran =I\} \] (Stiefel manifold ref e.g. Edelman,Arias,Smith) $A$ and $B$ $n\times n$ symmetric matrices \[ \begin{array}{rcl} {\rm QQP_O}\qquad \mu^*:=&\min& \tr AXBX\tran\\ &{\rm s.t.}& XX\tran=I. \end{array} \] \end{slide} \begin{slide}{} Tractable problem; can be solved using classical Hoffman-Wielandt inequality. Provides bounds for e.g. QAP. Proof using stationary point application of Lagrange multipliers: \[L(X,S)= \tr AXBX\tran + S(XX^T-I) \] \[ 0= \left< \nabla L(X,S),h \right> = 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}{} {A simple Example} Consider the following $2\times 2$ example $$ A:= \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right) ~~~~~~~~ B:= \left( \begin{array}{cc} 3 & 0 \\ 0 & 4 \end{array} \right). $$ $\mu^* = 10$ $$ 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}{} Summary: 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 (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}{} \begin{center} {\bf Quadratic Assignment Problem, QAP}\\ (additional constraints) \end{center} \[ (QAP)~~ \begin{array}{ccc} \mu^*:= &\min\limits_{X \in \Pi} & \tr AXBX^T - 2CX^T, \\ \end{array} \] $A, B$ real symmetric $n\times n$ matrices, $C$ real $n\times n$ matrix, $\Pi$ set of permutation matrices. model for e.g. allocating set of $n$ facilities to set of $n$ locations while minimizing quadratic objective (distance-flow) QAP is $N\!P$-hard and, in practice, problems of moderate sizes, such as $n=16$, are still considered very hard. recent surveys/books: Burkard/91, Rendl-Pardalos-Wolkowicz/93, Cellis/98. \end{slide} \begin{slide}{} Questions: \begin{enumerate} \item interesting numerical and theoretical difficulties, e.g. loss of constraint qualification and loss of sparsity in the optimality conditions. \item Can the new bound compete with other bounding techniques in speed and quality? \item comparison on the Nugent test problems? %\item %Can we incorporate the new bound in a branch and bound algorithm? \item add new facet inequalities? \end{enumerate} \end{slide} \begin{slide}{} Notation:\\ ${\mathcal E} := \{ X : Xe=X^Te=e \}$\\ set of matrices satisfying {\em assignment constraints} ${\mathcal Z} := \left\{ X : X_{ij} \in \{0,1\} \right\}$ \\ set of (0,1)-matrices ${\mathcal N} := \left\{ X : X_{ij} \geq 0 \right\}$ \\ set of {\em nonnegative matrices} ${\mathcal O} := \{ X : XX^T=X^TX=I \}$\\ set of orthogonal matrices \end{slide} \begin{slide}{} \[ \Pi = {\mathcal E} \cap {\mathcal Z} = {\mathcal O} \cap {\mathcal Z} \] rewrite QAP as (add redundant constraints) \[ \begin{array}{ccl} &\min & \tr AXBX^T - 2CX^T \\ &\mbox{~s.t.~} & XX^T = X^TX = I \\ && ||Xe - e||^2=0 \\ && || X^Te - e||^2=0 \\ && X_{ij}^2 - X_{ij} = 0, \quad \forall i,j.\\ && \diag(X_{:i}X_{:j}^T)=0, \quad \mbox{if } i \neq j\\ && X_{:i}X_{:j}^T - \Diag\left(\diag(X_{:i}X_{:j}^T)\right) =0, \quad \mbox{if } i = j\\ \end{array} \] \end{slide} \begin{slide}{} {Lagrangian Relaxation}\\ \[ \begin{array}{ll} \mu_{\mathcal O} \geq \mu_{\mathcal L} \\ ~~~:= \max\limits_{W,u_{0},v_{0}\ldots} \min\limits_{XX^T=X^TX = I} &\{\tr AXBX^T - 2CX^T\\ &~~+ \sum_{ij} W_{ij}(X_{ij}^2 - X_{ij})\\ &~~~+u_{0}\|Xe-e\|^{2}\\ &~~~~+v_0\|X^Te-e\|^{2}\\ &~~~~+\ldots \}. \end{array} \] homogenize the Lagrangian using scalar $x_0$ and constraint $x_{0}^{2}=1.$ \end{slide} \begin{slide}{} We get the lower bound\\ (quadratic, linear constant in $X$) \[ \begin{array}{ll} \max\limits_{W,S_b,S_o,u_{0}v_0,,w_{0}} \min\limits_{X,~x_0} \{ \tr [ AXBX^T \\ ~~+ u_{0}\|Xe\|^2+v_0 \|X^Te\|^2 \\ ~~~+ W(X \circ X)^T + w_0 x_0^2 \\ ~~~~~+ S_b XX^T + S_o X^TX ] \\ ~- \tr x_0(2C+ W)X^T\\ ~~~~ - 2x_{0}u_{0}e^T(X+X^T)e \\ ~~~~~ + \ldots \\ ~- w_0 - \tr S_b - \tr S_o +2nu_{0}x_0^2 \}. \end{array} \] Apply the hidden semidefinite constraint to get an SDP: \[ \begin{array}{cl} \max & - w_0 - \tr S_b - \tr S_o + \ldots \\ \mbox{~s.t.~}& L_Q +\Arrow(w) + \BoDiag(S_b) \\ & ~~+ \OoDiag(S_o)+u_{0}D + \ldots \succeq 0. \end{array} \] \end{slide} \begin{slide}{} check Slater's condition - OK\\ take Lagrangian dual again \[ \begin{array}{cll} \min &\tr L_QY \\ \mbox{~s.t.~} & \bodiag(Y) = I, & \oodiag(Y) = I \\ & \arrow(Y) = e_{0}, & \tr DY=0 \\ & \ldots \\ & Y \succeq 0, \end{array} \] check Slater's condition again - $D \succeq 0$ so it fails!! But we can project onto the minimal face!! Now remove redundant constraints to get simplified SDP relaxation \end{slide} \begin{slide}{} simple projected relaxation with $n^{3}-2n^{2}+1$ constraints. \[ \begin{array}{lll} \mu_{R2} := & \min & \tr (\hat{V}^TL_Q\hat{V})R \\ & \mbox{~s.t.} & {\mathcal G}_{\bar{J}}(\hat{V}R\hat{V}^T) = E_{00} \\ && R \succeq 0. \end{array} \] The dual problem is \[ \begin{array}{lll} \mu_{R2} = & \max & -Y_{00} \\ & \mbox{~s.t.} &\hat{V}^{T}(L_{Q}+{\mathcal G}^{*}_{\bar{J}}(Y))\hat{V} \succeq 0. \end{array} \] \end{slide} \begin{slide}{} \oddsidemargin -.45in \evensidemargin -.45in {\tiny \begin{center} \begin{tabular}{|l|rrrrr|rrr|} \hline & Sol. & GLB & ELI & RRD & EVB3 &$\mu_{R1}$ &$\mu_{R2}$&$\mu_{R3}$\\ \hline Esc16a & 68 & 38 & 47 & 68 & 50 & 47 & 50 & 47 \\ Esc16b & 292 & 220 & 250 & 278 & 276 & 250 & 276 & 277 \\ Esc16c & 160 & 83 & 95 & 118 & 113 & 95 & 113 & 110 \\ Esc16d & 16 & 3 & -19 & 4 & -12 & -19 & -12 & -6 \\ Esc16e & 28 & 12 & 6 & 14 & 13 & 6 & 13 & 9 \\ Esc16g & 26 & 12 & 9 & 14 & 11 & 9 & 11 & 10 \\ Esc16h & 996 & 625 & 708 & 704 & 708 & 708 & 909 & 806 \\ Esc16i & 14 & 0 & -25 & 0 & -21 & -25 & -21 & -6 \\ Esc16j & 8 & 1 & -6 & 2 & -4 & -6 & -4 & -4 \\ \hline Had12 & 1652 & 1536 & 1573 & n.a. & 1595 & 1604 & 1640 & 1648 \\ Had14 & 2724 & 2492 & 2609 & n.a. & 2643 & 2651 & 2709 & 2703 \\ Had16 & 3720 & 3358 & 3560 & n.a. & 3601 & 3612 & 3678 & 3648 \\ Had18 & 5358 & 4776 & 5104 & n.a. & 5176 & 5174 & 5286 & 5226 \\ Had20 & 6922 & 6166 & 6625 & n.a. & 6702 & 6713 & 6847 & 6758 \\ \hline Kra30a &88900 &68360 &63717 &76003 & n.a. & 69736 & --~ & --~ \\ Kra30b &91420 &69065 &63818 &76752 & n.a. & 70324 & --~ & --~ \\ \hline Nug12 & 578 & 493 & 472 & 523 & 498 & 486 & 530 & 547 \\ Nug14 & 1014 & 852 & 871 & n.a. & 898 & 903 & 959 & 967 \\ Nug15 & 1150 & 963 & 973 & 1041 & 1001 & 1009 & 1060 & 1075 \\ Nug16a & 1610 & 1314 & 1403 & n.a. & 1455 & 1461 & 1527 & 1520 \\ Nug16b & 1240 & 1022 & 1046 & n.a. & 1081 & 1082 & 1138 & 1132 \\ Nug17 & 1732 & 1388 & 1487 & n.a. & 1521 & 1548 & 1621 & 1604 \\ Nug18 & 1930 & 1554 & 1663 & n.a. & 1707 & 1723 & 1801 & 1776 \\ Nug20 & 2570 & 2057 & 2196 & 2182 & 2290 & 2281 & 2385 & 2326 \\ Nug21 & 2438 & 1833 & 1979 & n.a. & 2116 & 2090 & 2252 & 2157 \\ Nug22 & 3596 & 2483 & 2966 & n.a. & 3174 & 3140 & 3394 & 3234 \\ Nug24 & 3488 & 2676 & 2960 & n.a. & 3074 & 3068 & --~ & --~ \\ Nug25 & 3744 & 2869 & 3190 & n.a. & 3287 & 3305 & --~ & --~ \\ Nug30 & 6124 & 4539 & 5266 & 4805 & 5448 & 5413 & --~ & --~ \\ \hline \end{tabular} ~~\\ {QAPLIB instances 1} \end{center} } \end{slide} \begin{slide}{} \oddsidemargin -.85in \evensidemargin -.85in %\begin{turn} %\turn{ {\tiny \begin{center} \begin{tabular}{|l|rrrrr|rrr|} \hline & Sol. & GLB & ELI & RRD & EVB3 &$\mu_{R1}$ &$\mu_{R2}$&$\mu_{R3}$\\ \hline Rou12 &235528&202272&200024&224278&201337& 208685&220991&227986\\ Rou15 &354210&298548&296705&324869&297958& 306833&323141&324900\\ Rou20 &725522&599948&597045&643346& n.a. & 615549&642448&631680\\ \hline Scr12 & 31410& 27858& 4727& 29872& n.a. & 11117&24230 & 27183\\ Scr15 & 51140& 44737& 10355& 49264& n.a. & 17046&42094 & 40821\\ Scr20 &110030& 86766& 16113& 95113& n.a. & 28535&83026 & 59780\\ \hline Tai12a & 224416 & 195918 & 193124 & n.a. &195673 &203595&215377&220938\\ Tai15a & 388214 & 327501 & 325019 & n.a. &327289 &333437&349476&347908\\ Tai17a & 491812 & 412722 & 408910 & n.a. &410076 &419619&441238&435675\\ Tai20a & 703482 & 580674 & 575831 & n.a. & n.a. &591994&618720&606228\\ Tai25a &1167256 & 962417 & 956657 & n.a. & n.a. &974004 & --~ & --~ \\ Tai30a &1818146 &1504688 &1500407 & n.a. & n.a. &1529135& --~ & --~ \\ \hline Tho30 & 149936 & 90578 & 119254 & 100784 & n.a. &125972& --~ & --~ \\ \hline \end{tabular} ~~\\ {QAPLIB instances 2} \end{center} %\end{turn} } \end{slide} \begin{slide}{} \oddsidemargin -.85in \evensidemargin -.85in {\tiny \begin{center} \begin{tabular}{|l|rrrrr|rrr|} \hline & Sol. & GLB & ELI & RRD & EVB3 &$\mu_{R1}$ &$\mu_{R2}$&$\mu_{R3}$\\ \hline Car10ga& 4954 & 3586 & 4079 & n.a. & 4541 & 4435 & 4853 &4919 \\ Car10gb& 8082 & 6139 & 7211 & n.a. & 7617 & 7600 & 7960 &8035 \\ Car10gc& 8649 & 7030 & 7837 & n.a. & 8233 & 8208 & 8561 &8612 \\ Car10gd& 8843 & 6840 & 8006 & n.a. & 8364 & 8319 & 8666 &8780 \\ Car10ge& 9571 & 7627 & 8672 & n.a. & 8987 & 8910 & 9349 &9473 \\ Car10pa&32835 &28722 & -4813& n.a. & n.a. & 1583 & 12492 &30359 \\ Car10pb&14282 &12546 &-14944& n.a. & n.a. & -5782 & 9934 &13361 \\ Car10pc&14919 &12296 &-17140& n.a. & n.a. & -8040 & 2473 &13655 \\ \hline Esc08a & 2 & 0 & -2 & 0 & n.a. & -2 & 0 & 2 \\ Esc08b & 8 & 1 & -2 & 2 & n.a. & -2 & 3 & 6 \\ Esc08c & 32 & 13 & 8 & 22 & n.a. & 9 & 18 & 30 \\ Esc08d & 6 & 2 & -2 & 2 & n.a. & -2 & 2 & 6 \\ Esc08e & 2 & 0 & -6 & 0 & n.a. & -6 & -4 & 1 \\ Esc08f & 18 & 9 & 8 & 18 & n.a. & 9 & 13 & 18 \\ \hline Nug05 & 50 & 50 & 47 & 50 & 50 & 49 & 50 & 50 \\ Nug06 & 86 & 84 & 69 & 86 & 70 & 74 & 85 & 86 \\ Nug07 & 148 & 137 & 125 & 148 & 130 & 132 & 144 & 148 \\ Nug08 & 214 & 186 & 167 & 204 & 174 & 179 & 197 & 210\\ \hline \end{tabular} ~~\\ {Numerical Results for old instances} \end{center} } \end{slide} \begin{slide}{} \oddsidemargin -.95in \evensidemargin -.95in {\tiny \begin{center} \begin{tabular}{|l|rrrr|} \hline & Sol. & $\mu_{R1}$ &$\mu_{R2}$ & $\mu_{R3}$ \\ \hline Nug12C & 578 & 492 & 534 & 545 \\ Nug15C & 1150 & 1012 & 1075 & 1081 \\ Nug20C & 2570 & 2292 & 2396 & 2335 \\ Nug30C & 6124 & 5424 & 5648 & --~ \\ \hline \end{tabular} ~~\\ {Instances for which symmetry is destroyed} \end{center} %\begin{center} \begin{tabular}{|lc|rrr|rrrrrr|} \hline & $n$ & Sol. & GLB & ($ir$) & $\mu_{R1}$ & ($ir$) & $\mu_{R2}$ & ($ir$) &$\mu_{R3}$ & ($ir$)\\ \hline Nug12 & 12 & 578 & 493 & & 486 & & 530 & & 547 & \\ Nug12.1 & 11 & 586 & 496 & (0.6)& 514 & (5.4) & 551 & (3.9)& 574 & (4.9)\\ Nug12.2 & 11 & 578 & 495 & (0.4)& 514 & (5.4) & 553 & (4.3)& 571 & (4.3)\\ Nug12.5 & 11 & 578 & 494 & (0.2)& 524 & (7.8) & 552 & (4.1)& 570 & (4.2)\\ Nug12.6 & 11 & 586 & 499 & (1.2)& 530 & (9.0) & 561 & (5.8)& 578 & (5.6)\\ \hline Nug15 & 15 & 1150 & 963 & & 1009& & 1060& & 1075& \\ Nug15.1 & 14 & 1150 & 967 &(0.4)& 1049&(4.0)& 1104&(4.2)& 1114&(3.6)\\ Nug15.2 & 14 & 1166 & 974 &(1.1)& 1076&(6.6)& 1124&(6.0)& 1135&(5.6)\\ Nug15.3 & 14 & 1200 & 987 &(2.5)& 1075&(6.5)& 1133&(6.9)& 1145&(6.5)\\ Nug15.6 & 14 & 1152 & 968 &(0.5)& 1056&(4.7)& 1106&(4.3)& 1118&(4.0)\\ Nug15.7 & 14 & 1166 & 979 &(1.7)& 1052&(4.3)& 1112&(5.2)& 1125&(4.7)\\ Nug15.8 & 14 & 1168 & 983 &(2.1)& 1063&(5.4)& 1118&(5.5)& 1133&(5.4)\\ \hline Nug20 & 20 & 2570 & 2057& & 2281& & 2385& & 2326 & \\ Nug20.1 & 19 & 2628 & 2082&(1.2)& 2358&(3.4)& 2449&(2.7)& 2414 &(3.8) \\ Nug20.2 & 19 & 2600 & 2130&(3.6)& 2401&(5.3)& 2489&(4.4)& 2464 &(6.0) \\ Nug20.3 & 19 & 2588 & 2067&(0.5)& 2331&(2.2)& 2428&(1.8)& 2392 &(2.8) \\ Nug20.6 & 19 & 2570 & 2064&(0.3)& 2341&(2.6)& 2431&(1.9)& 2403 &(3.3) \\ Nug20.7 & 19 & 2634 & 2105&(2.3)& 2387&(4.6)& 2479&(3.9)& 2436 &(4.7) \\ Nug20.8 & 19 & 2636 & 2127&(3.4)& 2381&(4.4)& 2485&(4.2)& 2438 &(4.8) \\ \hline \end{tabular} %\end{center} ~~\\ Results for first level in branching tree } \end{slide} \begin{slide}{} \begin{center} {\bf A Strengthened SDP Bound for MC}\\ \end{center} (ref Anjos-Wolkowicz/99) Illustration of the recipe for SDP relaxation, based on a second lifting motivated by strong duality results obtained from adding redundant constraints of type $XX^T$ ------------------------------- 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.\\ \underline{\hspace{90mm}}\\ Now add redundant constraints and get: \begin{eqnarray*} \mu^*:=&\max& \tr QX\\ &\mbox{s.t.}&\diag(X)=e\\ &&X^2-nX=0\\ &&X \circ X=E \end{eqnarray*} where $E$ is the matrix of ones. \end{slide} \begin{slide}{} Note: $X^2=nX,~\trace X = n$ implies $X$ is rank one. But, we cannot solve this nonconvex problem in general, i.e. we have to look at the Lagrangian relaxation with vectors dimension $t(n).$ \end{slide} \begin{slide}{} Recipe for SDP relaxations: \begin{enumerate} \item add redundant constraints \item take Lagrangian dual \item homogenize \item use hidden semidefinite constraint to obtain SDP equivalent {\em (check Slater's constraint qualification - strict feasibility)} \item take Lagrangian dual again \item check Slater's CQ again - project if it fails \item delete redundant constraints \end{enumerate} \end{slide} \begin{slide}{} Notation:\\ (Interesting operators and adjoints --fun for me, if for no one else) ~$\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$ ignoring strictly lower triang. ~$\bullet$ $S=\sMat(s) \quad$ inverse of $\svec$ ~$\bullet$ $\hMat (v) \quad$ is adjoint of $\svec$, off-diagonal terms are multiplied by a half ~$\bullet$ $\dsvec (S) \quad$ is adjoint of $\sMat$, operator like $\svec$ but off diagonal elements are 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}{} start with equivalent program to MCQ: \beq \label{eq:maxcutstrength} {\rm MC2} \begin{array}{ccc} \mu^*= &\max & \ \tr QX \\ &\mbox{s.t.}& \diag(X) = e\\ &&X\circ X=E\\ &&X^2-nX=0,\\ \end{array} \eeq to efficiently apply Lagrangian relaxation and not lose information from the linear constraint, replace the constraint with the norm constraint $||\diag(X) - e||^2=0$. Add $1-y_0^2=0.$ We 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 $w,T,S$ \[ \begin{array}{lcc} \mu^*\leq \\ \nu_2^*:= \min\limits_{w,T,S} \max\limits_{x,y_0^2=1} \tr \left(Q\sMat(x)\right)y_0 \\ ~~~~+w( \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 + n)\\ ~~~~~~~~~~~+\tr T(E-\sMat(x) \circ \sMat(x))\\ ~~~~~~~~~~~~~ +\tr S((\sMat(x))^2-n\, \sMat(x)y_0). \end{array} \] move variable $y_0$ into the Lagrangian without increasing the duality gap since this is a trust region subproblem \[ \begin{array}{rl} \nu_2^*=& \min\limits_{t,w,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}{} The inner maximization of the above relaxation is an unconstrained pure qua\-d\-r\-a\-tic maximization, i.e. the optimal value is infinity unless the Hessian is negative semidefinite {\bf (hidden constraint)} is which case $x=0$ is optimal. Therefore we need to evaluate the Hessian of the Lagrangian. \end{slide} \begin{slide}{} Using $Q \sMat(x) = x^T \dsvec(Q),$ and adding a 2 for convenience, we get the constant part (no Lagrange multipliers) of the Hessian: \[ 2H_c:=2\pmatrix{ 0 & \frac 12 \dsvec(Q)^T\cr \frac 12 \dsvec(Q) & 0\cr }. \] \end{slide} \begin{slide}{} nonconstant part: Use: $\dsvec \Diag \diag \sMat = \sdiag^* \sdiag = \Diag \svec (I)$ rewrite the quadratic forms as follows: \[ \begin{array}{lll} \sdiag(x)^T \sdiag(x) = x^T \left(\dsvec \Diag \diag \sMat\right)x;\\ e^T \sdiag(x) = \left(\dsvec \Diag e \right)x;\\ ~~\\ \tr S (\sMat(x))^2 = \tr \sMat(x)\, S\, \sMat(x)\\ ~~~~~ = x^T \dsvec\left(S \sMat(x)\right)\\ ~~~~~= x^T \left(\dsvec S \sMat\right)x;\\ \mbox{ }\\ \tr T(\sMat(x) \circ \sMat(x))\\ ~~= x^T \left\{\dsvec \left(T \circ \sMat(x) \right) \right\} \\ ~~= x^T \left(\dsvec \left(T \circ \sMat \right)\right) x. \end{array} \] \end{slide} \begin{slide}{} use the {\em negative} of the Hessian and split it into four linear operators with the factor 2: \[ \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}{} The matrix $\sdiag^* \sdiag \in {\cal S}^{t(n)}$ is diagonal with elements determined using \begin{eqnarray*} e_i^T \left( \sdiag^* \sdiag \right)e_j &=&\sdiag(e_i)^T\sdiag(e_j)\\ &=& \left\{ \begin{array}{cc} 1 & \mbox{if } $i=j=t(k)$\\ 0 & \mbox{otherwise.} \end{array} \right. \end{eqnarray*} Similarly, we find that, for $T=\sum_{ij} t_{ij}E_{ij},$ where the matrices $E_{ij}$ are the elementary matrices $e_ie_j^T+e_je_i^T,$ we have \[ \dsvec \left( T \circ \sMat\right)= \sum_{ij} t_{ij} \dsvec \left(E_{ij}\circ \sMat\right). \] \end{slide} \begin{slide}{} cancel the 2 and get the (equivalent to the Lagrangian dual) semidefinite program MCDSDP2 \[ \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. the dual of this SDP is the 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} \] we need to calculate the adjoint operators and remove redundant constraints in MCDSDP2. \end{slide} \begin{slide}{} \[ Y \cong \left( \begin{array}{c}y_0 \\ x \end{array}\right) \left( y_0 ~x^T\right), \quad X = \sMat(x) \] simplified SDP relaxation MCPSDP2 \[ \begin{array}{ccl} &\max & \trace H_cY\\ &\mbox{s.t.}& \diag(Y) = e \\ & & Y_{0,t(i)}=1, \quad \forall i=1, \ldots , n\\ && \sum\limits_{k=1}^i Y_{t(i-1)+k,t(j-1)+k}\\ && ~~+ \sum\limits_{k=i+1}^j Y_{t(k-1)+i,t(j-1)+i}\\ &&~~~~~ +\sum_{k=j+1}^nY_{t(i-1)+i,t(k-1)+j} \\ && ~~~~~~~~~~-n Y_{0,t(j-1)+i}=0\\ && ~~~~~~~~~~~~ \quad \forall 1\leq i < j \leq n\\ && Y \succeq 0, Y \in S^{t(n)+1}. \end{array} \] This problem has $2t(n)-1$ constraints. \end{slide} \begin{slide}{} surprise result {\bf LEMMA 1}\\ Suppose that $Y$ is feasible in MCPSDP2. Then the first row \[ \sMat \left( Y_{0,1:t(n)} \right) \succeq 0 \] and there is feasible for MCSDP.\\ \underline{\hspace{90mm}}\\ Proof: For $Y$ feasible for MCPSDP3, write \[ Y =\pmatrix{1 & x^T \cr x & \bar{Y}}, \] with $x = Y_{0,1:t(n)}$. Note that $\bar{Y}$ is a principal submatrix of $Y$ and therefore $\bar{Y} \succeq 0$. First, let's find the adjoint of $\Hcal_3(\cdot).$ By definition of ${\cal H}_3$ \[ \begin{array}{rcl} \left< \Hcal_3(S),Y \right> &=& n \dsvec(S)^T x - \left< \vsMat^* \kvec S \sMat , \bar{Y} \right>, \end{array} \] or, taking adjoints, \[ \begin{array}{lcl} \left< S, \Hcal_3^*(Y) \right> =\\ ~~~~~~~ =\trace S n\sMat(x) - \left< S , \vsMat^* \kvec \bar{Y} \sMat \right>\\ ~~~~~~~ = \left< S, n\sMat(x) - \vsMat^* \kvec \bar{Y} \sMat \right>. \end{array} \] Recall that $\vsMat^* \kvec$ is essentially (and in the symmetric case reduces to) $\sMat^*$ except that it acts on possibly nonsymmetric matrices. Therefore the constraint ${\cal H}_3^*(Y) = 0$ is equivalent to \[ \sMat(x) = \frac{1}{n} \vsMat^* \kvec \bar{Y} \sMat \] and thus $\sMat(x)$ is a congruence of the positive semidefinite matrix $\bar{Y}$. The result follows. \QED \end{slide} \begin{slide}{} The added nonlinear constraint has the following interesting and useful properties.\\ {\bf LEMMA 2} \\ Suppose that $X, \bar X$ are both feasible for MCSDP. Then \[ \tr (X^2-nX)(\bar{X}^2-n\bar X) \geq 0. \] Suppose in addition that both \[ (X^2-nX) \neq 0, \quad (\bar{X}^2-n\bar X) \neq 0, \] and both $X, \bar X \in {\cal F},$ a face of $\p,$ with $\bar X \in \relint {\cal F}.$ Then \[ \tr (X^2-nX)(\bar{X}^2-n\bar X) > 0. \] \end{slide} \begin{slide}{} We always get a strict improvement in the bound unless we have solved the Max-Cut problem itself, i.e. {\bf THEOREM} The optimal values satisfy \[ \nu_2^* \leq \nu^* \quad \mbox{and} \quad \nu_2^* = \nu^* \Rightarrow \nu_2^* = \nu^* = \mu^*. \] \QED \end{slide} \begin{slide}{} \oddsidemargin -.35in \evensidemargin -.35in {\tiny %\begin{table}[b] %\begin{center} \begin{tabular}{||c|c|c|c|c|c|c|c|c||}\hline $n$ & Wt & MCSDP& MCPSDP2& Num. \\ & opt.& (\% rel. err) & (\% rel. err) & rank \\ \hline \hline 5 & 4 & 4.5225 (13.06\%) & 4.2890 (7.22\%) & 2 \\ \hline 7 & 56 & 56.4055 (0.72\%) & 56.0954 (0.17\%) & 3 \\ \hline 8 & 30 & 30.2015 (0.67\%) & 30. (e-10\%) & 1 \\ \hline 9 & 58 & 58.9361 (1.61\%) & 58.1182 (0.20\%) & 3 \\ \hline 10& 64& 64.08 (0.1268\%) & 64 (e-08\%) & 3 \\ \hline 12 & 88 & 90.3919 (2.72\%) & 89.5733 (1.79\%) & 4 \\ \hline \end{tabular} %\end{center} %\end{table} The first line of results corresponds to solving both MC relaxations for a 5-cycle with unit edge-weights; the others come from randomly generated weighted graphs. } \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? \end{slide} \end{document}