A Lagrange-Newton algorithm for sparse nonlinear programming

DOI10.1007/S10107-021-01719-XzbMATH Open1504.90164arXiv2004.13257OpenAlexW3208489956MaRDI QIDQ2089792FDOQ2089792

Authors: Chen Zhao, Ziyan Luo, Naihua Xiu, Houduo Qi 

Publication date: 24 October 2022

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

Abstract: The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning, pattern recognition, finance and management, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous $el{l}_0$-norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong $$-Lagrangian stationarity via the Lagrangian function, and reformulate it as a system of nonlinear equations called the Lagrangian equations. The nonsingularity of the corresponding Jacobian is discussed, based on which the Lagrange-Newton algorithm (LNA) is then proposed. Under mild conditions, we establish the locally quadratic convergence and the iterative complexity estimation of LNA. To further demonstrate the efficiency and superiority of our proposed algorithm, we apply LNA to solve two specific application problems arising from compressed sensing and sparse high-order portfolio selection, in which significant benefits accrue from the restricted Newton step in LNA.

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

Recommendations

• Optimality conditions for sparse nonlinear programming
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
• A sparse nonlinear optimization algorithm
• Newton method for \(\ell_0\)-regularized optimization

zbMATH Keywords

Newton methodlocally quadratic convergenceapplicationLagrangian equationsparse nonlinear programming

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonlinear programming (90C30) Newton-type methods (49M15)

Cites Work

• Superlinearly convergent variable metric algorithms for general nonlinear programming problems
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Restart procedures for the conjugate gradient method
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Compressed sensing
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• Complexity of unconstrained \(L_2 - L_p\) minimization
• On solutions of sparsity constrained optimization
• On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms
• Sparse Approximate Solutions to Linear Systems
• Sparse Approximation via Penalty Decomposition Methods
• The sparse principal component analysis problem: optimality conditions and algorithms
• An interior-point method for large-scale \(l_1\)-regularized logistic regression
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Minimization of \(\ell_{1-2}\) for compressed sensing
• Hard thresholding pursuit: an algorithm for compressive sensing
• Gradient Pursuits
• Optimal cardinality constrained portfolio selection
• Manifold elastic net: a unified framework for sparse dimension reduction
• Title not available (Why is that?)
• Optimality conditions for sparse nonlinear programming
• An efficient optimization approach for a cardinality-constrained index tracking problem
• A convergent iterative hard thresholding for nonnegative sparsity optimization
• DC formulations and algorithms for sparse optimization problems
• Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming
• Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method
• Title not available (Why is that?)
• Title not available (Why is that?)
• A null-space-based weightedl₁minimization approach to compressed sensing

Cited In (10)

• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Penalty method for the sparse portfolio optimization problem
• Solving Large Sparse Nonlinear Programs Using GRG
• A Lagrange–Newton algorithm for tensor sparse principal component analysis
• Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds
• A conjugate gradient algorithm for sparse linear inequalities
• The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results
• An algorithm for solving sparse nonlinear least squares problems
• A greedy Newton-type method for multiple sparse constraint problem
• Greedy Gauss-Newton algorithms for finding sparse solutions to nonlinear underdetermined systems of equations

Uses Software

• CoSaMP

This page was built for publication: A Lagrange-Newton algorithm for sparse nonlinear programming

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