The Interior Point NLP Solver: Overview of Constrained Optimization :: SAS/OR(R) 9.22 User's Guide: Mathematical Programming

The Interior Point NLP Solver

Overview of Constrained Optimization

A function that plays a pivotal role in establishing conditions that characterize a local minimum of an NLP problem is the Lagrangian function $\text{[math]}$ , which is defined as

$\text{[math]}$

Note that the Lagrangian function can be seen as a linear combination of the objective and constraint functions. The coefficients of the constraints, $\text{[math]}$ , and $\text{[math]}$ , are called the Lagrange multipliers or dual variables. At a feasible point $\text{[math]}$ , an inequality constraint is called active if it is satisfied as an equality—that is, $\text{[math]}$ . The set of active constraints at a feasible point $\text{[math]}$ is then defined as the union of the index set of the equality constraints, $\text{[math]}$ , and the indices of those inequality constraints that are active at $\text{[math]}$ ; that is,

$\text{[math]}$

An important condition that is assumed to hold in the majority of optimization algorithms is the so-called linear independence constraint qualification (LICQ). The LICQ states that at any feasible point $\text{[math]}$ , the gradients of all the active constraints are linearly independent. The main purpose of the LICQ is to ensure that the set of constraints is well-defined in a way that there are no redundant constraints or in a way that there are no constraints defined such that their gradients are always equal to zero.

The First-Order Necessary Optimality Conditions

If $\text{[math]}$ is a local minimum of the NLP problem and the LICQ holds at $\text{[math]}$ , then there are vectors of Lagrange multipliers $\text{[math]}$ and $\text{[math]}$ , with components $\text{[math]}$ , and $\text{[math]}$ , respectively, such that the following conditions are satisfied:

$\text{[math]}$

where $\text{[math]}$ is the gradient of the Lagrangian function with respect to $\text{[math]}$ , defined as

$\text{[math]}$

The preceding conditions are often called the Karush-Kuhn-Tucker (KKT) conditions, named after their inventors. The last group of equations ( $\text{[math]}$ ) is called the complementarity condition. Its main aim is to try to force the Lagrange multipliers, $\text{[math]}$ , of the inactive inequalities (that is, those inequalities with $\text{[math]}$ ) to zero.

The KKT conditions describe the way the first derivatives of the objective and constraints are related at a local minimum $\text{[math]}$ . However, they are not enough to fully characterize a local minimum. The second-order optimality conditions attempt to fulfill this aim by examining the curvature of the Hessian matrix of the Lagrangian function at a point that satisfies the KKT conditions.

The Second-Order Necessary Optimality Condition

Let $\text{[math]}$ be a local minimum of the NLP problem, and let $\text{[math]}$ and $\text{[math]}$ be the corresponding Lagrange multipliers that satisfy the first-order optimality conditions. Then $\text{[math]}$ for all nonzero vectors $\text{[math]}$ that satisfy the following conditions:

$\text{[math]}$ , $\text{[math]}$
$\text{[math]}$ , $\text{[math]}$ , such that $\text{[math]}$
$\text{[math]}$ , $\text{[math]}$ , such that $\text{[math]}$

The second-order necessary optimality condition states that, at a local minimum, the curvature of the Lagrangian function along the directions that satisfy the preceding conditions must be nonnegative.

Top of Page