Proximal distance algorithms: theory and practice

MaRDI QIDQ5381120zbMATH OpenFDO

Authors Kevin L. Keys, Hua Zhou, Kenneth Lange

Publication date 7 June 2019

Full work available at URL https://arxiv.org/abs/1604.05694, http://jmlr.csail.mit.edu/papers/v20/17-687.html

zbMATH Keywords

constrained optimizationEM algorithmmajorizationprojectionproximal operator

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30)

Abstract: Proximal distance algorithms combine the classical penalty method of constrained minimization with distance majorization. If $$ is the loss function, and $C$ is the constraint set in a constrained minimization problem, then the proximal distance principle mandates minimizing the penalized loss $$ and following the solution $$ to its limit as $ho$ tends to $infty$. At each iteration the squared Euclidean distance $$ is majorized by the spherical quadratic $$, where $$ denotes the projection of the current iterate $$ onto $C$. The minimum of the surrogate function $$ is given by the proximal map $$. The next iterate $$ automatically decreases the original penalized loss for fixed $ho$. Since many explicit projections and proximal maps are known, it is straightforward to derive and implement novel optimization algorithms in this setting. These algorithms can take hundreds if not thousands of iterations to converge, but the stereotyped nature of each iteration makes proximal distance algorithms competitive with traditional algorithms. For convex problems, we prove global convergence. Our numerical examples include a) linear programming, b) nonnegative quadratic programming, c) projection to the closest kinship matrix, d) projection onto a second-order cone constraint, e) calculation of Horn's copositive matrix index, f) linear complementarity programming, and g) sparse principal components analysis. The proximal distance algorithm in each case is competitive or superior in speed to traditional methods.

Recommendations

• The proximal distance algorithm
• Distance majorization and its applications
• Proximal algorithms in statistics and machine learning
• Common fixed points of an infinite family of nonexpansive mappings in uniformly convex metric spaces
• Rescaling and stepsize selection in proximal methods using separable generalized distances

Cites work

• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Numerically Stable Solver for Positive Semidefinite Quadratic Programs Based on Nonnegative Least Squares
• A Singular Value Thresholding Algorithm for Matrix Completion
• A variational approach to copositive matrices
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• An algorithmic approach to nonlinear analysis and optimization
• An Iteration Formula for Fredholm Integral Equations of the First Kind
• Applications of second-order cone programming
• Closest point search in lattices
• Composite difference-MAX programs for modern statistical estimation problems
• Computing in operations research using Julia
• Computing the nearest correlation matrix--a problem from finance
• Conic optimization via operator splitting and homogeneous self-dual embedding
• Constructing copositive matrices from interior matrices
• Convergence analysis of difference-of-convex algorithm with subanalytic data
• Convex analysis and monotone operator theory in Hilbert spaces
• Convex analysis and nonlinear optimization. Theory and examples.
• Convex functions and their applications. A contemporary approach
• Discussion
• Distance majorization and its applications
• Generalized power method for sparse principal component analysis
• scientific article; zbMATH DE number 3973706 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3201668 (Why is no real title available?)
• scientific article; zbMATH DE number 3192366 (Why is no real title available?)
• scientific article; zbMATH DE number 3061616 (Why is no real title available?)
• scientific article; zbMATH DE number 3108780 (Why is no real title available?)
• JuMP: a modeling language for mathematical optimization
• Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence
• Linear and nonlinear programming.
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Majorization as a tool for optimizing a class of matrix functions
• Matrix completion via an alternating direction method
• Mean Value Methods in Iteration
• Minimization of a class of matrix trace functions by means of refined majorization
• MM optimization algorithms
• On consistency and sparsity for principal components analysis in high dimensions
• On Fréchet subdifferentials
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Optimal detection of sparse principal components in high dimension
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal splitting methods in signal processing
• Second-order cone programming
• Semianalytic and subanalytic sets
• SPADES and mixture models
• Sparse inverse covariance estimation with the graphical lasso
• Sparse principal component analysis via regularized low rank matrix approximation
• Spectral regularization algorithms for learning large incomplete matrices
• The convergence rate of the penalty function method
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The proximal distance algorithm
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Variational methods for the solution of problems of equilibrium and vibrations

Cited in

(21)

• Finding best approximation pairs for two intersections of closed convex sets
• A penalized method of alternating projections for weighted low-rank Hankel matrix optimization
• High-performance statistical computing in the computing environments of the 2020s
• Random minibatch subgradient algorithms for convex problems with functional constraints
• Perspective functions: proximal calculus and applications in high-dimensional statistics
• A proximal algorithm with quasi distance. Application to habit's formation
• Distance majorization and its applications
• Algorithms for computing the optimal transitive approximation of a proximity relation
• The proximal distance algorithm
• Discussion: ``A brief survey of modern optimization for statisticians
• The Emperor Has No Caps! A Comparison of DCJ and Algebraic Distances
• Understanding non-negative matrix factorization in the framework of Bregman divergence
• Dimension Reduction for Integrative Survival Analysis
• A Legacy of EM Algorithms
• Algorithms for Sparse Support Vector Machines
• A Sharper Computational Tool for Regression
• The stochastic proximal distance algorithm
• Online Kernel-Based Mode Learning
• Sparse vertex discriminant analysis: variable selection for biomedical classification applications
• Proximal MCMC for Bayesian Inference of Constrained and Regularized Estimation
• Calculation of the Prokhorov distance by optimal quantization and maximum flow

Describes a project that uses

Uses Software

• UNLocBoX
• JuMP
• PMA
• proxdist
• CRAIG
• LSQR
• Ipopt
• GitHub

This page was built for publication: Proximal distance algorithms: theory and practice

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