Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization
From MaRDI portal
Publication:2001208
DOI10.1016/J.JCO.2018.11.001zbMATH Open1415.90118arXiv1705.07285OpenAlexW2963733310WikidataQ128957479 ScholiaQ128957479MaRDI QIDQ2001208FDOQ2001208
Publication date: 2 July 2019
Published in: Journal of Complexity (Search for Journal in Brave)
Abstract: Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.
Full work available at URL: https://arxiv.org/abs/1705.07285
Cites Work
- Title not available (Why is that?)
- Convex Analysis
- Linearly Constrained Non-Lipschitz Optimization for Image Restoration
- Trust Region Methods
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
- Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
- Second Order Optimality Conditions Based on Parabolic Second Order Tangent Sets
- Direct Search Based on Probabilistic Descent
- Metric regularity, tangent sets, and second-order optimality conditions
- Worst case complexity of direct search
- An envelope-like effect of infinitely many inequality constraints on second-order necessary conditions for minimization problems
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- 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
- 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
- Practical inexact proximal quasi-Newton method with global complexity analysis
- A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization
- Cubic regularization of Newton method and its global performance
- Optimality Conditions for Degenerate Extremum Problems with Equality Constraints
- Point-to-Set Maps in Mathematical Programming
- On a global complexity bound of the Levenberg-marquardt method
- Convergence properties of the regularized Newton method for the unconstrained nonconvex optimization
- An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
- On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization
- Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
- Nonlinear stepsize control algorithms: complexity bounds for first- and second-order optimality
- A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
- Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
- On the complexity of finding first-order critical points in constrained nonlinear optimization
- On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization
- The \(p\)th-order optimality conditions for inequality constrained optimization problems
- Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization
- On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models
- On the use of the energy norm in trust-region and adaptive cubic regularization subproblems
- On High-order Model Regularization for Constrained Optimization
- On Nesterov's smooth Chebyshev–Rosenbrock function
Cited In (10)
- A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis
- Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints
- Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian
- High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
- Ghost Penalties in Nonconvex Constrained Optimization: Diminishing Stepsizes and Iteration Complexity
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Hessian barrier algorithms for non-convex conic optimization
- 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
- Sharp Worst-Case Evaluation Complexity Bounds for Arbitrary-Order Nonconvex Optimization with Inexpensive Constraints
This page was built for publication: Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2001208)
