Optimality conditions (NLP)
From DDL Wiki
When solving a continuous nonlinear minimization problem:
a global minimum is a point such that no other feasible point has a lower objective function value. A local minimum is a point such that all feasible points in the neighborhood immediately surrounding the point have higher objective function values.
Because local optimality depends only on the small neighborhood surrounding the point, it is possible to derive necessary and sufficient conditions for local optimality using a Taylor series expansion. NLP algorithms in general search for points that satisfy these conditions. If the NLP formulation is convex, then there is only one local minimum, which is also the global minimum. If the formulation is nonconvex, these conditions do not guarantee global optimality.
For an unconstrained problem:
a candidate point can be tested for local optimality by writing the Taylor series expansion about the point:
If is a local minimum, then, by definition, it must be true that all points in the immediate neighborhood have a higher objective function value - i.e.: there exists an ε > 0 such that
For small (i.e.: for the region in the immediate neighborhood of the candidate point), the first order term of the Taylor series dominates, and higher order terms are negligible. Since the first order term alone cannot satisfy the condition of a local minimum, the linear term must be zero as a necessary condition (so that higher order terms will determine the nature of the point):
which is also written as
Any point satisfying this necessary condition is called a stationary point.
If the necessary condition is satisfied, the second order term of the Taylor series will dominate for small . If the second order term is positive for all (small) , this is sufficient to determine a minimum:
Common Mistake: While it is common to mention only the second order term in discussing sufficiency conditions for optimality, the Taylor series derivation implies other possible sufficiency conditions: If the second order term is zero for any particular direction , then higher order terms dominate along those directions, and their effects must be examined. A common mistake is to believe that a point with both first and second derivatives of zero is necessarily an inflection point. This is not necessarily the case: For example, consider the function f(x) = x4, which has a minimum at zero where the first three derivatives are zero and the fourth order term dominates, creating the sufficiency condition.
If the NLP optimization problem has constraints,
the problem can be reformulated in Lagrangian form to derive analogous optimality conditions. These conditions are again derived from a Taylor series expansion in the reduced space, although the derivation is not provided here:
where is the solution satisfied KKT condition, and
The second-order sufficient condition for local optimality in unconstrained models is:
where the Hessian matrix . To satisfy the sufficient condition, the Hessian matrix needs to be positive definite on the subspace tangent to the active constraints. Because a Hessian matrix is symmetric, it is positive definite when all eigenvalues are positive. A point that satisfies these necessary and sufficient conditions is a local minimum.