Block-simultaneous direction method of multipliers: a proximal primal-dual splitting algorithm for nonconvex problems with multiple constraints

DOI10.1007/S11081-018-9380-YzbMATH Open1422.90040arXiv1708.09066OpenAlexW3105408556WikidataQ130089265 ScholiaQ130089265MaRDI QIDQ2315079FDOQ2315079

Authors: Fred Moolekamp, Peter Melchior 

Publication date: 31 July 2019

Published in: Optimization and Engineering (Search for Journal in Brave)

Abstract: We introduce a generalization of the linearized Alternating Direction Method of Multipliers to optimize a real-valued function $f$ of multiple arguments with potentially multiple constraints $g_{c}irc$ on each of them. The function $f$ may be nonconvex as long as it is convex in every argument, while the constraints $g_{c}irc$ need to be convex but not smooth. If $f$ is smooth, the proposed Block-Simultaneous Direction Method of Multipliers (bSDMM) can be interpreted as a proximal analog to inexact coordinate descent methods under constraints. Unlike alternative approaches for joint solvers of multiple-constraint problems, we do not require linear operators $L$ of a constraint function $g(Lcdot)$ to be invertible or linked between each other. bSDMM is well-suited for a range of optimization problems, in particular for data analysis, where $f$ is the likelihood function of a model and $L$ could be a transformation matrix describing e.g. finite differences or basis transforms. We apply bSDMM to the Non-negative Matrix Factorization task of a hyperspectral unmixing problem and demonstrate convergence and effectiveness of multiple constraints on both matrix factors. The algorithms are implemented in python and released as an open-source package.

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

Recommendations

• Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications
• An inertial proximal partially symmetric ADMM-based algorithm for linearly constrained multi-block nonconvex optimization problems with applications
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Inertial alternating direction method of multipliers for non-convex non-smooth optimization

zbMATH Keywords

optimizationnonconvex optimizationnon-negative matrix factorizationblock coordinate descentproximal algorithms

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Title not available (Why is that?)
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A unified convergence analysis of block successive minimization methods for nonsmooth optimization
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• Gradient methods for minimizing composite functions
• Algorithms and applications for approximate nonnegative matrix factorization
• Projected Gradient Methods for Nonnegative Matrix Factorization
• Proximal splitting methods in signal processing
• Signal Recovery by Proximal Forward-Backward Splitting
• A proximal-based deomposition method for compositions method for convex minimization problems
• Image recovery via total variation minimization and related problems
• An algorithm for total variation minimization and applications
• On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
• A parallel inertial proximal optimization method
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Approximate ADMM algorithms derived from Lagrangian splitting

Cited In (2)

• bSDMM
• Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications

Uses Software

• UNLocBoX
• Python

This page was built for publication: Block-simultaneous direction method of multipliers: a proximal primal-dual splitting algorithm for nonconvex problems with multiple constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315079)