\begin{filecontents}{seceqn.sty} % seceqn.sty % From TeXhax 89.37 % % Substyle file for use with "article" to cause equations to be numbered % within sections. % % 13 Apr 89 Jerry Leichter \typeout{Document Option `seceqn': 13 Apr 89} \@addtoreset{equation}{section} %Make equation=0 when section steps \def\theequation{\thesection.\arabic{equation}} %How an equation number looks % From NUMINSEC.STY (with SIAM stuff). \@addtoreset{figure}{section} \def\thefigure{\thesection.\@arabic\c@figure} \@addtoreset{table}{section} \def\thetable{\thesection.\@arabic\c@table} \end{filecontents} %\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} \usepackage{seceqn} \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 } \newcommand{\gap}{{\rm gap\,}} \newcommand{\optval}{{\rm optval\,}} \newcommand{\Mat}{{\rm Mat\,}} \newcommand{\offDiag}{{\rm offDiag\,}} \newcommand{\usMat}{{\rm u2sMat\,}} \newcommand{\usvec}{{\rm u2svec\,}} \newcommand{\Kprod}{\otimes} \newcommand{\Kcal}{{\cal K}} \newcommand{\Hcal}{{\cal H}} \newcommand{\tran}{^T} % for Real number sign \newcommand\C{\mathbb C} \newcommand\R{{\Re}} %\newcommand{\eqref}[1]{{\rm (\ref{#1})}} \newcommand{\gesem}{\succeq} \newcommand{\lesem}{\preceq} \newcommand{\Sbar}{\bar{S}} \newcommand{\Qbar}{\bar{Q}} \newcommand{\Tbar}{\bar{T}} \newcommand{\xbar}{\bar{x}} \newcommand{\Xbar}{\bar{X}} \newcommand{\relint}{\rm relint\,} \newcommand{\nc}{\newcommand} \nc{\arrow}{{\rm arrow\,}} \nc{\Arrow}{{\rm Arrow\,}} \nc{\BoDiag}{{\rm B^0Diag\,}} \nc{\bodiag}{{\rm b^0diag\,}} \newcommand{\oodiag}{{\rm o^0diag\,}} \newcommand{\OoDiag}{{\rm O^0Diag\,}} \def\nr{\par \noindent} \nc{\proof}{\bf Proof. \rm \nr} \nc{\Mmn}{{\cal M}_{m,n} } \nc{\eqref}[1]{{\rm (\ref{#1})}} \nc{\kwqqp}{Q{$^2$}P\,} \nc{\kwqqps}{Q{$^2$}Ps} \def\argmin{\mathop{\rm argmin}} \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{\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{\XX}{{\mathcal X} } \newcommand{\ZZ}{{\mathcal Z} } \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}{\begin{equation}} \newcommand{\bet}{\begin{table}} \newcommand{\eet}{\end{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} \begin{document} \bibliographystyle{plain} \begin{slide}{} \begin{center} {\bf \underline{SIMPLE} Efficient Solutions\\ for\\ Semidefinite Programming} \end{center} \vspace{5mm} Henry Wolkowicz \\ \vspace{5mm} Department of Combinatorics \& Optimization \\ University of Waterloo \vspace{10mm} \mbox{ \begin{figure} \psfig{file=UWlogori.ps,height=20mm} \end{figure} } \end{slide} \begin{slide}{} primal and dual SDPs \[ (\mbox{PSDP}) \qquad \begin{array}{ccl} p^* :=&\max & \trace CX\\ &\mbox{s.t.} & \A X = b \\ & & X \succeq 0. \end{array} \] \[ (\mbox{DSDP}) \qquad \begin{array}{ccl} d^* :=&\min & b^Ty\\ &\mbox{s.t.} & \A^* y -Z = C \\ & & Z \succeq 0, \end{array} \] $\Sn$ space of $n \times n$ real symmetric matrices; $X,Z,C \in \Sn$;\\ $\succ 0$ ($\succeq 0$) denotes positive (semi)definiteness \\ ~~~~~(i.e. Loewner partial order);\\ $\A : \Sn \rightarrow \Re^m$ linear operator; $\A^*$ adjoint operator \end{slide} \begin{slide}{} Motivation/Background:\\ Many applications; polynomial time algorithms; difficulty with large sparse problems. SDP (cone optimization) studied back in 1960's; \\ Engineering applications in 60's;\\ matrix completion problems in 80's;\\ polynomial time algorithms Nesterov-Nemirovski 80's;\\ combinatorial applications and p-d i-p algorithms (explosion) in 90's. \end{slide} \begin{slide}{} SDP looks like a linear program (similar development)\\ For p-d i-p path following approach, use e.g. log-barrier on dual-problem to perturbed optimality conditions: \[ F_\mu(X,y,Z):= \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ X -\mu Z^{-1} \end{array} \right) =0. \] square system: $F_\mu: \Sn \times \Re^m \times \Sn \rightarrow \Sn \times \Re^m \times \Sn$ \\ So can apply Newton's method;\\ But: highly nonlinear; slow convergence; condition number of $F_\mu^\prime \rightarrow \infty$ as $\mu \rightarrow 0$. \end{slide} \begin{slide}{} Replace perturbed complementary slackness conditions with \[ ZX-\mu I =0. \] $Z,X$ diagonal in LP case, so $ZX$ is diagonal. But $ZX$ not necessarily symmetric in SDP case, so new $F_\mu: \Sn \times \Re^m \times \Sn \rightarrow \Sn \times \Re^m \times \Mn$, i.e.\\ \begin{center} {\bf overdetermined nonlinear system in SDP case} \end{center} \end{slide} \begin{slide}{} current approach (follows successful LP development; however, nonsquare system resulted in symmetrization approaches); Premultiplication by $Z$ (a form of preconditioning) leads to a less nonlinear system; avoids the ill-conditioning; \[ \pmatrix{ I & 0 & 0 \cr 0 & I & 0 \cr 0 & 0 & Z \cdot } \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ X -\mu Z^{-1} \end{array} \right) = \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ ZX -\mu I \end{array} \right) =0. \] \end{slide} \begin{slide}{} We now precondition a second time using the linear operator ${\cal P}$ with symmetrization operator ${\cal S}: \Mn \rightarrow \Sn$. \[ \begin{array}{rcl} {\cal P}F_\mu(x,y,Z) &=& \pmatrix{ I & 0 & 0 \cr 0 & I & 0 \cr 0 & 0 & {\cal S} } \pmatrix{ I & 0 & 0 \cr 0 & I & 0 \cr 0 & 0 & Z \cdot } \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ X -\mu Z^{-1} \end{array} \right) \\ &=& \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ {\cal S}(ZX) -\mu I \end{array} \right)=0 \end{array} \] However, symmetrizations, in general, reverse previous process, ill-conditioning problem returns;\\ e.g. AHO, HKM, NT, GT, MTW directions \end{slide} \begin{slide}{} For many different symmetrizations, e.g. Monteiro-Zhang family, for given $P$ nonsingular (scale-symmetrize): ${\cal S}(M)=\frac 12 \left(PMP^{-1}+P^{-T}M^TP^T\right)$ \[ \ZZ(\cdot):={\cal S} (Z \cdot );\quad \XX(\cdot):={\cal S} (\cdot X) \] use equation 1; eliminate $\Delta Z$: \[ \pmatrix{ I & 0 & 0 \cr 0 & I & 0 \cr -\XX & 0 & I } \pmatrix{ 0 & \A^* & I \cr \A & 0 & 0 \cr \ZZ & 0 & \XX } = \left( \begin{array}{ccc} 0 & \A^* & I \cr \A & 0 & 0 \cr \ZZ & -\XX\A^* & 0 \end{array} \right). \] \end{slide} \begin{slide}{} use equation 3; eliminate $\Delta X$: \[ \begin{array}{rcl} \vspace{.1in} F_n:= P_nK & := & \pmatrix{ I & 0 & 0 \cr 0 & I & -\A\ZZ^{-1} \cr 0 & 0 & \ZZ^{-1} } \left( \begin{array}{ccc} 0 & \A^* & I \cr \A & 0 & 0 \cr \ZZ & -\XX\A^* & 0 \end{array} \right) \\ &=& \left( \begin{array}{ccc} 0 & \A^* & I_n \cr 0 & \A\ZZ^{-1}X\A^* & 0 \cr I_n & -\ZZ^{-1}X\A^* & 0 \end{array} \right) \end{array} \] algorithm for Newton search direction using the normal equations (need existence of $\ZZ^{-1}$):\\ use the second row (the operator $\A\ZZ^{-1}\XX\A^*$) to solve for $\Delta y$; \\ back solve for $\Delta X$ using the third row ;\\ backsolve for $\Delta Z$ using the first row. \end{slide} \begin{slide}{} condition number for system found using matrix $F_n$, not just matrix $\A\ZZ^{-1}\XX\A^T$. (Though, latter can have uniformly bounded condition number under standard neighbourhood assumptions) \[ F_n^*F_n = \pmatrix{ I_n & -\ZZ^{-1}\XX\A^* & 0 \cr -\A\XX\ZZ^{-1} & (\A\A^*+(\A\ZZ^{-1}\XX\A^*)^2+\A\ZZ^{-2}\XX^2\A^*) & \A \cr 0 & \A^* & I_n }. \] using interlacing of eigenvalues, this operator becomes increasingly ill-conditioned \end{slide} \begin{slide}{} {\bf Simple/Stable Reduction}\\ There are other choices for the above second step for LP, e.g. so-called augmented system or quasi-definite system.\\ Other choices for SDP usually involve {\em dual directions}. New {\em second elimination for SDP}:\\ linear constraint $\A(X)=b$, (onto linear operator $\A$, full rank $m$);\\ range of linear operator $\NN: \Re^{\scriptsize{\pmatrix{n+1\cr 2}-m }} \rightarrow \Sn$ equals null space of $\A$; \\ $\A^\dagger$ generalized inverse; $A \hat{X}=b$: \[ \begin{array}{rcl} \A(X)=b &\mbox{ iff } & X = \A^\dagger b + (I-\A\A^\dagger)V, \quad \mbox{for some } V \in \Sn\\ &\mbox{ iff } & X = \hat{X} + \NN(v), \quad \mbox{for some } v \in \Re^{\scriptsize{\pmatrix{n+1\cr 2}-m }}. \end{array} \] \end{slide} \begin{slide}{} We partition the diagonal matrix $Z,X$ using the vectors $z=\pmatrix{z_m \cr z_v}, \quad x=\pmatrix{x_m \cr x_v}$ with lengths $m,v=n-m$; and we define the matrices $F_s,P_s$ with \[ \begin{array}{rcl} \vspace{.1in} F_s:&=&P_sK=\pmatrix{ I_n & 0 & 0 & 0 \cr 0 & I_m & 0 & 0 \cr 0 & -Z_m & I_m & 0 \cr 0 & 0 & 0 & I_v } \pmatrix{ 0 & 0 & A^T & I_n \cr I_m & E & 0 & 0 \cr Z_m & 0 & -X_m & 0 \cr 0 & Z_v & -X_vE^T & 0 }\\ &=& \pmatrix{ 0 & 0 & A^T & I_n \cr I_m & E & 0 & 0 \cr 0 & -Z_mE & -X_m & 0 \cr 0 & Z_v & -X_vE^T & 0 }. \end{array} \] \end{slide} \begin{slide}{} {\bf Illustrate on SDP Relaxation of Max-Cut problem} MC: \begin{quote} {em Partition of the set of vertices of a given undirected graph with weights on the edges so that the sum of the weights of the edges cut by the partition is maximized.} \end{quote} This NP-hard discrete optimization problem can be formulated as a (quadratic) program (e.g. $Q$ is a multiple of the Laplacian matrix of the graph). \[ (\mbox{MC0}) \qquad \begin{array}{ccl} \mu^* :=&\max & v^{T} Qv \\ &\mbox{s.t.} & v_i^2 = 1, \quad i=1,\ldots,n. \end{array} \] \end{slide} \begin{slide}{} Using e.g. Lagrangian relaxation, get SDP relaxation of (MC): \[ \mbox{(P)} \quad \begin{array}{ccl} \mu^* \leq \nu^*:=&\max & \tr QX \\ &\mbox{s.t.} & \diag(X)= e\\ && X\succeq 0, X \in \Sn, \end{array} \] $\diag$ is vector from the diagonal elements;\\ $e$ (column) vector of ones;\\ wolg $\diag (Q)=0$. And its (strong) dual SDP: \[ (D) \qquad \begin{array}{ccl} \nu^*= &\min & e^Ty\\ &\mbox{subject to} & \Diag(y) -Z = Q \\ & & Z \succeq 0. \end{array} \] $\Diag$ is diagonal matrix from vector \end{slide} \begin{slide}{} Preprocess: for $X \in \Sn$, $\usvec$ columnwise, strict upper triangular part of $X$;\\ $\sqrt{2}$ for isometry: \[ x=\usvec(X) := \sqrt{2} \pmatrix{X_{12} \cr X_{13} \cr X_{23} \cr X_{14} \cr \ldots } \in \Re^{\scriptsize{\pmatrix{n\cr 2}}} \] \[ \usMat:=\usvec^{\dagger} = \usvec^*: \Re^{\scriptsize{\pmatrix{n\cr 2} }} \rightarrow \Sn \] \fbox{ \begin{minipage}{2.55in} \[ \begin{array}{rcl} \diag(X)=e &\mbox{ iff } & X:=I+\usMat(x) ~~ ~~ \mbox{for some } x \in \Re^{\scriptsize{\pmatrix{n\cr 2} }} \end{array} \] \end{minipage} } \end{slide} \begin{slide}{} get single (overdetermined) perturbed optimality condition \[ F_\mu(x,y):=(\Diag(y)-Q)(\usMat(x)+I) -\mu I = 0 \] \[ F_\mu(x,y): \Re^{\scriptsize{\pmatrix{n\cr 2}}} \times \Re^n \rightarrow \Mn. \] \[ \Diag(y)-Q \succeq 0, \quad \usMat(x)+I \succeq 0 \] \end{slide} \begin{slide}{} linearization (or Gauss-Newton equation) for search direction $\Delta x, \Delta y$ is ($\kvec$ is understood) \[ \begin{array}{rcl} - F_{\mu}(x,y) &=& F^{\prime}_{\mu}(x,y) \pmatrix{\Delta x \cr \Delta y} \\ &=& \ZZ (\Delta x) + \XX(\Delta y) \end{array} \] i.e. \[ (\Diag(y)-Q)\usMat(\Delta x) + \Diag(\Delta y)(\usMat(x)+I)= - F_{\mu}(x,y) \] which defines the two linear operators \[ \ZZ, \quad \XX \] \end{slide} \begin{slide}{} This is a linear, full rank, overdetermined system and we find the least squares solution. The first part $\ZZ (\Delta x)$ is the large part of the system since it has $n(n-1)/2$ variables. However, the operator $\ZZ$ is sparse if the data $Q$ is sparse. The second part is the small part since it only has $n$ variables, though the operator $\XX$ is usually dense. This is the size of the normal equations system that arises in the standard approaches for SDP\@. The above system is full rank at each iteration, and, in addition, it has the strong property of being full rank at optimality, i.e. it does not necessarily get ill-conditioned as $\mu$ approaches 0. \end{slide} \begin{slide}{} {\bf START Algorithm} (p-d; GN with PCG)\\ {\bf $\bullet$ Initialization:} \begin{quote} {\bf $\bullet\bullet$ Input data:} a real symmetric $n\times n$ matrix $Q$ (set $\diag(Q)=0$)\\ {\bf $\bullet\bullet$ Positive tolerances:} $\delta_1$ (relative duality gap), $\delta_2$ (accuracy for lss) \\ {\bf $\bullet\bullet$ Find initial feasible points:} \[ \mbox{set: } \qquad \qquad x^0=0;\quad y^0=2\Diag(q) -Q, \] where $q_j= \|Q_{:,j}\|_2$;\\ (guarantees: both $X:=(\usMat (x) +I ),Z:=(\Diag(y)-Q)~\succ~0$. \\ {\bf $\bullet\bullet$ Set initial parameters:} \[ \gap=\trace ZX;~~ \mu=\gap/n;~~\optval=\trace QX;~~k=0. \] \end{quote} \end{slide} \begin{slide}{} {\bf $\bullet$ while} $\{ \frac {\gap}{\mid\optval\mid+1} \} > \delta_1$ \begin{quote} {\bf $\bullet$$\bullet$ solve for the search direction} (to tolerance $\max\left\{ \frac {\delta_2}{10},\frac {\min \{\mu^{\frac 13},1\}}{10^6} \right\}$, in a least squares sense with PCG, using $k$-th iterate $(x,y)=(x^k,y^k)$) \[ ~~~~F^{\prime}_{\sigma \mu}(x,y) \pmatrix{ \Delta x\cr \Delta y } = -F_{\sigma \mu}(x,y), \] where $\sigma_k$ centering, $\mu_k=\trace (\Diag(y)-Q)(\usMat(x)+I)/n $ \[ x^{k+1} = x + \alpha_k \Delta x, \quad y^{k+1} = y + \alpha_k \Delta y; ~~~ \alpha_k > 0, \] so that both $(X:=\usMat(x^{k+1})+I), (Z:=\Diag(y^{k+1})-Q) \succ 0$, before the crossover; so that $\alpha_k=1$ after the crossover.\\ {\bf $\bullet$$\bullet$ update} \[ k \leftarrow k+1 \quad \mbox{ and then update} \] \[ \mu_k, \sigma_k\quad (\sigma_k=0 \mbox{ after the crossover}). \] \end{quote} {\bf $\bullet$ end (while)}.\\ {\bf $\bullet$ Conclusion: } optimal $X$ is approx. $\usMat (x) +I$\\ {\bf END ALGORITHM} \end{slide} \begin{slide}{} {\bf Optimal Diagonal Column Preconditioning} for $A, m \times n, m \geq n$ a full rank matrix, \\ solution of optimization problem\\ $\min \omega ( (AD)^T(AD))$, over all positive diagonal matrices $D$, \\ condition number $\omega (K) = \frac{\trace (K)/n}{\det (K)^{\frac 1n}}$\\ \begin{center} optimum: $D_{rr}= \frac 1{\|A_{:r}\|}$. \end{center} \end{slide} \begin{slide}{} columns of the operator $F^\prime(x,y)(\cdot,\cdot) = \ZZ(\cdot) + \XX(\cdot)$\\ ($F^\prime = \left[ \ZZ ~|~ \XX \right]$)\\ ordered using $c=1,2,\ldots$, $c$ represents $(k,j),~1\leq k= \\ ~~~= \frac 12 \usvec(E_{ij})^T \usvec \left\{Z^2E_{kl}+E_{kl}Z^2 \right\}\\ ~~~= \frac 12 \trace (E_{ij}) \left\{Z^2E_{kl}+E_{kl}Z^2 \right\}\\ ~~~= \trace E_{ij} E_{kl}Z^2\\ ~~~= \frac 12\left\{ \delta_{jk} (Z^2)_{li}+ \delta_{jl} (Z^2)_{ki}+ \delta_{ik} (Z^2)_{lj}+ \delta_{il} (Z^2)_{kj} \right\}. \end{array} \eeq Can exploit graph structure since sparsity patterns of $Z,Q$ are the same. \end{slide} \begin{slide}{} {\bf Crossover Criteria} Advantage of GN approach: full rank and zero residual. Therefore, there is a local neighbourhood of quadratic convergence for affine scaling with step lengths of one without backtracking to maintain positive definiteness. \end{slide} \begin{slide}{} \[ \begin{array}{rcl} \|F^\prime (\Delta s)\|_F &=& \|Z\usMat (\Delta x) + \Diag (\Delta y)X\|_F \\ &\leq& \|Z\usMat (\Delta x)\|_F + \|\Diag (\Delta y)X\|_F \\ &\leq& \|Z\|_F\|\usMat (\Delta x)\|_F + \|\Diag (\Delta y)\|_F\|X\|_F \\ &=& \|Z\|_F\|\Delta x\|_2 + \|\Delta y\|_2\|X\|_F \\ &\leq& \sqrt{\|Z\|^2_F + \|X\|^2_F}\|\Delta s\|_2, \mbox{ (by C-S ineq.)}\\ \end{array} \] bound on the norm of the Jacobian is $\alpha =\sqrt{\|Z\|^2_F + \|X\|^2_F}.$ \[ \begin{array}{lcl} \|F^\prime (s-\bar{s}) (\Delta s)\|_F =\\ ~~= \|(Z-\bar{Z})\usMat (\Delta x) + \Diag (\Delta y)(X-\bar{X})\|_F \\ ~~\leq \|(Z-\bar{Z})\|_F\|\usMat (\Delta x)\|_F + \|\Diag (\Delta y)\|_F \|(X-\bar{X})\|_F \\ ~~= \|(y-\bar{y})\|_2\|\Delta x\|_2 + \|\Delta y\|_2 \|(x-\bar{x})\|_2. \\ \end{array} \] Lipschitz constant is $\gamma =1$. \end{slide} \begin{slide}{} suppose optimum $s^*$ is unique and the smallest singular value satisfies $\sigma_{\min} (F^\prime(s)) \geq \sqrt{K}$, for all $s$ in an $\epsilon_1$ neighbourhood of $s^*$, for some constant $K>0$. Then q-quadratic convergence is guaranteed once the current iterate is in the \[ \epsilon:= \min\left\{ \epsilon_1,\frac 1{K\alpha \gamma} \right\} = \min\left\{ \epsilon_1,\frac 1{K \sqrt{\|Z^*\|^2_F+\|X^*\|^2_F} }\right\}. \] neighbourhood of the optimum. Heuristic: start the crossover if $\sigma_{\min} (F^\prime(s)) \geq 2 \|ZX\|_2$. In our tests we started the crossover when the relative duality gap $\frac {\trace ZX}{|\trace QX|+1}<.1$; this simpler heuristic never failed to converge, q-quadratic convergence was detected empirically. \end{slide} \begin{slide}{} {\bf Numerical Tests} The crossover to using a steplength of 1, not maintaining interiority, and using affine scaling, has a significant effect on both the number of iterations and the conditioning of the linear system. The number of iterations are approximately halved. The best results were obtained by staying well-centered before the crossover. The tests were done using MATLAB 6.0.0.88 (R12) on a SUNW, Ultra $5-10$ with one GB of RAM using SunOS 5.8 (denoted by SUN), as well as on a Toshiba Pentium II, 300 MHZ, with 128 MB of RAM (denoted by PII). $99\%$ of the cputime was spent on finding the search direction. \end{slide} \begin{slide}{} The cost for the early iterations was very low, e.g. $21,50$ CG iterations, $24,58$ cpu seconds for the first two iterations for $n=365$ on the SUN. This cost increased as the relative duality gap (and the requested tolerance for the least squares solution) decreased. Low accuracy solutions were obtained quickly, e.g. one decimal accuracy after 4 to 5 iterations. The cost per iteration increased steadily and then levelled off near the optimum. \end{slide} \begin{slide}{} \small{ \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Cross. tol. & nmbr &norm(ZX) at end &min. eig. pos. \\ in rel. gap& iter& &violation in $Z,X$\\ \hline 1.0e-1 & 11 & 3.6281e-12 & -4.6478e-12\\ 1.0e-3 & 14 & 1.9319e-13& -2.1580e-13\\ 1.0e-5 & 16 & 2.0917e-11& -2.2839e-11\\ 1.0e-7 & 18 & 1.8293e-13& -1.5546e-13\\ 1.0e-9 & 20 & 7.2534e-10& 6.7006e-12\\ 1.0e-11 & 20 & 7.2544e-10& 6.7004e-12\\ \hline \end{tabular} \caption{Size of Q, $n=25$; Requested Accuracy in relative duality gap: 1.0e-10; Density is $\frac 1{25}$; Optimal Value is 5.7041e+01. } \eet } \end{slide} \begin{slide}{} \small{ \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Dim. of $Q$ & total cpu sec. & nmbr &norm(ZX) &violation of \\ $n$& & iter& at end &eig. pos. in $Z,X$\\ \hline 55 & 6.6000e+01 & 11 & 9.0884e-09 &-1.7515e-08\\ 65 & 1.1234e+02 & 11 & 7.2081e-10 &-2.5326e-09\\ 75 & 1.9134e+02 &13 & 2.1361e-11 &-1.7416e-10\\ \hline \end{tabular} \caption{Requested Accuracy in relative duality gap: 1.0e-10; Density is $\frac 1n$; crossover tolerance 1.0e-01; optimal values of order 150; SUN computer. } \label{table:density} \eet } \end{slide} \begin{slide}{} {\small \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Dim. of $Q$ & total cpu sec& nmbr &norm(ZX) at &violation of \\ $n$& & iter& end &eig. pos. in $Z,X$\\ \hline 165 & 2635 & 14 & 7.7056e-14 & -2.775e-14 \\ 175 & 6778.6 & 15 & 8.0369e-14 & -2.5371e-14 \\ 185 & 6908.8 & 15 & 9.0987e-14 & -4.011e-14 \\ 195 & 11397 & 15 & 1.7324e-12 & -3.2036e-11 \\ 205 & 8958.5 & 15 & 1.0029e-13 & -3.7858e-14 \\ \hline \end{tabular} \caption{Toler. relative duality gap: 1.0e-14; Density $\frac 1n$; cross. tol. 1.0e-01; opt. values order 1000; SUN computer. } \label{table:densityacc14} \eet } \small{ \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Dim $Q$ & total cpu sec& nmbr &norm(ZX) at &violation of \\ $n$& & iter & end &eig. pos. in $Z,X$\\ \hline 15 & 7.75 & 9 & 1.7535e-014 & -3.0863e-015 \\ 25 & 17.36 & 10 & 1.9291e-013 & -1.5217e-013 \\ 35 & 30.43 & 10 & 1.1044e-012 & -8.4977e-013 \\ 45 & 59.87 & 11 & 2.7926e-011 & -2.763e-011 \\ 55 & 86.89 & 12 & 4.0912e-011 & -3.7568e-011 \\ 65 & 131.11 & 11 & 4.9924e-012 & -5.0519e-012 \\ 75 & 275.89 & 12 & 1.0448e-008 & -1.4504e-008 \\ 85 & 468.46 & 14 & 8.6208e-011 & -3.4404e-010 \\ 95 & 414.03 & 11 & 7.4253e-011 & -3.0935e-010 \\ 105 & 878.64 & 15 & 7.5993e-010 & -1.4946e-008 \\ \hline \end{tabular} \caption{Tol. in rel. duality gap: 1.0e-10; Density is $\frac 3n$; cross. toler. 1.0e-01; optimal values of order 150; PII computer. } \label{table:densityPII} \eet } \end{slide} \begin{slide}{} \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Dim of $Q$ & total cpu sec & nmbr &norm(ZX) &violation of \\ $n$& & iter & at end &eig. pos. in $Z,X$\\ \hline 15 & 30.1 & 11 & 1.9039e-011 & -3.5098e-012 \\ 25 & 134.13 & 15 & 1.9742e-009 & -2.7465e-010 \\ 35 & 117.27 & 12 & 2.5534e-010 & -8.8532e-011 \\ 45 & 174.34 & 11 & 1.3799e-008 & -1.9154e-008 \\ 55 & 373.6 & 14 & 7.3741e-009 & -3.1854e-009 \\ 65 & 1388.1 & 19 & 9.6109e-009 & -2.7634e-009 \\ 75 & 507.46 & 13 & 3.5887e-009 & -3.3886e-009 \\ 85 & 1856.1 & 16 & 6.4806e-011 & -4.7964e-011 \\ \hline \end{tabular} \caption{{\bf Without preconditioning}; Requested Accuracy in relative duality gap: 1.0e-10; Density is $\frac 3n$; crossover tolerance 1.0e-01; optimal values of order 150; PII computer. } \label{table:densityPIIa} \eet \end{slide} \begin{slide}{} \bet[htbp] \centering \begin{tabular}{|c|c|c|c|c|}\hline Dim of $Q$ & cpu sec & nmbr &norm(ZX) &violation of \\ $n$& & iter & at end &eig. pos. in $Z,X$\\ \hline 155 & 5493.6 & 14 & 6.068e-014 & -4.3061e-013 \\ 165 & 4595.4 & 13 & 3.8625e-014 & -2.8454e-013 \\ \hline \end{tabular} \caption{Requested Accuracy in relative duality gap: 1.0e-14; Density is $\frac 1n$; crossover tolerance 1.0e-01; optimal values of order 150; PII computer. } \label{table:densityPII2} \eet \begin{figure} \epsfxsize=250pt \centerline{\epsfbox{meritplot.ps}} %\includegraphics[totalheight=3in]{meritplot.pdf} %\includegraphics[width=6in]{meritplot.pdf} \caption{$n=55$. Crossover at iteration 7. } \label{fig:plotmerit} \end{figure} \begin{figure} \epsfxsize=250pt \centerline{\epsfbox{nnzcpu.ps}} %%\includegraphics[totalheight=3in]{nnzcpu.pdf} %\includegraphics[width=6in]{nnzcpu.pdf} \caption{Nonzeros vs cputime. $n=15:10:105$. } \label{fig:plotnnzvscpu} \end{figure} %\includegraphics{nnzcpu.pdf} %see URL: http://www.math.uwaterloo.ca/~consulta/greatest-hits/tex.html#pdf \end{slide} \begin{slide}{} \small{ \bet[htbp] \label{table:densityacc14latest1} \centering \begin{tabular}{|c|c|c|c|c|c|c|}\hline Dim & cpu sec & &opt. val. & rel. $\|ZX\|$ &rel. eig. viol. & nnz\\ $n$& & iter. & at end & at end &pos. $Z,X$ & in $Q$\\ \hline 165 & 1120 & 14 & 869.61 & 8.9414e-17 & -3.3566e-17 & 476\\ 175 & 1891 & 15 & 928.97 & 8.5746e-17 & -3.2607e-17 & 504\\ 185 & 3079.6 & 15 & 1041.8 & 8.9598e-17 & -3.7512e-17 & 538\\ 195 & 3251.9 & 14 & 1045.7 & 8.2733e-17 & -4.2463e-17 & 572\\ 205 & 5874.7 & 17 & 1207.7 & 1.0142e-16 & -3.5923e-17 & 602\\ \hline \end{tabular} \caption{Random problems; Requested Accuracy in relative duality gap: 1.0e-14; Density is $\frac 1n$; crossover tolerance 1.0e-01; optimal values of order 1000; SUN computer. } \eet } \end{slide} \begin{slide}{} \tiny{ \bet[htbp] \label{table:SUNdensityacc14latest2} \centering \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}\hline Dim & cpu sec & cpu sec & cpu sec & &opt. & rel. $\|ZX\|$ &releig. viol. & nnz\\ $n$& 1 dec & 7 dec & 14 dec & iter. & at end & at end &pos. $Z,X$ & in $Q$\\ \hline 100 & 39.66 & 127.23 & 192.36 & 13 & 226.16 & 2.5926e-17 & -5.0771e-17 & 638\\ 124 & 70.93 & 351.73 & 502.57 & 14 & 141.99 & 3.3609e-17 & -2.8961e-16 & 410\\ 124 & 71.15 & 241.03 & 342.4 & 14 & 269.88 & 4.4706e-17 & -1.0508e-16 & 760\\ 124 & 56.32 & 392.78 & 547.51 & 14 & 467.75 & 2.3752e-17 & -3.3513e-17 & 1364\\ 124 & 82.79 & 370.25 & 577.79 & 14 & 864.41 & 1.6515e-16 & -8.7386e-16 & 2666\\ 250 & 648.9 & 2339.9 & 3087.2 & 15 & 317.26 & 2.1095e-16 & -4.7591e-15 & 892\\ 250 & 537.79 & 2384 & 2805.6 & 14 & 531.93 & 2.8552e-16 & -5.5422e-16 & 1472\\ 250 & 620.82 & 3844.2 & 5620 & 13 & 981.17 & 2.7276e-17 & -2.6909e-16 & 2816\\ 250 & 947.5 & 7834.3 & 10893 & 15 & 1682 & 6.5743e-16 & -2.2708e-15 & 5092\\ 500 & 6729.4 & 32472 & 42094 & 20 & 598.15 & 2.9931e-17 & -1.5378e-16 & 1701\\ 500 & 5422.5 & 38232 & 59391 & 18 & 1070.1 & 7.2114e-16 & -9.7197e-15 & 2939\\ 500 & 7282.3 & 42758 & 58360 & 16 & 1848 & 1.2577e-15 & -2.0375e-14 & 5210\\ 500 & 11548 & 80822 & 1.3137e+05 & 17 & 3566.7 & 6.1352e-15 & -5.7 509e-14 & 10740\\ \hline \end{tabular} \caption{Requested Accuracy in relative duality gap: 1.0e-14; SDPLIB test problems; crossover tolerance 1.0e-01; SUN computer. } \eet } \tiny{ \bet[htbp] \label{table:densityacc14latest2} \centering \begin{tabular}{|c|c|c|c|c|c|c|}\hline Dim $Q$ & cpu sec & major &rel. opt. & rel. norm(ZX) &rel. viol. & nnz\\ $n$& & iter. & at end & at end &eig. pos. $Z,X$ & in $Q$\\ \hline 100 & 96.34 & 12 & 226.16 & 1.2399e-13 & -1.2062e-12 & 638\\ 124 & 252.57 & 13 & 141.99 & 1.2238e-14 & -2.3655e-13 & 410\\ 124 & 171.99 & 13 & 269.88 & 2.0918e-11 & -1.1324e-11 & 760\\ 124 & 292.48 & 13 & 467.75 & 7.0013e-13 & -5.9152e-13 & 1364\\ 124 & 289.21 & 13 & 864.41 & 5.7229e-11 & -1.035e-11 & 2666\\ 250 & 1134.9 & 14 & 317.26 & 2.9025e-11 & -5.5891e-11 & 892\\ 250 & 1058.3 & 14 & 531.93 & 2.8552e-16 & -5.5638e-16 & 1472\\ 250 & 1633.6 & 12 & 981.17 & 8.9829e-12 & -5.8956e-12 & 2816\\ 250 & 3036 & 14 & 1682 & 3.481e-11 & -2.1537e-11 & 5092\\ 500 & 14669 & 19 & 598.15 & 4.12e-13 & -2.9424e-12 & 1701\\ 500 & 21489 & 17 & 1070.1 & 1.0229e-11 & -2.7013e-11 & 2939\\ 500 & 20691 & 15 & 1848 & 3.6924e-11 & -1.364e-11 & 5210\\ 500 & 46752 & 16 & 3566.7 & 3.3634e-11 & -1.5e-11 & 10740\\ \hline \end{tabular} \caption{Requested Accuracy in relative duality gap: 1.0e-10; SDPLIB test problems; crossover tolerance 1.0e-01; SGI (Irix$6.5\_64$-Mips) computer. } \eet } \end{slide} \end{document} \bf{Outline} \begin{enumerate} \item Semidefinite Programming (SDP) background (comparisons/differences with Linear Programming (LP)) \end{enumerate} \end{slide} \begin{slide}{} The \underline{primal SDP/LP} we consider is \[ (\mbox{PSDP}) \qquad \begin{array}{ccl} p^* :=&\max & \left \quad (=\trace CX)\\ &\mbox{s.t.} & \A X = b \\ & & X \succeq 0. \end{array} \] Its \underline{dual} is \[ (\mbox{DSDP}) \qquad \begin{array}{ccl} d^* :=&\min & b^Ty\\ &\mbox{s.t.} & \A^* y -Z = C \quad (\A^* y \succeq C)\\ & & Z \succeq 0, \end{array} \] where:\\ $X,Z \in \Sn$, space of $n \times n$ real symmetric matrices\\ $\succeq$ denotes positive semidefiniteness;\\ $\A : \Sn \rightarrow \Re^m$ linear operator; $\A^*$ is the adjoint operator \end{slide} \begin{slide}{} SDP is like LP.\\ But, some subtle differences. Weak duality: $p^* \leq d^*$ holds. But: strong duality can fail, i.e. there can exist a nonzero duality gap at optimality $p^* < d^*$ and/or the dual may not be attained. \end{slide} \begin{slide}{} with constraint qualification (e.g. Slater's strict feasibility) {\bf THEOREM.} Suppose that suitable constraint qualifications hold for (PSDP), (DSDP). The primal-dual variables $(X,y,Z)$, with $X,Z \succeq 0$, are optimal for the primal-dual pair of SDPs if and only if \[ F(X,y,Z):= \left( \begin{array}{cl} \A^* y -Z - C \\ \A X -b \\ ZX \end{array} \right) =0. \] \epr $F: \Sn \times \Re^m \times \Sn \rightarrow \Sn \times \Re^m \times \Mn$, (overdetermined)\\ $\Mn$ space of $n \times n$ matrices,\\ (product $ZX$ is not necessarily symmetric) \end{slide} \begin{slide}{} \bibliography{.master,.psd,.publs,.edm,.qap} \end{slide} %\end{multicols} \end{document}