Language Reference

NLPQUA Call

nonlinear optimization by quadratic method

CALL NLPQUA( rc, xr, quad, x0 <,opt, blc, tc, par, "ptit", lin>);

See the section "Nonlinear Optimization and Related Subroutines" for a listing of all NLP subroutines. See Chapter 11 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
\frac{1}2 x^tgx + g^tx + {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 a_k of active linear constraints is updated iteratively (refer to Gill et al. 1984). If n_f is the number of free parameters (that is, n minus the number of active boundary constraints), and n_a is the number of active linear constraints, then q is an n_f x   n_f orthogonal matrix containing null space z in its first n_f-n_a columns and range space y in its last n_a columns. The matrix t is an n_a x n_a triangular matrix of the form t_{ij}=0 for i \lt n-j. The Cholesky factor of the projected Hessian matrix z^t_kgz_k 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: 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 x \geq 0, 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: 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 Betts problem (see the section "Constrained Betts Function") can be expressed as a quadratic problem in the following way:
x = [ x_1 \    x_2    ],    g = [ 0.02 & 0 \    0 & 2    ],    g = [ 0 \    0    ],     {con} = -100
Then
\frac{1}2 x^tgx - g^tx + {con}   = 0.5[0.02x_1^2 + 2x_2^2] - 100   = 0.01x_1^2 + x_2^2 - 100
The following statements use the NLPQUA subroutine to solve the Betts problem:
  
    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 follows.

  
  
                          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
 

Previous Page | Next Page | Top of Page