The Sequential Quadratic Programming Solver

Overview

The sequential quadratic programming (SQP) solver is a component of the OPTMODEL procedure, and it can be used for solving general nonlinear programming (NLP) problems.

The general form of nonlinear optimization problems can be mathematically described as follows:

$\displaystyle\mathop{\rm minimize}_{x\in \mathbb{r}^n} & f(x) \ {\rm subjectto}& c(x) \:\{\le | = | \ge\}\: 0 \ & l \le x \le u$

where : $\mathbb{r}^n\mapsto\mathbb{r}$ is the nonlinear objective function, : $\mathbb{r}^n\mapsto\mathbb{r}^m$ is the set of general nonlinear equality and inequality constraints, and and are lower and upper bounds, respectively, on the decision variable .

The SQP solver solves NLP problems by using an iterative procedure. An improved estimate of the solution is obtained at the end of each iteration by taking a step along a certain search direction. This direction is computed by solving a quadratic programming (QP) subproblem (Fletcher 1987).

It has been found that SQP-based algorithms are very efficient for solving NLP problems. Such a view is based on their strong convergence properties, supported by good numerical results from test experiments (Conn, Gould, and Toint 1994).

The SQP solver basically adapts the ideas from Bartholomew-Biggs's work (Bartholomew-Biggs 1988). It uses an augmented Lagrangian penalty function as a merit function . The solver solves a QP subproblem to obtain a search direction, which is an approximation of the Newton direction to the minimum of the merit function. A line-search algorithm is then implemented along the resulting search direction. In the SQP solver, the line search is terminated when Wolfe-Powell conditions are satisfied, thereby ensuring global convergence to a local minimum (Fletcher 1987).

The SQP solver has several features that make it different from the other NLP solvers in the SAS/OR suite (see Chapter 10, "The NLPC Nonlinear Optimization Solver," and Chapter 11, "The Unconstrained Nonlinear Programming Solver"). To name a few:

It can handle general nonlinear constraints.
It exploits the sparsity (of the Jacobian) in NLP problems. This enables the SQP solver to solve fairly large NLP problems.
It finds the negative curvature of the NLP problem at a stationary point of the problem, thereby giving the solver a better chance of moving away from a stationary point.
It tries to find a good estimate of Lagrange multipliers based on a good starting point for the decision variables.

In general, the SQP solver approaches the solution of a NLP problem through a sequence of points that might not be in the feasible region. Therefore it requires that all the functions in the NLP problem be defined in the entire space, not just at the points that satisfy the constraints.

Another requirement is that all the functions in NLP problems be smooth. You do not need to supply the derivatives of these functions; the SQP solver calculates them, if needed.

Top of Page