Solvers and saddle points

Question

It seems like most solvers that can tackle nonlinear nonconvex optimization problems (e.g. IPOPT) operate on ultimately solving for the first-order optimality conditions. Can it therefore be assumed that these solvers do not guarantee convergence to a local minimzer, since saddle points and maximizers also satisfy the optimality conditions? If this is the case, what techniques do solvers use to try and avoid the points that are not minimizers (if at all)?

Answer 1

While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective function for algorithms which attain and maintain primal feasibility, or improvement in a merit function (or similarly with filter methods) for algorithms which don't immediately attain and maintain primal feasibility. This is often accomplished by line search or trust regions (in which whether tentative step is accepted and trust region size is changed depends on improvement in the objective function relative to what was expected).

None of these techniques generally guarantee convergence to a local minimum (for minimization), as opposed to a local maximum or saddle point, but they tend to help. They are very unlikely to "land" (terminate) on a local maximum, although this can happen at the starting point if it happens to be a local maximum and second order conditions are not checked. Most of these algorithms tend not to terminate at saddle points, but they can, and the propensity for doing so depends on the algorithm, the details of its implementation, and the problem and starting point.

It's not common, but it is possible to add a(n optional) second order optimality check, presuming the Hessian of the Lagrangian can be computed or adequately approximated. Note that a BFGS Hessian estimate is useless for this purpose as it artificially maintains positive semidefinitenss.

Second order KKT conditions are as follows: A point satisfying 1st order KKT conditions and for which objective function and constraints are twice continuously differentiable is (sufficient for) a local minimum if the the Hessian of the Lagrangian projected into the nullspace of the Jacobian of active constraints is positive semidefinite. Letting $Z$ be a basis for the nullspace of the Jacobian of active constraints, second order KKT condition is that $Z^THZ$ is positive semi-definite, where $H$ is the Hessian of the Lagrangian. If $Z^THZ$ is indefinite, i.e., has at least one positive eigenvalue and at least one negative eigenvalue, then the point is a saddle point. Active constraints consist of all equality constraints plus all inequality constraints which are satisfied with equality at the point under consideration. If no constraints are active at the 1st order KKT point under consideration, the identity matrix is a nullspace basis $Z$, and all Lagrange multipliers must be zero, therefore, the second order necessary condition for a local minimum reduces to the familiar condition from unconstrained optimization that the Hessian of the objective function is positive semidefinite. If all constraints are linear, the Hessian of the Lagrangian = Hessian of objective function because the 2nd derivative of a linear function = 0.

A good book to learn in depth about much of this is "Numerical Optimization", Nocedal and Wright