%\documentclass{slides} \documentclass[landscape]{seminar} %\documentclass[twoside]{seminar} %\usepackage{fancyhdr} \usepackage{amssymb} \usepackage{latexsym} \input epsf \usepackage{psfig} %\usepackage[hyperindex,pdfmark]{hyperref} %\usepackage{fullpage} %\usepackage{multicol} %\usepackage[pdftex]{graphicx} %\usepackage{hyperref} \pagestyle{plain} \newtheorem{exam}{Example}[subsubsection] \newtheorem{prob}{Problem}[subsubsection] \newtheorem{definition}{Definition}[subsubsection] \newtheorem{remark}{Remark}[subsubsection] \newtheorem{prop}{Proposition}[subsubsection] \newtheorem{lemma}{Lemma}[subsubsection] \newtheorem{lem}{Lemma}[subsubsection] \newtheorem{thm}{Theorem}[subsubsection] \newtheorem{cor}{Corollary}[subsubsection] \newtheorem{alg}{Algorithm}[subsubsection] \def\half{\frac{1}{2}} \def\Rm {\mathbb{R}^m} \def\Rn {\mathbb{R}^n} \def\RR {\mathbb{R}} \def\pols {\mathbb{P}} \newcommand{\D}[2]{[{\cal D}#1(#2)]} \newcommand{\inner}[2]{{\langle #1 , #2 \rangle}} \newcommand{\infpgms}[2]{\inf\,\Bigl\{#1 \bigm| #2\Bigr\}} \newcommand{\suppgms}[2]{\sup\,\Bigl\{#1 \bigm| #2\Bigr\}} \newcommand{\infpgm}[3]{\mbox{#1~~~~~}\inf\,\Bigl\{#2 \bigm| #3\Bigr\}} \newcommand{\suppgm}[3]{\mbox{#1~~~~~}\sup\,\Bigl\{#2 \bigm| #3\Bigr\}} \newcommand{\minpgm}[3]{\mbox{#1~~~~~}\min\,\Bigl\{#2 \bigm| #3\Bigr\}} \newcommand{\maxpgm}[3]{\mbox{#1~~~~~}\max\,\Bigl\{#2 \bigm| #3\Bigr\}} \newcommand{\minpgms}[2]{\min\,\Bigl\{#1 \bigm| #2\Bigr\}} \newcommand{\maxpgms}[2]{\max\,\Bigl\{#1 \bigm| #2\Bigr\}} \newcommand{\req}[1]{(\ref{#1})} \newcommand{\svec}{{\rm svec\,}} \newcommand{\hMat}{{\rm hMat\,}} \newcommand{\vsMat}{{\rm vsMat\,}} \newcommand{\kmat}{{\rm Mat\,}} \newcommand{\sMat}{{\rm sMat\,}} \newcommand{\dsvec}{{\rm dsvec\,}} \newcommand{\Hmat}{{\rm Hmat\,}} \newcommand{\vSmat}{{\rm vSmat\,}} \newcommand{\Smat}{{\rm Smat\,}} \newcommand{\sdiag}{{\rm sdiag\,}} \newcommand{\sn}{{\cal S}^n } \def\sdp {{\bf SDP}} \def\sqp {{\bf SQP}} \def\nep {{\bf NEP}} \def\Lag {{\cal L}} \def\lkp {\lambda^{(k+1)}} \def\lk {\lambda^{(k)}} \def\sqqp {{\bf SQQP}} \def\xk {{x}^{(k)}} \def\xkp {{x}^{(k+1)}} \def\df {:=} \def\pA{{\widetilde A}} \def\pZ{{\widetilde Z}} \def\pX{{\widetilde X}} \def\pdx{{\widetilde{dx}}} \def\pdz{{\widetilde{dz}}} \def\pfd{{\widetilde{f_d}}} \def\pfc{{\widetilde{f_c}}} \def\pdy{{\widetilde{dy}}} \def\pfp{{\widetilde{f_p}}} \def\V{\mathbb V} \def\L{{\cal L}} %The Lagrangian \def\F{{\cal F}} %The feasible region \def\Z{{\cal Z}} \def\X{{\cal X}} \def\I{{\cal I}} \def\P{{\cal P}} \def\RE{\mathbb R} \def\Mmn {\RE^{m\times n}} \def\SE {\mathbb S} \def\Snp {\SE^n_+} \def\Snpp {\SE^n_{++}} \newcommand{\pD}[3]{[{\cal D}_#2#1(#3)]} \newcommand{\Di}[3]{[{\cal D}^#2#1(#3)]} \newcommand{\Mn}{{\cal M}^n } \newcommand{\Sn}{{\cal S}^n } \newcommand{\hn}{{\cal H}^n } \newcommand{\p}{{\cal P} } \newcommand{\g}{{\cal G} } \newcommand{\kvec}{{\rm vec\,}} \newcommand{\adj}{{\rm adj\,}} \newcommand{\intr}{{\rm int\,}} \newcommand{\trace}{{\rm trace\,}} \newcommand{\relint}{{\rm relint\,}} \newcommand{\rank}{{\rm rank\,}} \newcommand{\cone}{{\rm cone\,}} \newcommand{\tr}{{\rm trace\,}} \newcommand{\diag}{{\rm diag\,}} \newcommand{\Diag}{{\rm Diag\,}} \newcommand{\Se}{{\mathcal S}_e } \newcommand{\Sd}{{\mathcal S}_d } \newcommand{\Sc}{{\mathcal S}_C } \newcommand{\Sh}{{\mathcal S}_H } \newcommand{\snn}{{\mathcal S}_{n-1} } \newcommand{\GG}{{\mathcal G} } \newcommand{\KK}{{\mathcal K} } \newcommand{\LL}{{\mathcal L} } \newcommand{\DD}{{\mathcal D} } \newcommand{\BB}{{\mathcal B} } \newcommand{\PP}{{\mathcal P} } \newcommand{\TT}{{\mathcal T} } \newcommand{\FF}{{\mathcal F} } \newcommand{\HH}{{\mathcal H} } \newcommand{\EE}{{\mathcal E} } \newcommand{\NN}{{\mathcal N} } \newcommand{\RRc}{{\mathcal R} } \newcommand{\UU}{{\mathcal U} } \newcommand\T{{\mathcal T}} \newcommand{\bt}{ \begin{tabular} } \newcommand{\et}{ \end{tabular} } \newcommand\A{{\mathcal A}} \newcommand\E{{\mathcal E}} \newcommand{\bpr}{{\bf Proof.} \hspace{1 em}} \newcounter{count} %\newcommand{\beq}{\begin{equation}} %\newcommand{\eeq}{\end{equation}} %\newcommand{\epr}{\\ \hspace*{4.5in} $\Box$} \renewcommand{\theequation}{\thesection.\thecount} %\newcommand{\beq}{\begin{equation}} \newcommand{\beq}{\addtocounter{count}{1} \begin{equation}} \newcommand{\bet}{\addtocounter{count}{1} \begin{table}} \newcommand{\eeq}{\end{equation}} %\newcommand{\beqr}{\begin{eqnarray}} \newcommand{\beqr}{\addtocounter{count}{1} \begin{eqnarray}} \newcommand{\addc}{\addtocounter{count}{1} } \newcommand{\bs}{\setcounter{count}{0} \section} %\newcommand{\bs}{\section} \newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~} \newcommand{\epr}{\QED} \newcommand{\arrow}{{\rm arrow\,}} \newcommand{\Arrow}{{\rm Arrow\,}} \newcommand{\trian}{{\rm trian\,}} \newcommand{\Trian}{{\rm Trian\,}} \newcommand{\BoDiag}{{\rm B^0Diag\,}} \newcommand{\OoDiag}{{\rm O^0Diag\,}} \newcommand{\bodiag}{{\rm b^0diag\,}} \newcommand{\oodiag}{{\rm o^0diag\,}} \begin{document} \bibliographystyle{plain} \title{ \begin{figure} \psfig{file=UWlogori.ps,height=10mm} \end{figure} Introduction to Semidefinite Programming: Motivation and Duality} \author{ %\href{http://orion.math.uwaterloo.ca/~hwolkowi} {Henry Wolkowicz}\thanks{ Department of Combinatorics \& Optimization, University of Waterloo } } \maketitle %\tableofcontents \newpage \begin{slide}{} {Outline} \begin{enumerate} \item[$\bullet$] Basic Properties and Notation \item[$\bullet$] Examples \item[$\bullet$] Duality \end{enumerate} \end{slide} \begin{slide}{} \bs{Basic Properties and Notation} \label{sect:basicpropnot} Basic linear {\bf Semidefinite Programming} looks just like Linear Programming \[ {\bf (PSDP)} \begin{array}{cccc} p^*= & \max &\tr CX & (\left< C,X \right>) \\ & \mbox{s.t.} & {\cal A}X = b & \mbox{(linear)}\\ && X \succeq 0,~~(X \in \p)& \mbox{(nonneg)} \end{array} \] \[ {\cal A}(\alpha X_1+\beta X_2)= \alpha {\cal A}(X_1)+ \beta {\cal A}(X_2), \quad \forall X_i, \mbox{ and scalars } \alpha, \beta \] \end{slide} \begin{slide}{} ${\cal S}^n$ := space of $n \times n$ real symmetric matrices,~~($A=A^T$) (Hermitian?) $\preceq$ denotes the L{\"{o}}wner partial order\\ $A\preceq B$ if $B-A \succeq 0$ (positive semidefinite)\\ \hrulefill For $A \in {\cal S}^n$:\\ A is positive semidefinite (positive definite), ({\tiny{denoted $A \succeq 0$ ($A \succ 0$),}})\\ if $x^TAx \geq 0 (>0), ~\forall x\neq 0$. \hrulefill For $M, n \times n$, $Mx=\lambda x$ (eigenvector-eigenvalue equation, simplest linear operation is multiplication by scalar), equivalently, $\det (M-\lambda I)=0$. \end{slide} \begin{slide}{} TFAE: \begin{enumerate} \item $A \succeq 0 \quad (A \succ 0)$ \item the eigenvalues $\lambda(A) \geq 0 \quad (\lambda(A) > 0)$ \item $A = R^TR$, for some $R$ (Cholesky factorization if $R$ is upper triangular - Gram matrix representation of $n$ columns of $R$, $a_{ij}=u_i^Tu_j$, $R$ nonsingular if $A \succ 0$) \item $A= \sum_i \alpha_i v_iv_i^T$ for some nonnegative $\alpha_i$ (sum of rank ones, $A \succ 0$??) \item all principal minors (determinants of principal submatrices) are nonnegative (positive for $A \succ 0$, leading princ. minors??) ( principal submatrix: delete some rows and corresp. cols.; history-Sylvester?) \item $S=(S^{\frac 12})^2$, for some $S^{\frac 12} \succeq 0 \quad (\succ 0)$ \end{enumerate} \end{slide} \begin{slide}{} For a general square matrix $M, n \times n$, define\\ $\trace M= \sum_i M_{ii}$ Then \[\trace M= \sum_i \lambda_{i} \quad \mbox{(trace is sum of eigenvalues)} \] \end{slide} \begin{slide}{} \begin{thm} (Interlacing/Majorization Eigenvalues, Fan, 1954) Let $H,\bar{H}$ be an $n \times n$ Hermitian matrices of the form \[ H=\pmatrix{ H_{11}&H_{12}\cr H_{21}&H_{22} }, \qquad \bar{H}=\pmatrix{ H_{11}&0\cr 0 &H_{22} }, \] with $H_{11}$ size $l \times l$. Then \[ (\lambda (H_{11}) ,\lambda (H_{22})) =\lambda (\bar{H}) \prec_M \lambda (H), \quad \mbox{on } \Re^n, \] where $\prec_M$ denotes majorization, i.e. $\lambda \prec_M \mu$ \underline{if} $\sum_{i=1}^k \lambda_{[i]} \leq \sum_{i=1}^k \mu_{[i]} $, with equality for $k=n$. ([.] denotes nonincreasing order). In particular, $\lambda_j(H) \geq \lambda_j(H_{11}), \quad \lambda_{n-j+1}(H) \leq \lambda_{l-j+1}(H_{11})$. \epr \end{thm} \end{slide} \begin{slide}{} \subsubsection{Further Properties and Definitions} \label{sect:furthpropdefs} \begin{enumerate} \item[$\bullet$] For matrices $P,Q$ compatible for multiplication, \[ \trace PQ = \trace QP. \] \item[$\bullet$] Every symmetric matrix $S$ has an orthogonal decomposition $S=Q\Lambda Q^T$, where $\Lambda$ is diagonal with the eigenvalues of $S$ on the diagonal, and $Q$ has orthonormal columns consisting of eigenvectors of $S$. \item[$\bullet$] $X \succeq 0 \Rightarrow P^TXP \succeq 0 \quad \mbox{(congruence)}$ \end{enumerate} \end{slide} \begin{slide}{} Further properties of $A \succeq 0$:\\ $\bullet$ $A= \sum^r_{i=1} \alpha_i v_iv_i^T$ for minimum number of nonnegative $\alpha_i$ characterizes $\rank A$;\\ $\bullet$ $\diag(A) \geq 0$; and $a_{ii}=0$ implies i-th and i-th col are 0;\\ $\bullet$ $\trace A \geq 0$ and $\trace A = 0$ iff $A=0$;\\ $\bullet$ $\p \subset \Sn$ is a closed convex cone, i.e. $\p \subset \p + \p; \alpha \p \subset \p, \forall \alpha \geq 0$; $\bullet$ $A,B \succeq 0$ implies $\trace AB \geq 0$ with equality iff $AB=0$ (proof?). $\bullet$ geometry of $\p$ in $\Sn$ equipped with $\trace$ inner product: all vectors within 45 degrees of identity matrix;\\ $\bullet$ $\p$ is a {\em self-polar} cone (proof??), $\p = \p^*$, where \[ C^* = \left\{ \phi \in \Re^n : \left<\phi,x\right> \geq 0, \forall x \in C \right\}. \] \end{slide} \begin{slide}{} \begin{lem} {\bf (Schur Complement)} Let $A= \pmatrix{ B & C^T \cr C & D }$ be a symmetric matrix with the block $B\succ 0$. Then \[ A \succ 0 ~ (\succeq 0) \mbox{ iff } D-CB^{-1}C^T \succ 0 ~ (\succeq 0). \] \end{lem} \end{slide} \begin{slide}{} \begin{thm} (Perron-Frobenius) If an $n \times n$ matrix has nonnegative entries then it has a nonegative real eigenvalue $\lambda$ which has maximum absolute value among all eigenvalues. This eigenvalue $\lambda$ has a nonnegative real eigenvector. If, in addition, the matrix has no block-triangular decomposition (is irreducible - does not contain a $k \times (n-k)$ block of 0-s disjoint from the diagonal), then $\lambda$ has multiplicity 1 and the corresponding eigenvector is positive. \epr \end{thm} \end{slide} \begin{slide}{} The linear operator ${\cal A}$ and its adjoint: \[ {\cal A} :{\cal S}^n \rightarrow \Rm, \qquad {\cal A}^* : \Rm \rightarrow {\cal S}^n \] \[ \begin{array}{c} \mbox{for given}~ A_i \in {\cal S}^n, i=1,\ldots m:\\ ({\cal A}X)_i =\tr (A_iX), \quad {\cal A}^*y= \sum_{i=1}^m y_iA_i \end{array} \] where \[ \left<{\cal A}X,y\right>=\left, \quad \forall X,y \] $\p$ - cone of positive semidefinite matrices\\ replaces\\ $\Rn_+$ - nonnegative orthant \end{slide} \begin{slide}{} $\trace CX = \left=\sum_{i=1}^n \sum_{j=1}^n C_{ij} X_{ij}$ SDP is equivalent to: \[ {\bf (PSDP)} \begin{array}{cccc} p^*= & \max & \sum_{i=1}^n \sum_{j=1}^n C_{ij} X_{ij}&\\ & \mbox{s.t.} & \left=b_i, & i=1,\ldots m \\ && X \succeq 0,~~(X \in \p) \end{array} \] \end{slide} \begin{slide}{} \subsubsection{Duality (like LP)} \label{sect:duality} payoff function, player $Y$ to player $X$ (Lagrangian) \[ L(X,y) := \tr (CX) +y^T(b-{\cal A}X) \] Optimal (worst case) strategy for player $X$: \[p^* = \max_{X \succeq 0 } \min_{y } L(X,y) \] Using the {\em hidden constraint} $b-{\cal A}X=0$, recovers primal problem (PSDP). \end{slide} \begin{slide}{} \[ \begin{array}{rcl} L(X,y) &=& \tr (CX) +y^T(b-{\cal A}X)\\ &=& b^Ty + \tr \left(C -{\cal A}^*y \right) X \end{array} \] ~\\ ~\\ adjoint operator,~~ ${\cal A}^*y= \sum_i y_i A_i $ \[ \left<{\cal A}^*y,X \right>= \left, ~~~ \forall X,y \] \[p^* = \max_{X \succeq 0 } \min_{y } L(X,y) \leq d^*:=\min_y \max_{X \succeq 0} L(X,y) \] For dual, use {\em hidden constraint} $g(y) := C-{\cal A}^*y \preceq 0$ \end{slide} \begin{slide}{} \[p^* = \max_{X \succeq 0 } \min_{y } L(X,y) \leq d^*:=\min_y \max_{X \succeq 0} L(X,y) \] dual obtained from optimal strategy of competing player Y;\\ use {\em hidden constraint} $g(y) = C-{\cal A}^*y \preceq 0$ \[ {\bf (DSDP)} \qquad \begin{array}{ccc} d^*=& \min &b^Ty \\ & \mbox{s.t.} & {\cal A}^*y \succeq C \\ \end{array} \] for the primal \[ {\bf (PSDP)} \qquad \begin{array}{ccc} p^*= & \max &\tr CX \\ & \mbox{s.t.} & {\cal A}X = b\\ && X \succeq 0 \end{array} \] \end{slide} \begin{slide}{} \subsubsection{Weak Duality - Optimality} \label{sect:weakduality} \begin{prop} (Weak Duality) If $X$ feas. in (PSDP), $y$ feas. in (DSDP), $Z=C-{\cal A}^*y \succeq 0$ is slack variable, then \[ \mbox{duality gap } := b^Ty-\tr CX = \trace XZ \geq 0. \] \end{prop} \bpr (Direct - using $\trace ZX = \tr X^{1/2} X^{1/2}Z = \tr X^{1/2} Z X^{1/2} \geq 0$) \begin{eqnarray*} \tr CX - b^Ty &=&\tr ({\cal A}^*y-Z)X - b^Ty\\ &=&\tr y^T{\cal A}X- \trace ZX - b^Ty\\ &=&\tr y^T\left({\cal A}X-b\right) -\trace ZX =-\trace ZX, \end{eqnarray*} \epr \end{slide} \begin{slide}{} Characterization of optimality \\ (in the case of a zero duality gap at optimality and attainment)\\ for the dual pair $X,y$~~(slack $Z\succeq 0$) \[ \begin{array}{cc} {\cal A}^*y -Z = C & \mbox{dual feasibility}\\ AX = b & \mbox{primal feasibility}\\ ZX = 0 & \mbox{complementary slackness (equiv. } \trace ZX=0) \end{array} \] \[ ZX = \mu I ~~~~~ \mbox{perturbed} \] Forms the basis for:\\ ~~\\ interior point methods\\ (primal simplex method, dual simplex method) \end{slide} \begin{slide}{} \subsubsection{Preliminary Examples} \label{sect:prelexamples} \begin{exam} {\bf Minimizing the Maximum Eigenvalue} Arises in e.g. stability of differential equations \begin{enumerate} \item[$\bullet$] The mathematical problem: \begin{enumerate} \item[$\diamond$] given $A(x)$ depending linearly on vector $x$ \item[$\diamond$] Find $x$ to minimize the maximum eigenvalue of $A(x)$ \end{enumerate} \item[$\bullet$] SDP Model: \begin{enumerate} \item[$\diamond$] the largest eigenvalue $\lambda_{\max}(A(x)) \leq \alpha \qquad$ \underline{iff} $\lambda_{\max}(A(x)-\alpha I) \leq 0 \qquad$ \underline{iff} $ \qquad A(x)-\alpha I \preceq 0$. \item[$\diamond$] The DSDP (in dual form) is: \[ \max -\alpha \qquad \mbox{s.t.} \quad A(x)- \alpha I \preceq 0. \] \end{enumerate} \end{enumerate} \end{exam} \end{slide} \begin{slide}{} {\bf HOW DOES SDP arise from quadratic approximations?} \[\mbox{Let} \quad q_i(y)=\frac 12 y^TQ_iy+y^Tb_i + c_i,~y\in \Rn \] \[ {\bf (QQP)} \qquad \left\{ \begin{array}{ccc} q^*= & \min &q_0(y) \\ & \mbox{s.t.} & q_i(y)=0\\ && i=1,\ldots m \end{array} \right. \] $\bullet$ Lagrangian (quadratic, linear, constant in $y$ terms): \[ 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) \] \[\mbox{$\bullet$ Primal-Dual pair:} \quad q^*=\min_y \max_x L(y,x) \geq d^* = \max_x \min_y L(y,x) \] \[ \mbox{$\bullet$ homogenize (add $y_0$): } \quad 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} \] {\em hidden semidefinite constraint} yields SDP constraint \[ (\A: \RR^{m+1} \rightarrow {\cal S}_{n+1})\qquad B-\A \left( \begin{array}{c} t \\ x \end{array} \right) \succeq 0. \] \[ B=\left( \begin{array}{cc} 0 & b_0^T \\ b_0 &Q_0 \end{array} \right), \quad \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] \] \end{slide} \begin{slide}{} The dual program is equivalent to the SDP (with $c_0=0$) \[ {\bf (D)} \qquad \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 \Rm, t \in \RR \end{array} \] As in linear programming, the dual is obtained from the optimal strategy of the competing player: \[ {\bf (DD)} \qquad \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}{} \begin{exam} {\bf Pseudoconvex (Nonlinear) Optimization Problem} \[ {\bf (PCP)} \qquad \begin{array}{ccc} d^*=& \min &\frac {(c^Tx)^2}{d^Tx} \\ & \mbox{s.t.} & A x +b \geq 0, \end{array} \] (where $Ax+b \geq 0 \Rightarrow d^T x > 0$) is equivalent to \[ \begin{array}{ccc} d^*=& \min & t \\ & \mbox{s.t.} & \left[ \begin{array}{ccc} \Diag(A x +b) & 0 & 0 \\ 0 & t & c^Tx \\ 0 & c^T x & d^T x \end{array} \right] \succeq 0 \end{array} \] \end{exam} \end{slide} \begin{slide}{} $\bullet$ {\bf \em Alternate Name - Linear Matrix Inequality} \[\qquad g(y) = C-{\cal A}^*y \preceq 0\] adjoint operator $\qquad {\cal A}^*y= \sum_i y_i A_i, \quad A_i=A_i^T $ ~~\\ $\bullet$ $g(y)$ is a {\bf convex constraint}, i.e. \[ g(\lambda x + (1-\lambda)y) \preceq \lambda g(x) + (1-\lambda)g(y), \quad \forall 0 \leq \lambda \leq 1, \forall x,y \in \Rm \] equivalently, for every $P \succeq 0$, the real valued function $f_P(x) := \trace Pg(x)$ is a convex function, i.e. \[ f_P(\lambda x + (1-\lambda)y) \leq \lambda f_P(x) + (1-\lambda)f_P(y), \quad \forall 0 \leq \lambda \leq 1, \forall x,y \in \Rm \] \end{slide} \begin{slide}{} $\bullet$ {\em feasible set} $\left\{ x \in \Rm : g(x) \preceq 0 \right\}$ is convex set $\bullet$ {\em optimum point} is on the boundary ($g(x)$ is singular) $\bullet$ {\em boundary of feasible set} is {\em not} smooth (piecewise smooth, algebraic surface) \begin{figure}[h] \centering\psfig{file=laurpol.ps,height=50mm} \end{figure} \end{slide} \begin{slide}{} \subsection{Introduction to Convex Cones and the L\"owner Partial Order} \label{sect:introCC} \begin{definition} Let $\alpha \in \RR$ and $S,T \subset \Rn$. Then $\alpha S = \{y:y=\alpha s, \mbox{ for some } s \in S\}$ and $S+T = \{y:y=s+t, \mbox{ for some } s \in S, t \in T\}$ \end{definition} \begin{definition} $\KK \subset \mathbb{R}^n$ is a \underline{cone} if $\alpha \KK \subset K, \quad \forall \alpha > 0$. \end{definition} \begin{definition} the cone $\KK$ is a \underline{convex cone} if $\KK + \KK \subset \KK$. \end{definition} \begin{definition} A cone $\KK$ is a \underline{pointed cone} if $\KK \cap (-\KK)=\{ 0 \}$. \end{definition} \begin{definition} A cone $\KK \subset \mathbb{R}^n$ is a \underline{proper cone} if it is closed, pointed, and convex and has nonempty interior. \end{definition} \end{slide} \begin{slide}{} {\bf Examples of Cones} \begin{exam} \underline{open half line:} $\{x\in\mathbb{R}: x > 0 \}$. \end{exam} \begin{exam} \underline{closed half line:} $\{x\in\mathbb{R}: x\geq 0 \}$. \end{exam} \begin{exam} \underline{psd matrices, $\p$:} $\{X\in \Sn: X\succeq 0 \}$. \end{exam} \begin{exam} \underline{Lorentz cone}\\ (ice-cream cone, second-order cone):\\ $L^m =\{ x=(x_1,\ldots,x_m)\in \Rm: x_m \geq \sqrt{x_1^2+ \ldots +x_m^2}$. \end{exam} \end{slide} \begin{slide}{} And, an important closed convex cone is: \begin{definition} \underline{Polar (dual, conjugate)} of set ${\mathcal S}$: ${\mathcal S}^+ := \{ z: \left< x, z\right> \geq 0, \forall x\in {\mathcal S} \} \quad (=S^*)$. \end{definition} \begin{exam} nonnegative orthant, psd cone $\p$, and Lorentz cone $L^m$, are all self-polar, i.e. $\KK = \KK^+$. \end{exam} \end{slide} \begin{slide}{} \begin{definition} \underline{Direct sum of two cones} $\KK \oplus \LL := \{ (k~ l) : k \in \KK, l \in \LL \}$. \end{definition} \begin{exam} Let $L$ denote the half line in $\RR$, then $\underbrace{L\oplus L \cdots \oplus L}_n$ is the $n$-dimension nonnegative orthant. \end{exam} \end{slide} \begin{slide}{} Suppose $\KK$, $\KK_1$, $\KK_2$ are proper cones, then: \begin{itemize} \item $\KK^+$ is proper. \item \( (\KK^+)^+=\KK \) . \item \( (\KK_1 \cap \KK_2)^+=\overline{\KK_1^++\KK_2^+} \). \item \( (\KK_1+\KK_2)^+=\KK_1^+\cap \KK_2^+ \). \item \( \KK_1\oplus \KK_2 \) is proper. \item \( ({\mathcal K}_1\oplus {\mathcal K}_2)^+ ={\mathcal K}_1^+ \oplus {\mathcal K}_2^+ \). \end{itemize} Useful Lemma, e.g. to Prove Farkas' Lemma \begin{lem} \[ \KK \mbox{ is a closed convex cone } \iff \KK = \KK^{++}. \] \end{lem} \end{slide} \begin{slide}{} Partial Orders: \begin{definition} ${ x{\succeq}_{\mathcal K} y} \mbox{ (respectively }{ x\succ_{\mathcal K} y)}$ if $ x- y \in \KK \mbox{ (respectively }x- y \in \intr \KK)$. \end{definition} \begin{remark} If $\KK$ is a pointed, convex cone, then ``$\succeq_\KK$'' is a \underline{(linear) partial order} ( reflexive, transitive, and antisymmetric): \begin{itemize} \item $0 \in {\mathcal K}$ $\Rightarrow x\succeq_{\mathcal K} x$ (reflexive); \item ${\mathcal K}$ is convex $\Rightarrow \mbox{if } x\succeq_{\mathcal K} y \mbox{ and } y\succeq_{\mathcal K} z, \mbox{ then } x\succeq_{\mathcal K} z$ (transitive); \item ${\mathcal K}$ is pointed $\Rightarrow \mbox{if } x\succeq_{\mathcal K} y \mbox{ and } y\succeq_{\mathcal K} x, \mbox{ then } x= y$ (antisymmetric); \item {${\mathcal K}$ is convex cone $\Rightarrow$} $\mbox{if } a,b \geq 0, u\succeq_{\mathcal K} x \mbox{ and } v\succeq_{\mathcal K} y, \mbox{ then } au+bv \succeq_{\mathcal K} ax+by$ (linear - homogeneous, additive); \end{itemize} \end{remark} \end{slide} \begin{slide}{} \subsection{Convex Cone Program} \label{sect:ccp} Let: $\KK,\LL$ be convex cones;\\ $f$ real valued convex function, $g$ is $\KK$-convex, i.e. $g(\alpha u + (1-\alpha) v) \preceq_\KK \alpha g(u) + (1-\alpha) g(v), \forall 0\leq \alpha \leq 1, \forall u,v$ \[ (CP)\qquad \begin{array}{cc} \mu^*=\min & f(x) \\ {\mbox{s.t.}} & g(x) \preceq_\KK 0\\ & x \succeq_\LL 0 \end{array} \] with Lagrangian dual (weak duality) \[ (DCP)\qquad \begin{array}{cc} \mu^* \geq \nu^*=\max\limits_{y \in \KK^+} \min\limits_{x \in \LL} & f(x) +\left \end{array} \] \end{slide} \begin{slide}{} \begin{exam} If $f(x)=\left, g(x)=b-{\mathcal A} x$, then we have a linear cone programming problem, (LCP). The dual \[ (DLCP)\qquad \begin{array}{rclc} \mu^* \geq \nu^*&=&\max\limits_{y \in \KK^+} \min\limits_{x \in \LL} & \left +\left \\ &=&\max\limits_{y \in \KK^+} \min\limits_{x \in \LL} & \left +\left \\ &=&\max\limits_{\stackrel{y \in \KK^+}{c-{\mathcal A}^*y \in \LL^+}} \min\limits_{x \in \LL} & \left +\left \\ \end{array} \] reduces to the elegant (LP or SDP type) form \[ (DLCP)\qquad \begin{array}{cc} \mu^* \geq \nu^*=\max & \left \\ \mbox{s.t.} & {\mathcal A}^*y \preceq_{\LL^+} c\\ & y \succeq_{\KK^+} 0 \end{array} \] \end{exam} \end{slide} \begin{slide}{} \[ (LCP)\qquad \begin{array}{cc} \mu^*=\min & \left \\ {\mbox{s.t.}} & {\cal A}x \succeq_\KK b\\ & x \succeq_\LL 0 \end{array} \] \[ (DLCP)\qquad \begin{array}{cc} \mu^* \geq \nu^*=\max & \left \\ \mbox{s.t.} & {\mathcal A}^*y \preceq_{\LL^+} c\\ & y \succeq_{\KK^+} 0 \end{array} \] \begin{thm} Suppose that Slater's CQ holds for (LCP), i.e. $\exists \hat{x}$ such that $ {\cal A}\hat{x} \succ_\KK b,\quad \hat{x} \succ_\LL 0$. Then {\em strong duality} holds for (LCP),(DLCP), i.e. there exists $y^*$ feasible for (DLCP) such that \[\mu^*=\nu^*=\left.\] \end{thm} \end{slide} \begin{slide}{} \begin{exam} If the primal is \[ {\bf (P)} \begin{array}{ccc} p^*= & \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\} \quad \mbox{(minimal cone containing feasible set)} $ \newpage 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 (below) has $ U \succeq_{(S^f)^+} 0,$ i.e. only constraint is $U_{11} \geq 0.$ So new dual optimal value is 0. (Attained.) ) \end{exam} \end{slide} \begin{slide}{} \subsection{Optimality Conditions without constraint qualifications} \subsubsection{Facial Structure} \begin{definition} $\FF$ is a {\em face} of a convex cone $\KK$ (denoted $\FF \lhd \KK$) if $\FF \subset \KK$ and \[ \frac 12 (x_1 + x_2) \in \FF \Rightarrow x_1,x_2 \in \FF, \qquad \forall x_1,x_2 \in \KK \] \end{definition} \begin{definition} A face $\FF \lhd \KK$ is called {\em exposed} if \[ \FF = \KK \cap \phi^{\perp}, \qquad \mbox{for some } \phi \in \KK^+ \] \end{definition} \begin{definition} A face $\FF \lhd \p$ is called {\em projectionally exposed} if \[ \FF = Q \p Q^t \qquad \mbox{for some matrix } Q \] \end{definition} \end{slide} \begin{slide}{} \subsubsection{Weak Duality} The weak duality: $ c^T x \geq b^T y$ holds in Cone-LP: \[ c^T x -b^T y = c^T x-(A x)^T y = x^T ( c-A^T y)= x^T s \geq 0 \] \subsubsection{Extended Farkas' Lemma} \begin{thm} \textbf{(Seperation Theorem)} If $K \subseteq \mathbb{R}^n$ is closed and convex, $b \in \mathbb{R}^n$, $b \not\in K$, then $\exists a \in \mathbb{R}^n$, such that $\forall x \in K: a^T b<0$ and $ a^T x\geq0$ . \end{thm} \begin{lem} \label{eq:farkaslem} \textbf{(Farkas' Lemma) }Let $\KK \subseteq \mathbb{R}^n$ be a closed, convex cone, $A \in \mathbb{R}^{m \times n}, A({\mathcal K})$ closed, and $b \in \mathbb{R}^m $. Then: \[ \left\{\exists x \succeq_{\mathcal K} 0 : A x=b \right\} \iff \left\{ A^T y \succeq_{{\mathcal K}^+} 0 \Rightarrow b^T y \geq 0 \right\}. \] \end{lem} \end{slide} \begin{slide}{} \bpr (Necessity:) Suppose $\exists x \in {\mathcal K} : A x=b$. And suppose $A^T y \succeq_{{\mathcal K}^+ } 0$. Then $b^T y=(A x)^T y= x^T(A^T y)\geq 0$, since $x \succeq_K 0$. (Sufficiency:) Suppose that the RHS of (\ref{eq:farkaslem}) holds but the LHS fails, i.e. $b \not\in A({\mathcal K})$. Then separate, i.e. $\exists y \in \mathbb{R}_m$ such that $b^T y < 0$, and $\forall x \in {\mathcal K}, (A x)^Ty \geq 0$. Therefore, $A^Ty \in K^+$ which implies $b^Ty \geq 0$, contradiction. \epr \end{slide} \begin{slide}{} Cone programming: $S$ a closed convex cone induces a linear partial order (\cite{bw2}) \[ \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, $\KK,\LL$ closed convex cones (\cite{w11}): primal: \[ \mu^*= \min \{cx : \A x \succeq_\KK 0, ~ x \succeq_\LL 0 \} \] minimal cones $\KK^f, \LL^f$ dual: \[ \mu^*= \nu^*= \max \{by : \A^*y \preceq_{(\LL^f)^+} b, ~ y \succeq_{(\KK^f)^+} 0 \} \] \end{slide} \begin{slide}{} Linear Programming ($\A:\Rm \rightarrow \Rn$) $\Rn_+$ is a closed convex cone \[ {\bf (P)} \begin{array}{cccc} p^*= & \mbox{sup} &c^Tx \\ & \mbox{s.t.} & \A x \preceq b&(b-\A x \in \Rn_+)\\ && x \in \Rm \end{array} \] Lagrangian (payoff function):\\ $L(x,U)=c^Tx+\left< U,b-\A x \right>$ \[p^*=\max_x \min_{U \succeq 0} L(x,U) \] (the constraint $U \succeq 0$ is needed to recover\\ the hidden constraint $\A x \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.} & \A x \preceq b\\ && x \in \Rm \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 \Rm \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-\A x^0)\right>=0. \] if and only if \[ U^0 \circ (b-\A x^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} \A x \preceq b & \mbox{primal feasibility}\\ ~\\ \A^*U = c & \mbox{dual feasibility}\\ ~\\ U \circ (\A x -b) = 0e & \mbox{complementary slackness} \end{array} \] \[ U \circ (\A x -b) = \mu e ~~~~~ \mbox{perturbed} \] Forms the basis for:\\ ~~\\ primal simplex method\\ dual simplex method\\ interior point methods \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}{} \begin{center} {\bf Facial Structure for $\p$} \end{center} the cone $T \subset \KK$ is a {\em face} of the cone $\KK$, denoted $T \lhd \KK$, if \[ x,y \in \KK,~ x+y \in T \Rightarrow x,y \in T. \] Each face, $\KK \lhd \p$, is characterized by a subspace, $S \subset \Rn.$ \[ \KK = \{ X \in \p : \NN (X) \supset S \}. \] \[ \relint \KK = \{ X \in \p : \NN (X) = S \}. \] The complementary face of $\KK$ is $\KK^c = \KK^{\perp} \cap \p$ \[ \KK^c = \{ X \in \p : \NN (X) \supset S^{\perp} \}. \] \[ \relint \KK^c = \{ X \in \p : \NN (X) = S^{\perp} \}. \] \end{slide} \begin{slide}{} the face $\KK$ (respectively, $\KK^c$) is determined by the supporting hyperplane corresponding to any $X \in \relint \KK^c$ (respectively, $\relint \KK$); and \[XY=0, \quad \forall X \in \KK, \forall Y \in \KK^c \] \end{slide} \begin{slide}{} An SDP: \[ {\bf (P)} \begin{array}{ccc} p^*= & \mbox{max} &c^Tx \\ & \mbox{s.t.} & \A x \preceq_{\p} b \\ && x \in \Rm. \end{array} \] \[ \mbox{Optimality conditions:}\qquad 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} \] \[ \mbox{Optimality conditions:}\qquad 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.} & \A x \preceq_{\p^f} b \\ && x \in \Rm. \end{array} \] there exists $x$ such that $b-\A x \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 \KK \lhd \p.$ Then the system \[ \A^*U=0, U \succeq_{\KK^+} 0, \tr Ub=0 \] is consistent only if \[ \mbox{the minimal cone}~ \p^f \subset \{U\}^{\perp} \cap \KK. \] {\bf PROOF}\\ Since $\tr U(\A x-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 \KK \lhd \p$ (proper face). Then \[ \p^+ + \KK^{\perp} = cl(\p^+ + span~\KK^c) ~\mbox{is always closed}. \] But \[ \p^+ + span ~\KK~ \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 $U_1=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.} & \A x \preceq_{\p_1} b \\ && x \in \Rm. \end{array} \] We get: $\qquad p^*\leq d_1^* \leq d^*$ \[ {\bf (DRP_1)} \begin{array}{ccc} d_1^*=& \min &\tr bU \\ & \mbox{s.t.} & \A^*U = c \\ && U \succeq_{(\p_1)^+} 0. \end{array} \] \end{slide} \begin{slide}{} $(\p_1)^+=(\p \cap \p_1)^+ = \p + (\p_1)^{\perp}$ \[ {\bf (ELSD_1)} \qquad \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 $U_2=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.} & \A x \preceq_{\p_2} b \\ && x \in \Rm. \end{array} \] $p^*\leq d_2^*\leq d_1^* \leq d^*$ \[ {\bf (DRP_2)} \begin{array}{ccc} d_2^*=& \min &\tr bU \\ & \mbox{s.t.} & \A^*U = c \\ && U \succeq_{(\p_2)^+} 0. \end{array} \] $(\p_2)^+=(\p \cap \p_2)^+ = \p + (\p_2)^{\perp}$ \end{slide} \begin{slide}{} \[ {\bf (ELSD_2)} \qquad \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 optim. cond.) \[ {\bf (HP)} \qquad \begin{array}{cccc} 0=& \max &c^Tx+t(-p^*)\\ & \mbox{~subject to~} & \A x + t(-b) +Z = 0 \\ && w \in \KK=\Rm \otimes \RR_+ \otimes \p\\ \end{array} \] This defines the objective, constraints, and variables: \[ \begin{array}{cccc} (=\left< a,w \right> )\\ (\BB w =0)\\ \left(w= \left( \begin{array}{c} x\\t\\Z \end{array} \right)\right) \end{array} \] the feasible set is \[ F_H = \NN (\BB) \cap \KK, \quad (\BB w=0, w \in \KK ~\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 -( \NN (\BB) \cap \KK)^+. \] \[ \left( \begin{array}{c} -c\\p\\0 \end{array} \right) \in \overline{\RRc (\BB^*) + \KK^+}, \] 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-\KK)$ 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 $\KK$ to attain the closure since \[ (\NN (\A) \cap (\KK \cap C))^+ = \overline{\RRc (\A^*) + \KK^+ + C^+}. \] \end{slide} \begin{slide}{} \end{slide} \begin{slide}{} \subsection{Logarithmic Barrier Function and the Central Path} \label{sect:logbarrier} References:\\ $\bullet$Fiacco and McCormick \cite{MR91d:90089} 1968, barrier techniques (SUMT)\\ $\bullet$Nesterov and Nemirovskii \cite{int:Nesterov5} 1990, self-concordant barriers\\ $\bullet$ $\log\det(X)$ is a strictly concave barrier on pos def cone (e.g. Bellman 1960, \cite{Bell:60}) ~~\\ family of strictly convex primal-dual (e.g. \cite{Le:94}) pairs, parameterized by the scalar $\mu>0$, \begin{eqnarray*} \min \left\{\trace CX-\mu\log\det(X) : \A(X)=b,X\succ 0 \right\},\\ \max \left\{b y+\mu\log\det(Z) : \A^*(y)+Z=C,Z\succ 0\right\}. \end{eqnarray*} \end{slide} \begin{slide}{} \begin{eqnarray*} \infpgm{$(P_\mu)$}{\inner{C}{X}-\mu\log\det(X)}{\A(X)=b},\\ \suppgm{$(D_\mu)$}{\inner{b}{y}+\mu\log\det(Z)}{\A^*(y)+Z=C}. \end{eqnarray*} log-barrier pair parametrized by $\mu$\\ objective functions are strictly convex/concave\\ under Slater's (strict feasibility), there exists unique (positive definite) solutions $X_\mu, y_\mu, Z_\mu$ \end{slide} \begin{slide}{} Lagrangians: \begin{eqnarray*} \L_P(X,y) &:=& \inner{C}{X}-\mu\log\det(X) + \inner{y}{b-\A(X)},\\ \L_D(X,y,Z) &:=& \inner{b}{y}+\mu\log\det(Z) + \inner{X}{C-Z-\A^*(y)}. \end{eqnarray*} stationarity: \[ 0 = \nabla{\L_P}{(X,y)} = \pmatrix{ C - \mu X^{-1} - \A^*(y)\cr b-\A(X) } \] add $Z:=\mu X^{-1}$ \[ 0 = \nabla{\L_D}{(X,y,Z)} = \pmatrix{ C - Z - \A^*(y)\cr b-\A(X)\cr \mu Z^{-1} - X } \] \end{slide} \begin{slide}{} \[ \mbox{optimality conditions} \quad \left\{ \begin{array}{c} \begin{array}{rcl} \A^*(y)+Z &=& C,\\ \A(X) &=& b,\\ \end{array} \\ \begin{array}{|c|} \hline\\ \star \star \quad Z = \mu X^{-1}.\\ ~~\\ \hline \end{array} \end{array} \right. \] \end{slide} \begin{slide}{} For all $\mu > 0$, the set of unique solutions, denoted $(X_\mu,y_\mu,Z_\mu)$ is called the \textit{primal-dual central path}. Note complementarity: \begin{displaymath} \inner{Z_\mu}{X_\mu} = \inner{\mu X^{-1}_\mu}{X_\mu} = \mu n. \end{displaymath} \end{slide} \begin{slide}{} {\bf Central Path } \begin{center} %\begin{figure}[htbp] % \begin{center} % \epsfig{file=cp.eps,height=1.5in} \psfig{file=cp.eps,height=1.5in} % \caption{Central Path } % \label{fig:cp} % \end{center} %\end{figure} \end{center} \end{slide} \begin{slide}{} \subsubsection{Nonlinearity and Smoothing} \label{sec:nonlinearity} \[ Z - \mu X^{-1}=0 \quad \mbox{is highly nonlinear} \] Replace with (multiplication by $X$) \beq \label{optmu_cs_lin} ZX = \mu I. \eeq to reduce the nonlinearity of the system with the aim of accelerating Newton-like methods. \end{slide} \begin{slide}{} Consider Newton-like method to find $v^*$ such that $F(v^*)=0$. \\ (From e.g. \cite{DennSch:83} Theorems 5.2.1 and 10.2.1) radius ($r$) for quadratic convergence is bounded by a measure of \textit{relative nonlinearity} of $F$ \begin{displaymath} r \propto \frac{k}{\beta \gamma}. \end{displaymath} $k$ small constant that depends on method (Newton or Gauss-Newton), \begin{displaymath} \|{\F^{\prime}}{(v^*)}^{-1}\| \le \beta, \quad \mbox{(bound)} \end{displaymath} $\gamma$ is Lipschitz continuity constant for $\F^{\prime}{(v)}$ near $v^*$. Equivalently: (condition number of Jacobian inverse) \begin{displaymath} r \propto k \frac{\sigma_{\min} \F^{\prime}{(v^*)}}{\sigma_{\max} \F^{\prime}{(v^*)}}. \end{displaymath} \end{slide} \begin{slide}{} for $F(X,Z):=Z-\mu X^{-1}$: we have \begin{displaymath} \F^{\prime}{(X,Z)}(dX,dZ) = dZ + \mu X^{-1}dX X^{-1}. \end{displaymath} $\bullet$ optimal solution $X^*$ is almost always rank deficient\\ $\bullet$ condition number is arbitrarily large\\ $\bullet$ proven radius of quadratic convergence is exceedingly small {\bf BUT} for $F(X,Z)=ZX-\mu I$: \begin{displaymath} \F^{\prime}{(X,Z)}(dX,dZ) = ZdX + dZX, \end{displaymath} $\bullet$ $\sigma_{\max}$ can be bounded by $||Z|| + ||X||$\\ (Jacobian is full-rank from standard assumptions)\\ $\bullet$ we obtain a nonzero radius of quadratic convergence. \end{slide} \begin{slide}{} Summary - optimality conditions (look like for LP): \begin{eqnarray} \label{S_optmu} \A^*(y)+Z &=& C,\label{S_optmu_df}\\ \A(X) &=& b,\label{S_optmu_pf}\\ ZX &=& \mu I\label{S_optmu_cs}. \end{eqnarray} \end{slide} \begin{slide}{} \subsection{Differences with LP} \label{sect:diffLP} \begin{enumerate} \item Duality gaps can exist for SDP in the absence of strictly feasible solutions (Slater's constraint qualification, CQ). \item Strict complementarity can fail at the optimum. \item The perturbed optimality conditions involve nondiagonal matrices and map between different spaces\\ (overdetermined -does it require symmetrization?). \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{Duality Gaps} \begin{exam} If the primal is \[ {\bf (P)} \begin{array}{ccc} p^*= & \max &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} \] then the dual is \[ {\bf (D)} \begin{array}{ccc} d^*=& \min &\tr U_{11}\\ & \mbox{s. t.} & U_{22}=0,\quad U_{11}+2U_{23}=1 \\ && U \succeq 0. \end{array} \] Then $p^*=0 < d^*=1.$ \end{exam} \end{slide} \begin{slide}{} \subsubsection{Strict Complementarity} \begin{exam} If the primal is \[ {\bf (P)} \begin{array}{ccc} p^*= & \max &x_1 \\ & \mbox{s. t.} & \left[ \begin{array}{ccc} x_1 & x_3 & x_2\\ x_3 & x_2 & 0 \\ x_2 & 0 & x_3 \end{array} \right] \preceq \left[ \begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{array} \right] \end{array} \] then the dual is \[ {\bf (D)} \begin{array}{ccc} d^*=& \min &\tr U_{33}\\ & \mbox{s. t.} & U_{11}=1 \\ & & U_{22}+2U_{13}=0 \\ & & U_{33}+2U_{12}=0 \\ && U \succeq 0. \end{array} \] Then the (unique) optimum pair is:\\ \[U=\Diag(1,0,0), \quad x=[0,0,0], Z=\Diag(0,0,1) \] ~~\\ ~~\\ ~~\\ But: $U+Z$ is not positive definite \end{exam} \end{slide} \begin{slide}{} \subsubsection{Overdetermined System of Optimality Conditions} \begin{eqnarray*} \A^*(y)+Z &=& C,\\ \A(X) &=& b,\\ ZX &=& \mu I. \end{eqnarray*} unfortunate consequence:\\ residual ($ZX-\mu I$) is not symmetric unless $X$ and $Z$ commute\\ therefore Newton step impossible \end{slide} \begin{slide}{} due to success in linear programming codes,\\ {\bf current philosophy - symmetrize?? But - correct???} E.g. AHO direction: project onto subspace of symmetric matrices \begin{displaymath} H(M) := \frac{1}{2}[M+M^T]. \end{displaymath} \emph{Unscaled Symmetric System}, \[ \begin{array}{rclr} \A^*(dy)+dZ &=& -(\A^*(y_y)+Z_k-C) &=: -F_d,\\ \A(dX) &=& -(\A(X_k)-b) &=: -f_p,\\ H(Z_kdX + dZX_k) &=& -H(Z_kX_k-\mu I) &=: -H(F_c). \end{array} \] \end{slide} \begin{slide}{} Monteiro-Zhang family of directions \cite{MontZhang:96}:\\ scale the problem, nonsingular matrix $P$ \beq\label{P_scaling} X := P X P^T, \quad A_i := P^{-t}A_iP^{-1}, \quad C := P^{-t}CP^{-1}. \eeq \emph{scaled primal problem} \beq\label{eq:scaled_primal} \minpgms{\inner{ C}{ X}}{ \A( X) = b, X\succeq 0}, \eeq \emph{scaled dual problem} using $y := y, Z := P^{-t}ZP^{-1}$ \beq \label{eq:scaled_dual} \maxpgms{\inner{b}{ y}} { \A^* (y)+ Z = C, Z\succeq 0}. \eeq \end{slide} \begin{slide}{} symmetric direction for family of parameterized programs \[ \begin{array}{rclr} \A^*(dy)+ dZ &=& -( \A^*( y_k)+ Z_k- C) &=: - F_d,\\ \A(dX) &=& -( \A( X_k)-b) &=: - f_p,\\ H( Z_kdX + dZ X_k) &=& - H( Z_k X_k-\mu I) &=: -H( F_c), \end{array} \] where \[ \begin{array}{rclcl} F_d &=& \A^*( y_k)+ Z_k- C &=& P^{-t} F_d P^{-1},\\ f_p &=& \A( X_k)-b &=& f_p,\\ F_c &=& Z_k X_k-\mu I &=& P^{-t} F_c P^{-1}. \end{array} \] \end{slide} \begin{slide}{} \begin{table}[htbp] % \begin{center} \leavevmode \begin{tabular}{|c|c|c|}\hline $P$ & Direction & Solvers\\ \hline $I$ & AHO \cite{AlHaOv:94}& SDPPack,SDPA,SDPT3\\ $Z^\half$& HKM \cite{HeReVaWo:93,KoShHa:94,Mont:95}&CSDP,SDPA,SDPT3\\ $[X^\half(X^\half ZX^\half)^{-\half}X^\half]^\half$ & NT \cite{NesterovTodd:97} &SDPA,SDPT3,SeDuMi \\ \hline \end{tabular} \caption{Instances of Monteiro-Zhang scaling matrix $P$ of equation (\ref{P_scaling}).} \label{tab:directions} % \end{center} \end{table} \end{slide} \begin{slide}{} \begin{table}[htbp] \begin{center} \begin{tabular}{|c|l|}\hline CSDP & {http://www.nmt.edu/\verb+~+borchers}\\ SDPA & {http://www-neos.mcs.anl.gov/neos/solvers/SDP:SDPA}\\ SDPPACK & {http://cs.nyu.edu/cs/faculty/overton/sdppack/sdppack.html}\\ SDPT3 & http://www.math.cmu.edu/\verb+~+reha/sdpt3.html\\ SeDuMi & {http://www2.unimaas.nl/\verb+~+sturm/research.html}\\ \hline \end{tabular} \caption{Major Semidefinite Solvers} \label{tab:implementations} \end{center} \end{table} \label{endsect:theory} \end{slide} \begin{slide}{} \subsubsection{Historical Notes} \label{sect:histnotes1} $\bullet$ currently most active area in optimization (see HANDBOOK OF SEMIDEFINITE PROGRAMMING: Theory, Algorithms, and Applications, 2000, \cite{SaVaWo:97}, for comprehensive results, history, references, ...) $\bullet$ Lyapunov over 100 years ago on stability analysis of differential equations $\bullet$ Bohnenblust 1948 on geometry of the cone of SDPs, \cite{Bohnen:48} $\bullet$ Yakubovitch in the 1960's and Boyd and others on convex optimization in control in the 1980's, e.g. solving Ricatti Equations (called LMIs), e.g. \cite{BoB:91},\cite{VanBoy:94,VanBoy:94b} \end{slide} \begin{slide}{} $\bullet$ matrix completion problems (another name for SDP) started early 1980's, continues to be a very active area of research, \cite{DymGoh:81},\cite{GrJoSaWo:84}, surveys: \cite{joh:90,infieldsLaur:97} $\bullet$ combinatorial optimization applications 1980's: Lov\'{a}sz {\em theta function} \cite{Lo:79}, more recently the strong approximation results for the max-cut problem by Goemans-Williamson, e.g. \cite{Goemans}, survey papers: \cite{Goem:97,Goemans98},\cite{Rendl:97} $\bullet$ linear complementarity problems can be extended to problems over the cone of semidefinite matrices, e.g. \cite{MR96h:90117,MR1430560,KoShHa:94,KoShShi:95,MoTu:96}. \end{slide} \begin{slide}{} $\bullet$ {Complexity, Distance to Ill-Posedness, and Condition Numbers} SDP is a convex program and it can be solved to any desired accuracy in polynomial time, see seminal work of Nesterov and Nemirovski e.g. \cite{MR89k:90130,int:Nesterov4,int:Nesterov5,NeN:90,NeN:88,NeN:90b,NeN:91}. Another measure of complexity is the distance to ill-posedness: e.g. work by Renegar \cite{Renegar:92,MR97g:90134,MR96i:90029,MR96c:90048,MR95d:65116}. $\bullet$ {Cone Programming} this is a generalization of SDP, also called {\em generalized linear programming}, in paper by Bellman and Fan 1963, \cite{FanBell:63}. Other books deal with problems over cones date back to 60s, e.g. \cite{MR55:13315},\cite{Hol:75,Lu:69,Jame:70,Ja:86,MR37:3315}. More recently, generalization of SDP to more general cones, e.g. G{\" u}ler and Tuncel, \cite{GulerTuncel:98,TunXu:99} and also Hauser \cite{Hauser:99} \end{slide} \begin{slide}{} $\bullet$ Other Related Areas e.g.: Eigenvalue Functions, e.g. \cite{CuDoWo:75}, \cite{Ov:88,Ov:92}; {Financial Applications}; {Generalized Convexity}, e.g. \cite{MR83g:90075,MarOlk:79}; Statistics; Nonlinear Programming; ... \label{endsect:basicpropnot} \end{slide} \begin{slide}{} \subsection{Motivation/Examples/Applications} \label{sect:motexampappl} \begin{enumerate} \item[$\bullet$] Quadratic constrained quadratic programs \item[$\bullet$] Lov\'{a}sz theta function \item[$\bullet$] Statistics \item[$\bullet$] minimizing the $L_2$-operator norm of a matrix \item[$\bullet$] linear programming \item[$\bullet$] robust mathematical programming \item[$\bullet$] engineering, e.g. control theory \item[$\bullet$] Combinatorial Problems, e.g. the Max-Cut Problem \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{Quadratic Constrained Quadratic Programs} \label{sect:qqpintro} {What is SEMIDEFINITE PROGRAMMING?\\ Why use it?} $\bullet$ Quadratic approximations are better than linear approximations. \\ (For example, model $x \in \{0,1\}$ using $x^2-x=0$.)\\ And, we can solve relaxations of quadratic approximations efficiently using semidefinite programming. \end{slide} \begin{slide}{} \subsubsection{Quadratic Matrix Inequalities} \label{sect:quadmatrix} Let $X$ be $k \times l$ and $F(X)=(AXB)AXB)^T+CXD+(CXD)^T+E$. Then \[ \begin{array}{l} \left\{ (X,Y) : F(X) \preceq Y \right\}=\\ \qquad \left\{ (X,Y) : \pmatrix{ I & (AXB)^T \cr (AXB) & \left( Y - E -CXD- (CXD)^T\right)} \succeq 0 \right\} \end{array} \] (by Schur Complement Lemma) \end{slide} \begin{slide}{} \subsubsection{Nonnegative Polynomial Approximation} \label{sect:poynapprox} (e.g. \cite{nesterov97,GenHachNestvandooren:00}) best polynomial $p(t)$ approximation to a given function $f(t)$, where $p(t) \in \pols^+_{2k}(\RR)$, i.e. nonnegative, degree $\leq 2k$ $p(t)=\sum\limits_{i=0}^k p_it^i \equiv (p_0, p_1, \ldots p_{2k})^T$ Then \[ p \in \pols^+_{2k}(\RR) \quad \underline{\mbox{ iff }}\quad p(t)=e(t)^TXe(t), \mbox{ for some } X \succeq 0, \] where $e(t)=\left(1,t,t^2, \ldots, t^k \right)$ \end{slide} \begin{slide}{} \subsubsection{Lov\'{a}sz theta function, \cite{Lo:79}} \label{sect:lovtheta} Let $G=(V,E)$ be a {\bf \em simple undirected graph}\\ $~~~~~~~~~~~~~~~~~~$(node set $V$, edge set $E$) a {\bf \em clique} - is subgraph of $G$, $\exists$ edge between every pair of nodes {\bf \em number of colours} to colour clique $\geq$ size of the clique {\bf \em $\chi (G)$ - chromatic number}, least number of colours for $G$ {\bf \em size of maximum clique} $\omega (G)$ \[\omega (G) \leq \chi (G) \quad \mbox{two {\bf hard} to compute integers}\] {\bf \em strict inequality}, for example: $G$ simple circle with $\|V\|=5$, then: $2=\omega(G) < \chi(G)=3$. \end{slide} \begin{slide}{} Let $A=A(G)$ be {\bf \em adjacency matrix} of $G$:\\ i.e. $A_{ij}=1$ if $(i,j)\in E$ and 0 otherwise. The largest eigenvalue of $A$, $\lambda_{\max}(A) = \max\limits_{||x||=1} x^TAx$ is a convex function of its elements, $A_{ij}$. Fix $A_{ij}=1$ if $(i,j)\in E$, otherwise leave the elements free, i.e. define the \emph{Lov\'{a}sz theta number} \[\vartheta(G) := \min \left\{ \lambda_{\max}(X) : X=X^T, X_{ij}=1 \mbox{ if } (i,j)\in E \right\} \] \end{slide} \begin{slide}{} \begin{lem} \[ \mbox{size of max clique} \quad \omega(G)\leq\vartheta(G) \quad \mbox{Lov\'{a}sz theta number} \] \end{lem} \bpr Rename vertices of $G$, such that ${1,2,\ldots,k}$ is the maximum clique of $G$. This is a permutation of the rows/columns of the adjacency matrix $X$, so the eigenvalues of $X$ are unchanged. We get \[ X=\left( \begin{array} {cc} J_k & X_2 \\ X_3 & X_4 \end{array} \right ), \qquad J_k= E \in \mathbb{R}^{k \times k}. \] Therefore \[\lambda_{\max}(J_k)=\tr (J_K)=\tr (e e^T) =\tr (e^T \cdot e) =k\] Now use interlacing of eigenvalues \[ \lambda_{max}(J_k) \leq \lambda_{max}(X)\]. \epr \noindent In addition, it can be shown that \[ \mbox{size of max clique} \quad \omega(G) \leq \vartheta(G) \leq \chi(G) \quad \mbox{size of chromatic number} \] $\vartheta (G)$ gives a lower bound of $\chi(G)$ and an upper bound of $\omega(G)$. \\ (bounds for two NP-hard numbers) And, as shown in Section~\ref{sect:prelexamples}, we can use SDP to solve the min-max eigenvalue problem (efficiently). \end{slide} \begin{slide}{} \subsubsection{Generalized Eigenvalue Problems for $X=X^T$} \label{sect:geneigprobs} \begin{enumerate} \item {\bf The Generalized Eigenvalue Problem} Let $M,A$ be two $n \times n$ symmetric matrices, $M \succ 0$. The set of eigenvalues of the {\em matrix pencil}, denoted $[M,A]$, is $\{ \lambda \in \RR : \lambda M - A \mbox{ is singular} \}$. \[ \lambda_{\max}([M,X]) \leq t \quad \mbox{is equivalent to}\quad tM-X \succeq 0. \] \item {\bf Spectral Norm of Symmetric $X$} \[ \left\{ | \lambda_i(X) | \leq t, ~ \forall i \right\} \mbox{ iff } \left\{ tI - X \succeq 0, ~ tI + X \succeq 0 \right\} \] \item {\bf Sum of $k$ largest eigenvalues of Symmetric $X$}\\ Let $S_k(X)$ denote the sum of the largest $k$ eigenvalues of $X$. \[ S_k(X) \leq t \underline{\bf \mbox{ iff }} \begin{array}{rcl} t-ks-\tr Z \succeq 0, Z \succeq 0, Z-X+sI \succeq 0. \end{array} \] \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{SDP Application in Statistics} \label{sect:stats} If $m_0, m_1, m_2, \ldots , m_{2n}$ are moments of some distribution, then \[ H(m_0, m_1, \ldots , m_{2n})=\left[ \begin{array}{cccc} m_0 & m_1 & \cdots & m_n \\ m_1 & \cdots & \cdots & m_{n+1} \\ \cdots & \cdots & \cdots & \cdots \\ m_n & m_{n+1} & \cdots & m_{2n} \end{array} \right ] \succeq 0 \] Find distribution with maximal variance and $l_i\leq m_i \leq u_i$: \begin{eqnarray*} \max & y \\ {\mbox{s.t.}} & \left[ \begin{array}{cc} m_2-y & m_1 \\ m_1 & 1 \end{array} \right] \succeq 0 \\ & l_i \leq m_i \leq u_i \, (i=1, \ldots 2n) \end{eqnarray*} \end{slide} \begin{slide}{} \subsubsection{Minimizing the $L_2$-operator Norm of a Matrix} \label{sect:opernorm} \subsubsection{Linear Programming} \label{sect:LP} \subsubsection{Robust Mathematical Programming} \label{sect:robust} \end{slide} \begin{slide}{} \subsubsection{Control Theory} \label{sect:cntrl} \end{slide} \begin{slide}{} \subsubsection{Max-Cut Problem} \label{sect:combprobs} (MC) is a combinatorial optimization problem on undirected graphs with weights on the edges. \begin{prob} Find a partition of the set of vertices into two parts that maximizes the sum of the weights on the edges that have one end in each part of the partition. \end{prob} \end{slide} \begin{slide}{} \begin{center} {\bf Quadratic Model of MC} \end{center} given graph $G$ with vertex set $\{1,\dots,n\}$\\ weighted adjacency matrix $A(G)=(a_{ij})$, weight on edge $ij$\\ {\em Laplacian matrix} $L := \Diag(A(G) \cdot e) - A(G)$\\ Let $v \in \{\pm 1\}^n$ represent any cut in the graph \[\label{mc} (\mbox{MC}) \quad \begin{array}{ccl} \mu^* =&\max & \frac{1}{4} v^{T} Lv \\ &\mbox{s.t.} & v_i^2 = 1,\quad i=1,\ldots,n, \end{array} \] where $\mu^*$ denotes the optimal value of MC. \end{slide} \begin{slide}{} \begin{center} {\bf Some applications of MC} \end{center} \vspace{10mm} \begin{itemize} \item Statistical physics: Finding the ground state of a spin glass according to the Ising model \item VLSI: Minimizing the number of vias in a two-sided circuit board \item Network design: Solving the separation problem in a cutting plane approach \end{itemize} \end{slide} \begin{slide}{} \begin{center} {\bf Spin glasses} \end{center} A {\em spin glass} is an alloy of magnetic impurities diluted in a nonmagnetic metal. Suppose we have a spin glass subjected to an exterior magnetic field. At a very low temperature (close to $0^{\mbox{{\small o}}}$K) the spin glass attains a minimum energy configuration, called the ground state. This state can be found by {\em minimizing} the hamiltonian representing the total energy of the system. \end{slide} \begin{slide}{} \begin{center} {\bf Ising model} \end{center} Suppose the spin glass has $n$ impurities, or atoms. Let $v_i \in \{\pm 1\}$ denote the magnetic orientation of atom $i$ (``north/south''), and $v_0$ denote the magnetic orientation of the exterior magnetic field which has strength $h$. For any pair $i,j$ of atoms, $J_{ij}$ denotes the interaction between them, e.g. \[ J_{ij} = A \frac{\cos(D r_{ij})}{B^3 r_{ij}^3}, \] where $r_{ij}$ is the distance between the atoms, and $A,B,D$ are given constants. \end{slide} \begin{slide}{} Then the energy of the system is modelled by the hamiltonian \[ H := - \sum\limits_{1 \leq i < j \leq n} J_{ij} v_i v_j - h \sum\limits_{j=1}^{n} v_0 v_j. \] To find the ground state, we want to minimize $H$ over the $2^n$ possible configurations of the Ising spins (assuming $v_0 = +1$ wlog). Equivalently, we can maximize $-H$. \end{slide} \begin{slide}{} \begin{center} {\bf MC Formulation} \end{center} Let $G=(V,E)$ be a complete graph with $V=\{0,1,\ldots,n\}$ and $ \begin{array}{l} w_{ij} = -J_{ij}, \,\mbox{for}\; 1 \leq i < j \leq n, \\ w_{0j} = -h, \,\mbox{for}\; 1 \leq j \leq n. \end{array} $ Then $ \begin{array}{ccl} H & = & \sum\limits_{0 \leq i < j \leq n} w_{ij} v_i v_j \\ &=& \sum\limits_{0 \leq i < j \leq n : v_i=v_j} w_{ij} v_i v_j + \sum\limits_{0 \leq i < j \leq n : v_i \not= v_j} w_{ij} v_i v_j \\ &=& \sum\limits_{ij \not\in \delta(S)} w_{ij} ~~ - \sum\limits_{ij \in \delta(S)} w_{ij}, \\ \end{array} $ where $S = \{ i \in V : v_i = +1 \}$ and $\delta(S) = \{ ij \in E : i \in S, j \in V \backslash S \}$. \end{slide} \begin{slide}{} Now define the constant $K := \sum\limits_{ij \in E} w_{ij}$. Then \[ H-K = - 2 \sum\limits_{ij \in \delta(S)} w_{ij} \] and so $-H = 2 \sum\limits_{ij \in \delta(S)} w_{ij} - K$. So our equivalent optimization problem is: $ \begin{array}{cl} \mbox{max} & \sum\limits_{ij \in \delta(S)} w_{ij} \\ \mbox{s.t.}& S \subseteq V\\ \end{array} $ which is a MC problem. \end{slide} \begin{slide}{} \begin{center} {\bf Approaches to MC} \end{center} The general MC problem is NP-hard, even though it is tractable for some classes of graphs, e.g. planar graphs. In fact, solving within relative error of 1 percent is NP-hard. Techniques used for general MC include: \begin{itemize} \item Heuristics; \item Integer programming enumerative techniques (Branch-and-Bound); \item Approximation algorithms. \end{itemize} We seek {\em SDP relaxations} of MC (solvable in polynomial-time) that yield tight (upper) bounds on the optimal value of MC. \end{slide} \begin{slide}{} \begin{center} {\bf One Formulation of MC} \end{center} Let $v \in \{\pm 1\}^n$, $n = | V |$, represent a cut in the graph $G$ via $S = \{i : v_i = +1\}$ and $V \backslash S = \{i : v_i = -1\}$. Then we can formulate MC as: $\begin{array}{cll} \mu^{*}=&\max &\sum\limits_{1\leq i0$ \hfill{\em Tolerance} \item[$\bullet$] Given $X,y,Z$ \hfill{\em Must satisfy some condition} \item[$\bullet$] $\mu=\frac{\inner{Z}{X}}{n}$ \hfill{\em Initial barrier parameter} \item[$\bullet$] {\bf WHILE}~~{$\mu > \epsilon$} \begin{enumerate} \item[$\bullet\bullet$] Choose scaling $P$\hfill{\em Possibly dependent on $X,Z$} \item[$\bullet\bullet$] Choose centrality $0<\tau<1$ \hfill{\em According to some condition} \item[$\bullet\bullet$] $\mu \leftarrow \tau \frac{\inner{Z}{X}}{n}$ \hfill{\em Update target} \item[$\bullet\bullet$] Solve ({\em scaled ahosystem})\hfill {\em Scaled AHO direction} \item[$\bullet\bullet$] Choose steplength $\alpha$\hfill{\em To maintain positive definiteness} \item[$\bullet\bullet$] $X=X+dX, y=y+dy, Z=Z+dZ$\hfill{\em Update iterate} \end{enumerate} \item[$\bullet$]{\bf ENDWHILE} \end{enumerate} \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{Common LP,SDP Framework} \label{sect:commonframewk} For LPs, Lor\'{e}ntz cone problems, SDPs: use Newton's method to get step at each iteration. Common system of equations at each step: \beq\label{System for all} \left( \begin{array}{ccc} \mathcal{A} & 0 & 0 \\ 0 & \mathcal{A}^* & I \\ \mathcal{E} & 0 & \mathcal{F} \end{array} \right) \left( \begin{array}{c} \Delta X \\ \Delta y \\ \Delta Z \end{array} \right) = \left( \begin{array}{c} \F_p\\ \F_d\\ \F_c \end{array} \right) \eeq $\Delta x$, $\Delta y$, $\Delta Z$ step; $\F_p$, $\F_d$, and $\F_c$ residuals primal, dual, complementarity \end{slide} \begin{slide}{} Assume $\mathcal{E}$ and $\mathcal{AE}^{-1}\mathcal{FA}^*$ are invertible. Then the solution to (\ref{System for all}) is: \beq\label{Solution to all} \begin{array}{lll} \Delta y & = & (\mathcal{AE}^{-1}\mathcal{FA}^T)^{-1}(\mathbf{F_p}- \mathcal{AE}^{-1}(\mathbf{F_c}-\mathcal{F}\mathbf{F_d})) \\ \Delta Z & = & \mathbf{F_d}-\mathcal{A}^*\Delta y \\ \Delta X & = & \mathcal{E}^{-1}(\mathbf{F_c}-\mathcal{F}(\mathbf{F_d} -\mathcal{A}^*\Delta y)) \end{array} \eeq \end{slide} \begin{slide}{} {\bf LP Case} central path satisfies \beq\label{LPxs} \begin{array}{rcl} \A X & = & b \\ \A^* y+ Z & = & C \\ X_i Z_i & = & \mu ~ i=1, \ldots, n, \end{array} \eeq where $X=x, Z=z$. Newton's method on \req{LPxs} yields \req{System for all}, where $\mathcal{A}=A$, $\mathcal{E}=\Diag({z})$, $\mathcal{F}=\Diag({x})$, $\mathbf{F_p}=b-A x$, $\mathbf{F_d}=c-A^T y- z$, $\mathbf{F_c}_i=\mu-x_i z_i,~ i=1, \dots,n$. \begin{remark} The main work is the computation of (the positive definite Schur complement) $(\mathcal{AE}^{-1}\mathcal{FA}^T)^{-1}$. \end{remark} \end{slide} \begin{slide}{} {\bf SDP Case} Use $(-\ln \det X)$ for barrier function. Then its gradient is $-X^{-1}$, its Hessian is $X^{-1}\otimes X^{-1}$. (So convex function on $\p$.) The log-barrier problem is: \begin{eqnarray*} \min_X & \trace C X-\mu \ln \det X \\ \mbox{s.t.}& \trace A_i X=b_i \, ~i=1, \cdots , m \end{eqnarray*} \end{slide} \begin{slide}{} Let $y$ be the Lagrange multiplier; Lagrangian is \[\mathcal{L}(X,y)= \trace C X-\mu \ln \det X + y^T(b - \A X ). \]. KKT system: \begin{eqnarray*} \nabla_X \mathcal{L} & = & C-\mu X^{-1}-\A^* y=0 \\ \nabla_{y} \mathcal{L} & = & b-\A X =0,~ i=1, \dots,m \end{eqnarray*} \end{slide} \begin{slide}{} Define $Z:= \mu X^{-1}$. The system of equations on the central path is now: \beq \begin{array}{rcl} A_i \bullet X & = & b_i \; (i=1, \cdots m) \\ \sum_{i=1}^m y_iA_i +S & = & C \\ \mbox{(one of)} & & \left\{ \begin{array}{rcl} S & = \mu X^{-1} \\ X & = \mu S^{-1} \\ XS & = \mu I \end{array} \right. \end{array} \label{eq:SDP} \eeq \end{slide} \begin{slide}{} Use $XZ=\mu I$ and apply Newton's method to the system: \beq \begin{array}{rclc}\label{eq:SDPXZ} \A \Delta X &=& b- \A X & (=(\mathbf{F_p})_i) \\ \A \Delta y +\Delta Z &=& C-S -\A^*y & (=F_d) \\ X \Delta Z + \Delta X Z &=& \mu I -XZ & (=F_c) \end{array} \eeq To write \req{eq:SDPXZ} into the common form of \req{System for all}, one should first turn matrix into vector. For a $p\times q$ matrix $B$, define $\kvec B$ to be a $pq$ column vector made up of columns of $B$ stacked on each other. Another way is to use $\svec$. Since here the matrices $X$ and $Z$ are symmetric, only the lower triangle of the matrices need to be saved. Let $\svec$ denote such an operator that maps $\mathbb{R}^{n\times n}$ to $\mathbb{R}^{\frac{n(n+1)}{2}}$. For the reason of simplicity, we use $kvec$ for now. \end{slide} \begin{slide}{} \begin{definition} \underline{Kronecker product($\otimes$):} If $A\in \mathbb{R}^{m\times n}$, $B \in \mathbb{R}^{p\times q}$, then $A \otimes B \in \mathbb{R}^{mp \times nq} $, \begin{displaymath} A\otimes B := \pmatrix{ a_{11}B & a_{12}B & \cdots & a_{1n}B \cr \vdots & \vdots & \vdots & \vdots \cr a_{m1}B & a_{m2}B & \cdots & a_{mn}B} \end{displaymath} \end{definition} \begin{exam} If \[ A= \pmatrix{ 1 & 2 \cr 3 & 4 } \mbox{ and } B= \pmatrix{ 5 & 6 } \] then \[ A\otimes B = \pmatrix{ 5 & 6 & 10 & 12 \cr 15 & 18 & 20 & 24} \] \end{exam} \end{slide} \begin{slide}{} Fundamental properties of Kronocker product: \begin{enumerate} \item \[ \kvec(ABC)=(C^T\otimes A)\kvec(B) \mbox{ and } (A\otimes B)(C \otimes D)=(AC)\otimes (BD) \] \item $(A\otimes B)^T=A^T \otimes B^T $ \item $ (A\otimes B)^{-1}=A^{-1}\otimes B^{-1} $ \item $ \Diag(x) \otimes \Diag(y) = \Diag( x \otimes y)$ \item Suppose $A=P^{-1}(\Diag(\lambda_i))P$, and $B=Q^{-1}(Diag(\omega_j))Q$, then $A \otimes B =(P^{-1}\otimes Q^{-1})(\Diag(\lambda_i \omega_j))(P \otimes Q) $ \item Let $\lambda_i$ be the $i$-th eigenvalue of $A$, and $\omega_j$ be the $j$-th eigenvalue of $B$, then the $ij$-th eigenvalue of $A\otimes I + I \otimes B$ is $\lambda_i+\omega_j$ \end{enumerate} \end{slide} \begin{slide}{} $X\Delta Z +\Delta X Z =\mu I -XZ$, can be rewritten using Kronocker products: \[ (Z\otimes I)\kvec \Delta X + (I \otimes X)\kvec \Delta Z =\kvec (\mu I -XZ) =\kvec(F_c) \] %Let $ith$ row of $\A$ be $(vec A)^T$, $\E=S\otimes I$, $\F=I\otimes X$, $\mathbf{r_P}=b-\A vec(X)$, $vec(R_d)=vec(C-S-mat(\A^T \vy))$, \req{eq:SDPXSp}---\req{eq:SDPXSc} now can be written as: %\begin{displaymath} %\begin{pmatrix} %\A & 0 & 0 \\ %0 & \A^T & I \\ %\E & 0 & \F %\end{pmatrix} %\begin{pmatrix} %vec(\Delta X) \\ %\dy \\ %vec(\Delta S) %\end{pmatrix} %= %\begin{pmatrix} %\mathbf{r_p} \\ %vec(R_d) \\ %vec(R_c) %\end{pmatrix} %\end{displaymath} %Notice that $\E$ are linear in $S$, and $\F$ are linear in $X$, $M=\A S^{-1} \otimes X \A^T$. %>From \req{eq:SDPXSd}, one can see that $\Delta S$ is symmetric, but $\Delta X$ is not necessarily symmetric. (\req{eq:SDPXSc} can be written as $\Delta X S=\mu I -X(S+\Delta S)$, for two symmetric matrices $C$ and $D$, $CD$ is not necessarily symmetric).\\ %\textbf{$XS$ Method:} One way to solve this problem is at each iteration, replace the iterate $\Delta X$ with $\frac{\Delta X + \Delta X^T}{2}$, we call it $XS$ method. \\ %\textbf{$SX$ Method:} One can replace $XS=\mu I$ with $SX=\mu I$, and symmetrize each $X$ iterate. This method differs from $XS$ method only on $R_c$, but technically, they are different directions. \\ %In both $XS$ method and $SX$ method, $M$ is symmetric and positvie definite in the interior(Assume $\A$ has full rank), so Cholesky factorization can be applied to them. The drawback of these methods is that they deviate from Newton direction, since $X$ iterate is changed. Another way is to use $S=\mu X^{-1}$ or $X=\mu S^{-1}$ in \req{eq:SDP}. \\ %\textbf{$X$ Method:} use $S=\mu X^{-1}$, then $\E=\mu X^{-1} \otimes X^{-1}$, $\F=I$ \\ %\textbf{$S$ Method:} use $X=\mu S^{-1}$, then $\E=I$, $\F=\mu S^{-1} \otimes S^{-1}$ \\ %$X$ method and $S$ method are pure Newton's methods, and $M$ in both cases are symmetric. But both methods are numerically unstable near boundary as they involve $X^{-1}$ or $S^{-1}$. Besides, the systems of equations are not symmetric in both cases.\\ % {\bf $XZ+ZX$ Method to guarantee symmetry (AHO Direction)} \[ \mbox{replace } XZ=\mu I \mbox{ with } \frac{XZ+ZX}{2}=\mu I. \] To justify this method, one can show that for $X \succeq 0, Z \succeq 0$, \[ XZ=\mu I \Longleftrightarrow \frac{XZ+ZX}{2}=\mu I. \] %\begin{proof} %$\Longrightarrow$ is trival. \\ %$\Longleftarrow$ : let $A= XS$, then $ \frac{XS+SX}{2}=\mu I \Longleftrightarrow \frac{A+A^T}{2}=\mu I$, which means %\begin{displaymath} %a_{ij}= %\begin{cases} %-a_{ji} & (i\neq j) \\ %\mu & (i=j) %\end{cases} %\end{displaymath} %So $XS-\mu I$ is a skew symmetric matrix, which means all its nonzero eigenvalues are pure imaginaries( If $B=-B^T$, then $B^2=-BB^T$. Since $BB^T$ is symmetric and positive semidefinite, all the eigenvalues of $B^2$ are negative.) %At the same time, $XS-\mu I \approx \Xsq S \Xsq -\mu I$, which is symmetric, so all its eigenvalues are real. %Thus, all the eigenvalues of $XS-\mu I$ are $0$. %\end{proof} %Apply Newton to $\frac{XS+SX}{2}=\mu I$, one can get: %\[ X\Delta S +\Delta S X + S \Delta X + \Delta X S =2 \mu I -XS -SX \] %Since $vec(\Delta X S + S \Delta X + \Delta S X + X \Delta S)=(S \otimes I +I \otimes S)\Delta X +(X \otimes I + I \otimes X ) \Delta S $, for $XS+SX$ method, $\E=S\otimes I +I\otimes S$, and $\F=X\otimes I + I \otimes X$, $R_c=2\mu I -XS -SX$. %Assume primal and dual nondegeneracy and strict complementary, then \req{System for all} is well defined for $XS+SX$ method. And it is numerically more stable even near the optimum. But $\E^{-1}\F$ is not symmetric any more, so instead of Cholesky factorization, LU factorization need to be employed. % % % % \end{slide} \begin{slide}{} \subsection{Gauss-Newton Method} \label{sect:GNmethod} \subsubsection{Outline} \begin{enumerate} \item[$\bullet$] Background for GN \item[$\bullet$] Properties of the Gauss-Newton Direction \item[$\bullet$] {Conditioning of the Jacobian} \item[$\bullet$] {Invariance} \item[$\bullet$] {Convergence of Gauss-Newton Method} \item[$\bullet$] Numerical Tests \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{Background for GN Methods} $H_1$, $H_2$ {\em TWO} real Hilbert spaces $F:H_1 \to H_2$ a nonlinear operator solve the equation: \beq \label{eq1} F(x)=0. \eeq {\bf Assumption}:\ Problem (\ref{eq1}) has a solution $\hat{x}$ Newton's method (\cite{OrRhe:70}): \beq \label{nm} x_{k+1}=x_k-F^{\prime}(x_k)^{-1}F(x_k), \eeq where $F^{\prime}(x) : H_1 \to H_2$ - Fr\'echet derivative of $F$ (linear operator) {\bf needs:} bounded invertibility of $F^{\prime}(x_k)$ \\ (existence of a bounded linear operator $[F^{\prime}(x)]^{-1}$ near $\hat{x}$) \end{slide} \begin{slide}{} to avoid the restrictions use Gauss-Newton procedure (\cite{OrRhe:70}): \beq\label{eq2} \begin{array}{rcl} x_{k+1}&=& x_k-[F^{\prime *}(x_k)]^{\dagger} F(x_k)\\ &=&x_k-[F^{\prime *}(x_k)F^{\prime}(x_k)]^{-1}F^{\prime *}(x_k)F(x_k), \end{array} \eeq where $\cdot^{\dagger}$ denotes Moore-Penrose generalized inverse \end{slide} \begin{slide}{} \subsubsection{Gauss-Newton Methods for SDP} In numerical analysis, how do we solve a nonlinear system of equations? The standard approach is to solve the equivalent nonlinear least squares problem using ``Gauss-Newton'' method. \[ \min \frac 12 || F_{\mu} (X,y,Z) ||^2_2 \] subject to $X,Z>0.$ \end{slide} \begin{slide}{} In the LP case, when we differentiate we get a square system and Gauss-Newton reduces to Newton's method. i.e. solving \[ \left( F_{\mu}^{\prime}\right)^T F_{\mu}^{\prime} (\Delta s) = - \left( F_{\mu}^{\prime}\right)^T F_{\mu} \] (where $F_{\mu}^{\prime}$ is the Jacobian)\\ is equivalent to solving \[ F_{\mu}^{\prime} (\Delta s) = - F_{\mu} \] \end{slide} \begin{slide}{} {\bf framework} p-d i-p:\\ {\bf Given} $(X^0,y^0,Z^0) \in {\cal F}^0$\\ {\bf for} $k=0,1,2 \ldots $\\ \hspace{.5in}{\bf solve} for the search direction\\ \[ ~~~~F_{\mu}^{\prime}(X^k,y^k,Z^k) \left( \begin{array}{ccc} \Delta X^k \\ \Delta y^k \\ \Delta Z^k \end{array} \right) = \left( \begin{array}{ccc} 0 \\ 0 \\ -X^kZ^k + \sigma_k \mu_k I \end{array} \right) \] \hspace{.5in}where $\sigma_k$ centering, $\mu_k=\tr X^kZ^k/n$ \[ \begin{array}{c} (X^{k+1},y^{k+1},Z^{k+1}) =~~~~~~~~~~~~~~~~~~\\ ~~~~~~~~~~~~~~~~ (X^k,y^k,Z^k) + \alpha_k (\Delta X^k, \Delta y^k, \Delta Z^k) \end{array} \] \hspace{.5in}so that $(X^{k+1},Z^{k+1}) \succ 0$\\ {\bf end (for)}. \end{slide} \begin{slide}{} \begin{center} Shrinking the Overdetermined System \end{center} We can find redundant equations and solve a smaller system. We can remove the lower triangular part from the nonlinear equation and get the equivalent equation \[ \T \left(ZX - \mu I \right)= 0, \] where the linear operator $\T: \Mn \rightarrow \Sn$ by ignoring the strictly lower triangular part of the matrix, i.e. the $i,j$ components are \[ \left(\T(W)\right)_{ij} = \left\{ \begin{array}{cc} W_{ij} & \mbox{if}~ i \leq j \\ W_{ji} & \mbox{if}~ i > j \\ \end{array} \right. \] The resulting system is now square. $\T$ is an orthogonal projection \end{slide} \begin{slide}{} The optimality conditions become \[ \left( \begin{array}{c} Z + C - \A^{*}y \\ b-\A(X)\\ \T(ZX-\mu I)\\ \end{array} \right) = 0. \] This does not introduce new nonlinearities but does guarantee that we map between the same spaces. In fact, we can prove that we do not lose information in the optimality conditions when we only consider the upper triangular parts. LEMMA\\ Suppose that $Z \succ 0.$ Then the linear operator $\T_Z(\cdot) := \T (Z \cdot )$ is a one-one mapping on $\Sn$. In addition, if $\T_Z(X) = \mu I$, for some $X=X^T$, then $ZX=\mu I.$ \end{slide} \begin{slide}{} The Newton direction is obtained from solving the system \begin{eqnarray*} \Delta Z-\A^{*}(\Delta y) &=& -F_{d} \label{shnewt1}\\ -\A(\Delta X) &=& -F_{p} \label{shnewt2}\\ \T(Z\Delta X+\Delta Z X) &=& -\T(Z F_{Z,X}) \label{shnewt4}. \end{eqnarray*} Equivalently, \[ \left[ \begin{array}{ccc} 0 & -\A^* & I \\ -\A & 0 & 0 \\ \T_Z (\cdot) & 0 & \T(\cdot X) \end{array} \right] \left( \begin{array}{c} \Delta X \\ \Delta y \\ \Delta Z \\ \end{array} \right) = \left( \begin{array}{c} -F_d\\ -F_p\\ -\T_Z(X)+\mu I \\ \end{array} \right). \] \end{slide} \begin{slide}{} \begin{center} MORE LINEARITY\\ SPEEDS UP NEWTON'S METHOD\\ but\\ results in overdetermined system \end{center} \end{slide} \begin{slide}{} \subsubsection{Properties of the Gauss-Newton Directions} \label{sec:properties} {\bf Well-Defined} \begin{lemma}\label{GNfullrank} If $\A$ is surjective, the Gauss-Newton direction exists and is unique for all $X\succ 0$, $Z\succ 0$. (The Jacobian is full-rank.) \end{lemma} result requires only positive definite $X$ and $Z$ in contrast to other directions \end{slide} \begin{slide}{} {\bf nonsingularity of Jacobian holds in the limit}\\ \begin{lemma}\label{fullrank0} If $\A$ is surjective and the optimal primal-dual solution $(X^*,y^*,Z^*)$ is unique and strictly complementary, then ${\F^{\prime}_\mu}{(v^*)}$ at $\mu=0$ is nonsingular. \end{lemma} \end{slide} \begin{slide}{} {\bf Merit function - Descent direction} \begin{eqnarray} \varphi(v) &:=& \half \inner{F_\mu(v)}{F_\mu(v)} \label{eq:phi}\\ &=& \half\inner{F_d}{F_d}+\half\inner{f_p}{f_p}+\half\inner{F_c}{F_c}\\ &=:&\varphi_d(v) + \varphi_p(v) + \varphi_c(v).\label{varphidpc} \end{eqnarray} \begin{lemma}\label{gndescent} The Gauss-Newton direction $dv$, is a strict descent direction for the merit function $f_\mu(v) = \half \inner{F_\mu(v)}{F_\mu(v)}$ if and only if $F_\mu(v)$ is not perpendicular to the range of ${\F^{\prime}_\mu}{(v)}$. \end{lemma} \end{slide} \begin{slide}{} \begin{center} Summary \end{center} {\bf Well-Defined}\\ {\bf nonsingularity of Jacobian holds in the limit}\\ {\bf Merit function - Descent direction}\\ if $\A$ is surjective (and we may assume it is), the Gauss-Newton direction is a strict descent direction until stationarity of the merit function is attained.\\ Moreover, under uniqueness of the optimal solution and strict complementarity, (conditions that hold generically \cite{PatTun:97}), the Gauss-Newton system minimizes the risk of ill-conditioning as we approach the optimal solution. \end{slide} \begin{slide}{} \subsubsection{Conditioning of the Jacobian} equivalent form of the (overdetermined) optimality system \begin{eqnarray} \mbox{AHO} \quad \left\{ \begin{array}{rcl} \A^*(dy)+dZ &=& -(\A^*(y)+Z-X) \label{expand_gn1},\\ \A(dX) &=& -(\A(X)-b), \\ H(ZdX + dZX) &=& -H(ZX-\mu I), \end{array} \right.\\ \mbox{GN uses extra info}\quad K(ZdX + dZX) = -K(ZX-\mu I),\label{expand_gn4} \end{eqnarray} where \[ \begin{array}{rclr} H(M) &:=& \frac{1}{2}[M+M^T],&\quad \mbox{(symmetric part);} \label{symm_op}\\ K(M) &:=& \frac{1}{2}[M-M^T],&\quad \mbox{(skew-symmetric part).} \label{skew_op} \end{array} \] \end{slide} \begin{slide}{} matrix formulation \beq\label{aho-gn} J_{gn} d = P \left[ \begin{array}{c} J_{aho} \\ J_{k} \end{array} \right] d = - \left[ \begin{array}{c} F_{s} \\ F_{k} \end{array} \right], \eeq permutation of the rows $P$\\ $J_{gn}$ - Jacobian of the Gauss-Newton system\\ $J_{aho}$ - Jacobian of the symmetric (AHO) system\\ $J_{k}$ - skew-symmetric component \begin{eqnarray} \bar n &:=& t(n)+m+t(n),\\ \bar m &:=& t(n)+m+n^2,\\ r &:=& \bar m - \bar n = t(n)-t(n-1). \end{eqnarray} $J_{gn}$ is $(\bar m \times \bar n)$, $J_{aho}$ is $(\bar n \times \bar n)$, and $J_{k}$ is $(r \times \bar n)$. \end{slide} \begin{slide}{} ordering of the singular values \begin{displaymath} \sigma_{\max}(J) := \sigma_1(J) \ge \sigma_2(J) \ge \ldots \ge \sigma_n(J) =: \sigma_{\min}(J). \end{displaymath} \begin{lemma} The singular values of $J_{gn}$ and of $J_{aho}$ are related by $\sigma_k(J_{gn}) \ge \sigma_k(J_{aho}) \ge \sigma_{k+t(n-1)}(J_{gn})$ for $1\le k\le \bar n$. \end{lemma} \bpr Follows from {\em interlacing} of singular values. \cite{HoJo:91}. \epr Gauss-Newton Jacobian is no closer to singularity than the AHO Jacobian is. \begin{lemma} The largest singular value of the Gauss-Newton Jacobian is bounded by $\sigma_{\max}(J_{gn}) \le \sqrt{\sigma_{\max}^2(J_{aho}) + \sigma_{\max}^2(J_{k})}$. \end{lemma} \end{slide} \begin{slide}{} Gauss-Newton system is nonsingular and has a bounded condition number as we approach the optimal solution. (as with AHO direction; but not with NT nor HKM nor original Newton system) (assuming backward-stable algorithm) the (numerical) direction $\widehat{dv}$ is the exact solution to a nearby problem \cite{MR2000j:90078} \begin{displaymath} (J_{s} - \delta J_{s}) \widehat{dv} = -(f + \delta f), \end{displaymath} with bounded relative error \beq\label{errorAHO} \frac{\|\widehat{dv} - dv\|}{\|dv\|} \le \frac{\kappa(J_s)}{1-\kappa(J_s)\frac{\|\delta J_s\|}{\|J_s\|}} \Bigl( \frac{\|\delta J_s\|}{\|J_s\|}+ \frac{\|\delta f\|}{\|f\|}\Bigr). \eeq \end{slide} \begin{slide}{} \begin{lemma}\label{GNeqHKM} Suppose that $\A$ is surjective, that $X,y,Z$ is on the central path with $F_d=0, F_p=0$ and $ZX-\mu I = 0, ~ \mu > 0$. Suppose that the new target for the barrier parameter is $\tau \mu,$ where $0 < \tau < 1$. Then the Gauss-Newton direction from coincides with the HKM direction. \end{lemma} This is the only case where the Gauss-Newton direction coincides with other directions of the Monteiro-Zhang family. \end{slide} \begin{slide}{} \subsubsection{Invariance} \begin{lemma} (Q-scale invariance) Let $(dX,dy,dZ)$ be the Gauss-Newton direction obtained at point $(X,y,Z)\in\Snpp\times\Rm\times\Snpp$. Consider the scaled primal-dual pair obtained using orthogonal $P$. Then the scaled vector $(PdXP^T,dy,P^{-t}dZT^{-1})$ is the Gauss-Newton direction at the iterate $(\widetilde X,\widetilde y, \widetilde Z)$ for the scaled problem. \end{lemma} \begin{thm} The Gauss-Newton direction, at any point $v_c\in \V$ is invariant under affine transformation of the variables $w=H(v)+h$ where $H:\V \rightarrow \V$ is nonsingular. \end{thm} \end{slide} \begin{slide}{} \subsubsection{Convergence of Gauss-Newton Method} semidefinite program pair \[ \minpgm{{}}{\inner{C}{X}}{\A(X) = b, X \succeq 0}, \] \[ \maxpgm{}{\inner{b}{y}}{\A^*(y)+Z = C, Z \succeq 0}. \] merit function: (combined norms infeasibility and complementarity) \beq \label{eq:phimu} \varphi(v,\mu) := \half \inner{F_\mu(v)}{F_\mu(v)}. \eeq \end{slide} \begin{slide}{} {\bf Generic Gauss-Newton based interior-point code} \begin{enumerate} \item \begin{enumerate} \item[$\bullet$] Given $\epsilon>0$ \hfill{\em Tolerance} \item[$\bullet$] $k := 1; X^{(k)}:= I; Z^{(k)}:= I; y^{(k)}:= 0; \mu^{(k)}:=\frac{\inner{Z^{(k)}}{X^{(k)}}}{n}=1;$ \item[$\bullet$]{\bf WHILE}~~{$\max\left\{\varphi(v^{(k)},\mu^{(k)}\right\} > \epsilon$} \begin{enumerate} \item[$\bullet\bullet$] $d^{(k)} = - {F^{\prime}_\mu(v^{(k)})}F_\mu(v^{(k)});$\hfill {\em Gauss-Newton direction} \item[$\bullet\bullet$] $\alpha^{(k)} := \mbox{LineSearch}(v^{(k)},d^{(k)},\mu^{(k)});$\hfill{\em Decrease $\varphi$} \item[$\bullet\bullet$] $\mu^{(k+1)} := \mbox{TargetSelect}(v^{(k)},d^{(k)},\alpha^{(k)},\mu^{(k)});$\\ ~~~~~~~~~~~\hfill{\em $\mu^{(k+1)} = \tau\mu^{(k)}, 0\le \tau <1$} \item[$\bullet\bullet$] $v^{(k+1)} := v^{(k)} + \alpha^{(k)} d^{(k)};$\hfill{\em New iterate} \item[$\bullet\bullet$] $k := k+1;$ \end{enumerate} {\bf ENDWHILE} \end{enumerate} \end{enumerate} \end{slide} \begin{slide}{} {\bf Now: assumptions for convergence analysis}\\ \begin{itemize} \item $\exists v^0$ satisfying centrality condition \item operator $\A$ is surjective. \item optimal primal-dual pair is unique and satisfies strict complementarity (i.e. $Z+X \succ 0$). \end{itemize} -algorithm approximately follows the central path by attempting to solve $F_\mu(X,y,Z)=0$ for decreasing values of $\mu$\\ \end{slide} \begin{slide}{} -major difference: the scalar $\mu$ is not updated using the iterates, but is reduced by a factor $\tau<1$ at every step ($\mu \leftarrow \tau \mu$);\\ no attempt is made to dampen the step to maintain the iterates within the cone of positive definite matrices. (The algorithm only maintains the weaker full rank condition on the Jacobian.) \begin{lemma} The operator $F_{\tau \mu}^\prime(s)$ is Lipschitz continuous with constant 1. \epr \end{lemma} \end{slide} \begin{slide}{} \begin{thm} \label{stdcvg} Let $\sigma_{\min}$ and $\sigma_{\max}$ be, respectively, the smallest and largest singular value of $F_{\tau \mu}^\prime(s_{\tau\mu})$. There is a $\delta > 0$ such that for all $s_c$ such that $\|s_c - s_{\tau\mu}\| < \delta$, the Gauss-Newton step \begin{displaymath} s_+ = s_c - F_{\tau \mu}^\prime(s_c)^\dagger F_{\tau \mu}(s_c) \end{displaymath} is well-defined and converges to $s_{\tau\mu}$ at a rate such that \begin{displaymath} \|s_+ - s_{\tau\mu}\| \le \frac{1}{\sigma_{\min}} \|s_c - s_{\tau\mu}\|^2. \end{displaymath} Moreover, we can choose $\delta$ as long as $\delta < \frac {\sigma_{\min}}{2}$. \epr \end{thm} \end{slide} \begin{slide}{} \begin{cor}\label{gndecrease} Let $\sigma_{\min}$ and $\sigma_{\max}$ be, respectively, the smallest and largest singular value of $F_{\tau\mu}^\prime(s_{\tau\mu})$. There is a $\delta > 0$ where for all $s_c$ such that $\|s_c - s_{\tau\mu}\| < \delta$, \begin{displaymath} \|F_{\tau\mu}(s_+)\| \le \frac{1}{2} \|F_{\tau\mu}(s_c)\|. \end{displaymath} Moreover, we can choose any $\delta$ such that \beq \label{eq:deltacor} \delta < \frac{\sigma_{\min}^2}{8 \sigma_{\max} }. \eeq \epr \end{cor} \end{slide} \begin{slide}{} general idea:\\ from an iterate $s_k$ , ``close enough'' to $s_\mu$, we can choose a target on the central path $s_{\tau\mu}$ in such a way that the next iterate $s_{k+1}$, obtained from the Gauss-Newton direction, is now ``close enough'' to $s_{\tau\mu}$ for the process to be repeated. \end{slide} \begin{slide}{} First we estimate the distance between two points on the central paths in terms of the required radius of convergence. \begin{lemma}\label{mu2taumu} Let $\sigma_{\min}$ and $\sigma_{\max}$ be, respectively, the smallest and largest singular value of $F_\tau^\prime(s_{\tau\mu})$. Let $s_\mu$ and $s_{\tau\mu}$ be the optima on the central path. \begin{enumerate} \item \label{item:part1} If we choose $0 < \tau < 1$ such that \beq \label{eq:tauvalue} 1-\tau \le \frac{\sigma_{\min}^2}{8\sqrt{n}\mu}, \eeq then \beq \label{eq:halfrad} \|s_\mu - s_{\tau\mu}\| \leq \frac 12 \left( \frac {\sigma_{\min}}{2} \right), \eeq which implies $s_\mu$ is within half of the radius of quadratic convergence of $s_{\tau\mu}$. \item \label{item:part2} If we choose $0 < \tau < 1$ such that \beq \label{eq:tauvalueforF} 1-\tau \le \frac{ \sigma_{\min}^3}{32 \sqrt{n}\mu \sigma_{\max} }, \eeq then \beq \label{eq:halfradforF} \|s_\mu - s_{\tau\mu}\| \leq \frac 12 \left( \frac {\sigma_{\min}^2}{8 \sigma_{\max}} \right). \eeq In this case $s_\mu$ is within half of the radius of guaranteed constant decrease of the merit function in (\ref{eq:deltacor}) in Corollary \ref{gndecrease}. \end{enumerate} \epr \end{lemma} \end{slide} \begin{slide}{} We now estimate the distance to the new target after a Gauss-Newton step. \begin{lemma} \label{lem:totarget} Let $\sigma_{\min}$ and $\sigma_{\max}$ be, respectively, the smallest and largest singular value of $F_\tau^\prime(s_{\tau\mu})$. Let $s_\mu$ and $s_{\tau\mu}$ be optima on the central path. Suppose that the point $s_c$ is well-centered in the sense that \begin{eqnarray*} \|s_\mu - s_c\| &\le& \min\left\{\frac{\sigma_{\min}}{4},\frac{\sigma_{\min}}{16\sigma_{\max}}\right\}, \end{eqnarray*} and we choose $\tau$ to satisfy \begin{equation} \label{eq:tauvalue2} 0 < \tau < 1, \quad 1-\tau \le \min \left\{\frac{\sigma_{\min}^2 }{8 \sqrt{n}\mu}, \frac{\sigma_{\min}^3 }{32 \sqrt{n}\mu}\right\}, \end{equation} as in Lemma \ref{mu2taumu}. Then, after one Gauss-Newton step, the new point $s_+$ will be within half the radius of convergence of $s_{\tau\mu}$, i.e. \begin{eqnarray} \|s_{\tau\mu} - s_+\| &\le& \frac{\sigma_{\min} }{4}. \end{eqnarray} Moreover, the merit function is reduced \begin{equation} \label{eq:meritred} \|F_{\tau}(s_+)\| \leq \frac 12 \|F_{\tau}(s_c)\|. \end{equation} \epr \end{lemma} \end{slide} \begin{slide}{} Main Convergence Theorem: \begin{thm} \label{thm:mainthm} Suppose that we are given a tolerance $\epsilon > 0$, an initial barrier parameter $\mu_0 > \epsilon$, and $Z_0,X_0 \in\Snpp$ such that $s_0=(X_0,y_0,Z_0)$ is a well-centered starting point: $s_0$ is within half the quadratic convergence radius of $s_{\mu_0}$ in Theorem \ref{stdcvg}, \begin{equation}\label{s0} \|s_{\mu_0} - s_0\| \leq \frac 12 \left( \frac {\sigma_{\min}} {2} \right). \end{equation} Suppose moreover that $s_0$ is within half the radius for guaranteed constant decrease of the merit function given in Corollary \ref{gndecrease}, \begin{displaymath} \|s_{\mu_0}-s_0\|\leq\frac 12\left(\frac{\sigma_{\min}^2}{8\sigma_{\max}}\right), \end{displaymath} where $0< \sigma_{\min}$ (respectively $\sigma_{\max}$) is smaller than the smallest (respectively larger than the largest) singular value of $F_{\omega \mu_0}^{\prime}(s_{\omega \mu_0})$, for all $\frac {\epsilon}{\mu_0} < \omega < 1$. If we choose $\tau$ ({\em small}) satisfying (\ref{eq:tauvalue2}) in Lemma \ref{lem:totarget}, i.e. \begin{displaymath} \alpha = \min \left\{ \frac {\sigma^2_{\min}}{8\sqrt{n}\mu_0}, \, \frac {\sigma^3_{\min}}{32\sqrt{n}\mu_0} \right\}, \end{displaymath} and $\tau \geq \max\left\{0,1-\alpha\right\},\,0<\tau<1$, then the GN Algorithm converges to $\bar{s}$, $\epsilon$-optimal in the following sense, \begin{displaymath} \tau^k\mu_0 \le \epsilon, \quad \|F_{\tau^k \mu_0}(\bar{s})\| \leq \epsilon, \quad \|\bar{s}-s_{\tau^k\mu_0}\| \le 2 \sigma_{\min} \epsilon; \end{displaymath} and the number of iterations, $k$, depends on $\tau$: \begin{enumerate} %%%%%%%%%%%%%%%%%%%%% Simplification since we are using big-Oh %%%%%%%%%%%%%%%%%%%%% You can replace by the commented out part if you %%%%%%%%%%%%%%%%%%%%% want % \item %\begin{enumerate} % \item % \begin{equation} % \label{eq:iterations1} % {\cal O}\left(\max \left\{ % \left( % \frac % {\log \left(\frac{\|F_{\mu_0}(s_0)\|}{\epsilon} \right)} % {\log {2} } +1 % \right),\,\,\, % 2\left( \frac {\log \frac {\mu_0\sqrt{n}}{\epsilon} } % {\log 2}+1 \right),\,\,\, % \left( \frac {-\log \frac {\epsilon}{\mu_0}}{\log 2} \right) % \right\} \right) % \end{equation} % iterations, if $0<\tau \leq \frac 12$; % \item % \begin{equation} % \label{eq:iterations2} % {\cal O}\left(\max \left\{ % \left( % \frac % {\log \left(\frac{\|F_{\mu_0}(s_0)\|}{\epsilon} \right)} % {\log {2} } +1 % \right),\,\,\, % \left( \frac {\log % \frac % {(2\tau-1)\epsilon}{(1-\tau)2\mu_0\sqrt{n} } } % {\log \tau} \right),\,\,\, % \left( \frac {\log \frac {\epsilon}{\mu_0}}{\log \tau} \right) % \right\} \right) % \end{equation} % iterations, if $\frac 12<\tau < 1$. % \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%% End of commented out region %%%%%%%%%%%%%%%%%%%%%%%%%%% Begin replacement \item \begin{equation} \label{eq:iterations1} {\cal O}\left(\max \left\{ \log \left(\frac{\|F_{\tau \mu_0}(s_0)\|}{\epsilon} \right) ,\,\,\, \log \left( \frac {\mu_0\sqrt{n}}{\epsilon} \right) \right\} \right) \end{equation} iterations, if $0<\tau \leq \frac 12$; \item \begin{equation} \label{eq:iterations2} {\cal O}\left(\max \left\{ {\log \left(\frac{\|F_{\tau \mu_0}(s_0)\|}{\epsilon} \right)} ,\,\,\, \left( \frac {\log \frac {(2\tau-1)\epsilon}{(1-\tau)2\mu_0\sqrt{n} } } {\log \tau} \right),\,\,\, \left( \frac {\log \frac {\epsilon}{\mu_0}}{\log \tau} \right) \right\} \right) \end{equation} iterations, if $\frac 12<\tau < 1$. \end{enumerate} \epr \end{thm} \end{slide} \begin{slide}{} {Asymptotic Convergence} We are also able to specialize a standard result pertaining to the asymptotic convergence rate of the Gauss-Newton method. \begin{thm} (Superlinear Convergence) Assume a primal-dual pair with a unique, strictly complementary, optimal solution, denoted $v^*$. Then for each $c \in (1, \infty)$, there is an $\epsilon > 0$ such that, from $v^{(0)}$ satisfying $\|v^{(0)}-v^*\| < \epsilon$, the sequence generated by the Gauss-Newton method converges to $v^*$ and obeys \begin{equation} \label{eq:ds1} \|v^{(k+1)} - v^* \| \le \frac{c\alpha}{2\sigma_{\min}^2}\|v^{(k)} - v^* \|^2. \end{equation} where $\|J(v)\| \le \alpha$ in the $\epsilon$-neighborhood of $v^*$ and where $\sigma_{\min}$ represent the smallest singular value of $J(v^*)$. \end{thm} This last result suggests that, whatever upper-level algorithm we use, if we use the Gauss-Newton as the search direction, then as soon as we can estimate $\sigma_{\min}$ accurately, we compute the radius of superlinear convergence and we can set the barrier parameter to zero, ignore the cone constraint and let the algorithm converge to the optimal solution. \end{slide} \begin{slide}{} \subsubsection{Numerical Tests with GN} \tiny{ \begin{center} \begin{tabular}{||c|c|c|c||}\hline Iter & $\|F_d\|$ & $\|f_p\|$ & $\inner{Z}{X}/n$\\ \hline\hline 1 & +8.900e+01 & +4.175e+01 & +8.749e-01 \\ 2 & +5.433e+01 & +3.545e+01 & +8.580e-01 \\ 3 & +1.503e+01 & +1.759e+01 & +6.269e-01 \\ 4 & +3.066e+00 & +3.465e-03 & +3.841e-01 \\ 5 & +2.131e-02 & +4.408e-04 & +1.278e-01 \\ 6 & +5.573e-03 & +8.302e-05 & +2.873e-02 \\ 7 & +1.042e-04 & +3.153e-06 & +1.367e-02 \\ 8 & +1.611e-05 & +2.913e-07 & +7.862e-04 \\ 9 & +7.275e-08 & +1.620e-09 & +8.680e-05 \\ 10 & +4.473e-13 & +2.041e-14 & +1.812e-06 \\ 11 & +1.017e-14 & +2.800e-15 & +3.784e-08 \\ 12 & +1.030e-14 & +3.426e-15 & +7.902e-10 \\ 13 & +1.318e-14 & +5.184e-15 & +1.650e-11 \\ 14 & +1.138e-14 & +4.835e-15 & +4.964e-14 \\ \hline \end{tabular} \end{center} {\bf One instance of well-conditioned problem. $n=15,m=30$} } \end{slide} \begin{slide}{} \tiny{ \begin{center} \begin{tabular}{|c|cccccccccc|}\hline &\multicolumn{5}{c|}{$-\log_{10}\max\{\|F_d\|,\|f_p\|\}$} & \multicolumn{5}{c|}{$-\log_{10}\inner{Z}{X}/n$}\\ \hline & AHO & HKM & NT & GT & GN & AHO & HKM & NT & GT & GN\\ \hline random & 14.7 & 9.1 & 10.6 & 9.5 & 13.3 & 12.0 & 10.7 & 5.5 & 12.8 & 14.4 \\ norm min. & 15.0 & 9.9 & 10.9 & 15.3 & 14.8 & 13.8 & 12.7 & 10.1 & 14.4 & 14.9 \\ Maxcut& 15.7 & 9.6 & 10.6 & 14.8 & 15.8 & 14.4 & 12.4 & 9.3 & 14.4 & 15.5 \\ Lov{\`a}sz $\theta$& 14.7 & 9.2 & 9.2 & 13.9 & 14.8 & 14.2 & 13.7 & 12.8 & 14.1 & 15.3 \\ \hline \end{tabular} \end{center} {\bf Accuracy of solutions on SDPT3 test problems. Average of one hundred random instances.} } \end{slide} \begin{slide}{} \begin{center} \begin{tabular}{|c|cccccc|}\hline & \multicolumn{3}{c}{AHO}& \multicolumn{3}{c|}{GN}\\ $r,n,m$ & iter. & Infeas. & Gap & iter. & Infeas. & Gap \\ \hline 3,10,9 & 18 & 14.2 & 15.1 & 13 & 14.3 & 15.4\\ 6,20,24 & 22 & 12.1 & 14.6 & 17 & 13.8 & 16.3\\ \hline \end{tabular} \end{center} {\bf Ill-conditioned problems' solutions. Average of fifty random instances.} \end{slide} \begin{slide}{} \begin{center} \begin{tabular}{|c|c||c|c|c|c|}\hline $n$ & $m$ & iter & $\|F_d\|$& $\|f_p\|$&$\inner{Z}{X}$\\\hline 10 & 11 & 24 &9.296152e-13& 5.594466e-11& 5.842689e-07\\\hline 20 & 21 & 25 &2.260052e-12& 4.882512e-15& 7.906645e-07\\\hline 30 & 31 & 22 &4.211995e-12& 9.367561e-15& 2.190712e-06\\\hline 40 & 41 & 23 &1.816565e-12& 7.334760e-15& 2.301071e-06\\\hline \end{tabular} \end{center} {\bf Gruber-Rendl ill-posed Problems with $\alpha=10^{-7}$ and accuracy set to $10^{-5}$.} (average iterations for G-R was 115; $\alpha = 0$ means no primal Slater point) \end{slide} \begin{slide}{} \begin{center} \begin{tabular}{|c|c||c|c|c|c|}\hline $n$ & $m$ & iter & $\|F_d\|$& $\|f_p\|$&$\inner{Z}{X}$\\\hline 10 & 11 & 23 & 2.377587e-12 & 4.076899e-08 & 9.096929e-06\\\hline 20 & 21 & 22 & 2.479800e-12 & 1.516398e-08 & 1.050569e-06\\\hline 30 & 31 & 25 & 5.153522e-12 & 5.729514e-08 & 1.416319e-06\\\hline \end{tabular} \end{center} {\bf with $\alpha=0$ and accuracy set to $10^{-5}$.} ~~\\ \begin{center} \begin{tabular}{|c|c||c|c|c|c|}\hline $n$ & $m$ & iter & $\|F_d\|$& $\|f_p\|$&$\inner{Z}{X}$\\\hline 50 & 51 & 32 & 3.467449e-12 & 6.469784e-15 & -1.233752e-14\\\hline \end{tabular} \end{center} {\bf with $\alpha=0$ and increased accuracy.} \end{slide} \begin{slide}{} \begin{center} \begin{tabular}{|c|c||c|c|c|c|}\hline $n$ & $m$ & iter & $\|F_d\|$& $\|f_p\|$&$\|\inner{Z}{X}\|$\\\hline 10 & 9 & 7 & 8.015765e-11 & 8.009760e-11 & 5.080324e-06\\\hline 20 & 19 & 8 & 9.000070e-11 & 9.001461e-11 & 1.743560e-06\\\hline 30 & 28 & 8 & 1.272965e-10 & 9.000636e-11 & 2.615344e-06\\\hline 40 & 15 & 5 & 2.593612e-09 & 9.999999e-11 & 1.651607e-07\\\hline 40 & 30 & 5 & 2.642280e-09 & 1.000001e-10 & 3.821364e-07\\\hline 40 & 39 & 5 & 2.231644e-09 & 9.999997e-11 & 5.396936e-07\\\hline 50 & 49 & 5 & 2.928152e-09 & 9.999996e-11 & 6.840107e-07\\\hline \end{tabular} \end{center} {\bf no primal or dual Slater points: accuracy set to $10^{-5}$.} (G-R needed average of 52 iterations) \end{slide} \begin{slide}{} \subsubsection{Solving SDPs using NLP} Though the current popular approaches for solving SDP use extensions of interior-point methods from LP (successful approaches), there are several that use NLP techniques, e.g. Monteiro-Zhang... or Vanderbei... details???? However, we use the primal-dual framework with known results from NLP to derive the Gauss-Newton method. Provide convergence results based on standard NLP approaches (redo KW paper using $\cos \theta$ bounded below and Wolfe conditions) \end{slide} \begin{slide}{} \subsection{Exploiting Sparsity} \subsubsection{Special Structure} \subsubsection{Bundle Trust Methods} \subsubsection{Potential Function Methods} \label{endsect:algorithms} \end{slide} \begin{slide}{} \bs{Applications} \label{sect:appl} \subsection{Outline} \begin{enumerate} \item[$\bullet$] Quadratic Boolean Programming \item[$\bullet$] Quadratically Constrained Quadratic Programs \item[$\bullet$] Trust Region Algorithms for NLP \item[$\bullet$] Sequential Quadratic Programming for NLP \item[$\bullet$] Historical Notes \end{enumerate} \end{slide} \begin{slide}{} \subsection{Quadratic Boolean Programming} \label{sect:QBP} \subsubsection{Outline} \begin{enumerate} \item[$\bullet$] Tractable Relaxations \item[$\bullet$] Strengthened SDP relaxations \item[$\bullet$] Strengthened Bounds for Max-Cut \item[$\bullet$] Historical Notes \end{enumerate} \end{slide} \begin{slide}{} \subsubsection{Tractable Relaxations of Max-Cut} (quadratic boolean programming) \[ (MCQ)~~~ \begin{array}{c} \mu^*:= \max\limits_{x \in \FF} q_0(x) \quad ( : = x^TQx -2 c^Tx). \end{array} \] where $\FF=\left\{\pm 1\right\}^n$\\ \underline{\hspace{90mm}}\\ perturbing diagonal of $Q$ on $\FF:$ \[ \begin{array}{rcl} q_u(x)& : = &x^T(Q+\Diag(u))x -2 c^Tx - u^Te\\ &~=&q_0(x),~~\forall x \in \FF, \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} \] \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\limits_{u} f_1^c(u).\\ ~~\\ \hline \end{array} \] Similarly, equivalent bnds $B_0^c$ and homog. bnds for 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 \FF,$ $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 the theme: ``Lagrangian relaxation is best'' \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}{} \subsubsection{Strengthened SDP Bounds for Max-Cut Problem} (ref Anjos-Wolkowicz/99 -Illustration of the recipe for SDP relaxation. based on a second lifting - motivated by strong duality results that follow from adding redundant constraints of type $XX^T$, ref. Anstreicher-Wolkowicz/98 and below) 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 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. Note: $\left(X^2=nX,~\trace X = n\right) \Rightarrow \left(\rank X=1\right)$. But, nonconvex problem too hard to solve in general. Need Lagrangian relaxation with vectors dimension $t(n)=n(n+1)/2.$ \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 \RR^{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\HH:= 2\HH(w) + 2\HH(T)+ 2\HH(S) + 2\HH(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; get (equivalent to the Lagrangian dual) \[ \mbox{MCDSDP2} \quad \begin{array}{ccc} \nu^*_2 = &\min & nw +\tr ET+\tr 0S +t\\ &\mbox{s.t.}& \HH(w,T,S,t) \succeq H_c\\ \end{array} \] take $T$ sufficiently positive definite and $t$ sufficiently large; get Slater's constraint qualification! take dual; get strengthened SDP relaxation of MC: \[ {\rm MCPSDP2} \begin{array}{ccc} \nu_2^* = &\max & \trace H_cY\\ &\mbox{s.t.}& \HH^*(Y) = n\\ & & \HH^*(Y) = E\\ & & \HH^*(Y) = 0\\ & & \HH^*(Y) = 1\\ && Y \succeq 0. \end{array} \] \end{slide} \begin{slide}{} We need to calculate the adjoint operators and remove redundant constraints in MCDSDP2. Use: \[ 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}\\ Suppose that $Y$ is feasible in MCPSDP2. Then the first row \[ \sMat \left( Y_{0,1:t(n)} \right) \succeq 0. \] \underline{\hspace{90mm}}\\ Proof: Let $x=Y_{0,2:t(n)}$. $X^2=nX$ constraint: \[ n \sMat (x) = \sMat (x) \sMat (x) =\sMat (x) x^T \sMat^*. \] identify $xx^T$ with lower right block of $Y$; get congruence of a positive semidefinite matrix. Alternatively: using ${\cal H}_3^*,$ and $\dsvec (\cdot) \sMat$ is self-adjoint operator \[ n\dsvec^* (x) = \dsvec \bar{Y} \sMat = \left( \dsvec \bar{Y} \sMat \right)^*, \] where $\bar{Y}$ is the bottom right block of $Y.$ Again congruence. \QED \end{slide} \begin{slide}{} {\bf Second Strengthened SDP Relaxation}\label{sect:2ndstrrel} add more redundant quadratic constraints to MC2; dual provides tighter relaxation change of variable $X = v v^T$ gives $X_{ij} = v_iv_j$ and $v_k^2 = 1$ for $k=1,\ldots,n$; therefore \[ X_{ij} = v_iv_j = v_i v_k^2 v_j = v_i v_k \cdot v_k v_j = X_{ik} \cdot X_{kj} \] interesting connection between these constraints and the metric polytope. \end{slide} \begin{slide}{} Add these constraints to MC2 \[ (\mbox{MC3}) \quad \begin{array}{ccl} \mu^*= &\max & \ \tr QX \\ &\mbox{s.t.}& \diag(X) = e\\ &&X\circ X=E\\ &&X^2-nX=0\\ &&X_{ij}=X_{ik}X_{kj}, \quad \forall\, 1 \leq i,j,k \leq n.\\ \end{array} \] \end{slide} \begin{slide}{} Taking the dual of the dual of MC3 (and removing redundant constraints in the resulting SDP) yields the relaxation SDP3 defined below. Alternatively, for rank-one matrices $X = v v^T, v \in \{\pm1\}^n$. have all their entries equal to $\pm 1$. Hence $Y$ feasible for SDP2 have all their entries in the first row and column equal to $\pm 1$. Now consider the following constraints from SDP2: \[Y_{0,T(i,j)} = \frac{1}{n} \sum\limits_{k=1}^n Y_{T(i,k),T(k,j)}, \,\,\,\forall\, 1\leq i