Distance Majorization and Its Applications

Abstract

The problem of minimizing a continuously differentiable convex function over an intersection of closed convex sets is ubiquitous in applied mathematics. It is particularly interesting when it is easy to project onto each separate set, but nontrivial to project onto their intersection. Algorithms based on Newton's method such as the interior point method are viable for small to medium-scale problems. However, modern applications in statistics, engineering, and machine learning are posing problems with potentially tens of thousands of parameters or more. We revisit this convex programming problem and propose an algorithm that scales well with dimensionality. Our proposal is an instance of a sequential unconstrained minimization technique and revolves around three ideas: the majorization-minimization (MM) principle, the classical penalty method for constrained optimization, and quasi-Newton acceleration of fixed-point algorithms. The performance of our distance majorization algorithms is illustrated in several applications.

29 pages, 6 figures

References in corpus (2)

• The MM Alternative to EM
• A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization

Cited by in corpus (12)

• Physical Layer Security for Integrated Sensing and Communication: A Survey
• Generalized Linear Model Regression under Distance-to-set Penalties
• Nonconvex Optimization via MM Algorithms: Convergence Theory
• The proximal distance algorithm
• Simple and Scalable Sparse k-means Clustering via Feature Ranking
• Proximal MCMC for Bayesian Inference of Constrained and Regularized Estimation
• A Sharper Computational Tool for ${\text{L}}_2\text{E}$ Regression
• A D.C. Algorithm via Convex Analysis Approach for Solving a Location Problem Involving Sets
• A Proximal Distance Algorithm for Likelihood-Based Sparse Covariance Estimation
• An MM Algorithm for Split Feasibility Problems
• Proximal Distance Algorithms: Theory and Examples
• An Introduction to MM Algorithms for Machine Learning and Statistical