convex optimization

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method … Read more

A survey on operator splitting and decomposition of convex programs

Categories Convex Optimization Tags , ,

Many structured convex minimization problems can be modeled by the search of a zero of the sum of two monotone operators. Operator splitting methods have been designed to decompose and regularize at the same time these kind of models. We review here these models and the classical splitting methods. We focus on the numerical sensitivity … Read more

Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators

Categories Infinite Dimensional Optimization, Stochastic Programming Tags , , , , ,

We investigate the asymptotic behavior of a stochastic version of the forward-backward splitting algorithm for finding a zero of the sum of a maximally monotone set-valued operator and a cocoercive operator in Hilbert spaces. Our general setting features stochastic approximations of the cocoercive operator and stochastic perturbations in the evaluation of the resolvents of the … Read more

An optimal randomized incremental gradient method

Categories Convex Optimization Tags , , , , ,

In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of $m$ ($\ge 1$) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-box iteration complexity for solving these composite optimization … Read more

Understanding the Convergence of the Alternating Direction Method of Multipliers: Theoretical and Computational Perspectives

Categories Convex Optimization Tags ,

The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. While it is … Read more

A semi-proximal-based strictly contractive Peaceman-Rachford splitting method

Categories Convex and Nonsmooth Optimization Tags , , , ,

The Peaceman-Rachford splitting method is very efficient for minimizing sum of two functions each depends on its variable, and the constraint is a linear equality. However, its convergence was not guaranteed without extra requirements. Very recently, He et al. (SIAM J. Optim. 24: 1011 – 1040, 2014) proved the convergence of a strictly contractive Peaceman-Rachford … Read more

An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting … Read more

On the Step Size of Symmetric Alternating Directions Method of Multipliers

Categories Convex Optimization Tags , , , ,

The alternating direction method of multipliers (ADMM) is an application of the Douglas-Rachford splitting method; and the symmetric version of ADMM which updates the Lagrange multiplier twice at each iteration is an application of the Peaceman-Rachford splitting method. Sometimes the symmetric ADMM works empirically; but theoretically its convergence is not guaranteed. It was recently found … Read more

Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

Categories Convex and Nonsmooth Optimization Tags , , ,

The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more