The NLP Procedure

Introductory Examples

The following introductory examples illustrate how to get started using the NLP procedure.

An Unconstrained Problem

Consider the simple example of minimizing the Rosenbrock function (Rosenbrock 1960):

f(x) & = & \frac{1}2 \{ 100 (x_2 - x_1^2)^2 + (1 - x_1)^2 \} \    & = & \frac{1}2 \{ f_1^2(x) + f_2^2(x) \} ,  x = (x_1,x_2)
The minimum function value is  f(x^*) = 0 at  x^* = (1,1). This problem does not have any constraints.

The following statements can be used to solve this problem:

  
    proc nlp; 
       min f; 
       decvar x1 x2; 
       f1 = 10 * (x2 - x1 * x1); 
       f2 = 1 - x1; 
       f  = .5 * (f1 * f1 + f2 * f2); 
    run;
 

The MIN statement identifies the symbol f that characterizes the objective function in terms of f1 and f2, and the DECVAR statement names the decision variables x1 and x2. Because there is no explicit optimizing algorithm option specified (TECH=), PROC NLP uses the Newton-Raphson method with ridging, the default algorithm when there are no constraints.

A better way to solve this problem is to take advantage of the fact that  f is a sum of squares of  f_1 and  f_2 and to treat it as a least-squares problem. Using the LSQ statement instead of the MIN statement tells the procedure that this is a least-squares problem, which results in the use of one of the specialized algorithms for solving least-squares problems (for example, Levenberg-Marquardt).

  
    proc nlp; 
       lsq f1 f2; 
       decvar x1 x2; 
       f1 = 10 * (x2 - x1 * x1); 
       f2 = 1 - x1; 
    run;
 

The LSQ statement results in the minimization of a function that is the sum of squares of functions that appear in the LSQ statement. The least-squares specification is preferred because it enables the procedure to exploit the structure in the problem for numerical stability and performance.

PROC NLP displays the iteration history and the solution to this least-squares problem as shown in Figure 4.1. It shows that the solution has  x_1=1 and  x_2=1. As expected in an unconstrained problem, the gradient at the solution is very close to  0.



PROC NLP: Least Squares Minimization


Levenberg-Marquardt Optimization


Scaling Update of More (1978)

Parameter Estimates 2
Functions (Observations) 2

Optimization Start
Active Constraints 0 Objective Function 0.8046925827
Max Abs Gradient Element 9.3700799757 Radius 94.336306213

Iteration   Restarts Function
Calls
Active
Constraints
  Objective
Function
Objective
Function
Change
Max Abs
Gradient
Element
Lambda Ratio
Between
Actual
and
Predicted
Change
1   0 3 0   0.44143 0.3633 7.4070 0.253 0.570
2   0 4 0   0.15159 0.2898 0.6027 0.0535 0.998
3   0 7 0   0.10794 0.0436 2.3715 0.0166 0.621
4   0 10 0   0.05200 0.0559 1.3795 0.00931 0.888
5   0 12 0   0.02748 0.0245 0.7380 0.00742 0.928
6   0 13 0   0.02257 0.00491 3.4397 0.00131 0.208
7   0 14 0   0.00300 0.0196 1.5486 0 0.867
8   0 15 0   9.8608E-32 0.00300 4.44E-16 0 1.000

Optimization Results
Iterations 8 Function Calls 16
Jacobian Calls 9 Active Constraints 0
Objective Function 9.860761E-32 Max Abs Gradient Element 4.440892E-16
Lambda 0 Actual Over Pred Change 1
Radius 0.1548641224    

ABSGCONV convergence criterion satisfied.



PROC NLP: Least Squares Minimization

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
1 x1 1.000000 4.440892E-16
2 x2 1.000000 0


Value of Objective Function = 9.860761E-32



Figure 4.1: Least-Squares Minimization

Boundary Constraints on the Decision Variables

Bounds on the decision variables can be used. Suppose, for example, that it is necessary to constrain the decision variables in the previous example to be less than 0.5. That can be done by adding a BOUNDS statement.

  
    proc nlp; 
       lsq f1 f2; 
       decvar x1 x2; 
       bounds x1-x2 <= .5; 
       f1 = 10 * (x2 - x1 * x1); 
       f2 = 1 - x1; 
    run;
 

The solution in Figure 4.2 shows that the decision variables meet the constraint bounds.

PROC NLP: Least Squares Minimization

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
Active
Bound
Constraint
1 x1 0.500000 -0.500000 Upper BC
2 x2 0.250000 0  


Value of Objective Function = 0.125



Figure 4.2: Least-Squares with Bounds Solution

Linear Constraints on the Decision Variables

More general linear equality or inequality constraints of the form

\sum_{j=1}^n a_{ij} x_j \: \{\le | = | \ge\} \: b_i  {\rm for} \; i=1, ... ,m
can be specified in a LINCON statement. For example, suppose that in addition to the bounds constraints on the decision variables it is necessary to guarantee that the sum  x_1 + x_2 is less than or equal to 0.6. That can be achieved by adding a LINCON statement:

  
    proc nlp; 
       lsq f1 f2; 
       decvar x1 x2; 
       bounds x1-x2 <= .5; 
       lincon x1 + x2 <= .6; 
       f1 = 10 * (x2 - x1 * x1); 
       f2 = 1 - x1; 
    run;
 

The output in Figure 4.3 displays the iteration history and the convergence criterion.

PROC NLP: Least Squares Minimization


Levenberg-Marquardt Optimization


Scaling Update of More (1978)

Parameter Estimates 2
Functions (Observations) 2
Lower Bounds 0
Upper Bounds 2
Linear Constraints 1

Optimization Start
Active Constraints 0 Objective Function 0.253373098
Max Abs Gradient Element 2.3979413805 Radius 24.73760934

Iteration   Restarts Function
Calls
Active
Constraints
  Objective
Function
Objective
Function
Change
Max Abs
Gradient
Element
Lambda Ratio
Between
Actual
and
Predicted
Change
1   0 2 1   0.20859 0.0448 3.8588 0 0.177
2   0 3 1   0.16658 0.0420 0.0244 0 0.998
3   0 4 1   0.16658 1.734E-6 0.000043 0 0.998
4   0 5 1   0.16658 5.42E-12 7.862E-8 0 0.998

Optimization Results
Iterations 4 Function Calls 6
Jacobian Calls 5 Active Constraints 1
Objective Function 0.1665792899 Max Abs Gradient Element 7.862265E-8
Lambda 0 Actual Over Pred Change 0.998190938
Radius 6.7030595E-6    

GCONV convergence criterion satisfied.



Figure 4.3: Least-Squares with Bounds and Linear Constraints Iteration History

Figure 4.4 shows that the solution satisfies the linear constraint. Note that the procedure displays the active constraints (the constraints that are tight) at optimality.



PROC NLP: Least Squares Minimization

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
1 x1 0.423645 -0.312000
2 x2 0.176355 -0.312000


Value of Objective Function = 0.1665792899

Linear Constraints Evaluated at Solution
1 ACT 2.7756E-17 = 0.6000 - 1.0000 * x1 - 1.0000 * x2



Figure 4.4: Least-Squares with Bounds and Linear Constraints Solution

Nonlinear Constraints on the Decision Variables

More general nonlinear equality or inequality constraints can be specified using an NLINCON statement. Consider the least-squares problem with the additional constraint

x_1^2 - 2x_2 \ge 0
This constraint is specified by a new function c1 constrained to be greater than or equal to 0 in the NLINCON statement. The function c1 is defined in the programming statements.

  
    proc nlp tech=QUANEW; 
       min f; 
       decvar x1 x2; 
       bounds x1-x2 <= .5; 
       lincon x1 + x2 <= .6; 
       nlincon c1 >= 0; 
  
       c1 = x1 * x1 - 2 * x2; 
  
       f1 = 10 * (x2 - x1 * x1); 
       f2 = 1 - x1; 
  
       f = .5 * (f1 * f1 + f2 * f2); 
    run;
 

Figure 4.5 shows the iteration history, and Figure 4.6 shows the solution to this problem.

PROC NLP: Nonlinear Minimization


Dual Quasi-Newton Optimization


Modified VMCWD Algorithm of Powell (1978, 1982)


Dual Broyden - Fletcher - Goldfarb - Shanno Update (DBFGS)


Lagrange Multiplier Update of Powell(1982)

Parameter Estimates 2
Lower Bounds 0
Upper Bounds 2
Linear Constraints 1
Nonlinear Constraints 1

Optimization Start
Objective Function 29.25 Maximum Constraint Violation 0
Maximum Gradient of the Lagran Func 76.5    

Iteration   Restarts Function
Calls
Objective
Function
Maximum
Constraint
Violation
Predicted
Function
Reduction
Step
Size
Maximum
Gradient
Element
of the
Lagrange
Function
1   0 4 2.88501 0 2.9362 1.000 20.961
2   0 5 0.91110 0 0.5601 1.000 6.777
3   0 6 0.61803 0 0.00743 1.000 1.148
4 ' 0 7 0.61090 0 0.0709 1.000 1.194
5 ' 0 8 0.54427 0 0.6015 1.000 0.988
6   0 10 0.49223 0 0.3369 0.100 0.970
7   0 12 0.45728 0 0.1848 0.114 1.332
8   0 14 0.40785 0 0.0749 0.355 2.390
9   0 15 0.36175 0 0.0556 1.000 1.128
10   0 16 0.33086 0 0.00178 1.000 0.138
11   0 17 0.33017 0 0.000290 1.000 0.0522
12   0 18 0.33004 0 0.000012 1.000 0.00221
13   0 19 0.33003 0 2.96E-8 1.000 0.00004

Optimization Results
Iterations 13 Function Calls 20
Gradient Calls 16 Active Constraints 1
Objective Function 0.3300307303 Maximum Constraint Violation 0
Maximum Projected Gradient 0.00001427 Value Lagrange Function 0.3300307155
Maximum Gradient of the Lagran Func 0.0000138538 Slope of Search Direction -2.959812E-8



Figure 4.5: Least-Squares with Bounds, Linear and Nonlinear Constraints, Iteration History

PROC NLP: Nonlinear Minimization

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
Gradient
Lagrange
Function
1 x1 0.246953 0.753017 -0.000013854
2 x2 0.030493 -3.049292 -0.000003421


Value of Objective Function = 0.3300307303


Value of Lagrange Function = 0.3300307155

Linear Constraints Evaluated at Solution
1   0.32255 = 0.6000 - 1.0000 * x1 - 1.0000 * x2

Values of Nonlinear Constraints
Constraint Value Residual Lagrange
Multiplier
 
[ 2 ] c1_G 9.699E-9 9.699E-9 1.5246 Active NLIC  



Figure 4.6: Least-Squares with Bounds, Linear and Nonlinear Constraints, Solution

Not all of the optimization methods support nonlinear constraints. In particular the Levenberg-Marquardt method, the default for LSQ, does not support nonlinear constraints. (For more information about the particular algorithms, see the section "Optimization Algorithms".) The Quasi-Newton method is the prime choice for solving nonlinear programs with nonlinear constraints. The option TECH=QUANEW in the PROC NLP statement causes the Quasi-Newton method to be used.

A Simple Maximum Likelihood Example

The following is a very simple example of a maximum likelihood estimation problem with the log likelihood function:

l(\mu,\sigma) = -\log(\sigma) -    \frac{1}2 ( \frac{x - \mu}{\sigma} ) ^2

The maximum likelihood estimates of the parameters \mu and \sigma form the solution to

\max_{\mu,\sigma\gt} \sum_i l_i(\mu,\sigma)
where
l_i(\mu,\sigma) = -\log(\sigma) -    \frac{1}2 ( \frac{x_i - \mu}{\sigma} ) ^2

In the following DATA step, values for  x are input into SAS data set X; this data set provides the values of  x_i.

  
     data x; 
       input x @@; 
     datalines; 
     1 3 4 5 7 
     ;
 

In the following statements, the DATA=X specification drives the building of the objective function. When each observation in the DATA=X data set is read, a new term l_i(\mu,\sigma) using the value of  x_i is added to the objective function LOGLIK specified in the MAX statement.

  
    proc nlp data=x vardef=n covariance=h pcov phes; 
       profile mean sigma / alpha=.5 .1 .05 .01; 
       max loglik; 
       parms mean=0, sigma=1; 
       bounds sigma > 1e-12; 
       loglik=-0.5*((x-mean)/sigma)**2-log(sigma); 
    run;
 

After a few iterations of the default Newton-Raphson optimization algorithm, PROC NLP produces the results shown in Figure 4.7.

PROC NLP: Nonlinear Maximization

Optimization Results
Parameter Estimates
N Parameter Estimate Approx
Std Err
t Value Approx
Pr > |t|
Gradient
Objective
Function
1 mean 4.000000 0.894427 4.472136 0.006566 -1.33149E-10
2 sigma 2.000000 0.632456 3.162278 0.025031 5.6064147E-9


Value of Objective Function = -5.965735903



Figure 4.7: Maximum Likelihood Estimates

In unconstrained maximization, the gradient (that is, the vector of first derivatives) at the solution must be very close to zero and the Hessian matrix at the solution (that is, the matrix of second derivatives) must have nonpositive eigenvalues. The Hessian matrix is displayed in Figure 4.8.

Hessian Matrix
  mean sigma
mean -1.250000003 1.331489E-10
sigma 1.331489E-10 -2.500000014


Determinant = 3.1250000245


Matrix has Only Negative Eigenvalues



Figure 4.8: Hessian Matrix


Under reasonable assumptions, the approximate standard errors of the estimates are the square roots of the diagonal elements of the covariance matrix of the parameter estimates, which (because of the COV=H specification) is the same as the inverse of the Hessian matrix. The covariance matrix is shown in Figure 4.9.

Covariance Matrix 2: H = (NOBS/d)
inv(G)
  mean sigma
mean 0.7999999982 4.260766E-11
sigma 4.260766E-11 0.3999999978


Factor sigm = 1


Determinant = 0.3199999975


Matrix has 2 Positive Eigenvalue(s)



Figure 4.9: Covariance Matrix


The PROFILE statement computes the values of the profile likelihood confidence limits on SIGMA and MEAN, as shown in Figure 4.10.

Wald and PL Confidence Limits
N Parameter Estimate Alpha Profile Likelihood Confidence
Limits
Wald Confidence Limits
1 mean 4.000000 0.500000 3.384431 4.615569 3.396718 4.603282
1 mean . 0.100000 2.305716 5.694284 2.528798 5.471202
1 mean . 0.050000 1.849538 6.150462 2.246955 5.753045
1 mean . 0.010000 0.670351 7.329649 1.696108 6.303892
2 sigma 2.000000 0.500000 1.638972 2.516078 1.573415 2.426585
2 sigma . 0.100000 1.283506 3.748633 0.959703 3.040297
2 sigma . 0.050000 1.195936 4.358321 0.760410 3.239590
2 sigma . 0.010000 1.052584 6.064107 0.370903 3.629097



Figure 4.10: Confidence Limits


Previous Page | Next Page | Top of Page