Fast alternating linearization methods for minimizing the sum of two convex functions

DOI10.1007/s10107-012-0530-2zbMath1280.65051arXiv0912.4571WikidataQ101200642 ScholiaQ101200642MaRDI QIDQ378095

Katya Scheinberg, Donald Goldfarb, Shi-Qian Ma

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.4571

zbMATH Keywords

algorithm; convergence; maximal monotone operators; numerical results; convex optimization; Gauss-Seidel method; subgradient; Lipschitz constant; Peaceman-Rachford method; alternating direction method; large-scale problems; alternating linearization method; augmented Langrangian method; iteration complexity bounds; Lipschitz continuous gradient; optimal gradient method; variable splitting

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90C25: Convex programming

90C06: Large-scale problems in mathematical programming

Related Items

Unnamed Item, Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming, Least-squares approach to risk parity in portfolio selection, A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization, An Accelerated Linearized Alternating Direction Method of Multipliers, A new convergence analysis and perturbation resilience of some accelerated proximal forward–backward algorithms with errors, Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection, IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems, A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems, Fast first-order methods for composite convex optimization with backtracking, Alternating direction method of multipliers for sparse principal component analysis, Proximal-based pre-correction decomposition methods for structured convex minimization problems, An alternating direction method with increasing penalty for stable principal component pursuit, Fast algorithm for color texture image inpainting using the non-local CTV model, On the linear convergence of the alternating direction method of multipliers, Adaptive smoothing algorithms for nonsmooth composite convex minimization, Alternating direction augmented Lagrangian methods for semidefinite programming, Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems, An alternating linearization bundle method for a class of nonconvex nonsmooth optimization problems, A proximal alternating linearization method for minimizing the sum of two convex functions, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Stochastic accelerated alternating direction method of multipliers with importance sampling, Proximal alternating penalty algorithms for nonsmooth constrained convex optimization, A nonmonotone gradient algorithm for total variation image denoising problems, ROML: a robust feature correspondence approach for matching objects in a set of images, Accelerated linearized Bregman method, Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, Selective linearization for multi-block statistical learning, An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, An ADMM-based SQP method for separably smooth nonconvex optimization, A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem, Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems, Manifold regularized matrix completion for multi-label learning with ADMM, Robust PCA using nonconvex rank approximation and sparse regularizer, Efficient iterative solution of finite element discretized nonsmooth minimization problems, Robust principal component analysis using facial reduction, A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application, A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, An alternating direction method of multipliers for tensor complementarity problems, Semisupervised data classification via the Mumford-Shah-Potts-type model, A class of alternating linearization algorithms for nonsmooth convex optimization, Mirror Prox algorithm for multi-term composite minimization and semi-separable problems, On the global and linear convergence of the generalized alternating direction method of multipliers, Alternating proximal gradient method for convex minimization, LAVIR -- locally adaptive variational image registration, Fast bundle-level methods for unconstrained and ball-constrained convex optimization, Efficient algorithms for robust and stable principal component pursuit problems, Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming, A proximal multiplier method for separable convex minimization, Multiplicative noise removal combining a total variation regularizer and a nonconvex regularizer, Distributed solutions for loosely coupled feasibility problems using proximal splitting methods, A survey on operator splitting and decomposition of convex programs, Convergence rate of a proximal multiplier algorithm for separable convex minimization, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions, A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization

Uses Software

Cites Work