SNOPT Description of the SQP method

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.

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 $5\leq 2x_{1}+3x_{2}\leq +\infty$ is replaced by $2x_{1}+3x_{2}-s_{1}=0\,$ together with the bounded slack $5\leq s_{1}\leq +\infty$. SparseNP can therefore be written in the equivalent form

$\min _{x,s}\quad f_{0}(x)$

${\text{subject to}}\quad \left({\begin{array}{c}f(x)\\A_{L}x\end{array}}\right)-s=0,l\leq \left({\begin{array}{c}x\\s\end{array}}\right)\leq u.$

The general constraints become the equalities f (x) - s_N = 0 and A_Lx - s_L = 0, where s_L and s_N are known as the 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_Lx - 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

${\begin{array}{ccc}f'(x_{k})x-s_{N}&=&f(x_{k})+f(x_{k})'x_{k},\\A_{L}X-s_{L}&=&0,\end{array}}$

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

$A=\left({\begin{array}{c}f'(x_{k})\\A_{L}\end{array}}\right)\quad and\quad b=\left({\begin{array}{c}-f(x_{k})+f'(x_{k})x_{k}\\0\end{array}}\right),$

then the QP subproblem can be written as

$\min _{x,s}\quad q(x)\quad {\text{subject to}}\quad Ax-s=b,\quad l\leq \left({\begin{array}{c}x\\s\end{array}}\right)\leq u,$

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

$Bx_{B}+Sx_{S}+Nx_{N}=b,$

where the basis matrix B is square and nonsingular. The elements of x_B, x_S and x_N are called the 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_S 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 (x, s) continues to satisfy Ax - s = b. The number of superbasic variables (n_S , say) therefore indicates the number of degrees of freedom remaining after the constraints have been satisfied. In broad terms, n_S is a measure of how nonlinear the problem is. In particular, n_S will always be zero for LP problems.

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_S is decreased by one.

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^Tπ, where 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_j = 0 for all nonbasic variables at their lower bounds, d_j = 0 for all nonbasic variables at their upper bounds, and d_j = 0 for other variables, including superbasics. In practice, an approximate QP solution $({\hat {x}}_{k},{\hat {t}}_{k},{\hat {\pi }}_{k})$ 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,\pi )=f_{0}(x)-\pi ^{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_k, s_k , p_k) denotes the current solution estimate and $({\hat {x}}_{k},{\hat {t}}_{k},{\hat {pi}}_{k})$ denotes the QP solution, the line search determines a step $\alpha _{k}(0<\alpha _{k}\leq 1)$ such that the new point

$\left({\begin{array}{c}x_{k+1}\\s_{k+1}\\\pi _{k+1}\end{array}}\right)=\left({\begin{array}{c}x_{k}\\s_{k}\\\pi _{k}\end{array}}\right)+\alpha _{k}\left({\begin{array}{c}{\hat {x}}_{k}-x_{k}\\{\hat {s}}_{k}-s_{k}\\{\hat {\pi }}_{k}-\pi _{k}\end{array}}\right)$

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)

$\min _{x,v,w}\quad e^{T}(v+w)$

${\text{subject to}}\quad l\leq \left({\begin{array}{c}x\\A_{L}x-v+w\end{array}}\right)\leq u,\quad v\geq 0,\quad w\geq 0,$

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(γ))

$\min _{x,v,w}\quad f_{0}(x)+\gamma e^{T}(v+w)$

${\text{subject to}}\quad l\leq \left({\begin{array}{c}x\\f(x)-v+w\\A_{L}x\end{array}}\right)\leq u\quad v\geq 0,\quad w\geq 0$

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

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

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