convex optimization

The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex

Categories Convex Optimization Tags , , ,

The alternating direction method of multipliers (ADMM) is a benchmark for solving a two-block linearly constrained convex minimization model whose objective function is the sum of two functions without coupled variables. Meanwhile, it is known that the convergence is not guaranteed if the ADMM is directly extended to a multiple-block convex minimization model whose objective … Read more

Conditional Gradient Sliding for Convex Optimization

Categories Convex and Nonsmooth Optimization Tags , , , ,

In this paper, we present a new conditional gradient type method for convex optimization by utilizing a linear optimization (LO) oracle to minimize a series of linear functions over the feasible set. Different from the classic conditional gradient method, the conditional gradient sliding (CGS) algorithm developed herein can skip the computation of gradients from time … Read more

Block-wise Alternating Direction Method of Multipliers with Gaussian Back Substitution for Multiple-block Convex Programming

Categories Convex Optimization Tags , , , , , ,

We consider the linearly constrained convex minimization model with a separable objective function which is the sum of m functions without coupled variables, and discuss how to design an efficient algorithm based on the fundamental technique of splitting the augmented Lagrangian method (ALM). Our focus is the specific big-data scenario where m is huge. A … Read more

On the iterate convergence of descent methods for convex optimization

Categories Convex Optimization Tags ,

We study the iterate convergence of strong descent algorithms applied to convex functions. We assume that the function satisfies a very simple growth condition around its minimizers, and then show that the trajectory described by the iterates generated by any such method has finite length, which proves that the sequence of iterates converge. CitationFederal University … Read more

On the Sublinear Convergence Rate of Multi-Block ADMM

Categories Convex and Nonsmooth Optimization Tags , ,

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems. Despite of its success in practice, the convergence of the standard ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions whose variables are linked by linear constraints, has remained unclear for a very long time. Recently, Chen … Read more

On the Global Linear Convergence of the ADMM with Multi-Block Variables

Categories Convex and Nonsmooth Optimization Tags , ,

The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of $N$ convex functions with $N$-block variables linked by some linear constraints. While the convergence of the ADMM for $N=2$ was well established in the literature, … Read more

Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond

Categories Convex Optimization Tags , , , , , , ,

The alternating direction method of multipliers (ADMM) is a benchmark for solving a linearly constrained convex minimization model with a two-block separable objective function; and it has been shown that its direct extension to a multiple-block case where the objective function is the sum of more than two functions is not necessarily convergent. For the … Read more

Multiperiod Multiproduct Advertising Budgeting: Stochastic Optimization Modeling

Categories Marketing Tags , , , ,

We propose a stochastic optimization model for the Multiperiod Multiproduct Advertising Budgeting problem, so that the expected profit of the advertising investment is maximized. The model is a convex optimization problem that can readily be solved by plain use of standard optimization software. It has been tested for planning a realistic advertising campaign. In our … Read more

A Class of Randomized Primal-Dual Algorithms for Distributed Optimization

Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , ,

Based on a preconditioned version of the randomized block-coordinate forward-backward algorithm recently proposed in [Combettes,Pesquet,2014], several variants of block-coordinate primal-dual algorithms are designed in order to solve a wide array of monotone inclusion problems. These methods rely on a sweep of blocks of variables which are activated at each iteration according to a random rule, … Read more

Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems

Categories Applications - Science and Engineering, Convex Optimization, Integer Programming Tags , , , , , , , ,

Optimization methods are at the core of many problems in signal/image processing, computer vision, and machine learning. For a long time, it has been recognized that looking at the dual of an optimization problem may drastically simplify its solution. Deriving efficient strategies which jointly brings into play the primal and the dual problems is however … Read more