The Sequential Quadratic Programming Solver: Conditions of Optimality :: SAS/OR(R) 9.2 User's Guide: Mathematical Programming

The Sequential Quadratic Programming Solver

Conditions of Optimality

To facilitate discussion of the optimality conditions, we present the notation to be used for easy reference:

: number of general nonlinear constraints, which include the linear constraints but not the bound constraints
: dimension of , i.e., the number of decision variables
: iterate, i.e., the vector of decision variables
: objective function
$\nabla\!f(x)$: gradient of the objective function
$\nabla^2\!f(x)$: Hessian matrix of the objective function
$\lambda$: Lagrange multiplier vector, $\lambda\in{\mathbb r}^m$
$l(x,\lambda)$: Lagrangian function of constrained problems
$\nabla\!_x l(x,\lambda)$: gradient of the Lagrangian function with respect to

For

and $\lambda$ , the superscript

is used to denote the value at the

th iteration, such as

, and the superscript

is used to denote their corresponding optimal values, such as $\lambda^*$ .

We rewrite the general form of nonlinear optimization problems in the section "Overview" by grouping the equality constraints and inequality constraints. We also rewrite all the general nonlinear inequality constraints and bound constraints in one form as `` $\ge$ '' inequality constraints. Thus we have the following:

$\displaystyle\mathop{\rm minimize}_{x\in{\mathbb r}^n} & f(x) \ {\rm subjectto}& c_i(x) = 0, & i \in {\cal e} \ & c_i(x) \ge 0, & i \in {\cal i}$

where $\cal e$ is the set of indices of the equality constraints, $\cal i$ is the set of indices of the inequality constraints, and $m=|{\cal e}|+|{\cal i}|$ .

A point is feasible if it satisfies all the constraints $c_i(x) = 0, i\in{\cal e}$ , and $c_i(x) \ge 0, i\in{\cal i}$ . The feasible region ${\cal f}$ consists of all the feasible points. In unconstrained cases, the feasible region ${\cal f}$ is the entire ${\mathbb r}^n$ space.

A feasible point is a local solution of the problem if there exists a neighborhood ${\cal n}$ of such that

$f(x)\ge f(x^*)\;\;{\rm forall} x\in{\cal n}\cap{\cal f}$

Further, a feasible point

is a strict local solution if strict inequality holds in the preceding case, i.e.,

$f(x) \gt f(x^*)\;\;{\rm forall} x\in{\cal n}\cap{\cal f}$

A feasible point

is a global solution of the problem if no point in ${\cal f}$ has a smaller function value than

), i.e.,

$f(x)\ge f(x^*) \;\; {\rm for all } x\in{\cal f}$

The SQP solver finds a local minimum of an optimization problem.

Unconstrained Optimization

The following conditions hold for unconstrained optimization problems:

First-order necessary conditions: If is a local solution and is continuously differentiable in some neighborhood of , then
$\nabla\!f(x^*) = 0$
Second-order necessary conditions: If is a local solution and is twice continuously differentiable in some neighborhood of , then $\nabla^2\!f(x^*)$ is positive semidefinite.
Second-order sufficient conditions: If is twice continuously differentiable in some neighborhood of , and if $\nabla\!f(x^*) = 0$ and $\nabla^2\!f(x^*)$ is positive definite, then is a strict local solution.

Constrained Optimization

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

$l(x,\lambda) = f(x) - \sum_{i\in{\cal e}\cup{\cal i}} \lambda_i c_i(x)$

where $\lambda_i,i\in{\cal e}\cup{\cal i}$ , are called Lagrange multipliers. $\nabla\!_x l(x,\lambda)$ is used to denote the gradient of the Lagrangian function with respect to

, and $\nabla_{\!x}^2 l(x,\lambda)$ is used to denote the Hessian of the Lagrangian function with respect to

. The active set at a feasible point

is defined as

${\cal a}(x)={\cal e}\cup\{i\in{\cal i}: c_i(x)=0\}$

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
$\nabla\!c_i(x), i\in{\cal a}(x)$
are linearly independent. 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 is a local minimum and also a regular point. If and $c_i(x),i \in{\cal e}\cup{\cal i}$ , are continuously differentiable, there exist Lagrange multipliers $\lambda^*\in{\mathbb r}^m$ such that the following conditions hold:
$& & \;\:\nabla\!_x l(x^*,\lambda^*) = \nabla\!f(x^*)-\displaystyle\mathop{\sum}_... ...^* & \ge & 0, & i\in{\cal i} \ \lambda_i^* c_i(x^*) & = & 0, & i\in{\cal i}$
The preceding conditions are often known as the Karush-Kuhn-Tucker conditions , or KKT conditions for short.
Second-order necessary conditions: Suppose is a local minimum and also a regular point. Let $\lambda^*$ be the Lagrange multipliers that satisfy the KKT conditions. If and $c_i(x),i \in{\cal e}\cup{\cal i}$ , are twice continuously differentiable, the following conditions hold:
$z^{\rm t} \nabla_{\!x}^2 l(x^*,\lambda^*)z \ge 0$
for all $z\in{\mathbb r}^n$ that satisfy
$\nabla\!c_i(x^*)^{\rm t}z = 0, i\in{\cal a}(x*)$
Second-order sufficient conditions: Suppose there exist a point and some Lagrange multipliers $\lambda^*$ such that the KKT conditions are satisfied. If the conditions
$z^{\rm t} \nabla_{\!x}^2 l(x^*,\lambda^*)z \gt 0$
hold for all $z\in{\mathbb r}^n$ that satisfy
$\nabla\!c_i(x^*)^{\rm t}z = 0, i\in{\cal a}(x^*)$
then is a strict local solution.

Note that the set of all such 's forms the null space of matrix $[\nabla\!c_i(x^*)^{\rm t} ]_{i\in{\cal a}(x*)}$ . Hence we can numerically check 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).

Solver's Criteria

The SQP solver declares a solution to be optimal when all the following criteria are satisfied:

The relative norm of the gradient of the Lagrangian function is less than OPTTOL, and the absolute norm of the gradient of the Lagrangian function is less than 1.0E - 2.
When the problem is a constrained optimization problem, the relative norm of the gradient of the Lagrangian function is defined as
$\frac{\vert \nabla _x l(x,\lambda)\vert} {1+ \vert \nabla f(x) \vert}$

When the problem is an unconstrained optimization problem, it is defined as
$\frac{\parallel \nabla\!f(x) \parallel} {1+ | f(x)|}$
The absolute value of each equality constraint is less than FEASTOL.
The value of each `` $\geq$ '' inequality is greater than the right-hand-side constant minus FEASTOL.
The value of each `` $\leq$ '' inequality is less than the right-hand-side constant plus FEASTOL.
The value of each Lagrange multiplier for inequalities is greater than -OPTTOL.
The minimum of both the values of an inequality and its corresponding Lagrange multiplier is less than OPTTOL.

The last four points imply that the complementarity error, defined as $\vert{\min (\lambda_i, c_i)}\vert$ , $i \in {\cal i}$ , approaches zero as the solver progresses.

The SQP solver provides the HESCHECK option to verify that the second-order necessary conditions are also satisfied.

Top of Page