\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\,}
\newcommand{\beq}{\begin{equation}}
\def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\begin{document}
%=======================
%=======================
\begin{slide}{}
\begin{center}
{\bf
Semidefinite Relaxations for Hard Combinatorial Problems
}
\end{center}


~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz \\
University of Waterloo\\

~\\
~\\

\end{slide}
\begin{slide}{}
Outline

?????????
\end{slide}
\begin{slide}{}
{Problem Definition}
\label{sect:probdef}
Suppose that $G=(V,E)$ is an undirected graph with
edge set $V = \{v_i\}_{i=1}^n$ and weights $w_{ij}$
on the edges $(v_i,v_j) \in E$.
The {\em max-cut problem} consists in finding
the index set ${\cal I} \subset \{1,2, \ldots n\},$
to maximize the weight of the edges
with one end point with index in ${\cal I}$ and the other in the
complement.
This is equivalent to the following discrete optimization problem with a
quadratic objective.
\[
(MC)~~~  \begin{array}{c}
    \max ~ \frac 12 \sum_{i<j} w_{ij}(1-x_ix_j),~~~x \in  \{ \pm 1 \}^n.
\end{array}
\]
We equate $x_i=1$ with $i \in \cal I$ and -1 otherwise.  Define the
quadratic objective
\[ q(x) := x^tQx-2c^tx, \]
where $Q$ is an $n \times n$ symmetric matrix.
Then, the boolean quadratic programming problem is
 equivalent to the
{\em $(\pm 1)$-quadratic programming problem}
\beq
\label{eq:homogquad}
\mu^*:=\max ~ q(x),~~~x \in \{ \pm 1 \}^n.
\end{equation}
The max-cut problem is obtained by setting $c=0$ in the above objective
function.


{Polyhedral Approach}
\label{sect:polappr}
A linear relaxation is obtained using ...???
give details of linear relaxation here ?????

see e.g. the vast
literature on roof duality for boolean quadratic programming
\cite{HaHaSi:84,HaRu:70,AdDe:94} and other linear based approximations,
e.g. \cite{AdJo:94}.

For 0-1 quadratic programming there have been many different linear
approximations derived and tested. In \cite{BoCrHa:90}, the authors
show that three seemingly different linear relaxations are all equal.
These linear relaxations are referred to as roof duality. Then in
\cite{AdDe:94} it is shown that roof duality is in fact equal to
Lagrangian duality, i.e. the roof relaxation is equivalent to the
Lagrangian relaxation. Thus, many attempts in improving linear
relaxations have all led to the Lagrangian relaxation for a linear
version of the problem.

Another approach is to start by relaxing the cut polytope, the convex
hull of all cut characteristic vectors, into the unit cube. Valid
inequalities, preferably facet-defining inequalities, for the cut polytope 
are added successively as needed to tighten the relaxed set. Various classes of
facet-defining inequalities are known for the cut polytope \cite{PoTu:95}.
One such class of facet-defining inequalities is the class of triangle 
inequalities
  \[ x_{ij} +x_{ik} +x_{jk} \leq 2.\]
For a computational study of the max cut problem using such cutting plane
algorithm see \cite{DeRi:92}. 


{SDP Relaxation}
\label{sect:sdprelax}
Can we find a better approximation?
We can start by replacing the $(\pm 1)$ 
constraints with the quadratic constraints
\[  x_i^2=1,~i=1,\ldots,n. \]
This of course is an equivalent representation of the $\pm 1$
constraints. Thus this equivalent problem is just as hard to solve.
However, we can use Lagrangian relaxation to get an upper bound.
We delete the quadratic constraints and add them to the objective
function with Lagrange multipliers $\lambda_i.$
We then solve an unconstrained problem to get an upper bound
for the original constrained problem.
\begin{eqnarray*}
\mu^* \leq 
 \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i).
\end{eqnarray*}
Since the above is an upper bound for any choice of $\lambda_i$, we get
the following Lagrangian relaxation bound.
\begin{eqnarray*}
\mu^* \leq 
B_{mc} &:=& \min_{\lambda} \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i) \\
       & =& \min_{\lambda} \max_{x} x^t\left(Q-\Diag (\lambda) \right)x 
           + \lambda^te.
\end{eqnarray*}
First, we remark that the above min-max problem reduces to a tractable
convex minimization problem, since the {\em dual functional}
\[ 
  h(\lambda) := \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i) 
\]
is the maximum of linear functions and so is convex. In fact, the
Lagrangian dual is always a nice tractable problem.
We now note that the inner maximization problem is infinite valued
unless the Hessian of the Lagrangian is negative semidefinite, i.e. we
have the {\em hidden semidefinite constraint}
\[ Q - \Diag (\lambda) \preceq 0.  \]
Moreover, once we add this semidefinite constraint to the outer
minimization problem, the inner maximization is attained at $x=0.$ We
have eliminated the $x$ variable and the maximization part of the
problem.

Therefore the upper bound for MC can be obtained by solving the following SDP.
\beq
\label{eq:mcD}
\begin{array}{cc}
\min & \left<\lambda ,e\right> \\
\mbox{subject to} & Q-\Diag (\lambda) \preceq 0,
\end{array}
\end{equation}
where $\Diag ( \lambda)$ is the diagonal matrix formed using the vector
$\lambda.$
We can then treat this program as if it were an LP and note that the
adjoint operator $\Diag^*(Y)=\diag(Y),$ the vector of the matrix $Y.$
Moreover, the semidefinite cone is
self polar. We then get the following dual SDP to the above Lagrangian
dual.
\beq
\label{eq:mcP}
\begin{array}{cc}
\max & \tr QX \\
\mbox{subject to} & \diag(X) = e\\
      & X \succeq 0.
\end{array}
\end{equation}
The above is the SDP relaxation of MC. This can be obtained directly by
noting that $x_i^2=1$ is equivalent to
\[  \diag(xx^t) = e  \]
and $x^tQx= \tr Qxx^t.$ Therefore the relaxation is obtained by
replacing $xx^t$ by the symmetric positive semidefinite matrix $X$, i.e.
we relax the rank-1 requirement when $X=xx^t.$




{SDP Algorithm}
We can derive very efficient primal-dual
interior-point (p-d i-p) algorithms. For example, we start
with the dual problem and formulate the log-barrier problem with fixed
parameter $\mu >0$
\beq
\label{eq:duallogbar}
\begin{array}{cc}
\min & \left<\lambda ,e\right> + \tr Y\left(Q-\Diag (\lambda) + Z \right) 
             - \mu \log \det Z\\
\mbox{subject to} & Z \succ 0.
\end{array}
\end{equation}
We now solve this unconstrained problem by differentiation.

We get the dual and primal feasibility and complementary slackness.

change to get more linearity - apply  Newton step. Different
directions???

{Theoretical Error Bounds}
\label{sect:approxsol}
(Franz working on this)
We now discuss Goemans-Williamson and the approximate solution - start
with Poljak conjecture.
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\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}