PROC NLP (SAS/OR Software)

General and specialized nonlinear optimization

The NLP procedure offers a set of optimization techniques for minimizing or maximizing a continuous nonlinear function f(x) of n decision variables with boundary, general linear, and nonlinear equality and inequality constraints. PROC NLP supports a number of algorithms for solving this problem that take advantage of the special structure of the objective and constraint functions.  Two algorithms are especially designed for quadratic optimization problems, and two other algorithms are provided for the efficient solution of nonlinear least-squares problems.  

PROC NLP is part of SAS/OR Software, a fully-integrated component of the SAS System.  Along with its programming statements, PROC NLP uses SAS data sets (proprietary format) for input and for output.  By taking advantage of the SAS System's Multiple Engine Architecture, PROC NLP can in effect read from and write to over fifty different database formats.  

In addition to producing output SAS data sets, PROC NLP can print text output detailing the initial decision variable values, the search for an initial feasible solution, the optimization history, and the values of decision variables, derivatives, and covariance matrices at optimality.

Input Data

• objective function and the constraints are specified using the programming statements of PROC NLP
• additional data sets can be used to generate constraints and objectives
  • DATA= data set specifies an objective function that is a combination of n other functions
  • INQUAD= data set (sparse or dense format) specifies the objective of a quadratic programming problem
  • INEST= or INVAR= data set specifies initial values for the decision variables, the values of constants that are referred to in the program statements, as well as simple boundary and general linear constraints
  • MODEL= data set specifies a model saved from a previous execution of the NLP procedure

Output Data

• OUT= output data set contains variables generated in the program statements defining the objective function (and perhaps derivatives) plus any variables used in a DATA= input data set
• OUTEST= data set contains values of decision variables, derivatives, and covariance matrices at optimality, and can be used in subsequent PROC NLP calls as an INEST= input data set
• OUTMOD= data set contains the programming statements and can be used in subsequent PROC NLP calls as a MODEL= input data set

Optimizers

The following algorithms are available via PROC NLP for use with these categories of nonlinear programs:

• Nonlinear min/maximization with linear constraints
  • a trust-region algorithm (Dennis, Gay, & Welsch, 1981, Gay, 1983, and Moré and Sorensen, 1983)
  • two different Newton-Raphson algorithms using line search or ridging
  • quasi-Newton algorithms updating either an approximation of the inverse Hessian or the Cholesky factor of an approximate Hessian
  • a double dogleg algorithm (Gay, 1983 and Dennis and Mei, 1979)
  • various conjugate gradient algorithms with the Powell and Beale automatic restart update (Powell, 1977, and Beale, 1972), Fletcher-Reeves update, Poliak-Ribiere update, or conjugant-descent update (Fletcher, 1987)
  • the Nelder-Mead simplex algorithm with a modification of Powell's COBYLA implementation (Powell, 1992)
    
    
• Nonlinear min/maximization, unconstrained or with boundary constraints
  • any of the algorithms listed above, substituting the original Nelder-Mead simplex algorithm for the COBYLA version
    
    
• Nonlinear min/maximization with nonlinear constraints
  • a quasi-Newton algorithm that is a modification of Powell's Variable Metric Constrained Watch Dog (VMCWD) algorithm (Powell, 1978, 1982)
  • the Nelder-Mead simplex algorithm with a modification of Powell's COBYLA implementation (Powell, 1992)
    
    
• Nonlinear least squares with linear constraints
  • the Levenberg-Marquardt algorithm (Moré, 1978)
  • a hybrid quasi-Newton algorithm (Fletcher & Xu, 1987, Lindstrom & Wedin, 1984, and Al-Baali & Fletcher, 1986)
    
    
• Quadratic min/maximization with linear or boundary constraints
  • solve as a linear complementarity problem (if the symmetric matrix is positive/negative semi-definite for a min/maximization and the variables are restricted to be positive)
  • use a general quadratic optimization active set algorithm (Gill, Murray, Saunders, & Wright, 1984)

Derivatives

PROC NLP may require derivatives of the objective function and the constraints.  These can be obtained

• analytically (using a special derivative compiler), the default method
• via finite difference approximations
• via user-supplied exact or approximate numerical functions

Problem Size Limitations

The size of a problem that PROC NLP can solve depends on the host platform, the available memory, and the available space for utility data sets.   PROC NLP does not place any additional limits on problem size. 

Available Platforms

The SAS System is supported on all major personal computer, workstation, and mainframe operating systems.

Need more info?

Visit SAS Institute Research & Development on the WWW or contact:

SAS Institute Inc. 
SAS Campus Drive 
Cary, NC 27513 
Phone: (919) 677-8000 ext. 6916 
Fax: (919) 677-4444
Email: saseph@unx.sas.com

References

M. Al-Baali and R. Fletcher (1985), "Variational methods for nonlinear least squares," J. Oper. Res. Soc., 36, 405-421.

E.M.L. Beale (1972), "A derivation of conjugate gradients," in F.A. Lootsma (ed.), Numerical Methods for Nonlinear Optimization, Academic Press, London.

J.E. Dennis, D.M. Gay, and R.E. Welsch (1981), "An adaptive nonlinear least-squares algorithm," ACM Trans. Math. Software, 7, 348-368.

J.E. Dennis and H.H.W. Mei (1979), "Two new unconstrained optimization algorithms which use function and gradient values," J. Optim. Theory Appl., 28, 453-482.

R. Fletcher (1987), Practical Methods of Optimization, 2nd Ed., John Wiley & Sons, Chichester.

R. Fletcher and C. Xu (1987), "Hybrid methods for nonlinear least squares," J. Numerical Analysis, 7, 371-389.

D.M. Gay (1983), "Subroutines for unconstrained minimization," AMC Trans. Math. Software, 9, 503-524.

E.P. Gill, W. Murray, M.A. Saunders, and M.H. Wright (1984), "Procedures for Optimization Problems with a Mixture of Bounds and General Linear Constraints," AMC Trans. Math. Software, 10, 282-298.

P. Lindstrom and P.A. Wedin (1984), "A new linesearch algorithm for nonlinear least-squares problems," Math. Prog., 29, 268-296.

J.J. Moré (1978), "The Levenberg-Marquardt Algorithm: Implementation and Theory," in G.A. Watson (ed.), Lecture Notes in Mathematics 630, Springer-Verlag, Berlin, 1978, 105-116.

J.J. Moré and D.C. Sorensen (1983), "Computing a Trust-Region Step," SIAM J. Sci. Stat. Comput., 4, 553-572.

J.M.D. Powell (1977), "Restart procedures for the conjugate gradient method," Math. Prog., 12, 241-254.

J.M.D. Powell (1978a), "A fast algorithm for nonlinearly constrained optimization calculations," in G.A. Watson (ed.), Lecture Notes in Mathematics 630, Springer-Verlag, Berlin, 1978, 144-175.

J.M.D. Powell (1978b), "Algorithms for nonlinear constraints that use Lagrangian functions," Math. Prog., 14, 224-248.

J.M.D. Powell (1982a), "Extensions to subroutine VF02AD," in R.F. Drenick and F. Kozin (ed.), Systems Modeling and Optimization, Lecture Notes in Control and Information Sciences 38, Springer-Verlag, Berlin, 1982, 529-538.

J.M.D. Powell (1982b), "VMCWD: A Fortran subroutine for constrained optimization," DAMTP 1982/NA4, Cambridge, England.

J.M.D. Powell (1992), "A direct search optimization method that models the objective and constraint functions by linear interpolation," DAMTP/NA5, Cambridge, England.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]