Distance majorization and its applications

DOI10.1007/S10107-013-0697-1zbMATH Open1297.65067arXiv1211.3907OpenAlexW2090541242WikidataQ42053741 ScholiaQ42053741MaRDI QIDQ403660FDOQ403660

Eric C. Chi, Kenneth Lange, Hua Zhou

Publication date: 29 August 2014

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

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.

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

Recommendations

• Proximal distance algorithms: theory and practice
• The proximal distance algorithm
• Sharp quadratic majorization in one dimension
• Majorization-minimization algorithms for nonsmoothly penalized objective functions
• Incremental majorization-minimization optimization with application to large-scale machine learning

zbMATH Keywords

numerical examplesprojectionalgorithmconstrained optimizationmajorization-minimizationconvex programminginterior point methodpenalty methodfixed-point algorithmsNetwon's methodquasi-Newton accelerationsequential unconstrained minimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Interior-point methods (90C51) Methods of quasi-Newton type (90C53)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constrained Statistical Inference
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach
• Optimization
• Robust Statistics
• Monotonicity of quadratic-approximation algorithms
• Title not available (Why is that?)
• A quasi-Newton acceleration for high-dimensional optimization algorithms
• Numerical Analysis for Statisticians
• Equivalent Subgradient Versions of Hamiltonian and Euler–Lagrange Equations in Variational Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Alternating minimization as sequential unconstrained minimization: a survey
• Proximal Splitting Methods in Signal Processing
• Solving a Generalized Heron Problem by Means of Convex Analysis
• Applications of variational analysis to a generalized Heron problem
• Title not available (Why is that?)
• Applications of variational analysis to a generalized Fermat-Torricelli problem
• A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization
• Sequential unconstrained minimization algorithms for constrained optimization
• Signal Recovery by Proximal Forward-Backward Splitting
• Sufficient conditions for the convergence of monotonic mathematical programming algorithms
• Title not available (Why is that?)
• Nonlinear optimization.
• Applied iterative methods.
• An Algorithm for Restricted Least Squares Regression
• Title not available (Why is that?)
• Convex analysis and nonlinear optimization. Theory and examples
• How good are projection methods for convex feasibility problems?
• On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
• A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\)
• Projected Newton Methods for Optimization Problems with Simple Constraints
• Proximity function minimization using multiple Bregman projections, with applications to split feasibility and Kullback--Leibler distance minimization
• The MM alternative to EM

Cited In (12)

• The log-exponential smoothing technique and Nesterov's accelerated gradient method for generalized Sylvester problems
• Proximal Distance Algorithms: Theory and Examples
• Calculation of the Prokhorov distance by optimal quantization and maximum flow
• Clustering and multifacility location with constraints via distance function penalty methods and dc programming
• Algorithms for Sparse Support Vector Machines
• A Sharper Computational Tool for Regression
• Distance measures with heavy aggregation operators
• Asymptotic distance and its application
• A Legacy of EM Algorithms
• The stochastic proximal distance algorithm
• An MM Algorithm for Split Feasibility Problems
• High-performance statistical computing in the computing environments of the 2020s

Uses Software

• NNLS
• UNLocBoX

This page was built for publication: Distance majorization and its applications

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