Iterative reweighted minimization methods for l_p regularized unconstrained nonlinear programming

DOI10.1007/S10107-013-0722-4zbMATH Open1308.90170arXiv1210.0066OpenAlexW2063761188MaRDI QIDQ463732FDOQ463732

Authors: Zhaosong Lu 

Publication date: 17 October 2014

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

Abstract: In this paper we study general $l_p$ regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of first- and second-order stationary points, and hence also of local minimizers of the $l_p$ minimization problems. We extend some existing iterative reweighted $l_1$ (IRL1) and $l_2$ (IRL2) minimization methods to solve these problems and proposed new variants for them in which each subproblem has a closed form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous $epsilon$-approximation to $|x{|}_p^p$. Using this result, we develop new IRL1 methods for the $l_p$ minimization problems and showed that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter $epsilon$ is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that $epsilon$ be dynamically updated and approach zero. Our computational results demonstrate that the new IRL1 method is generally more stable than the existing IRL1 methods [21,18] in terms of objective function value and CPU time.

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

Recommendations

• Iterative reweighted methods for \(\ell _1-\ell _p\) minimization
• A new spectral method for \(l_1\)-regularized minimization
• Convergence rate analysis of proximal iteratively reweighted \(\ell_1\) methods for \(\ell_p\) regularization problems
• A Globally Convergent Method for $l_p $ Problems
• On large-scale unconstrained optimization and arbitrary regularization

zbMATH Keywords

\(l_p\) minimizationiterative reweighted \(l_1\) minimizationiterative reweighted \(l_2\) minimization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Probing the Pareto frontier for basis pursuit solutions
• Title not available (Why is that?)
• Atomic Decomposition by Basis Pursuit
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• 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
• Sparse Reconstruction by Separable Approximation
• Iterative hard thresholding for compressed sensing
• An affine scaling methodology for best basis selection
• Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization
• Optimization and nonsmooth analysis
• Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
• Restricted isometry properties and nonconvex compressive sensing
• Iteratively reweighted least squares minimization for sparse recovery
• Recovery of sparsest signals via \(\ell^q \)-minimization
• Sparse Approximation via Penalty Decomposition Methods
• Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
• Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
• An interior-point method for large-scale \(l_1\)-regularized logistic regression
• Minimizing Nonconvex Functions for Sparse Vector Reconstruction
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization

Cited In (72)

• A new globally convergent algorithm for non-Lipschitz \(\ell_{p}-\ell_q\) minimization
• Entropy function-based algorithms for solving a class of nonconvex minimization problems
• On optimal solutions of the constrained \({\ell}_{0}\) regularization and its penalty problem
• Isotropic non-Lipschitz regularization for sparse representations of random fields on the sphere
• On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1]\)
• An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis
• A residual-based algorithm for solving a class of structured nonsmooth optimization problems
• A smoothing iterative method for quantile regression with nonconvex \(\ell_p\) penalty
• Accelerated sparse recovery via gradient descent with nonlinear conjugate gradient momentum
• Relating \(\ell_p\) regularization and reweighted \(\ell_1\) regularization
• Convergence of the reweighted \(\ell_1\) minimization algorithm for \(\ell_2-\ell_p\) minimization
• The nonconvex tensor robust principal component analysis approximation model via the weighted \(\ell_p\)-norm regularization
• Lagrangian regularization approach to constrained optimization problems
• The method IRLs for some best \(\ell_p\) norm solutions of under- or overdetermined linear systems
• Nonconvex sorted \(\ell_1\) minimization for sparse approximation
• A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
• An efficient non-convex total variation approach for image deblurring and denoising
• Penalty methods for a class of non-Lipschitz optimization problems
• Iterative reweighted methods for \(\ell _1-\ell _p\) minimization
• A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem
• Linearly constrained non-Lipschitz optimization for image restoration
• Nonlinear residual minimization by iteratively reweighted least squares
• A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron
• A Globally Convergent Method for $l_p $ Problems
• Tensor Robust Principal Component Analysis via Tensor Fibered Rank and \({\boldsymbol{{l_p}}}\) Minimization
• A constrained optimization reformulation and a feasible descent direction method for \(L_{1/2}\) regularization
• A general framework of rotational sparse approximation in uncertainty quantification
• On constrained optimization with nonconvex regularization
• A unified primal dual active set algorithm for nonconvex sparse recovery
• Global optimality condition and fixed point continuation algorithm for non-Lipschitz \(\ell_p\) regularized matrix minimization
• Iteratively reweighted \(\ell _1\) algorithms with extrapolation
• Smoothing neural network for \(L_0\) regularized optimization problem with general convex constraints
• Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
• A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems
• A joint matrix minimization approach for multi-image face recognition
• Bayesian robust principal component analysis with structured sparse component
• A Laplacian approach to \(\ell_1\)-norm minimization
• Convergence rate analysis of proximal iteratively reweighted \(\ell_1\) methods for \(\ell_p\) regularization problems
• An efficient optimization approach for a cardinality-constrained index tracking problem
• \(L_p\)-norm regularization algorithms for optimization over permutation matrices
• Optimality conditions for locally Lipschitz optimization with \(l_0\)-regularization
• An interior stochastic gradient method for a class of non-Lipschitz optimization problems
• Mathematical programs with complementarity constraints and a non-Lipschitz objective: optimality and approximation
• Iterative reweighted linear least squares for exact penalty subproblems on product sets
• Iterative thresholding algorithm based on non-convex method for modified \(l_p\)-norm regularization minimization
• An outer-inner linearization method for non-convex and nondifferentiable composite regularization problems
• Sparse minimax portfolio and Sharpe ratio models
• Nonconvex and nonsmooth sparse optimization via adaptively iterative reweighted methods
• Theory and application of \(p\)-regularized subproblems for \(p>2\)
• An improved algorithm for the \(L_2-L_p\) minimization problem
• Image retinex based on the nonconvex TV-type regularization
• Fast half-quadratic algorithm for image restoration and reconstruction
• Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization
• Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm
• Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
• A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems
• A general non-Lipschitz infimal convolution regularized model: Lower bound theory and algorithm
• An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration
• Non-convex \(\ell_p\) regularization for sparse reconstruction of electrical impedance tomography
• An efficient semismooth Newton method for adaptive sparse signal recovery problems
• \(\ell _p\) regularized low-rank approximation via iterative reweighted singular value minimization
• A new computational method for the sparsest solutions to systems of linear equations
• Nonconvex flexible sparsity regularization: theory and monotone numerical schemes
• A globally convergent algorithm for a class of gradient compounded non-Lipschitz models applied to non-additive noise removal
• A fast and effective algorithm for sparse linear regression with \(\ell_p\)-norm data fidelity and elastic net regularization
• Constrained optimization involving nonconvex \(\ell_p\) norms: optimality conditions, algorithm and convergence
• Nonnegative iterative reweighted method for sparse linear complementarity problem
• Robust amplitude method with \(L_{1/2}\)-regularization for compressive phase retrieval
• Doubly iteratively reweighted algorithm for constrained compressed sensing models
• Approximation methods for a class of non-Lipschitz mathematical programs with equilibrium constraints
• A unified analysis of convex and non-convex \(\ell_p\)-ball projection problems
• An accelerated majorization-minimization algorithm with convergence guarantee for non-Lipschitz wavelet synthesis model

Uses Software

• PDCO
• SPGL1

This page was built for publication: Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming

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