Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization

DOI10.1007/s10107-014-0753-5zbMath1318.90075OpenAlexW2018672358MaRDI QIDQ2515043

Yinyu Ye, Wei Bian, Xiaojun Chen

Publication date: 9 February 2015

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

Full work available at URL: https://doi.org/10.1007/s10107-014-0753-5

zbMATH Keywords

nonconvex minimizationcomplexity analysisinterior point algorithmnon-Lipschitz minimizationfirst-order interior point algorithmsecond-order interior point algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Interior-point methods (90C51)

Related Items

Non-convex regularization and accelerated gradient algorithm for sparse portfolio selection, A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem, Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron, Linearly Constrained Non-Lipschitz Optimization for Image Restoration, A truncated Newton algorithm for nonconvex sparse recovery, A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms, High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks, Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints, An interior stochastic gradient method for a class of non-Lipschitz optimization problems, An improved algorithm for the \(L_2-L_p\) minimization problem, Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions, Some theoretical limitations of second-order algorithms for smooth constrained optimization, Smoothing neural network for \(L_0\) regularized optimization problem with general convex constraints, A singular value \(p\)-shrinkage thresholding algorithm for low rank matrix recovery, Neural network for a class of sparse optimization with \(L_0\)-regularization, A convergent iterative support shrinking algorithm for non-Lipschitz multi-phase image labeling model, Accelerated smoothing hard thresholding algorithms for \(\ell_0\) regularized nonsmooth convex regression problem, A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees, A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees, An Augmented Lagrangian Method for Non-Lipschitz Nonconvex Programming, First-order methods for convex optimization, \(k\)-sparse vector recovery via truncated \(\ell_1 -\ell_2\) local minimization, A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Nonconvex Optimization, Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming, On constrained optimization with nonconvex regularization, Implementable tensor methods in unconstrained convex optimization, Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities, Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, A note on the smoothing quadratic regularization method for non-Lipschitz optimization, Smoothing quadratic regularization method for hemivariational inequalities, Unnamed Item, Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization, High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms, Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization, A gradient descent based algorithm for \(\ell_p\) minimization, Computation of second-order directional stationary points for group sparse optimization, On sparse beamformer design with reverberation, A constrained optimization reformulation and a feasible descent direction method for \(L_{1/2}\) regularization, Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives, An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming, Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary, Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems

Uses Software

• ElemStatLearn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly unbiased variable selection under minimax concave penalty
• Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
• Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
• Complexity bounds for second-order optimality in unconstrained optimization
• Smoothing methods for nonsmooth, nonconvex minimization
• Accelerating the cubic regularization of Newton's method on convex problems
• On the complexity of approximating a KKT point of quadratic programming
• Introductory lectures on convex optimization. A basic course.
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models
• Complexity of unconstrained \(L_2 - L_p\) minimization
• Cubic regularization of Newton method and its global performance
• Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization
• Optimality Conditions and a Smoothing Trust Region Newton Method for NonLipschitz Optimization
• Worst-Case Complexity of Smoothing Quadratic Regularization Methods for Non-Lipschitzian Optimization
• 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
• On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming
• Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
• Comments on «Wavelets in statistics: A review» by A. Antoniadis
• Non-Lipschitz $\ell_{p}$-Regularization and Box Constrained Model for Image Restoration
• Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization