% % massey08_talk.tex % % This is my talk at Massey University on June 10, 208. % Based on work done with Levent Tuncel and Henry Wolkowicz % % This file requires input from the following files: % massey08_talk.mac % seminar.bug % seminar.bg2 % seminar.bg3 % % \documentclass{seminar} %%%%%%%%%%%%%%%% %%% Packages %%% %%%%%%%%%%%%%%%% \usepackage{epsfig} \usepackage{fancyhdr} \usepackage{fancybox} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{amstext} \usepackage{verbatim} \usepackage{url} \usepackage{boxedminipage} \usepackage{graphicx} \usepackage{dcolumn} % column alignment \usepackage{epic} % enhancements to picture environment \usepackage[usenames]{color} \usepackage{pstricks} \usepackage{semlayer} % for overlays \usepackage{semcolor} %\usepackage{slidesec} \usepackage{framed} %\usepackage[draft,bookmarks=false]{hyperref} % Must come last %\usepackage[bookmarks=false]{hyperref} % Must come last so it doesn't get overridden %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Overlay preamble code %%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% For overlays, to force printer to print all preceding ones. %% The general form of an overlay is: %% \bo{1}{Overlay text here}\eo %% \bo{2}{Overlay text here}\eo etc. % The following code is in my macros file % \makeatletter % \def\pst@initoverlay#1{% % \pst@Verb{% % /BeginOL {dup (all) eq exch TheOL le or {IfVisible not {Visible % /IfVisible true def} if} {IfVisible {Invisible /IfVisible false def} if} % ifelse} def % \tx@InitOL /TheOL (#1) def}} % \makeatother %%%%%%%%%%%%%%%%%%%% %%%% Input files %%% %%%%%%%%%%%%%%%%%%%% \input{massey08_talk.mac} \input{seminar.bug} \input{seminar.bg2} % See the Seminar bugs list \input{seminar.bg3} % Unofficial bug fixes %\usepackage{fixseminar} % has to be loaded after hyperref? %%%%%%%%%%%%%%%%%%%% %%% Slide Set-up %%% %%%%%%%%%%%%%%%%%%%% %\landscapeonly %\def\printlandscape{\special{landscape}} % works with dvips, not dvi2pdf \renewcommand{\printlandscape}{\special{landscape}} % Workaround to use hyperref and landscape slides % Remove if you are using portrait slides \makeatletter % A4 paper: \def\special@paper{297mm,210mm} % uncomment to produce landscape; but comment the next line (and uncomment % the \twoup line to produce portrait twoups. %\def\special@paper{11in,8.5in} \makeatother \twoup %\psdraft % \setlength{\slidewidth}{8.5in} % \setlength{\slideheight}{6.3in} % \def\SeminarPaperWidth{210truemm} % \def\SeminarPaperHeight{297truemm} \addtolength{\slideheight}{.5in} \renewcommand{\slidetopmargin}{.35in} % \sliderotation{right} %% Note that I can also define \pagestyle immediately after \begin{document} %\pagestyle{empty} \slideframe{shadow} %% only generate some slides: % \onlyslides{1-3,4,8} %%% The following is needed since \maketitle sets \pagestyle to plain. %\thispagestyle{fancy} %\rhead{\textbf{\Large{\orchid{\thepage}}}} %% Change page number labels (MUST COME AFTER THE PAGE MARGIN SETTINGS ABOVE) %\usepackage{fancyhdr} %\pagestyle{fancy} %\renewcommand{\headrulewidth}{0pt} %\renewcommand{\footrulewidth}{0pt} %%% I want a right-aligned header and no (default) centered footer %\rhead{\textbf{\Large{\orchid{\thepage}}}} %\lhead{} \cfoot{\vspace{-30pt}\hfill{\scriptsize \theslide/\pageref{final_page}}\hspace{8pt}} % Headers and footers personalization using the fancyhdr package % \fancyhead{} % Clear all fields \renewcommand{\headrulewidth}{0mm} \renewcommand{\footrulewidth}{0mm} % \fancyhead[C]{\large\textbf{My Title}} % \fancyfoot[L]{\thedate} % \fancyfoot[C]{} % \fancyfoot[R]{\small Page \theslide} % To center horizontally the headers and footers (see seminar.bug) \renewcommand{\headwidth}{\textwidth} % % To adjust the frame length to the header and footer ones \autoslidemarginstrue % To avoid that the headers be too close of the top of the page % \renewcommand{\slidebottommargin}{0.3in} %\pagestyle{fancy} % put a psbox around math in the same way that it would around text \everypsbox{\psmathboxfalse} %% \renewcommand{\headwidth}{\textwidth} % import eps files at their original size. \epsfslidesize % Additional local settings \setlength{\parskip}{1.5ex}% % \enlargethispage*{30pt} %%%%%%%%%%%%%%%%%%%%%%%% %%% Column Alignment %%% %%%%%%%%%%%%%%%%%%%%%%%% \newcolumntype{d}[1]{D{.}{.}{#1}} %%%%%%%%%%%%% %%% Title %%% %%%%%%%%%%%%% \renewcommand{\title}[1]{\begin{center}{\Large \sc #1}\end{center}} %%%%%%%%%%%%%%%%%%%%%%%%% %%% Centered Minipage %%% %%%%%%%%%%%%%%%%%%%%%%%%% \newenvironment{cminipage}[1] % centered minipage {\begin{center}\begin{minipage}{#1}\raggedright} {\end{minipage}\end{center}} %%%%%%%%%%%%%%%%%%%%%%%% %%% Local macros %%% %%%%%%%%%%%%%%%%%%%%%%%% % \renewcommand{\ss}{\smallskip\\}% Note the line break % \newcommand{\ms}{\medskip\\}% Note the line break % \newcommand{\bs}{\bigskip\\}% Note the line break %% The following command reduces the column separation between the %% vertical lines in the table, and the beginning of each entry. %\newcommand{\cs}{@{\extracolsep{4pt}}}% % Create table with additional struts %\newcommand\tstrut{\rule{0pt}{3.3ex}} % Top strut %\newcommand\bstrut{\rule[-1.9ex]{0pt}{0pt}} % Bottom strut %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% BEGIN DOCUMENT %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%% Abstract and Keywords %%%%%%%%%%%%%%%%%%% \begin{comment} \textbf{Location:} Massey University \textbf{Title:} \textbf{Date:} June 10, 2008 \textbf{Speaker:} Simon Schurr \begin{abstract} \end{abstract} \end{comment} \begin{comment} Things to check: % -- Use 10pt font or less in slide format % -- I cannot mentioned cones before the notation slide. % -- Use color consistently: blue for important math % and red for important new terms/words. % -- Remember the audience may not be familiar with convex/conic optimization. % -- ensure titles of page are consistent with outline bullets. \end{comment} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Global setting \sffamily \pagestyle{fancy} \begin{slide}%[8.5in,7in] \begin{cminipage}{.95\textwidth} \begin{center} \blue{\large Strong Duality and Stability\\[4pt] in Conic Convex Optimization }\\[25pt] \green{Simon Schurr\\[4pt] University of Waterloo\\[4pt] spschurr@uwaterloo.ca\\[20pt] Joint work with Levent Tun{\c{c}}el and Henry Wolkowicz}\\[25pt] Massey University\\[4pt] June 2008 \end{center} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.98\textwidth} \vspace{-0.3\semin} \title{Outline} \par\vspace{0.3\semin} \begin{itemize} \mitem \textbf{Strong duality in convex optimization} \mitem \textbf{Guaranteeing strong duality} \mitem \textbf{Solving ill-posed convex programs via stable auxiliary problems} \mitem \textbf{Numerical results} \mitem \textbf{Relating strict complementarity to finite nonzero duality gaps} \mitem \textbf{Conclusions and future work} \end{itemize}%%% \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ptsize{9} \begin{slide} \begin{cminipage}{.92\textwidth} \title{Duality in linear programming (LP)} \par\vspace{0.1\semin} Data: $A \in \Rmn$, $b \in \Rm$, and $c \in \Rn$.\\ Primal problem: \blue{\vspace{-6pt} \begin{align*} v_P &= \min\limits_{x}\;\{c^T x :\ Ax=b,\ x \geq 0\}\\ &= \min_x\ \max_{s \geq 0,y}\ L(x,y,s), \end{align*} }% end of \blue where $L(x,y,s) := c^T x - y^T (Ax-b) - s^T x$ is the Lagrangian. \medskip Dual problem: \blue{\vspace{-6pt} \begin{align*} v_D &= \max_{s \geq 0,y}\ \min_x\ L(x,y,s)\\ &= \max\limits_{s,y}\;\{b^T y :\ A^T y + s = c,\ s \geq 0\}. \end{align*} } \red{Weak duality} holds for this pair of problems: \blue{$v_P \geq v_D$}. Proof: $\min_x \max_y F(x,y) \geq \max_y \min_x F(x,y)$ for \textit{any} function $F(x,y)$, provided the minima and maxima are attained. \medskip The nonnegative quantity $v_P - v_D$ is called the \red{duality gap}. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.9\textwidth} \title{Strong duality for LP} \par\vspace{-0.1\semin} \blue{\vspace{-0.2\semin} \begin{align*} v_P &= \min\limits_{x}\;\{c^T x :\ Ax=b,\ x \geq 0\},\\ v_D &= \max\limits_{y,s}\;\{b^T y :\ A^T y + s = c,\ s \geq 0\}. \end{align*} } % end of \blue \red{Strong duality} holds for both problems. That is,\\ (1) $v_P$ finite $\rra v_P = v_D$ and $v_D$ is attained, and\\ (2) $v_D$ finite $\rra v_P = v_D$ and $v_P$ is attained. \medskip Alternatively, either:\\ (a) $v_P = v_D$ is finite and both values are attained, or\\ (b) at least one problem is infeasible. \bigskip Importance of strong duality: \bi \nitem Optimal dual variables (``Lagrange multipliers'') can be used in sensitivity analysis. \nitem Many classes of algorithms converge only if the duality gap is $0$. \nitem Certificate of optimality can be found. \ei \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{1.02\textwidth} \vspace{-0.1\semin} \title{Strong duality can fail for nonlinear problems} \par\vspace{-0.2\semin} \beas \hspace{-8pt}\mbox{Consider}\hspace{15pt} \ptsize{8} \sup\limits_{y \in \R^2}\;\left\{-y_2\ :\ S = \arr{ccc}{1+y_2&0&0\\0&y_1&y_2\\0&y_2&0},\ S \text{ is PSD}\right\}. \eeas \smallskip \ptsize{9} Solution set is\vspace{-3pt} \begin{align*} \ptsize{8} y^* \in \left\{\arr{c}{y_1\\ 0}: y_1 \geq 0\right\},\qquad S^* \in \left\{\arr{ccc}{ 1 & 0 & 0\\ 0 & s_{22} & 0\\ 0 & 0 & 0}: s_{22} \geq 0 \right\}. \ptsize{9} \end{align*} Primal and dual optimal values are attained, but duality gap is $1$. \smallskip The software package Sedumi $1.1$ gives the primal ``solution'' \begin{align*} \ptsize{8} y = \arr{c}{ 4.6 \times 10^7 \\ -0.38 }, \qquad S = \arr{ccc}{ 0.62 & 0 & 0 \\ 0 & 4.6 \times 10^7\hspace{-10pt}& -0.38\\ 0 & -0.38 & 0}\!. \end{align*} \smallskip \ptsize{9} Dual solution is also found, but $S$ is not PSD and duality gap $= -0.13$. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.96\textwidth} \vspace{-0.2\semin} \title{Formulations of convex optimization problems} \par\vspace{0.4\semin} Minimize a convex function over a closed convex set: \beas \inf\limits_{x \in S}\; f(x), \eeas where $f: \Rn \to \R$ is convex, and $S \subset \Rn$ is a closed convex set. \medskip $S$ may be specified in terms of nonlinear inequalities $\{x: g_i(x) \leq 0,\ i=1,\cdots,m\}$, where each $g_i$ is a convex function. \bigskip Writing an explicit dual can be difficult or impossible, so primal-dual algorithms might not be suitable. \bigskip $\rightarrow$ Write the problem in \red{conic form}: the objective function becomes linear, and the feasible set is expressed as the intersection of an \red{affine subspace} and a \red{convex cone}. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.96\textwidth} \title{Preliminaries and notation for cones} \par\vspace{0.0\semin} \begin{itemize} \mitem A set $K \subset \Rn$ is a \red{cone} if for every $\lambda \geq 0$ and $x \in K$, $\lambda x \in K$.%% \bitem %\sloppy %\hspace{-10pt}% \begin{tabular}{ll} %\hspace{-10pt} \raisebox{20pt}{\hspace{-10pt} \begin{minipage}{202pt} \vspace{-17pt} % \hspace{-10pt} Given $K \subset \Rn$, denote its \red{interior} by $\Int(K)$, and its \red{dual} by \mbox{$K^*:= \{x\in\Rn: \langle x,y \rangle \geq 0\ \forall\,y\in K\}.$} \vspace{15pt} \end{minipage}% }% end of \raisebox & \hspace{-13pt}\raisebox{-10pt}{\scalebox{.4}{\input{dual3.pstex_t}}}\vspace{-28pt}%% \end{tabular}\\[4pt] %\fussy % to over-ride sloppy command issue earlier. % \bigskip \vspace{15pt} \bitem A cone $K$ is \red{proper} if it is closed, convex, has nonempty interior,\\ and contains no straight lines.\\ If $K$ is proper, so is $K^*$. \medskip E.g., the nonnegative orthant, $K = \{x \in \Rn: x_i \geq 0,\ i=1,\cdots,n\}$, is a proper cone. \bitem $x \preceq_K y$ denotes a partial order induced by $K$, i.e.,~$y-x \in K$.\\ Write $x \prec_K y$ if $y-x \in \Int(K)$. \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.96\textwidth} \vspace{-0.2\semin} \title{Primal-dual conic convex formulation} \par\vspace{0.3\semin} Any primal-dual pair of convex problems can be written in conic form: \blue{ \begin{align} v_P &= \sup\limits_{y}\;\{\langle b,y \rangle :\ A^* y \preceq_K c\}, \tag{$\P$}\label{eq:P}\\ v_D &= \inf\limits_{x}\;\{\langle c,x \rangle :\ Ax=b,\ x \succeq_{K^*} 0\}. \tag{$\D$}\label{eq:D} \end{align} }% end of \blue where $A$ is an onto linear operator between vector spaces,\\ its adjoint is $A^*$, and $K$ is a proper cone. \bigskip Important special cases: \begin{itemize} \item If $K$ is the nonnegative orthant, then \eqref{eq:P} and \eqref{eq:D} are LPs. \item If $K$ is the (proper) cone of positive semidefinite matrices $\Sn_+$, then $K^*=K$, and \eqref{eq:P} and \eqref{eq:D} are \red{semidefinite programs} (SDPs). \item If $K = \{x\in \Rn: x_1 \geq \sqrt{x_2^2 + \cdots + x_n^2}\}$, then $K^*=K$, and \eqref{eq:P} and \eqref{eq:D} are \red{second-order cone programs} (SOCPs). \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.99\textwidth} \vspace{-0.4\semin} \title{Two important convex cones} \par\vspace{0.5\semin} \begin{figure*}[htbp] \hspace{-15pt} %\centering \includegraphics[width = 2.2\textwidth]{cone_plots.eps} %\caption{....} %\label{fig:cones} \end{figure*} \vspace{-40pt} The cone of PSD matrices of order $2$ and the second-order cone of dimension $3$. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.93\textwidth} \title{Application: relaxation of hard discrete optimization problems} \vspace{0.2\semin} \ptsize{8} \textbf{Maximum cut of a graph:} Given a weighted undirected graph $G = (V,E)$, find a set $S \subset V$ such that the weight of the cut $(S,V\setminus S)$ is maximal. \begin{minipage}{260pt} \begin{center} \scalebox{0.2}{\input{max_cut.pstex_t}} \end{center} \end{minipage} \vspace{7pt} Let $V = \{1,\cdots,n\}$, $w_{ij} \geq 0$ be the weight of edge $(i,j) \in E$, and let $x \in \{-1,1\}^n$ be the incidence vector of a cut of $G$. We wish to solve \begin{align*} w^* &:= \max_x \bigg\{\frac{1}{4} \sum_{(i,j) \in E} w_{ij}(1 - x_i x_j): x \in \{-1,1\}^n \bigg\}\\ &= \max_x \bigg\{\frac{1}{4} x^T L x : x \in \{-1,1\}^n \bigg\}, \end{align*} where $L$ is the Laplacian of the graph. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \title{Application: relaxation of hard discrete optimization problems} \vspace{0.1\semin} \ptsize{8} \[ \hspace{-25pt}\mbox{Since } x \in \{-1,1\}^n \lra x_i^2 = 1\ \forall\,i, \quad \blue{w^* = \max_x \bigg\{\frac{1}{4} x^T L x: x_i^2 = 1\ \forall\,i \bigg\}}. \] The Lagrangian dual is \begin{align} (w^* \leq)\ v^* &:= \min_{\lambda}\ \max_x \bigg\{\frac{1}{4} x^T L x - \sum_{i=1}^n \lambda_i(x_i^2 - 1) \bigg\}\nn\\ &= \min_{\lambda}\ \bigg\{\sum_{i=1}^n \lambda_i: \bigg(\diag(\lambda)- \frac{1}{4}L\bigg) \mbox{ PSD} \bigg\}. \tag{MCD}\label{maxcut_dual} \end{align} Strong duality holds for \eqref{maxcut_dual}, so the optimal values of \eqref{maxcut_dual} and its Lagrangian dual are equal: \blue{% \begin{align*} v^* &= \max_{X \in \Rnn} \bigg\{ \trace\bigg(\frac{1}{4}LX\bigg): X_{ii}=1\ \forall\,i, \ X \textrm{ PSD}\bigg\}. \end{align*} } % Alternatively one could lift the original max cut problem from R^n to S^n % by setting $X = x*x^T$, and relaxing the resulting rank constraint % on X (rank(X) = 1). % \begin{itemize} \nitem This \red{SDP relaxation} can be efficiently solved using a poly time algorithm. \nitem The optimal $X$ is used to obtain a cut whose weight is no more than $14\%$ above the optimal weight [Goemans \& Williamson, 1995]. \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{comment} \begin{slide} \begin{cminipage}{.95\textwidth} \vspace{-0.8\semin} \title{Application: worst-case robust optimization} \vspace{0.5\semin} Least squares problem with certain data $A \in \Rmn$ and $b \in \Rm$, where $m > n$: \[ \min_{x \in \Rn}\ \|Ax-b\|_2\ . \] \bigskip \smallskip It's more realistic to assume $A$ is not known with certainty, but instead lies inside some nonempty bounded \red{uncertainty set} $\U \subset \Rmn$. \bigskip The worst-case error associated with a point $x$ is \[ \sup_{A \in \U}\ \|Ax-b\|_2\ . \] \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \title{Application: worst-case robust optimization} \vspace{0.2\semin} Goal: find the worst-case robust approximation \[ \min_{x \in \Rn}\ \sup_{A \in \U}\ \|Ax-b\|_2\ . \] This is a convex problem (even if $\U$ is nonconvex), but its difficulty depends on the description of $\U$. \smallskip Suppose $\U$ is the convex hull of the matrices $A_1,\cdots,A_k$, where each $A_i \in \Rmn$. I.e.,~$\U$ is a polyhedron. \medskip Then the problem becomes \[ \min_{x \in \Rn, t}\ \{t: t \geq \|A_i x-b\|_2,\ i=1,\cdots,k\}, \] which is a convex problem (SOCP). \medskip Other possibilities for $\U$, such as an ellipsoidal uncertainty for each row of $A$, also lead to SOCP formulations. % See Section 3.1 of Alizadeh/Goldfarb paper for more extensions. % For example, $b$ may also lie in an uncertainty ellipsoid. \end{cminipage} \end{slide} \end{comment} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.96\textwidth} \title{Sufficient conditions (constraint qualifications) for strong duality} \par\vspace{0.0\semin} \bi \sitem \textbf{Slater CQ for \eqref{eq:P}:} if \eqref{eq:P} is strongly feasible, i.e.,\\ \hspace{50pt} \blue{$\exists\ y,s$ such that $A^* y + s = c,\ s \in \Int(K)$},\\ then\hspace{32pt} $v_P$ finite $\rra v_P = v_D$ and $v_D$ is attained. \sitem \textbf{Slater CQ for \eqref{eq:D}:} if \eqref{eq:D} is strongly feasible, i.e.,\\ \hspace{50pt} \blue{$\exists\ x$ such that $Ax=b,\ x \in \Int(K^*)$},\\ then\hspace{32pt} $v_D$ finite $\rra v_P = v_D$ and $v_P$ is attained. \ei \medskip Weaker sufficient conditions also exist, but strong feasibility of \eqref{eq:P} and \eqref{eq:D} is necessary for many classes of algorithms to work. \bigskip Q. What can we do if strong feasibility fails for \eqref{eq:P}? A. Construct a \red{regularized} primal problem that: \begin{itemize} \item has the same feasible set as \eqref{eq:P}; \item is strongly feasible. \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.9\textwidth} \title{Faces and minimal faces} \par\vspace{0.1\semin} \begin{itemize} \item A convex set $F$ is a \red{face} of $K$, denoted $F \unlhd K$, if \beas x,y \in K \text{ and } \frac{x+y}{2} \in F \rra x,y \in F. \eeas \item If $F \unlhd K$ and $F \ne \{0\},K$, write $F \lhd K$ (\red{a proper face}). \bigskip \begin{tabular}{ll} \hspace{-9pt} \begin{minipage}{150pt} \item If $F \unlhd K$, the \red{conjugate face} of $F$ is \beas F^c := F^{\perp} \cap K^* \unlhd K^*. \eeas \end{minipage} \hspace{3pt}\raisebox{-46pt}{\scalebox{.4}{\input{conjugate_face.pstex_t}}}%\vspace{-28pt}%% \end{tabular} \smallskip \item If $x \in \relint(F)$, then $F^c = \{x\}^{\perp} \cap K^*$. \mitem Let $\F_P := \{y: A^*y \preceq_K c\}$ denote the feasible set of \eqref{eq:P}. Assuming $\F_P$ is nonempty, the \red{minimal face} of \eqref{eq:P} is \beas \blue{ f_P := \bigcap \{F \unlhd K: F \supset c-A^*(\F_P)\}. } \eeas \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \par\vspace{-0.4\semin} \title{Example} \par\vspace{0.3\semin} In the earlier SDP example \beas \sup\limits_y\;\left\{-y_2\ :\ \arr{ccc}{1+y_2&0&0\\0&y_1&y_2\\0&y_2&0} \mbox{ is PSD}\right\}, \eeas Slater's CQ fails and the duality gap is $1$. \medskip The feasible set is $\F_P = \{y \in \R^2: y_1 \geq 0,\ y_2 = 0\}$,\\ so the minimal face is \beas f_P = \arr{cc}{\S^2_+&0\\0&0} \lhd \S^3_+ \ . \eeas \smallskip More generally, if \eqref{eq:P} is feasible, then \beas \blue{% A^*y \not\prec_K c \ \forall y \text{ \black{ [Slater's CQ fails for \eqref{eq:P}] }} \llra f_P \lhd K. } \eeas \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.99\textwidth} \title{Primal feasible set $\{y: A^* y \preceq_K c\}$} \par\vspace{0.2\semin} \begin{center} \scalebox{.5}{\input{feasible_set.pstex_t}} \end{center} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \title{Regularization} \par\vspace{0.2\semin} Borwein \& Wolkowicz (1981): If Slater's CQ fails for \eqref{eq:P}, then \eqref{eq:P} is equivalent to the \red{regularized primal problem} \blue{% \begin{align} \red{v_{RP}} &= \sup\limits_y\;\{\langle b,y \rangle :\ A^* y \preceq_{\red{f_P}} c\}. \tag{RP}\label{eq:RP} \end{align} }% Its Lagrangian dual is \blue{% \begin{align} \red{v_{DRP}} &= \inf\limits_{x}\;\{\langle c,x \rangle :\ Ax=b,\ x \succeq_{\red{f_P^*}} 0\}. \tag{DRP}\label{eq:DRP} \end{align} }% Slater's CQ holds for \eqref{eq:RP}, so if $v_{RP} = v_{DRP}$ is finite, then $v_{DRP}$ is attained, i.e.,~strong duality holds for \eqref{eq:RP}. Borwein \& Wolkowicz also gave an algorithm to compute $f_P$. \bigskip Difficulties:\\ (1) The algorithm requires the solution of several convex programs that are potentially much larger then the original problem \eqref{eq:P}.\\ (2) If Slater's CQ fails for \eqref{eq:D}, then each of these convex programs also fail to satisfy Slater's CQ. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \title{Ramana's strong dual} \par\vspace{0.2\semin} In 1995 Ramana proposed the \red{Extended Lagrange-Slater dual (ELSD)} for \eqref{eq:P} in the case of SDP. The construction of the dual takes advantage of the well understood facial structure of $\Sn_+$. \medskip \textbf{Advantages:}\\ (1) The ELSD is written explicitly in terms of the original data $(A,b,c)$, unlike the regularized dual of Borwein \& Wolkowicz. \smallskip (2) The size of the ELSD is polynomial in the size of \eqref{eq:P}. In particular, the number of variables in the ELSD is $\O(k n^2)$, where $k \leq \min\{m,n\}$ depends on the original data. \medskip \textbf{Disadvantages:}\\ (1) Solving ELSD using a primal-dual interior-point method may be difficult since it might not satisfy Slater's CQ. Slater's CQ may also fail for the Lagrangian dual of ELSD. % If the original dual satisfies Slater, then so does ELSD. \smallskip (2) Size of the ELSD can potentially be very large. % The SDP paper of Nesterov and Todd on page 787 shows a % complexity per itertion of O(m^2 n^2), giving a complexity % of O(m^2 n^2.5) for the IPM. % $\O(k n^2)$ can be large, since the worst case bound on % $k$ can be achieved. There exist SDP instances for which % $k = m-1 = n-1$. For such instances, an interior-point method % applied to ELSD could require $\O(n^2 (n^3)^2.5)$ arithmetic % operations (ignoring structure and potential sparsity in ELSD). \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \title{Towards a better regularization (1)} \par\vspace{0.3\semin} In 1997, Ramana, Tun{\c{c}}el, \& Wolkowicz showed that Ramana's ELSD is equivalent to (DRP) (the dual of the regularized primal of Borwein \& Wolkowicz) in the case of SDP. \medskip For SDP, both approaches require the solution of one or more potentially large SDPs (compared to the size of the original problem) that need not satisfy Slater's CQ. \bigskip \textbf{Goal}: An algorithm to solve \eqref{eq:P} that satisfies the following properties:\\[2pt] (1) It recognizes if \eqref{eq:P} satisfies Slater's CQ and if \eqref{eq:P}--\eqref{eq:D} has a zero duality gap;\\ (2) The size of any intermediate convex program solved does not exceed that of \eqref{eq:P} or \eqref{eq:D};\\ (3) Any intermediate convex programs to be solved are well-posed, i.e.,~Slater's CQ holds for primal and dual. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \vspace{-0.3\semin} \title{Towards a better regularization (2)} \par\vspace{0.6\semin} Suppose that \eqref{eq:P} is feasible.\\ Then exactly one of the following two systems is consistent: \smallskip (1)\; $Ax=0,\ \langle c,x \rangle = 0,$ and $0 \ne x \succeq_{K^*} 0$; (2)\; $A^*y \prec_K c$\; [Slater's CQ holds for \eqref{eq:P}]. \bigskip $\rightarrow$ In theory, we can solve \[ \min\{0: Ax=0,\ \langle c,x \rangle = 0,\ 0 \ne x \succeq_{K^*} 0\} \] to determine if Slater's CQ fails for \eqref{eq:P}. \bigskip But this problem need not satisfy Slater's CQ. \bigskip So how can we solve (1)? \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \title{The Auxiliary problem (1)} \par\vspace{0.1\semin} Let $e \in \Int(K) \cap \Int(K^*)$, and consider the following auxiliary problem: \blue{% \be \begin{array}{rcl} \alpha^* := \min\limits_{x,\alpha} & \alpha \\ \mbox{s.t.} & Ax = 0 \\ & \langle c,x \rangle = 0\\ & x + \alpha e \succeq_{K^*} 0\\ & \langle e, x \rangle \leq 1. \tag{$\A$}\label{eq:A} \end{array} \ee } \bi \item Assume $c \notin \Range(A^*)$, otherwise we can remove $\langle c,x \rangle = 0$. \item The size of \eqref{eq:A} is essentially that of \eqref{eq:D}. \item Slater's CQ holds for \eqref{eq:A} and its dual. \item A strongly feasible primal-dual point is easily found. \item Applying a primal-dual IPM, we need to follow the central path closely at the end of the algorithm. \ei \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{1.00\textwidth} \vspace{-0.1\semin} \title{The Auxiliary problem (2)} \par\vspace{-0.3\semin} \blue{% \be \begin{array}{rcl} \alpha^* := \min\limits_{x,\alpha} & \alpha \\ \mbox{s.t.} & Ax = 0 \\ & \langle c,x \rangle = 0\\ & x + \alpha e \succeq_{K^*} 0\\ & \langle e, x \rangle \leq 1. \tag{$\A$}\label{eq:A} \end{array} \ee }\\[-4pt] \ptsize{9} What does a solution to \eqref{eq:A} tell us about \eqref{eq:P}--\eqref{eq:D}? \textbf{Theorem:} Let \eqref{eq:P} be feasible. Then the $x$ component of the central path for \eqref{eq:A} and its dual converges to a point in \blue{$\relint(\face(R))$}, where \blue{% \beas R := \{x :\ Ax = 0,\ \langle c,x \rangle = 0,\ x \succeq_{K^*} 0\}. \eeas }% Moreover, since $f_P \subset \{x^*\}^{\perp} \cap K = [\face(R)]^c \unlhd K$, either: \smallskip (1) $\alpha^* = 0$ and $x^* = 0$, so Slater's CQ holds for \eqref{eq:P}, or\\ (2) $\alpha^* = 0$ and $0 \ne x^* \succeq_{K^*} 0$, so $f_P \subset \{x^*\}^{\perp} \cap K \red{\lhd} K$, or\\ (3) $\alpha^* < 0$ and $x^* \succ_{K^*} 0$, so Slater's CQ holds for \eqref{eq:D}. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.96\textwidth} \vspace{-0.2\semin} \title{Our algorithm} \par\vspace{0.3\semin} \textbf{Input:} $A,b,c,K$, and $\varepsilon > 0$. \smallskip \textbf{Output:} optimal $\alpha^*$ and $x^* \in \relint(\face(R))$ for \eqref{eq:A}. \medskip \textbf{While} $\|x^*\| > \varepsilon$\\[2pt] \hspace{20pt} \begin{minipage}{250pt} \smallskip \textbf{If} $\alpha^* < 0$, then $x^* \succ_{K^*} 0$, so $f_P = \{0\}$.\\ Hence optimal $y$ for \eqref{eq:P} satisfies $A^* y = c$, and exit algorithm. \medskip \textbf{Else} (1) Any feasible $y$ for \eqref{eq:P} satisfies $c - A^*y \in [\face(R)]^c \lhd K$, giving a \red{reduced primal problem} with cone \blue{$K' = [\face(R)]^c$}. \smallskip (2) Solve \eqref{eq:A} and its dual with cone $K'$ to find optimal $\alpha^*, x^*$.\\ \textbf{End} \end{minipage} \textbf{End} \medskip Finally, solve reduced primal problem for which Slater's CQ holds.\\ (This provides a \red{certificate of optimality}.) \bigskip For cones such as $\Sn_+$ \& SOC, auxiliary problems get progressively smaller. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.92\textwidth} \par\vspace{-0.1\semin} \title{The SDP case} \par\vspace{0.1\semin} The faces of $\Sn_+$ are of the form \blue{ \beas \hspace{8pt} F &=& [P\:\: Q]\sarr{\S^{\red{r}}_+&0\\0&0} [P\:\: Q]^T = P \S^{\red{r}}_+ P^T,\\ \text{with}\quad F^c &=& [P\:\: Q]\sarr{0&0\\0&\S^{\red{n-r}}_+} [P\:\: Q]^T = Q \S^{\red{n-r}}_+ Q^T, \eeas } where $[P\:\: Q]$ is orthogonal. \medskip Suppose that $x^* = [P\; Q]\sarr{D&0\\0&0}[P\; Q]^T$, where $D \in \R^{r \times r}$. \medskip Then $\face(R) = \face(x^*) = [P\:\: Q]\sarr{\S^r_+&0\\0&0} [P\:\: Q]^T$, so $K' = [\face(R)]^c = Q \S^{n-r}_+ Q^T$. \medskip So reduced primal problem has constraints \blue{$A^*y \preceq_{K'} c$}. This is equivalent to [\blue{$Q^T(A^*y)Q \preceq_{\S^{n-r}_+} Q^TcQ$ and $(c - A^*y)P = 0$}], so the reduced primal problem lies in a lower dimensional space. \medskip Using $(c - A^*y)P = 0$ we can always eliminate some $y_i$'s, so reduced primal has lower dimension \textit{and} fewer variables. % We've assumed that \eqref{eq:P} is feasible). % Moreover, $c - A^*y \preceq{K'} 0$ is equivalent to % $Q^T(c - A^*y)Q \preceq_K'} 0$ and $(c - A^*y)P = 0$. % So if the linear system $(c-A^*y)P = 0$ is inconsistent, % we can conclude that \eqref{eq:P} is infeasible. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.98\textwidth} \vspace{-0.6\semin} \title{Numerical Experiments (1)} \par\vspace{0.5\semin} For the earlier SDP with $K = \S^3_+$ and a duality gap of $1$, we obtained (using Sedumi) the primal ``solution'' \begin{align*} y = \arr{c}{ 4.6 \times 10^7 \\ -0.38 }, \qquad S = \arr{ccc}{ 0.62 & 0 & 0 \\ 0 & 4.6 \times 10^7\hspace{-10pt}& -0.38\\ 0 & -0.38 & 0}\!. \end{align*} \bigskip Our code requires two iterations, giving a correct primal solution: \begin{align*} y^* = \arr{c}{ 1.50\\ 0},\quad S^* = \arr{ccc}{ 1.00 & 0 & 0\\ 0 & 1.50 & 0\\ 0 & 0 & 0}. \end{align*} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ptsize{9} \begin{slide} \begin{cminipage}{.92\textwidth} \title{Numerical Experiments (2)} \par\vspace{0.1\semin} Let $e_i$ be the $i$th unit vector in $\Rn$.\\ Consider the SDP with $m=n \geq 3$, $b = e_2$, $c = 0$, and \ptsize{8} \beas A^*y = \arr{ccccccc}{y_1&y_2&y_3&y_4&\cdots&y_{n-1}&y_n\\y_2&y_3&&&&&\\y_3&&y_4&&&&\\y_4&&&&&&\\\vdots&&&&\ddots&&\\y_{n-1}&&&&&y_n&\\y_n&&&&&&0}. \eeas \ptsize{9} Here $\F_P = \{y \in \R^n: y_1 \leq 0,\ y_2 = \cdots = y_n = 0\}$, $f_P = \{Z \in \Sn_+: Z_{11} \geq 0,\ Z_{ij} = 0\ \forall (i,j) \ne (1,1)\}$,\\ and \eqref{eq:D} is infeasible. \smallskip For various $n$, Sedumi gives an incorrect primal and dual solution with a duality gap of $-1$, whereas our algorithm gives a correct primal optimal solution. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \vspace{-1.1\semin} \title{Strict complementarity and nonzero gaps (1)} \par\vspace{0.6\semin} Write \eqref{eq:P}--\eqref{eq:D} in \red{symmetric subspace} form: \medskip Let $\bar{x}, \bar{y}$, and $\bar{s}$ satisfy $A\bar{x}=b$ and $A^*\bar{y} + \bar{s} = c$, and let $\L = {\rm Nullspace}(A)$. \bigskip The original primal-dual pair \eqref{eq:P}--\eqref{eq:D} can then be written as \blue{% \begin{align*} v_P &= \langle b,\bar{y} \rangle - \inf\limits_{s}\;\{\langle \bar{x},s \rangle :\ s \in (\bar{s}+\L^{\perp}) \cap K\},\\ v_D &= \langle c,\bar{x} \rangle + \inf\limits_{x}\;\{\langle \bar{s},x \rangle :\ x \in (\bar{x}+\L) \cap K^*\}. \end{align*} }% end of \blue \bigskip Set of primal \red{recession directions} is \blue{$\L^{\perp} \cap K$};\\ set of dual \red{recession directions} is \blue{$\L \cap K^*$}. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.99\textwidth} \vspace{-0.5\semin} \title{Strict complementarity and nonzero gaps (2)} \vspace{0.4\semin} The faces $F_1 \unlhd K$ and $F_2 \unlhd K^*$ form a: \begin{itemize} \mitem \red{complementarity partition} of $K$ and $K^*$ if \blue{$F_1 \subset F_2^c$} and \blue{$F_2 \subset F_1^c$}; \mitem \red{strict complementarity partition} of $K$ and $K^*$ if \blue{$F_1 = F_2^c$} and \blue{$F_2 = F_1^c$}. \end{itemize} \bigskip A complementarity partition is said to be \red{proper} if $F_1$ and $F_2$ are proper faces. \bigskip $\rightarrow$ Existence of a proper strict complementarity partition is important in optimization. \bigskip Fact: $\face(\L^\perp \cap K)$ and $\face(\L \cap K^*)$ form a complementarity partition. \bigskip $\rightarrow$ Whether \eqref{eq:P}--\eqref{eq:D} has a finite nonzero duality gap depends on whether the complementarity partition is proper and strict. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \vspace{-0.3\semin} \title{Strict complementarity and nonzero gaps (3)} \par\vspace{0.4\semin} \textbf{Theorem:} Let $K$ be a proper cone, and let\\ $F_1 := \face(\L^\perp \cap K)$ and $F_2 := \face(\L \cap K^*)$. \smallskip (1) If $(F_1,F_2)$ form a proper complementarity partition but not a strict complementarity partition, then there exists $\bar{s}$ and $\bar{x}$ such that \eqref{eq:P}--\eqref{eq:D} with data $(\L,K,\bar{x},\bar{y},\bar{s})$ has a finite nonzero duality gap. \medskip (2) If (a) \eqref{eq:P}--\eqref{eq:D} with data $(\L,K,\bar{x},\bar{y},\bar{s})$ has a finite nonzero duality gap, and\\ (b) the primal and dual objective functions are constant along all feasible recession directions,\\ then $(F_1,F_2)$ forms a proper complementarity partition but not a strict complementarity partition. \bigskip This result can be used to generate primal-dual instances possessing a finite nonzero duality gap. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \par\vspace{-0.2\semin} \title{Generating problems with nonzero gaps} \par\vspace{0.2\semin} For SDP, an instance with $K = \Sn_+$ is generated as follows: \medskip (1) Choose positive integers $n,p,d$ with $n > p+d$.\\ Take $e = I_n \in \Int(K) \cap \Int(K^*).$ \smallskip (2) Choose a subspace $\L$ and orthogonal matrix $Q$ such that \beas \face(\L^{\perp} \cap K)= Q\sarr{0&&\\&0&\\&&\blue{\S^p_+}}Q^T, \quad \face(\L \cap K^*)= Q\sarr{\blue{\S^d_+}&&\\&0&\\&&0}Q^T. \eeas These faces form a complementarity partition, but not a strict complementarity partition. \smallskip (3) Choose a nonzero $U \in \S^{n-p-d}_+$, and let \beas \bar{s} = \bar{x} = Q \sarr{0&&\\&\blue{U}&\\&&0} Q^T. \eeas The duality gap between the resulting SDPs is $\langle \bar{s},\bar{x} \rangle = \|U\|_F^2 > 0$. \medskip We have written a code to implement this. \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \begin{cminipage}{.95\textwidth} \title{Conclusions and future work} \vspace{-0.1\semin} \label{final_page} \begin{itemize} \mitem We gave a stable algorithm to solve conic problems for which Slater's CQ fails. \mitem The algorithm requires the solution of problems whose size is the same as that of the original dual. In special cases such as SDP and SOCP, these problems become progressively smaller. \mitem Failure of strict complementarity for the associated recession problems is closely related to the existence of instances having a finite nonzero duality gap, giving a means of testing our algorithm. \mitem We intend to refine our code and test it on larger SDPs having a finite nonzero duality gap. \mitem Perform error analysis to study how rounding errors and errors in computing approximate solutions to the auxiliary problems affects the number of iterations of our algorithm. \end{itemize} \end{cminipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}