CADFamily.com: Sequential Quadratic Programming Algorithm NLPQL in ISight

1. INTRODUCTION

In this document we describe some basic features of the sequential quadratic programming algorithm NLPQL of Schittkowski (1985/86), a Fortran code for solving nonlinear programming problems of the form

It is assumed that objective function and constraints are continuously differentiable. The idea is to generate a sequence of quadratic programming subproblems obtained by a quadratic approximation of the Lagrangian function and a linearization of the constraints. Second order information is updated by a quasi-Newton formula and the method is stabilized by an additional line search.

A particular advantage of NLPQL is its ease of use based on a very robust implementation. Only the maximum number of iterations and the desired final accuracy must be defined by the user.

span style='mso-ignore:vglayout;;z-index:1;margin-left:0px; margin-top:11px;width:617px;height:3px'

2. THE MATHEMATICAL ALGORITHM

Sequential quadratic programming or SQP methods are the standard general purpose tool for solving smooth nonlinear optimization problems under the following assumptions:

- The problem is not too large.

- The functions and gradients can be evaluated with sufficiently high precision.

- The problem is smooth and well-scaled.

- There is no further model structure that can be exploited.

The mathematical convergence and the numerical performance properties of SQP methods are very well understood now and are published in so many papers, that only a few can be mentioned here. Theoretical convergence is investigated in Han (1976,1977)EASY_OPT.L__001, Powell (1978a,1978b)EASY_OPT.L__001, Schittkowski (1983)EASY_OPT.L__001, e.g., and the numerical comparative studies of Schittkowski (1980)EASY_OPT.L__001 and Hock, Schittkowski (1981)EASY_OPT.L__001 show their superiority over other mathematical programming algorithms under the assumptions mentioned above.

The key idea is to approximate also second order information to get a fast final convergence speed. Thus we define a quadratic approximation of the Lagrange function L(x,u) and an approximation of the Hessian matrix of L(x_k,u_k) by a so-called quasi-Newton matrix B_k. Then we get the quadratic programming subproblem

To stabilize the algorithm particularly when starting from a bad initial guess x₀, and to ensure global convergence, an additional line search is performed, i.e. a steplength computation to accept a new iterate

for a suitable a_k only if x_k+1 satisfies a descent property with respect to a solution d_k of the quadratic programming subproblem. Following the approach of Schittkowski (1983)EASY_OPT.L__001, e.g., we need also a simultaneous line search with respect to the multiplier approximations and use an augmented Lagrangian merit function to determine the line search parameter. Moreover certain safeguards must be taken into account to prevent that the linearized constraints are contradictious.

The update of the matrix B_k can be performed by standard techniques known from unconstrained optimization. In our case, the BFGS-method is applied, a numerically simple rank-2 correction starting from the identy matrix. Only the difference vectors x_k+1 - x_k and ?L(x_k+1,u_k ) - ?L(x_k ,u_k) are required. Under some safeguards it is possible to guarantee that all matrices B_k are positive definite.

Among the most attractive features of SQP methods is the superlinear convergence speed in the neighbourhood of a solution given by

where g_k is a sequence of positive numbers converging to zero and x* an optimal solution.

To understand this convergence behavior, replace B_k by the true Hessian of the Lagrangian function and consider only equality constraints. Then it is very easy to see that an SQP method is identical to Newton's method for solving the nonlinear system of n+m equations in n+m unknowns given by the Kuhn-Tucker conditions. This result can be extended to inequality constraints as well. Then we get immediately the quadratic convergence behavior and, if we replace B_k again by its approximation, the weaker superlinear convergence rate as proved in the references mentioned above.

3. EXTENSIONS

SQP methods allow the solution of a wide range of nonlinear programming problems in an efficient and reliable way. Either implicitely or proceeding from simple modifications of the underlying optimization problem, a much larger class of different nonlinear programming problems can be solved by NLPQL. A few are to be mentioned subsequently, for more details see Schittkowski (1988,1994).

3.1 Linear Constraints

If some or all of the constraints are linear, we note that they are not changed at all during the constraint linearization process, i.e. they are passed directly to the algorithm solving the quadratic programming subproblem. A particular advantage is that once a linear constraint or bound is satisfied, then this restriction remains satisfied during the whole iteration process.

3.2 System of Nonlinear Equations

In case of finding a solution of a system of nonlinear equations either with or without inequalities, i.e. when trying to find a solution of the system

a nonlinear programming algorithm can be applied directly by defining the above equations as constraints and by adding an artificial objective function. A typical function to be minimized, could be of the form f(x)=x^Tx, if a minimum-norm solution in case of an underdetermined system or inequlities is required.

3.3 Problems with Very Many Constraints

There exists an extension of NLPQL for solving nonlinear programming problems where the number of constraints is very large compared to the number of variables, see Schittkowski (1991). Typical application is semi-infinite optimization, when constraints possess an additional parameter varying in a given continuous set, and where we discretize these constraints at a finite number of break points.

In this situation an active set strategy is applied to prevent a too large number of constraints in the quadratic programming subproblem. One reason is lack of memory, another one the dangerous generation of degenerate or nearly degenerate restrictions, that prevent a stable solution of the subproblem.

3.4 Least Squares Optimization

We consider a mathematical model in form of a least squares problem, i.e. the problem of minimization of a sum of squares of nonlinear functions in the following form:

Here we assume that the parameter vector x is n-dimensional and that all nonlinear functions are continuously differentiable with respect to x. Upper and lower bounds are treated independently from the remaining constraints.

The most important application is parameter estimation, where one model function is available with an additional variable called time. Proceeding now from l measurements of the form

we get the above least squares formulation by

together with a real valued model function h(x,t) and suitable non-negative weighting factors.

Then the underlying idea is to minimize the distance between the model function at certain time points and the corresponding measurement values. This distance is denoted the residual of the problem. In the ideal case the residuals are zero indicating a perfect fit of the model function by the measurements.

Usually least squares problems are solved by the Gauss-Newton-algorithm or any of its numerous variants. If any of theses special purpose implementations is not available, it is recommended to transform the original problem into a general nonlinear programming problem by introducing additional variables and equality constraints, i.e.

Typical features of a Gauss-Newton and quasi-Newton method are retained, see Schittkowski (1988)EASY_OPT.L__001. The resulting optimization problem can be solved by NLPQLEASY_OPT.L__001 as in the general situation. The proposed method is implemented within an interactive system to solve parameter estimation problems in dynamical systems, see Schittkowski (1996).

EASY_OPT.MMA001

3.5 L₁- Optimization

In this case the model consists of minimizing the sum of absolute function values subject to general nonlinear equality or inequality constraints, i.e.

Again we assume that the parameter vector x is n-dimensional and that all nonlinear functions are continuously differentiable with respect to x. Upper and lower bounds are handled separately. However the problem is not differentiable and it is proposed to introduce l additional variables