Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization
For researchers in nonconvex optimization, this work provides theoretical foundations and algorithmic insights for high-order optimality, though it is largely theoretical and incremental.
The paper explores necessary conditions for high-order optimality in constrained nonconvex optimization and proposes a two-phase algorithm achieving approximate first-, second-, and third-order criticality with analyzed evaluation complexity. It also shows that standard penalization approaches fail to find approximate constrained high-order critical points.
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.