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

DOI10.1007/S12532-019-00163-5zbMATH Open1434.90118arXiv1611.05483OpenAlexW2963118864WikidataQ127757507 ScholiaQ127757507MaRDI QIDQ2175442FDOQ2175442

Ewout van den Berg

Publication date: 29 April 2020

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

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.

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

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

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)

Cites Work

• Sparse Optimization with Least-Squares Constraints
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Title not available (Why is that?)
• Atomic Decomposition by Basis Pursuit
• qpOASES: a parametric active-set algorithm for~quadratic programming
• Title not available (Why is that?)
• On the limited memory BFGS method for large scale optimization
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• Two-Point Step Size Gradient Methods
• Decoding by Linear Programming
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Signal Recovery by Proximal Forward-Backward Splitting
• Proximité et dualité dans un espace hilbertien
• Convex Polytopes
• A limited memory steepest descent method
• On the Goldstein-Levitin-Polyak gradient projection method
• Compressed sensing with coherent and redundant dictionaries
• Proximal Newton-Type Methods for Minimizing Composite Functions

Cited In (3)

• Properties and iterative methods for the \(Q\)-lasso
• Safe feature elimination for non-negativity constrained convex optimization
• A gradient descent algorithm for LASSO

Uses Software

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

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)