We consider the separate convex programming problem with linking linear constraints, where the objective function is in the form of the sum of m individual functions without crossed variables. The special case with m=2 has been well studied in the literature and some algorithms are very influential, e.g. the alternating direction method. The research for … Read more
Let $\cX,\cY,\cZ$ be real Hilbert spaces, let $f : \cX \rightarrow \R\cup\{+\infty\}$, $g : \cY \rightarrow \R\cup\{+\infty\}$ be closed convex functions and let $A : \cX \rightarrow \cZ$, $B : \cY \rightarrow \cZ$ be linear continuous operators. Let us consider the constrained minimization problem $$ \min\{f(x)+g(y):\quad Ax=By\}.\leqno (\cP)$$ Given a sequence $(\gamma_n)$ which tends toward … Read more
Alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems. Recently, because of its significant efficiency and easy implementation in novel applications, ADM is extended to the case where the number of separable parts is a finite number. The algorithmic framework of the extended method consists of two … Read more
In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number … Read more
In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more
We show that minimizers of convex functions subject to almost all linear perturbations are nondegenerate. An analogous result holds more generally, for lower-C^2 functions. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2010. ArticleDownload View PDF
In this paper, we analyze two popular semidefinite programming \SDPb relaxations for quadratically constrained quadratic programs \QCQPb with matrix variables. These are based on \emph{vector-lifting} and on \emph{matrix lifting} and are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline … Read more
CG, SYMMLQ, and MINRES are Krylov subspace methods for solving symmetric systems of linear equations. When these methods are applied to an incompatible system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ’s solution could explode, while MINRES would give a least-squares solution but not necessarily the minimum-length (pseudoinverse) solution. This … Read more
Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual … Read more
The main concern of this article is to study Ulam stability of the set of $\varepsilon$-approximate minima of a proper lower semicontinuous convex function bounded below on a real normed space $X$, when the objective function is subjected to small perturbations (in the sense of Attouch \& Wets). More precisely, we characterize the class all … Read more