User’s Guide for SNOPT Version 7.6: Software for …

1 User s Guide for SNOPT Version : Software forLarge- scale nonlinear programming Philip E. GILL and Elizabeth WONGD epartment of MathematicsUniversity of California, San Diego, La Jolla, CA 92093-0112, USAW alter MURRAY and Michael A. SAUNDERSS ystems Optimization LaboratoryDepartment of Management Science and EngineeringStanford University, Stanford, CA 94305-4121, USAJ anuary 2017 AbstractSNOPT is a general-purpose system for constrained optimization. It minimizes alinear or nonlinear function subject to bounds on the variables and sparse linear ornonlinear constraints. It is suitable for large - scale linear and quadratic programmingand for linearly constrained optimization, as well as for general nonlinear finds solutions that arelocally optimal, and ideally any nonlinear functionsshould be smooth and users should provide gradients.

2 It is often more widely example, local optima are often global solutions, and discontinuities in the functiongradients can often be tolerated if they are not too close to an optimum. Unknowngradients are estimated by finite uses a sequential quadratic programming (SQP) algorithm. Search di-rections are obtained from QP subproblems that minimize a quadratic model of theLagrangian function subject to linearized constraints. An augmented Lagrangian meritfunction is reduced along each search direction to ensure convergence from any large problems, SNOPT is most efficient if only some of the variables enternonlinearly, or there are relatively few degrees of freedom at a solution ( , manyconstraints are active).

3 SNOPT requires relatively few evaluations of the problemfunctions. Hence it is especially effective if the objective or constraint functions (andtheir gradients) are expensive to source code is re-entrant and suitable for any machine with a Fortran may be called from a driver program in Fortran,Matlab, orC/C++with thenew interface based on the Fortran 2003 standard on Fortran-C interoperability. Af2ctranslation of SNOPT to theClanguage is still provided, although this feature will bediscontinued in the future (users should migrate to the newC/C++interface).Keywords: optimization, large - scale nonlinear programming , nonlinear constraints,SQP methods, limited-storage quasi-Newton updates, Fortran ~saunders Partially supported by Northrop Grumman Aerospace Systems, National Science Foundation grantsDMS-1318480 and DMS-1361421, and the National Institute of General Medical Sciences of the NationalInstitutes of Health [award U01GM102098].

4 The content is solely the responsibility of the authors and doesnot necessarily represent the official views of the funding Problem types .. Implementation .. TheSNOPT interfaces .. Files .. Overview of the package .. SubroutinesnInit..62. Description of the SQP Constraints and slack variables .. Major iterations .. Minor iterations .. The reduced Hessian and reduced gradient .. The merit function .. Treatment of constraint infeasibilities .. 103. Subroutines associated withsnOptA.. Getting Started .. Exploiting problem structure .. SubroutinesnOptA.. SubroutinesnJac.. Subroutineusrfun.. Exampleusrfun.. SubroutinesnMemA.

5 294. Subroutines used bysnOptB.. Identifying structure in the objective and constraints .. Problem dimensions .. SubroutinesnOptB.. User-supplied routines required bysnOptB.. Subroutinefuncon.. Subroutinefunobj.. Example .. Constant Jacobian elements .. SubroutinesnMemB.. 475. SubroutinesnOptC.. Subroutineusrfun.. 506. Subroutines used bynpOpt.. SubroutinenpOpt.. User-supplied subroutines fornpOpt.. Subroutinefunobj.. Subroutinefuncon.. Constant Jacobian elements .. 6137. Optional The SPECS file .. Multiple sets of options in the Specs file .. SPECS file checklist and defaults .. SubroutinesnSpec.

6 SubroutinessnSet,snSeti,snSetr.. SubroutinessnGet,snGetc,snGeti,snGetr.. Description of the optional parameters .. 688. The PRINT file .. The major iteration log .. The minor iteration log .. Basis factorization statistics .. Crash statistics .. EXIT conditions .. Solution output .. The SOLUTION file .. The SUMMARY file .. 1029. Basis New and Old basis files .. Punch and Insert files .. Dump and Load files .. Restarting modified problems .. 107 References110 Index1104 SNOPT User s Guide1. IntroductionSNOPTis a general-purpose system for constrained optimization. It minimizes a linearor nonlinear function subject to bounds on the variables and sparse linear or nonlinearconstraints.

7 It is suitable for large - scale linear and quadratic programming and for linearlyconstrained optimization, as well as for general nonlinear programs of the formNPminimizexf0(x)subject tol xf(x)ALx u,wherexis ann-vector of variables,landuare constant lower and upper bounds,f0(x) isa smooth scalar objective function,ALis a sparse matrix, andf(x) is a vector of smoothnonlinear constraint functions{fi(x)}. An optional parameterMaximizemay specify thatf0(x) should be maximized instead of , the first derivatives (gradients) off0(x) andfi(x) should be known and codedby the user. If only some of the gradients are known, SNOPT estimates the missing ones byfinite and lower bounds are specified for all variables and constraints. Thejth constraintmay be defined as anequalityby settinglj=uj.

8 If certain bounds are not present, theassociated elements oflorumay be set to special values that are treated as or + .Free variables and free constraints ( free rows ) have both bounds Problem typesIff0(x) is linear andf(x) is absent, NP is alinear program(LP) andSNOPT applies theprimal simplex method [2]. Sparse basis factors are maintained byLUSOL[12] as inMINOS[18].If only the objective is nonlinear , the problem islinearly constrained(LC) and tends tosolve more easily than the general case with nonlinear constraints (NC). For both nonlinearcases, SNOPT applies a sparse sequential quadratic programming (SQP) method [8], usinglimited-memory quasi-Newton approximations to the Hessian of the Lagrangian. The meritfunction for steplength control is an augmented Lagrangian, as in the dense SQP solverNPSOL[11, 14].

9 In general, SNOPT requires less matrix computation thanNPSOLand fewer evaluationsof the functions than the nonlinear algorithms inMINOS[16, 17]. It is suitable for nonlinearproblems with thousands of constraints and variables, and is most efficient if only some ofthe variables enter nonlinearly, or there are relatively few degrees of freedom at a solution( , many constraints are active). However, unlike previous versions ofSNOPT, there is nolimit on the number of degrees of ImplementationSNOPTis implemented as a library of Fortran 77 subroutines. The source code is compatiblewith all known Fortran 77, 90, and 95 compilers, and can be converted to C code by thef2ctranslator [4] included with the routines inSNOPTare intended to be re-entrant (as long as the compiler allocateslocal variables dynamically).

10 Hence they may be used in a parallel or multi-threaded envi-ronment. They may also be called TheSNOPT interfacesSNOPT contains severalinterfacesbetween the user and the underlying solver, allowingproblems to be specified in various users are encouraged to use thesnOptAinterface. This allows linear and nonlinearconstraints and variables to be entered inarbitrary order, and allows all nonlinear functionsto be defined in one user routine. It may also be used with SnadiOpt [7], which providesgradients byautomatic differentiationof the problem efficiency reasons, the solver routines require nonlinear variables and constraints tocome before linear variables and constraints, and they treat nonlinear objective functionsseparately from nonlinear (thebasicinterface) imposes these distinc-tions and was used by all versions ofSNOPT prior to Version some applications, the objective and constraint functions share data and allows the functions to becombinedin one user ,npOptis an interface that accepts problem data written in the same format asthe dense SQP codeNPSOL.