Unconstrained Optimization

The following conditions hold true for unconstrained optimization problems:

• First-order necessary conditions:  If is a local solution and is continuously differentiable in some neighborhood of , then

• Second-order necessary conditions:  If is a local solution and is twice continuously differentiable in some neighborhood of , then is positive semidefinite.

• Second-order sufficient conditions:  If is twice continuously differentiable in some neighborhood of , , and is positive definite, then is a strict local solution.

Constrained Optimization

For constrained optimization problems, the Lagrangian function is defined as follows:

where , are called Lagrange multipliers. is used to denote the gradient of the Lagrangian function with respect to , and is used to denote the Hessian of the Lagrangian function with respect to . The active set at a feasible point is defined as

We also need the following definition before we can state the first-order and second-order necessary conditions:

• Linear independence constraint qualification and regular point:  A point is said to satisfy the linear independence constraint qualification if the gradients of active constraints

  are linearly independent. Further, we refer to such a point as a regular point.

We now state the theorems that are essential in the analysis and design of algorithms for constrained optimization:

• First-order necessary conditions:  Suppose that is a local minimum and also a regular point. If and , are continuously differentiable, there exist Lagrange multipliers such that the following conditions hold:

  The preceding conditions are often known as the Karush-Kuhn-Tucker conditions, or KKT conditions for short. Also, the first set of equations are referred to as the stationarity condition, and the last set of equations are referred to as the complementarity condition.

• Second-order necessary conditions:  Suppose is a local minimum and also a regular point. Let be the Lagrange multipliers that satisfy the KKT conditions. If and , are twice continuously differentiable, the following conditions hold:

  for all that satisfy

• Second-order sufficient conditions:  Suppose there exist a point and some Lagrange multipliers such that the KKT conditions are satisfied. If the conditions

  for all that satisfy

  hold true, then is a strict local solution.

  Note that the set of all such ’s forms the null space of the matrix . Hence we can search for strict local solutions by numerically checking the Hessian of the Lagrangian function projected onto the null space. For a rigorous treatment of the optimality conditions, see Fletcher (1987) and Nocedal and Wright (1999).

The optimization algorithms in the NLPC solver apply an iterative process that results in a sequence of points, , that converge to a local solution satisfying the first-order conditions. At the solution the NLPC solver performs tests to confirm that the second-order conditions are also satisfied.