NLPQUA Call
nonlinear optimization by quadratic method
- CALL NLPQUA( rc, xr, quad, x0 <,opt, blc, tc, par,
"ptit", lin>);
See "Nonlinear Optimization and Related Subroutines" for a listing of all NLP subroutines.
See Chapter 11, "Nonlinear Optimization Examples," for a description of
the inputs to and outputs of all NLP subroutines.
The NLPQUA subroutine uses a fast algorithm for
maximizing or minimizing the quadratic objective function
-
(1/2) xTGx + gTx + con
subject to boundary constraints and general
linear equality and inequality constraints.
The algorithm is memory-consuming for
problems with general linear constraints.
The matrix G must be symmetric but not necessarily positive
definite (or negative definite for maximization problems).
The constant term con affects only the value of the objective
function, not its derivatives or the optimal point x*.
The algorithm is an active-set method in which the update of
active boundary and linear constraints is done separately.
The QT decomposition of the matrix Ak of
active linear constraints is updated iteratively
(refer to Gill, Murray, Saunders, and Wright, 1984).
If nf is the number of free parameters (that is, n minus
the number of active boundary constraints), and na is the
number of active linear constraints, then Q is an nf ×nf orthogonal matrix containing null space Z in its first
nf-na columns and range space Y in its last na columns.
The matrix T is an na ×na triangular
matrix of the form tij=0 for i < n-j.
The Cholesky factor of the projected Hessian
matrix ZTkGZk is updated simultaneously with
the QT decomposition when the active set changes.
The objective function is specified by the input
arguments quad and lin, as follows:
- The quad argument specifies the symmetric
n ×n Hessian matrix, G, of the quadratic term.
The input can be in dense or sparse form.
In dense form, all n2 entries of the
quad matrix must be specified.
If , the dense specification must be used.
The sparse specification can be useful
when G has many zero elements.
You can specify an nn ×3 matrix in which each
row represents one of the nn nonzero elements of G.
The first column specifies the row location in G, the
second column specifies the column location, and the
third column specifies the value of the nonzero element.
- The lin argument specifies the linear
part of the quadratic optimization problem.
It must be a vector of length n or n+1.
If lin is a vector of length n, it
specifies the vector g of the linear term,
and the constant term con is considered zero.
If lin is a vector of length n+1, then
the first n elements of the argument specify
the vector g and the last element specifies the
constant term con of the objective function.
As in the other optimization subroutines, you can use
the blc argument to specify boundary and general
linear constraints, and you must provide a starting
point x0 to determine the number of parameters.
If x0 is not feasible, a feasible initial
point is computed by linear programming, and
the elements of x0 can be missing values.
Assuming nonnegativity constraints , the
quadratic optimization problem solved with the LCP
call, which solves the linear complementarity problem.
Refer to SAS/IML Software: Usage and
Reference, Version 6, First Edition for details.
Choosing a sparse (or dense) input form of the quad
argument does not mean that the algorithm used in the
NLPQUA subroutine is necessarily sparse (or dense).
If the following conditions are satisfied, the NLPQUA
algorithm will store and process the matrix G as sparse:
- No general linear constraints are specified.
- The memory needed for the sparse storage of G is
less than 80% of the memory needed for dense storage.
- G is not a diagonal matrix.
If G is diagonal, it is stored
and processed as a diagonal matrix.
The sparse NLPQUA algorithm uses a modified form of
minimum degree Cholesky factorization (George and Liu 1981).
In addition to the standard iteration history, the
NLPNRA subroutine prints the following information:
- The heading alpha is the step size,
, computed with the line-search algorithm.
- The heading slope refers to gTs, the slope of the
search direction at the current parameter iterate x(k).
For minimization, this value should
be significantly smaller than zero.
Otherwise, the line-search algorithm has difficulty
reducing the function value sufficiently.
The Betts problem (see "Constrained Betts Function" ) can be
expressed as a quadratic problem in the following way:
Then
-
(1/2) xTGx - gTx + con = 0.5[0.02x12 + 2x22] - 100 = 0.01x12 + x22 - 100
The following statements use the NLPQUA
subroutine to solve the Betts problem:
proc iml;
lin = { 0. 0. -100};
quad = { 0.02 0.0 ,
0.0 2.0 };
c = { 2. -50. . .,
50. 50. . .,
10. -1. 1. 10.};
x = { -1. -1.};
optn = {0 2};
CALL NLPQUA(rc,xres,quad,x,optn,c,,,,lin);
The quad argument specifies the G matrix, and
the lin argument specifies the g vector with
the value of con appended as the last element.
The matrix C specifies the boundary
constraints and the general linear constraint.
The iteration history is shown in Figure 17.10.
Optimization Start
Parameter Estimates
Gradient Lower Upper
Objective Bound Bound
N Parameter Estimate Function Constraint Constraint
1 X1 6.800000 0.136000 2.000000 50.000000
2 X2 -1.000000 -2.000000 -50.000000 50.000000
Value of Objective Function = -98.5376
Linear Constraints
1 59.00000 : 10.0000 <= + 10.0000 * X1 - 1.0000 * X2
Null Space Method of Quadratic Problem
Parameter Estimates 2
Lower Bounds 2
Upper Bounds 2
Linear Constraints 1
Using Sparse Hessian _
Optimization Start
Active Constraints 0 Objective Function -98.5376
Max Abs Gradient Element 2
Function Active Objective
Iter Restarts Calls Constraints Function
1 0 2 1 -99.87349
2 0 3 1 -99.96000
Objective Max Abs Slope of
Function Gradient Step Search
Iter Change Element Size Direction
1 1.3359 0.5882 0.706 -2.925
2 0.0865 0 1.000 -0.173
Optimization Results
Iterations 2 Function Calls 4
Gradient Calls 3 Active Constraints 1
Objective Function -99.96 Max Abs Gradient Element 0
Slope of Search Direction -0.173010381
ABSGCONV convergence criterion satisfied.
Optimization Results
Parameter Estimates
Gradient Active
Objective Bound
N Parameter Estimate Function Constraint
1 X1 2.000000 0.040000 Lower BC
2 X2 0 0
Value of Objective Function = -99.96
Linear Constraints Evaluated at Solution
1 10.00000 = -10.0000 + 10.0000 * X1 - 1.0000 * X2
Figure 17.10: Iteration History for the NLPQUA Subroutine
Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.