A hybrid quasi-Newton projected-gradient method with application to lasso and basis-pursuit denoising

DOI10.1007/S12532-019-00163-5MaRDI QIDQ2175442zbMATH OpenOpenAlexWikidataFDO

Authors Ewout van den Berg

Publication date 29 April 2020

Published in Mathematical Programming Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

projected gradient methodquasi-Newton method\(\ell_1\) minimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Convex programming (90C25) Methods of quasi-Newton type (90C53) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: We propose a new algorithm for the optimization of convex functions over a polyhedral set in Rn. The algorithm extends the spectral projected-gradient method with limited-memory BFGS iterates restricted to the present face whenever possible. We prove convergence of the algorithm under suitable conditions and apply the algorithm to solve the Lasso problem, and consequently, the basis-pursuit denoise problem through the root-finding framework proposed by van den Berg and Friedlander [SIAM Journal on Scientific Computing, 31(2), 2008]. The algorithm is especially well suited to simple domains and could also be used to solve bound-constrained problems as well as problems restricted to the simplex.

Recommendations

• Inexact spectral projected gradient methods on convex sets
• Probing the Pareto frontier for basis pursuit solutions
• A gradient descent algorithm for LASSO
• Tackling box-constrained optimization via a new projected quasi-Newton approach
• A reduced-space algorithm for minimizing \(\ell_1\)-regularized convex functions

Cites work

• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A limited memory steepest descent method
• Atomic Decomposition by Basis Pursuit
• Compressed sensing
• Compressed sensing with coherent and redundant dictionaries
• Convex Polytopes
• Decoding by Linear Programming
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• On the Goldstein-Levitin-Polyak gradient projection method
• On the limited memory BFGS method for large scale optimization
• Probing the Pareto frontier for basis pursuit solutions
• Proximal Newton-type methods for minimizing composite functions
• Proximité et dualité dans un espace hilbertien
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Signal Recovery by Proximal Forward-Backward Splitting
• Sparse Optimization with Least-Squares Constraints
• Two-Point Step Size Gradient Methods
• qpOASES: a parametric active-set algorithm for~quadratic programming

Cited in

(5)

• Projected gradient approach to the numerical solution of the SCoTLASS
• Properties and iterative methods for the \(Q\)-lasso
• Safe feature elimination for non-negativity constrained convex optimization
• A gradient descent algorithm for LASSO
• Probing the Pareto frontier for basis pursuit solutions

Describes a project that uses

Uses Software

• SPGL1
• Sparco
• PDCO
• qpOASES
• L-BFGS

This page was built for publication: A hybrid quasi-Newton projected-gradient method with application to lasso and basis-pursuit denoising

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