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

Fred Moolekamp, Peter Melchior

Research output: Contribution to journalArticle

2 Scopus citations

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 on each of them. The function f may be nonconvex as long as it is convex in every argument, while the constraints g 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(L·) 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.

Original languageEnglish (US)
Pages (from-to)871-885
Number of pages15
JournalOptimization and Engineering
Volume19
Issue number4
DOIs
StatePublished - Dec 1 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Civil and Structural Engineering
  • Aerospace Engineering
  • Mechanical Engineering
  • Control and Optimization
  • Electrical and Electronic Engineering

Keywords

  • Block coordinate descent
  • Non-negative matrix factorization
  • Nonconvex optimization
  • Optimization
  • Proximal algorithms

Fingerprint Dive into the research topics of 'Block-simultaneous direction method of multipliers: a proximal primal-dual splitting algorithm for nonconvex problems with multiple constraints'. Together they form a unique fingerprint.

  • Cite this