Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to the first- and second-order conditions. The f...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optimization theory and applications 2020-08, Vol.186 (2), p.480-503
Main Authors: Hallak, Nadav, Teboulle, Marc
Format: Article
Language:English
Subjects:
Applications of Mathematics
Calculus of Variations and Optimal Control
Optimization
Constraints
Engineering
First order algorithms
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to the first- and second-order conditions. The first-order step is a generic closed map algorithm, which can be chosen from a variety of first-order algorithms, making it adjustable to the given problem. The second-order step can be viewed as a second-order feasible direction step for nonconvex minimization subject to a convex set. We prove that any limit point of the resulting scheme satisfies the second-order necessary optimality condition, and establish the scheme’s convergence rate and complexity, under standard and mild assumptions. Numerical tests illustrate the proposed scheme.
ISSN:0022-3239
1573-2878
DOI:10.1007/s10957-020-01713-x