Publication:2001208

DOI10.1016/J.JCO.2018.11.001zbMATH Open1415.90118arXiv1705.07285OpenAlexW2963733310WikidataQ128957479 ScholiaQ128957479MaRDI QIDQ2001208FDOQ2001208

Yanyan Li

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

zbMATH Keywords

nonlinear optimizationcomplexity theoryconstrained problemshigh-order optimality conditions

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonlinear programming (90C30)

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)