Convex and Nonsmooth Optimization – Page 173

Alternating proximal algorithms for constrained variational inequalities. Application to domain decomposition for PDE’s

Published: 2010/06/20

Convex Optimization alternating direction method, convex optimization, domain decomposition for pde's, monotone inclusions, proximal algorithm, variational inequality

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

Implicit Multifunction Theorems in complete metric spaces

Published: 2010/06/12

Infinite Dimensional Optimization, Nonsmooth Optimization error bound, generalized equations, implicit multifunction, metric regularity, perturbation stability

In this paper, we establish some new characterizations of the metric regularity of implicit multifunctions in complete metric spaces by using the lower semicontinuous envelopes of the distance functions for set-valued mappings. Through these new characterizations it is possible to investigate implicit multifunction theorems based on coderivatives and on contingent derivatives as well as the … Read more

First order dependence on uncertainty sets in robust optimization

Published: 2010/06/12

C.H. Jeffrey Pang

Nonsmooth Optimization, Robust Optimization robust optimization, sensitivity analysis, uncertainty sets, variational analysis

We show that a first order problem can approximate solutions of a robust optimization problem when the uncertainty set is scaled, and explore further properties of this first order problem. ArticleDownload View PDF

A first-order primal-dual algorithm for convex problems with applications to imaging

Published: 2010/06/10

Convex and Nonsmooth Optimization convex optimization, first-order primal-dual algorithm, imaging problems

In this paper we study a first-order primal-dual algorithm for convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1/N ) in finite dimensions, which is optimal for the complete class of non-smooth problems we are considering in this paper. We further show accelerations of the proposed algorithm to … Read more

Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization

Published: 2010/05/25

Complementarity and Variational Inequalities, Convex Optimization alternating direction method, contraction method, linearly constrained convex programming, separable structure

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

A Unified Approach for Minimizing Composite Norms

Published: 2010/05/25, Updated: 2012/08/06

Convex and Nonsmooth Optimization, Nonsmooth Optimization augmented lagrangian method, basis pursuit, compressed sensing, first-order methods, matrix completion, nuclear norm, robust pca

L1 Minimization via Randomized First Order Algorithms

Published: 2010/05/16, Updated: 2011/06/05

Applications - Science and Engineering, Convex Optimization bilinear saddle point problems, compressed sensing, l1-minimization, randomized algorithms

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

Information Geometry and Primal-Dual Interior-point Algorithms

Published: 2010/05/14

Convex Optimization, Linear, Cone and Semidefinite Programming complexity, convex optimization, differential geometry, embedding curvature, informaion geometry, interior point methods, linear programming, polynomial-time algorithm, semidefinite programming

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

Generic nondegeneracy in convex optimization

Published: 2010/05/06

Convex Optimization, Nonsmooth Optimization convex, hausdorff measure, lower-c^2, normal cone, subdifferential

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

On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

Published: 2010/04/28

Constrained Nonlinear Optimization, Convex Optimization hard combinatorial problems, quadratic constrained quadratic programming, quadratic matrix programming, semidefinite programming

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