Distance majorization and its applications.
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 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.
Department of Human Genetics, University of California, Los Angeles, CA 90095, USA.
Eric C
EC
Chi
Department of Statistics, North Carolina State University, Raleigh, NC 27695-8203, USA hua_zhou@ncsu.edu.
Hua
H
Zhou
Departments of Biomathematics, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095, USA klange@ucla.edu.
Kenneth
K
Lange
Constrained optimization; Majorization-minimization (MM); Projection; Sequential unconstrained minimization