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 (47)

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

This page was built for publication: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization