NLPQL (Nonlinear Programming by Quadratic Lagrangian) is a mathematical optimization algorithm developed by Klaus Schittkowski. It solves constrained nonlinear programming problems of the form
Minimize:
Subject to:
where:
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 (Armijo) line search.
The method presupposes that the problem size is not too large and that it is well-scaled. Also, the accuracy of the methods depends on the accuracy of the gradients. Because analytical gradients are unavailable for most practical problems, it is imperative that the numerical (finite difference based) gradients are as accurate as possible.
Before the actual derivation of the NLPQL equations, Newton's iterative method for
the solution of nonlinear equation sets is reviewed. Let be a multivariable function such that it can be expanded about the
point
in a Taylor's series.
(15) |
where it is assumed that the Taylor series actually models a local area of the function by a quadratic approximation. The objective is to devise an iterative scheme by linearizing the vector Equation 15. To this end, it is assumed that at the end of the iterative cycle, the Equation 15 would be exactly valid. This implies that the first variation of the following expression with respect to Δx must be zero.
(16) |
Which implies that
(17) |
The first expression indicates the first variation of the converged solution with respect to the increment in the independent variable vector. This gradient is necessarily zero because the converged solution clearly does not depend on the step-length. Therefore, Equation 17 can be written as the following:
(18) |
where the index indicates the iteration. Equation 18 is therefore used
in the main quadratic programming scheme.
Consider the following single-objective nonlinear optimization problem. It is
assumed that the problem is smooth and analytic throughout and is a problem of
decision variables.
Minimize:
Subject to:
where:
(19) |
Where and
are the numbers of inequality and equality constraints. In many cases
the inequality constraints are bound above and below, in such cases, it is customary to
split the constraint into two inequality constraints. To approximate the quadratic
sub-problem assuming the presence of only equality constraints, the Lagrangian for Equation 19 as:
(20) |
Where is a
dimensional vector (non-zero), which are used as Lagrange multipliers.
Thus, Equation 20 becomes a functional, which depends on two sets of
independent vectors. To minimize this expression, you seek the stationarity of this
functional with respect to the two sets of vectors. These expressions give rise to two
sets of vector expressions as the following:
(21) |
Equation 21 defines the Karush-Kuhn-Tucker (KKT) conditions that are the
necessary conditions for the existence of the optimal point. The first equation
is composed of nonlinear algebraic equations and the second one is made up of
nonlinear algebraic equations. The matrix
is a
matrix defined as the following:
(22) |
Thus, in Equation 22, each column is a gradient of the corresponding equality constraint. For convenience, the nonlinear equations of Equation 21 can be written as the following:
(23) |
Where Equation 23 is a system of nonlinear equations. The independent variable set
can be written as:
(24) |
while the functional set is written as the following:
(25) |
Referring to the section on Newton based methods, the vector in Equation 24 is updated as the following:
(26) |
The increment of the vector is given by the iterative scheme in Equation 18. Referring to Equation 23, Equation 24, and Equation 25, the iterative equation is expressed as the following:
(27) |
Note that this is only a first order approximation of the Taylor expansion of Equation 23. This is in contrast to Equation 18 where a quadratic approximation is done. This is because in Equation 24, a first order approximation has already been done. The matrices and the vectors in Equation 27 can be expanded as the following:
(28) |
and
(29) |
This is obtained by taking the gradients of Equation 25 with respect
to the two variable sets. The sub-matrix is the
Hessian of the Lagrange function in implicit form.
To demonstrate how Equation 29 is formed, let us consider the
following simple case. Given a vector of two variables and
, you write:
It is required to find the gradient or Jacobian of the vector function
). To this effect, the derivation of the Jacobian is evident because in
the present context, the vector
indicates a set of nonlinear (algebraic) equations and the Jacobian is
the coefficient matrix that "links" the increment of the independent variable vector to
the dependent variable vector. Thus, you can write:
Thus, the Jacobian matrix is formed. In some applications, the equation is written in the following form:
Where the column indicates the gradient of the
component of the dependent variable vector with respect to the
independent vector. This is the formalism you use in determining Equation 29.
Equation 27 can be rewritten as the following:
(30) |
Solution of Equation 30 iteratively solves Equation 31 in a series of linear steps till the point when the increment is negligible. The
update schemes for the independent variable and Lagrange multiplier vectors
and
are written as the following:
(31) |
The individual equations of the Equation 30 are written separately
now. The first equation (corresponding to minimization with respect to ) can be written as:
(32) |
The last step in Equation 32 is done by using Equation 31. Thus, using Equation 32 and Equation 30, the iterative scheme can be rewritten in a simplified form as:
(33) |
Thus, Equation 33 can be used directly to compute the
value of the Lagrange multiplier vector. Note that by using Equation 33, it is possible to compute the update of
and the new value of the Lagrange multiplier vector
in the same iterative step. Equation 33 shows the
general scheme by which the KKT optimality condition can be solved iteratively for a
generalized optimization problem.
Now, consider the following quadratic approximation problem as given by:
(34) |
Subject to the equality constraints given by the following:
(35) |
Where the definition of the matrices in Equation 34 and Equation 35 are given earlier. To solve the quadratic minimization problem let us form the Lagrangian as:
(36) |
Now, the KKT conditions can be derived (as done earlier) by taking gradients of the Lagrangian in Equation 36 as the following:
(37) |
In a condensed matrix form Equation 37 can be written as the following:
(38) |
Equation 38 is the same as Equation 33 – this
implies that the iterative scheme in Equation 38, which actually solves
a quadratic subproblem (Equation 34 and Equation 35) in
the domain . In case the real problem is quadratic, then this iterative scheme
solves the exact problem.
On addition of inequality constraints, the Lagrangian of the actual problem can be written as the following:
(39) |
Note that the inequality constraints have been converted to equality constraints by
using a set of slack variables as the following:
(40) |
The squared term is used to ensure that the slack variable remains positive, which is required to satisfy Equation 40. The Lagrangian in Equation 39 acts as an enhanced objective function. It is seen that the only case where the additional terms might be active is when the constraints are not satisfied.
The KKT conditions as derived from Equation 39 (by taking first variations with respect to the independent variable vectors) are:
(41) |
From the KKT conditions in Equation 41, it is evident that there are
equations for a similar number of unknowns. Therefore, this equation
set possesses a unique solution. Let this (optimal) solution be marked as
. At this point, a certain number of constraints are active while
others are inactive. Let the number of active inequality constraints be
and the total number of active equality constraints be
. By an active constraint, it is assumed that the constraint is at its
threshold value of zero. Therefore, let
and
be the sets of active and inactive equality constraints (respectively)
and
and
be the sets of active and inactive inequality constraints
respectively. Therefore, you can write the following relations:
(42) |
Where indicates the count of the elements of the set under consideration.
These sets partition the constraints into active and inactive sets. Therefore, you can
write:
(43) |
Thus, the last three equations in Equation 41 can be represented by
the Equation 43. These are the optimality conditions for constraint
satisfaction. From these equations, you can now eliminate such that the Lagrangian in Equation 39 depends on
only three independent variable vectors. From the last two conditions in Equation 43, you can write the following condition, which is always valid
for an optimal point:
(44) |
Using Equation 44 in the set Equation 41, the KKT optimality conditions can be written as the following:
(45) |
Thus, the new set contains only unknowns. Now, following the same logic as in Equation 24 as done earlier—let us express Equation 45
in the same form as in Equation 23. This represents a
system of nonlinear equations. The independent variable set can be
written in vector form as the following:
(46) |
Newton's iterative scheme is also used here. Therefore, the same equations as in Equation 26 and Equation 27 also apply here. Following Equation 27, you can write:
(47) |
Taking the first variation of the KKT equations in Equation 45 and equating to zero, the sub-quadratic equation is formulated as the following:
(48) |
where: indicates a diagonal matrix.
At the step, the first equation can be written (by linearization) as:
(49) |
Which simplifies to:
(50) |
Thus, the linearized set of equations for Newton’s method to be applied can be written in an explicit form as:
(51) |
So, in presence of both equality and inequality constraints, Equation 51 can be used in a quasi-Newtonian framework to determine the
increments and Lagrange multipliers
and
when stepping from iteration
to
.
The Hessian matrix is not computed directly but is estimated and updated in a BFGS type
line search.