separable structure – Optimization Online

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

Published: 2014/11/18

Convex Optimization alternating direction method of multipliers, convergence analysis, convex optimization, separable structure

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

A relaxed customized proximal point algorithm for separable convex programming

Published: 2011/08/30

Convex Optimization alternating direction method, convergence rate, convex optimization, over-relaxation, proximal point algorithm, separable structure

The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an … Read more

Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming

Published: 2010/12/30, Updated: 2011/08/05

Bingsheng He

Tao Min

Xiao-Ming Yuan

Convex Optimization alternating direction method, convex optimization, gaussian elimination, separable structure

We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … Read more

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

Published: 2010/05/25

Bingsheng He

Peng Zheng

Wang XiangFeng

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

Alternating directions based contraction method for generally separable linearly constrained convex programming problems

Published: 2009/11/19

Convex Optimization alternating direction method, contraction method, convex optimization, linear constraint, separable structure

The classical alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems and variational inequalities where both the involved operators and constraints are separable into two parts. In particular, recentness has witnessed a number of novel applications arising in diversified areas (e.g. Image Processing and Statistics), for which … Read more

Alternating Direction Methods for Sparse Covariance Selection

Published: 2009/09/03

Xiao-Ming Yuan

Convex and Nonsmooth Optimization alternating direction method, first-order methods, large-scale optimization, separable structure, sparse covariance selection

The mathematical model of the widely-used sparse covariance selection problem (SCSP) is an NP-hard combinatorial problem, whereas it can be well approximately by a convex relaxation problem whose maximum likelihood estimation is penalized by the $L_1$ norm. This convex relaxation problem, however, is still numerically challenging, especially for large-scale cases. Recently, some efficient first-order methods … Read more