A smoothing SQP framework for a class of composite L_q minimization over polyhedron
From MaRDI portal
Publication:304258
DOI10.1007/S10107-015-0939-5zbMATH Open1346.90684arXiv1407.7205OpenAlexW1577667013MaRDI QIDQ304258FDOQ304258
Authors: Ya-Feng Liu, Yuhong Dai, Shiqian Ma, Shuzhong Zhang 
Publication date: 25 August 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: The composite minimization problem over a general polyhedron has received various applications in machine learning, wireless communications, image restoration, signal reconstruction, etc. This paper aims to provide a theoretical study on this problem. Firstly, we show that for any fixed , finding the global minimizer of the problem, even its unconstrained counterpart, is strongly NP-hard. Secondly, we derive Karush-Kuhn-Tucker (KKT) optimality conditions for local minimizers of the problem. Thirdly, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires a (approximate) solution of a convex quadratic program at each iteration. Finally, we analyze the worst-case iteration complexity of the framework for returning an -KKT point; i.e., a feasible point that satisfies a perturbed version of the derived KKT optimality conditions. To the best of our knowledge, the proposed framework is the first one with a worst-case iteration complexity guarantee for solving composite minimization over a general polyhedron.
Full work available at URL: https://arxiv.org/abs/1407.7205
Recommendations
- Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization
- Complexity of unconstrained \(L_2 - L_p\) minimization
- A note on the complexity of \(L _{p }\) minimization
- A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
- An improved algorithm for the \(L_2-L_p\) minimization problem
optimality conditionsmoothing approximation\(\epsilon \)-KKT pointcomposite \(L_q\) minimizationnonsmooth nonconvex non-Lipschitzian optimizationworst-case iteration complexity
Numerical mathematical programming methods (65K05) Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)
Cites Work
- Preprocessing for quadratic programming
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Probing the Pareto frontier for basis pursuit solutions
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Support-vector networks
- Title not available (Why is that?)
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Smooth minimization of non-smooth functions
- Title not available (Why is that?)
- Nonmonotone Spectral Projected Gradient Methods on Convex Sets
- Optimization theory and methods. Nonlinear programming
- Two-Point Step Size Gradient Methods
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Decoding by Linear Programming
- A group bridge approach for variable selection
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Title not available (Why is that?)
- Smoothing methods for nonsmooth, nonconvex minimization
- Sparse Reconstruction by Separable Approximation
- An affine scaling methodology for best basis selection
- Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization
- Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization
- Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization
- A mathematical introduction to compressive sensing
- Optimization and nonsmooth analysis
- Title not available (Why is that?)
- Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Complexity of unconstrained \(L_2 - L_p\) minimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- 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
- Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
- Title not available (Why is that?)
- A note on the complexity of \(L _{p }\) minimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
- Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization
- Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization
- Large-scale linear programming techniques for the design of protein folding potentials
- Recursive approximation of the high dimensional max function
- \(R\)-linear convergence of the Barzilai and Borwein gradient method
- Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization
- On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
- Minimizing Nonconvex Functions for Sparse Vector Reconstruction
- Joint Power and Admission Control via Linear Programming Deflation
- Joint Power and Admission Control: Non-Convex <formula formulatype="inline"><tex Notation="TeX">$L_{q}$</tex></formula> Approximation and An Effective Polynomial Time Deflation Approach
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
- Non-Lipschitz $\ell_{p}$-Regularization and Box Constrained Model for Image Restoration
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- A framework of constraint preserving update schemes for optimization on Stiefel manifold
Cited In (20)
- Nonnegative iterative reweighted method for sparse linear complementarity problem
- Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability
- Complexity of finite-sum optimization with nonsmooth composite functions and non-Lipschitz regularization
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problems
- Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
- On constrained optimization with nonconvex regularization
- Sparse Solutions by a Quadratically Constrained ℓq (0 <q< 1) Minimization Model
- A gradient descent based algorithm for \(\ell_p\) minimization
- \(L_p\)-norm regularization algorithms for optimization over permutation matrices
- An augmented Lagrangian method for non-Lipschitz nonconvex programming
- 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
- A Smoothing Active Set Method for Linearly Constrained Non-Lipschitz Nonconvex Optimization
- An improved algorithm for the \(L_2-L_p\) minimization problem
- Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs
- A generalized elastic net regularization with smoothed \(\ell _{q}\) penalty for sparse vector recovery
- Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- A smoothing direct search method for Monte Carlo-based bound constrained composite nonsmooth optimization
Uses Software
This page was built for publication: A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304258)
