# SNOPT Description of the SQP method

### From TomWiki

This page is part of the SNOPT Manual. See SNOPT. |

Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the description of the subroutine and its arguments. The SQP algorithm is fully described by Gill, Murray and Saunders.

## Contents |

## Constraints and slack variables

The upper and lower bounds on the *m *components of *f *(*x*) and *AL x *are said to define the *general constraints* of the problem. SNOPT converts the general constraints to equalities by introducing a set of *slack variables*. For example, the linear constraint is replaced by together with the bounded slack . SparseNP can therefore be written in the equivalent form

The general constraints become the equalities *f *(*x*) *- s _{N}* = 0 and

*A*= 0, where

_{L}x - s_{L}*s*and

_{L}*s*are known as the

_{N}*linear*and

*nonlinear*slacks.

## Major iterations

The basic structure of the SQP algorithm involves *major *and *minor *iterations. The major iterations generate a sequence of iterates *{x _{k}} *that satisfy the linear constraints and converge to a point that satisfies the first-order

conditions for optimality. At each iterate a QP subproblem is used to generate a search direction towards the next iterate *x*_{k+1} . The constraints of the subproblem are formed from the linear constraints *A _{L}x - s_{L}* = 0 and the nonlinear constraint linearization

*f*(*x*_{k}) + *f*'(*x*_{k})(*x* − *x*_{k}) − *s*_{N} = 0,

where *f'*(*xk *) denotes the *Jacobian matrix*, whose elements are the first derivatives of *f *(*x*) evaluated at *x _{k} *. The QP constraints therefore comprise the

*m*linear constraints

where *x *and *s *are bounded above and below by *u *and *l *as before. If the *m × n *matrix *A *and *m*-vector *b *are defined as

then the QP subproblem can be written as

where *q*(*x*) is a quadratic approximation to a modified Lagrangian function.

## Minor iterations

Solving the QP subproblem is itself an iterative procedure. The iterations of the QP solver are the *minor *iterations of the SQP method. At each minor iteration, the constraints *Ax - s *= *b *are (conceptually) partitioned into the form

*B**x*_{B} + *S**x*_{S} + *N**x*_{N} = *b*,

where the *basis matrix B* is square and nonsingular. The elements of *x _{B}*,

*x*and

_{S}*x*are called the

_{N}*basic*,

*superbasic*and

*nonbasic*variables respectively; they are a permutation of the elements of

*x*and

*s*. At a QP solution, the basic and superbasic variables will lie somewhere between their bounds, while the nonbasic variables will normally be equal to one of their bounds. At each iteration,

*x*is regarded as a set of independent variables that are free to move in any desired direction, namely one that will improve the value of the QP objective (or the sum of infeasibilities). The basic variables are then adjusted in order to ensure that (

_{S}*x, s*) continues to satisfy

*Ax - s*=

*b*. The number of superbasic variables (

*n*, say) therefore indicates the number of degrees of freedom remaining after the constraints have been satisfied. In broad terms,

_{S}*n*is a measure of

_{S}*how nonlinear*the problem is. In particular,

*n*will always be zero for LP problems.

_{S}If it appears that no improvement can be made with the current definition of *B*, *S* and *N *, a nonbasic variable is selected to be added to *S*, and the process is repeated with the value of *n _{S} *increased by one. At all stages, if a basic or superbasic variables encounters one of its bounds, the variables is made nonbasic and the value of

*n*is decreased by one.

_{S}Associated with each of the *m* equality constraints *Ax - s *= *b *are the *dual variables p*. Similarly, each variable in (*x, s*) has an associated *reduced gradient d _{j} *. The reduced gradients for the variables

*x*are the quantities

*g-A*, where

^{T}π*g*is the gradient of the QP objective, and the reduced gradients for the slacks are the dual variables

*p*. The QP subproblem is optimal if

*d*0 for all nonbasic variables at their lower bounds,

_{j}=*d*0 for all nonbasic variables at their upper bounds, and

_{j}=*d*= 0 for other variables, including superbasics. In practice, an

_{j}*approximate*QP solution is found by relaxing these conditions.

## The merit function

After a QP subproblem has been solved, new estimates of the SparseNP solution are computed using a line search on the augmented Lagrangian merit function

*f*(*x*,*s*,π) = *f*_{0}(*x*) − π^{T}(*f*(*x*) − *s*_{N}) + (*f*(*x*) − *S*_{N})^{T}*D*(*f*(*x*) − *S*_{N})

where *D *is a diagonal matrix of penalty parameters (*D _{ii} >= *0). If (

*x*) denotes the current solution estimate and denotes the QP solution, the line search determines a step such that the new point

_{k}, s_{k}, p_{k}

gives a *sufficient decrease *in the merit function. When necessary, the penalties in *D *are increased by the minimum-norm perturbation that ensures descent for *M *.

As in NPSOL, *s _{N}* is adjusted to minimize the merit function as a function of

*s*prior to the solution of the QP subproblem.

## Treatment of constraint infeasibilities

SNOPT makes explicit allowance for infeasible constraints. First, infeasible *linear* constraints are detected by solving the linear program (FLP)

where *e *is a vector of ones, and the nonlinear constraint bounds are temporarily excluded from *l *and *u*. This is equivalent to minimizing the sum of the general linear constraint violations subject to the bounds on *x*. (The sum is the *£*1 -norm of the linear constraint violations. In the linear programming literature, the approach is called *elastic programming*.)

The linear constraints are infeasible if the optimal solution of FLP has *v *≠ 0 or *w *≠ 0. SNOPT then terminates without computing the nonlinear functions.

Otherwise, all subsequent iterates satisfy the linear constraints. (Such a strategy allows linear constraints to be used to define a region in which the functions can be safely evaluated.) SNOPT proceeds to solve SparseNP as given, using search directions obtained from the sequence of QP subproblems.

If a QP subproblem proves to be infeasible or unbounded (or if the dual variables *π *for the nonlinear constraints become large), SNOPT enters "elastic" mode and thereafter solves the problem (NP(γ))

where *γ* is a nonnegative parameter (the *elastic weight *), and *f*_{0}(*x*) + γ*e*^{T}(*v* + *w*) is called a *composite objective* (the penalty function for the nonlinear constraints).

The value of γ may increase automatically by multiples of 10 if the optimal *v *and *w *continue to be nonzero. If γ is sufficiently large, this is equivalent to minimizing the sum of the nonlinear constraint violations subject to the linear constraints and bounds. A similar formulation of SparseNP is fundamental to the QP algorithm of Fletcher. See also Conn.

The initial value of *γ *is controlled by the optional parameters Elastic mode and Elastic weight.