Home

User's Guide for SNOPT Version 7, A Fortran

1. subject to u w 2 vt z 4 2u 4v gt 0 3w 5z 4 with bounds w gt 0 z gt 0 lt s4 lt where s4 is treated implicitly as the 4th slack variable Similarly for the constraints we define a vector function f u v to include just the nonlinear terms In this example f u v u v and fo u v ut vt The number of nonlinear constraints the dimension of f is specified by the input parameter nnCon 2 The variables x u v are known as nonlinear Jacobian variables with dimension specified by nnJac 2 Thus the constraint functions and the linear part of the objective have the form f e ER A3y Aya co Ary 2 4 1 where g is the first nnJac variables f x is defined by subroutine funcon and y contains the remaining variables The full Jacobian is of the form je os As de Ao Aa with the Jacobian of f always appearing in the top left corner of A The sparsity pattern of f x and the constant matrices A2 A3 A4 are input column wise via the array parameters Acol indA locA Elements that are identically zero need not be included The inequalities l lt f a Agy lt uy and l2 lt Aga Ary lt ug implied by the constraint functions 4 1 are known as the nonlinear and linear constraints respectively Together these two sets of inequalities constitute the general constraints In general the vectors x and x have different dimensions but they
2. 15 16 A R Conn Constrained optimization using a nondifferentiable penalty function SIAM J Numer Anal 10 1973 pp 760 779 G B DANTZIG Linear Programming and Extensions Princeton University Press Princeton New Jersey 1963 S K ELDERSVELD Large Scale Sequential Quadratic Programming Algorithms PhD thesis Depart ment of Operations Research Stanford University Stanford CA 1991 S I FELDMAN D M Gay M W MAIMONE AND N L SCHRYER A Fortran to C converter Com puting Science Technical Report 149 AT amp T Bell Laboratories Murray Hill NJ 1990 R FLETCHER An 1 penalty method for nonlinear constraints in Numerical Optimization 1984 P T Boggs R H Byrd and R B Schnabel eds Philadelphia 1985 pp 26 40 R FOURER Solving staircase linear programs by the simplex method 1 Inversion Math Program 23 1982 pp 274 313 E M Gertz P E GILL AND J MUETHERIG User s guide for SnadiOpt A package adding automatic differentiation to Snopt Report NA 01 1 Department of Mathematics University of California San Diego 2001 P E GILL W MURRAY AND M A SAUNDERS SNOPT An SQP algorithm for large scale constrained optimization SIAM J Optim 12 2002 pp 979 1006 P E GILL W MURRAY M A SAUNDERS AND M H WRIGHT User s guide for NPSOL Version 4 0 a Fortran package for nonlinear programming Report SOL 86 2 Department of Operations Research Stanford Universi
3. SNOPT 7 User s Guide neJac is the number of nonzero elements in gCon If gCon is stored as a two dimensional array then neJac nnCon x nnJac x nnJac contains the nonlinear Jacobian variables x The array x must not be altered nState indicates the first and last calls to usrfun If nState 0 there is nothing special about the current call to usrfun If nState 1 sn0ptC is calling your subroutine for the first time Some data may need to be input or computed and saved Note that if there are nonlinear constraints the first call to funcon will occur before the first call to funobj If nState gt 2 snOptC is calling your subroutine for the last time You may wish to perform some additional computation on the final solution Note again that if there are nonlinear constraints the last call to funcon will occur before the last call to funobj In general the last call is made with nState 2 INFO where INFO indicates the status of the final solution In particular if nState 2 the current x is optimal if nState 3 the problem appears to be infeasible if nState 4 the problem appears to be unbounded and if nState 5 the iterations limit was reached In some cases the solution may be nearly optimal if nState 11 this value occurs if the linesearch procedure was unable to find an improved point If the nonlinear functions are expensive to evaluate it may be desirable to do nothing on the last call by includi
4. 0 or 2 the value of the ith constraint at x must be stored in Con i The other components of fCon are ignored gCon is an array of declared dimension 1dg k where k gt n It contains the appropriate elements of the Jacobian evaluated at x See the discussion of mode and gCon above mode may be set as in funobj 6 6 Constant Jacobian elements If all constraint gradients Jacobian elements are known i e Derivative Level 2or 3 any constant elements may be assigned to gCon one time only at the start of the optimization An element of gCon that is not subsequently assigned in funcon will retain its initial value throughout Constant elements may be loaded into gCon either before the call to npOpt or during the the first call to funcon signalled by the value nState 1 The ability to preload constants is useful when many Jacobian elements are identically zero in which case gCon may be initialized to zero and nonzero elements may be reset by funcon Note that constant nonzero elements do affect the values of the constraints Thus if gCon i 7 is set to a constant value it need not be reset in subsequent calls to funcon but the value gCon i 7 x j must nonetheless be added to fCon i It must be emphasized that if Derivative level lt 2 unassigned elements of gCon are not treated as constant they are estimated by finite differences at non trivial expense 7 Optional parameters 63 7 Optional parameters
5. On some systems the file may need to be opened before snSpec is called On exit cw lencw iw leniw rw lenrw contain the specified options INFO reports the result of the call to snSpec Here is a summary of possible values Further details are given in Section 8 6 finished successfully 101 OPTIONS file read errors while reading OPTIONS file 131 no OPTIONS file specified 132 End offile encountered while reading OPTIONS file 133 End offile encountered while looking for OPTIONS file 134 ENDRUN found before any valid OPTIONS gt 134 there were i INFO 134 errors while reading the OPTIONS file 7 Optional parameters 67 7 4 Subroutines snSet snSeti snSetr These routines specify a single option that might otherwise be defined in one line of a SPECS file subroutine snSet amp buffer iPrint iSumm Errors amp cw lencw iw leniw rw lenrw subroutine snSeti amp buffer ivalue iPrint iSumm Errors amp cw lencw iw leniw rw lenrw subroutine snSetr amp buffer rvalue iPrint iSumm Errors amp cw lencw iw leniw rw lenrw character amp buffer integer amp Errors ivalue iPrint iSumm lencw leniw lenrw iw leniw double precision amp rvalue rw lenrw character amp cw lencw 8 On entry buffer is a string to be decoded Use snSet if the string contains all relevant data For example if the value 1000 is known at compile time say call snSet Iterations 1
6. where k locA j and l locA j 1 1 Note Every element of Acol must be assigned a value in the calling program In general elements in the nonlinear part of Acol see the notes below may be any dummy value e g zero because they are initialized at the first point that is feasible with respect to the linear constraints If Derivative level 2 or 3 the nonlinear part of Acol may be used to define any constant Jacobian elements If funcon does not define all entries of gCon the missing values will be obtained from Acol 1 It is essential that locA 1 1 and locA n 1 neA 1 2 The Jacobian f x forms the top left corner of Acol and indA see Section 4 2 If a Jacobian column j 1 lt j lt nnJac contains any entries Acol k indA k associated with nonlinear constraints 1 lt indA k lt nnCon those entries must come before any entries belonging to linear constraints 36 SNOPT 7 User s Guide 3 The row indices indA k for a column may be in any order subject to Jacobian entries appearing first Subroutine funcon must define the Jacobian entries gCon in the same order except gCon does not contain elements in linear constraints 4 If your problem has no constraints or just bounds on the variables you may include a dummy free row with a single zero element by setting Acol 1 0 0 indA 1 1 locA 1 1 and locA j 2 for j 2 n 1 This row is made free by se
7. A good starting point may be required An important application is to the class of nonlinear least squares problems 4 In cases where several local optima exist specifying a small value for r may help locate an optimum near the starting point Minimize Default Maximize Feasible point The keywords Minimize and Maximize specify the required direction of optimization It applies to both linear and nonlinear terms in the objective The keyword feasible point means Ignore the objective function while finding a feasible point for the linear and nonlinear constraints It can be used to check that the nonlinear constraints are feasible without altering the call to SNOPT Minor iterations limit k Default 500 If the number of minor iterations for the optimality phase of the QP subproblem exceeds k then all nonbasic QP variables that have not yet moved are frozen at their current values and the reduced QP is solved to optimality Note that more than k minor iterations may be necessary to solve the reduced QP to optimality These extra iterations are necessary to ensure that the terminated point gives a suitable direction for the line search In the major iteration log a t at the end of a line indicates that the corresponding QP was artificially terminated using the limit k Note that Iterations limit defines an independent absolute limit on the total number of minor iterations summed over all QP subproblems Minor feasibility
8. A blank name may be used Section 3 6 is the name of a subroutine that calculates the vector of problem functions F x and optionally its Jacobian F x for a given vector x usrfun must be declared external in the routine that calls snOpta xlow n xupp n contain the lower and upper bounds J and uz on the variables zx To specify a non existent lower bound ls oo set xlow j lt infBnd where infBnd is the Infinite Bound size whose default value is 10 To specify a non existent upper bound uz 00 set xupp j gt infBnd To fix the jth variable say x 6 where 8 lt infBnd set xlow j xupp j 6 Flow nF Fupp nF contain the lower and upper bounds lp and uz on F z To specify a non existent lower bound lp oo set Flow j lt infBnd For a non existent upper bound uz 00 set Fupp j gt infBnd To make the ith constraint an equality constraint say F 8 where 8 lt infBna set Flow i Fupp i 6 3 The snOptA interface 15 xnames nxname Fnames nFname sometimes contain 8 character names for the variables and problem functions If nxname 1 or nFname 1 then names are not used The printed solution will use generic names for the columns and rows If nxname n and nFname nF the elements xnames j and Fnames should contain the 8 character names of the jth variable and ith row of F xstate n sometimes contains a set of initial states for each variable x S
9. Columns of L and rows of U are formed one at a time and the remaining rows and columns of the basis are altered appropriately At any stage if the density of the remaining matrix exceeds r the Markowitz strategy for choosing pivots is terminated The remaining matrix is factored by a dense LU procedure Raising the density tolerance towards 1 0 may give slightly sparser LU factors with a slight increase in factorization time The singularity tolerance r helps guard against ill conditioned basis matrices When the basis is refactorized the diagonal elements of U are tested as follows if U lt ra or U lt rgmax U the jth column of the basis is replaced by the corresponding slack variable This is most likely to occur after a restart or at the start of a major iteration In some cases the Jacobian matrix may converge to values that make the basis exactly singular For example a whole row of the Jacobian could be zero at an optimal solution Before exact singularity occurs the basis could become very ill conditioned and the opti mization could progress very slowly if at all Setting a larger tolerance r2 1 0e 5 say may help cause a judicious change of basis Major feasibility tolerance Er Default 1 0e 6 This specifies how accurately the nonlinear constraints should be satisfied The default value of 1 0e 6 is appropriate when the linear and nonlinear constraints contain data to about that accuracy Let rowerr b
10. DHDLOMMINE SPOR boo oa aS aw RA ee by SE Oe a A a User supplied subroutines for npOpt o a FUNG fo ek ee ee ee a Sa A A eevee kk Subroutine TUNGO o ee AA A Ok wR Goes Constant Jacobian elements o o ee eee tewma 10 12 13 20 22 25 28 31 31 31 33 34 40 41 43 43 47 47 50 50 50 7 Optional parameters Val THE SPECS Aler 222 iii se eee BR 7 2 SPECS file checklist and defaults o o Tad SUbROMtiMe BnSpec occ a ewe ee EES A Subroitines siset suSeti snSetr so cs cr Ge sead paoa dOa a 7 5 Subroutines snGet snGetc snGeti snGetr 7 6 Description of the optional parameters o oaoa aea 8 Output 8 1 The PRIND HE oga ei e AA a Ee ae 8 2 The major iteration l g ooeec mae ea a ds ee eee a SS Bo The min r eration l g 2 a Oe aa ge ads a a ee 84 Basis factorization statistics i 24 2 6440 45 2b eee eee ee ee So RA S60 EXIT COMMONS daa aaa ba ee Pa eee A ST DOMO DUDO px eos RO IAEA S S The SOLUTION Bless aa Aa RA es 2 9 The SUMMARY Dile cocos a AA A A 9 Basis Files 9 1 NEW and OLD BASIS files 5 2 44644 sagadi ddadda See ea 92 PUNCH end INSERT files ese oes Bee ew ee een aS a eae 03 DUMP and LOAD fles e se coe eaa Bae hh ee DEH oe es T 1 Introduction 3 1 Introduction SNOPT is a general purpose system for constrained optimization It minimizes a linear or nonlinear function subject to bounds on the variables
11. In particular ns will always be zero for LP problems If it appears that no improvement can be made with the current definition of B S and N a nonbasic variable is selected to be added to S and the process is repeated with the value of ng increased by one At all stages if a basic or superbasic variables encounters one of its bounds the variables is made nonbasic and the value of ns is decreased by one Associated with each of the m equality constraints Ax s b are the dual variables m Similarly each variable in x s has an associated reduced gradient dj The reduced gradients for the variables x are the quantities g A where g is the gradient of the QP objective and the reduced gradients for the slacks are the dual variables 7 The QP subproblem is optimal if d gt 0 for all nonbasic variables at their lower bounds d lt 0 for all nonbasic variables at their upper bounds and d 0 for other variables including superbasics In practice an approximate QP solution Tx 8 Tx is found by relaxing these conditions 2 4 The merit function After a QP subproblem has been solved new estimates of the SparseNP solution are com puted using a line search on the augmented Lagrangian merit function T M z 5s T fo x ri f x sn H f 2 Sy D f z sy 2 2 where D is a diagonal matrix of penalty parameters Dii gt 0 If k Sk nk denotes the current solution estimate and Tk 8 Tk denotes the Q
12. See the description of Fstate below on exit 4 For Warm starts Fstate 1 nF must be 0 1 2 or 3 probably from some previous call Fmul nF contains an estimate of A the vector of Lagrange multipliers shadow prices for ns the constraints lp lt F x lt up All nF components must be defined If nothing is known about A set Fmul i 0 0 i 1 nF need not be specified for Cold starts but should retain its value from a previous call when a Warm start is used cu lencu iu leniu ru lenru are 8 character integer and real arrays of user work space They may be used to pass data or workspace to your function routine usrfun which has the same parameters They are not touched by snOpta If the function routines don t reference these parameters you may use any arrays of the appropriate type such as cw iw rw see next paragraph Alternatively you should use the cw iw rw arrays if usrfun needs to access snOptA s workspace cw lencw iw leniw rw lenrw are 8 character integer and real arrays of workspace for snOpta lencw leniw lenrw must all be at least 500 If variable and function names are specified in xnames and Fnames then lencw must be at least 500 n nF otherwise lencw 500 is appropriate Arguments leniw and lenrw should be as large as possible because it is uncertain how much storage will be needed for the basis factorization As an estimate leniw should be about 100 m n or larger
13. and lenrw should be about 200 m n or larger Appropriate values may be obtained from a call to the routine snMemA see Sec tion 3 8 or from a preliminary run of snOptA with lencw leniw lenrw 500 If Print level is positive the required amounts of workspace are printed before snOptA terminates with INFO 82 83 or 84 The values are returned in mincw miniw and minrw On exit xstate n gives the final state of the variables The elements of xstate have the following meaning 3 The snOptA interface 17 x n xstate j State of variable j Usual value of x 0 nonbasic xlow 7 1 nonbasic xupp j 2 superbasic Between xlow j and xupp j 3 basic Between xlow j and xupp j Basic and superbasic variables may be outside their bounds by as much as the Minor feasibility tolerance Note that if scaling is specified the feasibility tolerance applies to the variables of the scaled problem In this case the variables of the original problem may be as much as 0 1 outside their bounds but this is unlikely unless the problem is very badly scaled Check the Primal infeasibility printed after the EXIT message Very occasionally some nonbasic variables may be outside their bounds by as much as the Minor feasibility tolerance and there may be some nonbasics for which x j lies strictly between its bounds If nInf gt 0 some basic and superbasic variables may be outside their bounds by an arbitrary a
14. for some k gt n If ncnln 0 gCon is not referenced In that case gCon may be dimensioned 1dg 1 with ldg 1 In general gCon need not be initialized before the call to npOpt However if Derivative level 3 any constant elements of gCon may be initialized Such elements need not be reassigned on subsequent calls to funcon see Section 6 6 6 The npOpt interface 97 cMul nctot1 is an array that need not be initialized if npOpt is called with a Cold start the default Otherwise the ordering of cMul is the same as for b1 bu and istate Fora Warm start the components of cMul corresponding to nonlinear constraints must contain a multiplier estimate The sign of each multiplier should match istate as follows If the ith nonlinear constraint is defined as inactive via the initial value istate j 0 j n nclin i then cMul j should be zero If the constraint r x gt 4 is active istate j 1 cMul j should be non negative and if r x lt u is active istate j 2 cMul j should be non positive If necessary npOpt will change cMul to match these rules Hess 1dH is an array of dimension 1dH k for some k gt n Hess need not be initialized x n if npOpt is called with a Cold Start the default and will be taken as the identity For a Warm Start Hess provides the initial approximation of the Hessian of the Lagrangian i e H i j 07L a Ox 0x where L x A fo x f x an
15. lencu leniu lenru mode nnObj nState iu leniu double precision amp fObj g0bj nn0bj ru lenru x nn0bj character amp cu lencu 8 On entry mode may be set as in funcon nnObj is the number of variables involved in fo x 0 lt nnObj lt n These must be the first nnObj variables in the problem x nn0bj contains the nonlinear objective variables x The array x must not be altered nState is used as in funcon cu lencu iu leniu ru lenru are the same as in funcon On exit mode may be set as in funcon to indicate that you are unable to evaluate fo at x If you wish to terminate the solution of the current problem set mode lt 2 fObj must contain the computed value of fo x except perhaps if mode 1 g0bj nn0bj must contain the known components of the gradient vector g x i e g0bj j contains the partial derivative Ofo Ox except perhaps if mode 0 4 8 Example Here we give the subroutines funobj and funcon for the example of Section 4 2 repeated here for convenience with generic variables zj minimize 21 z2 3 323 524 subject to r r 23 2 x T Ta 4 2x1 4x9 2 0 and 3 gt 0 4 gt 0 This problem has 4 variables 3 nonlinear objective variables 2 nonlinear Jacobian variables 2 nonlinear constraints and 1 linear constraint The objective has some linear terms that we include as an extra free row with infinite bounds The calling program must as
16. nnCon nnJac nState amp iu leniu double precision amp fCon nnCon gCon neJac ru lenru x nnJac character amp cu lencu 8 integer amp nout double precision amp x1 x2 9 x 1 x 2 nout x1 x2 if nState eq 1 then First entry if nout gt 0 write nout a This is problem Toy end if if mode eq 0 or mode eq 2 then fCon 1 xi 2 x2 2 fCon 2 x2xx 4 end if if mode ge 1 then gCon 1 2 0d 0 x1 Jacobian elements for column 1 gCon 2 2 0d 0 x2 Jacobian elements for column 2 gCon 3 4 0d 0 x2 3 end if if nState ge 2 then Last entry if nout gt 0 write nout a Finished problem Toy end if end subroutine funcon 4 The snOptB interface 47 4 9 Constant Jacobian elements If all constraint gradients Jacobian elements are known Derivative level 2 or 3 any constant elements may be given to snOptB in the array Acol if desired The Jacobian array gCon is initialized from the appropriate elements of Acol If any are constant and have the correct value funcon need not reassign them in gCon Note that constant nonzero elements do affect fCon Thus if Jij is assigned correctly in a and is constant a linear term gCon i 7 x j or gCon x j must be added to fCon i depending on whether gCon is a two or one dimensional array Remember if Derivative level lt 2 unassigned elements of gCon are not treated as const
17. nnL neJac amp x fObj g0bj fCon gCon amp nState cu lencu iu leniu ru lenru integer amp lencu leniu lenru mode nn0bj nnCon nnJac nnL neJac amp nState iu leniu double precision amp fObj fCon nmnCon g0bj nn0bj ru lenru x nnL character amp cu lencu 8 Choose ONE of the following double precision gCon nnCon nnJac double precision gCon neJac On entry mode indicates which combination of fCon gCon fObj and g0bj must be assigned during the present call of usrfun snOptC will call usrfun with mode 0 1 or 2 You may test mode to decide what to do e If mode 2 assign f0bj fCon and the known components of g0bj and gCon e If mode 1 assign the known components of g0bj and gCon f0bj and fCon are not required and are ignored e If mode 0 only f0bj and fCon need be assigned g0bj and gCon are ignored nnObj is the number of variables involved in fo x 0 lt nn0bj lt n These must be the first nnObj variables in the problem nnCon is the number of nonlinear constraints nnCon gt 0 These must be the first nnCon constraints in the problem nnJac is the number of variables involved in f x 0 lt nnJac lt n These must be the first nnJac variables in the problem nnL is max nn0bj nnJac the number of nonlinear variables These must be the first nnL variables in the problem x nnL contains the nonlinear variables x The array x must not be altered 52
18. only the elements of fCon corresponding to positive values of needc need to be set and similarly for the known components of gCon e If mode 1 the knowm components of the rows of gCon corresponding to positive values in needc must be set Other rows of gCon and the array fCon will be ignored e If mode 0 the components of Con corresponding to positive values in needc must be set Other components and the array gCon are ignored ncnln is the number of nonlinear constraints i e the dimension of fCon The actual parameter ncnln is the same Fortran variable as that input to npOpt and must not be altered by funcon n is the number of variables i e the dimension of x The actual parameter n is the same Fortran variable as that input to npOpt and must not be altered by funcon ldg is the leading dimension of the array gCon ldg gt 1 and ldg gt ncnin needc is an array of dimension at least ncnln containing the indices of the elements of fCon or gCon that must be evaluated by funcon needc can be ignored if every constraint is provided x is an array of dimension at least n containing the values of the variables x for which the constraints must be evaluated z must not be altered by funcon nState has the same meaning as for funobj 62 SNOPT 7 User s Guide On exit mode fCon is an array of dimension at least ncnln that contains the appropriate values of the nonlinear constraint functions If needc i is nonzero and mode
19. see below For each column of the Jacobian one call to usrfun is needed to estimate all missing elements in that column if any If the sparsity pattern of the Jacobian happens to be ko x sa where indicates known derivatives and indicates unknown elements snOptA will use one call to usrfun to estimate the missing element in column 2 and another call to estimate both missing elements in column 3 No calls are needed for columns 1 and 4 At times central differences are used rather than forward differences Twice as many calls to usrfun are then needed This is not under the user s control Difference interval hy Default e 2 1 5e 8 This alters the interval h that is used to estimate gradients by forward differences in the following circumstances e In the initial cheap phase of verifying the problem derivatives e For verifying the problem derivatives e For estimating missing derivatives In all cases a derivative with respect to x is estimated by perturbing that component of x to the value x hi 1 z and then evaluating fo x or f x at the perturbed point The resulting gradient estimates should be accurate to O h unless the functions are badly scaled Judicious alteration of h may sometimes lead to greater accuracy 14 SNOPT 7 User s Guide Dump file 1 Default 0 If i gt 0 the last solution obtained will be output to the file with unit number 7 in the format describe
20. 2 The upper and lower bounds on x The vectors ly and uz are input as arrays infBnd 1 0d 20 xlow 1 0 0 xlow 2 infBnd xupp 1 infBnd xupp 2 infBnd where infBnd represents infinity It must be at least as large as the Infinite Bound size default value 107 3 The upper and lower bounds on F x The vectors lp and up are also in arrays Flow 1 infBnd Flow 2 infBnd Flow 3 infBnd Fupp 1 infBnd Fupp 2 4 0 Fupp 3 5 0 Note that the objective row must have infinite bounds to make it a free row 3 The snOptA interface 11 4 A subroutine usrfun that computes F x For this example usrfun would contain the assignments F 1 x 2 The objective row F 2 x 1 2 4 0 x 2 2 F 3 x 1 2 0 xx2 x 2 2 5 As many elements of G x as possible Ideally Derivative option 1 should be spec ified and subroutine usrfun should compute all derivatives of F x Elements that are identically zero may be omitted Here usrfun could include the following additional assignments They compute all Gij row wise excluding G11 0 G 1 1 0 G 1 2 G 2 2 0 x 1 G 2 1 G 3 8 0 x 2 G 2 2 G 4 2 0 x 1 2 0 G 3 1 G 5 2 0 x 2 G 3 2 The elements of G may be stored in any order row wise column wise or more ran domly The ordering implies a list of coordinates i j in this case 1 2 2 1 2 2 8 1 3 2 This list must match the
21. 2 1 0E 00 4 4 1E 01 1 2E 01 1 0000000E 00 sm 3 O 4 6E 01 5 3 6E 01 3 4E 02 9 9959887E 01 4 9E 02 4 1 1 0E 00 6 1 7E 01 2 0E 03 9 9913996E 01 1 6 6E 02 5 1 1 0E 00 7 3 0E 03 3 0E 04 1 0000159E 00 6 6E 02 6 O 1 0E 00 8 1 5E 05 1 5E 06 1 0000000E 00 1 4E 00 6 O 1 0E 00 8 1 5E 05 1 5E 06 1 0000000E 00 1 4E 00 7 O 1 0E 00 9 2 3E 11 2 4E 12 1 0000000E 00 1 4E 00 SNOPTA EXIT 0 finished successfully SNOPTA INFO 1 optimality conditions satisfied Problem name Toy0 No of iterations T No of major iterations 7 Penalty parameter 1 393E 00 No of calls to funobj 44 Calls with modes 1 2 known g 9 Calls for forward differencing 16 Calls for central differencing 8 No of degenerate steps 0 Max x 2 1 0E 00 Max Primal infeas 0 0 0E 00 Nonlinear constraint violn 3 9E 11 Solution printed on file 9 Time for MPS input Time for solving problem Time for solution output Time for constraint functions Time for objective function Objective value 1 0000000000E 00 Linear objective 1 0000000000E 00 Nonlinear objective 0 0000000000E 00 No of calls to funcon 44 Calls with modes 1 2 known g 9 Calls for forward differencing 16 Calls for central differencing 8 Percentage 0 00 Max pi 3 1 0E 00 Max Dual infeas 2 4 8E 12 0 00 seconds 0 01 seconds 0 00 seconds 0 00 seconds 0 00 seconds 106 SNOPT 7 User s Guide 9 Basis Files For non trivial problems it is advisable to save a BASIS file at the end of a run in order
22. BASIS INSERT or LOAD file then hs and x need not be set 2 Otherwise hs 1 n and x 1 n must be defined for a Cold start If nothing special is known about the problem or if there is no wish to provide special information you may set hs j 0 x j 0 0 for all j 1 n All variables will be eligible for the initial basis Less trivially to say that the optimal value of variable 7 will probably be equal to one of its bounds set hs j 4 and x j b1 5 or hs j 5 and x j bu j as appropriate 3 For Cold starts with no basis file a CRASH procedure is used to select an initial basis The initial basis matrix will be triangular ignoring certain small entries in each column The values hs j 0 1 2 3 4 5 have the following meaning hs j State of variable 7 during CRASH 0 1 3 Eligible for the basis 3 is given preference 2 4 5 Ignored After CRASH columns for which hs j 2 are made superbasic Other entries not selected for the basis are made nonbasic at the value x j if b1 j lt x j lt 4 The snOptB interface 37 pi ns bu j or at the value b1 j or bu j closest to x j See the description of hs below on exit 4 For Warm starts all of hs 1 n m must be 0 1 2 or 3 probably from some previous call and all of x 1 n m must have values contains an estimate of A the vector of Lagrange multipliers shadow prices for the nonlinear constraints The first nnCon co
23. In the major iteration log a T at the end of a line indicates that the QP was terminated early in this way Old basis file f Default 0 If f gt 0 the starting point will be obtained from this file in the format of Section 9 1 The file will usually have been output previously as a New Basis file It will not be acceptable if the number of rows or columns in the problem has been altered Partial price i Default 10 LP or 1 NLP This parameter is recommended for large problems that have significantly more variables than constraints It reduces the work required for each pricing operation when a nonbasic variable is selected to become superbasic e When i 1 all columns of the constraint matrix A I are searched 82 SNOPT 7 User s Guide e Otherwise A and J are partitioned to give roughly equal segments A I j 1 to i If the previous pricing search was successful on Aj I the next search begins on the segments Aj 1 Ij 1 All subscripts here are modulo 7 e Ifa reduced gradient is found that is larger than some dynamic tolerance the variable with the largest such reduced gradient of appropriate sign is selected to become superbasic If nothing is found the search continues on the next segments Aj 2 Lj 2 and so on e Partial price t or t 2 or t 3 may be appropriate for time stage models having t time periods Pivot tolerance r Default 2 3 3 7e 11 During solution of QP subproble
24. SPECS file a list of run time options npSet npSeti npSetr Section 7 4 May be called to specify a single option npGet npGetc npGeti npGetr Section 7 5 May be called to obtain an option s current value funcon funobj Section 6 3 Supplied by the user and called by npOpt They define the constraint functions f x and objective function fo x npOpt Section 6 The main solver npMem In distribution file np021ib f Computes the size of the workspace arrays iw and rw required for given problem dimensions Intended for Fortran 90 drivers that reallocate workspace if necessary The user routines funcon and funobj have a fixed parameter list but may have any conve nient name They are passed to npOpt as parameters 6 2 Subroutine npOpt In the following specification of npOpt we define r x as the vector of combined constraint functions r x x A x f x and use nctotl to denote a variable that holds its dimension nctotl n nclin ncn1n Note that most machines use double precision declarations as shown but some machines use real The same applies to the user routines funcon and funobj subroutine npOpt amp n nclin ncnln 1dA ldg 1dH amp A bl bu funcon funobj amp INFO majlts iState amp fCon gCon cMul fObj g0bj Hess x amp iw leniw rw lenrw external amp funcon funobj integer amp INFO 1dA ldg 1dH leniw lenrw majlts n nclin amp ncnln iState ntnclintncnl
25. The performance of each SNOPT interface is controlled by a number of parameters or op tions Each option has a default value that should be appropriate for most problems The defaults are given in the next section For special situations it is possible to specify non standard values for some or all of the options This options may be defined in a file called a SPECS file or may be defined in the calling program using a call to one of the option setting routines snSet snSeti and snSetr see Section 7 4 At any stage of the computation the current value of an optional parameter may be examined by calling one of the routines snGet snGeti and snGetr see Section 7 5 7 1 The SPECS file The specs file contains a list of option definitions using data in the following general form Begin options Iterations limit 500 Minor feasibility tolerance 1 0e 7 Solution Yes End options We call such data a SPECS file because it specifies various options The file starts with the keyword Begin and ends with End Each line specifies a single option in free format using one or more items as follows 1 A keyword required for all options 2 A phrase one or more words that qualifies the keyword only for some options 3 A number that specifies an integer or real value only for some options Such numbers may be up to 16 contiguous characters in Fortran 77 s I F E or D formats terminated by a space The items may be entered in u
26. and sets all user options to be undefined Each SNOPT interface will later check the options and set undefined ones to default values subroutine snInit amp iPrint iSumm cw lencw iw leniw rw lenrw integer amp iPrint iSumm lencw leniw lenrw iw leniw character amp cw lencw 8 double precision amp rw lenrw On entry iPrint defines a unit number for the PRINT file Typically iPrint 9 On some systems the file may need to be opened before snInit is called If iPrint lt 0 there will be no PRINT file output iSumm defines a unit number for the SUMMARY file Typically iSumm 6 In an interactive environment this usually denotes the screen On some systems the file may need to be opened before snInit is called If iSumm lt 0 there will be no SUMMARY file output cw lencw iw leniw rw lenrw must be the same arrays that are passed to other SNOPT routines They must all have length 500 or more On exit Some elements of cw iw rw are given values to indicate that most optional parameters are undefined 6 SNOPT 7 User s Guide 2 Description of the SQP method Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the description of the subroutine and its arguments The SQP algorithm is fully described by Gill Murray and Saunders 8 2 1 Constraints and slack variables The upper and lower bounds on the m components of f
27. and sparse linear or nonlinear constraints It is suitable for large scale linear and quadratic programming and for linearly constrained optimization as well as for general nonlinear programs of the form SparseNP minimize folz x subject to L lt f x lt u A x where l and u are constant lower and upper bounds fo x is a smooth scalar objective function A is a sparse matrix and f x is a vector of smooth nonlinear constraint functions fi x An optional parameter maximize may specify that fo x should be maximized instead of minimized Ideally the first derivatives gradients of folx and f x should be known and coded by the user If only some of the gradients are known SNOPT will estimate the missing ones with finite differences Note that upper and lower bounds are specified for all variables and constraints This form allows full generality in specifying various types of constraint Special values are used to indicate absent bounds l oo or uj for appropriate j Free variables and free constraints free rows are ones that have both bounds infinite Fixed variables and equality constraints have lj uj 1 1 Problem types If fo x is linear and f x is absent SparseNP is a linear program LP and SNOPT applies the primal simplex method 2 Sparse basis factors are maintained by LUSOL 10 as in MINOS 16 If only the objective is nonlinear the problem is linearly constrained LC and ten
28. approximation to the Hessian of the Lagrangian A BFGS update is applied after each major iteration If Hessian full memory is specified the approximate Hessian is treated as a dense matrix and the BFGS updates are applied explicitly This option is most efficient when the number of nonlinear variables n is not too large say less than 75 In this case the storage requirement is fixed and one can expect 1 step Q superlinear convergence to the solution Hessian limited memory should be used on problems where n is very large In this case a limited memory procedure is used to update a diagonal Hessian approximation H a limited number of times Updates are accumulated as a list of vector pairs They are discarded at regular intervals after H has been reset to their diagonal Hessian frequency a Default 999999 If Hessian Full is selected and i BFGS updates have already been carried out the Hessian approximation is reset to the identity matrix For certain problems occasional resets may improve convergence but in general they should not be necessary 76 SNOPT 7 User s Guide Hessian Full memory and Hessian frequency 20 have a similar effect to Hessian Limited memory and Hessian updates 20 except that the latter retains the current diagonal during resets Hessian updates 1 Default 20 If Hessian Limited memory is selected and BFGS updates have already been carried out all but the diagonal elements of the accumulated
29. at points k ap for various steplengths a where f x has already been evaluated satisfactorily For any such x if you set Status 1 sn0ptA will reduce a and evaluate f again closer to xz where it is more likely to be defined If for some reason you wish to terminate the current problem set Status lt 2 contains the computed functions f x except perhaps if needf 0 contains the computed derivatives G x except perhaps if needG 0 These derivative elements must be stored in G in exactly the same positions as implied by the definitions of snOptA s arrays iGfun jGvar There is no internal check for consistency except indirectly via the Verify option so great care is essential 3 The snOptA interface 25 3 7 Example usrfun Here we give subroutine usrfun for the problem minimize 321 5 2 21 23 24 subject to z 23 r 213 424 gt La a z4 plus bounds on x This problem has 4 variables a nonlinear objective function 2 nonlinear constraints and 1 linear constraint The vector of functions is 3x1 5202 a1 z3 24 2 2 21 3 1 F x 2x3 Ars T2 xt The Jacobian of F is the matrix 3 2 11 3 4 5 2 121 23 4 2 11 3 24 1 2 2 F a 0 T3 LA 0 0 2 4 0 1 4 We can write F x f 1 Az and F x f x A G x A where 3x1 x1 3 24 0 5 0 0 PS T3 24 1 0 0 0 T j A Ho 0 0 0 2 4 x4 0 1 0 0 and G
30. form k QPk after they have already been evaluated satisfactorily at xx At any such a if you set m ode to 1 npOpt will evaluate the functions at some point closer to where they are more likely to be defined If for some reason you wish to terminate solution of the current problem set mode to a negative value other than 1 fObj must contain the computed value of fo x except perhaps if mode 1 g0bj must contain the assigned components of the gradient vector g x i e gObj j con tains the partial derivative Ofo x Ox except perhaps if mode 0 6 The npOpt interface 61 6 5 Subroutine funcon This subroutine must compute the nonlinear constraint functions f x and optionally their derivatives A dummy subroutine funcon must be provided if there are no nonlin ear constraints The ith row of the Jacobian gCon is the vector 9f 0x1 0f 0 2 Of OXn subroutine funcon amp mode ncnln n ldg amp needc x fCon gCon nState integer amp mode ncnln n ldg nState needc double precision amp x n fCon gCon ldg On entry mode is set by npOpt to request values that must be assigned during each call of funcon mode will always have the value 2 if all elements of the Jacobian are available i e if Derivative level is either 2 or 3 see Section 7 If some elements of gCon are unspecified npOpt will call funcon with mode 0 1 or 2 e If mode 2
31. integer arrays iGfun and jGvar below If Derivative option 0 is specified some or all of the gradient elements need not be assigned values in G snOptA will estimate them by finite differences 6 The pattern of nonzero elements of the Jacobian G This is a list of coordinates i j of the nonzero elements G held in two integer arrays If i iGfun k and j jGvar k then G k holds G In the example the program calling snOptA would include the following iGfun 1 1 row coordinate of G 1 1 0 jGvar 1 2 col coordinate of G 1 iGfun 2 2 row coordinate of G 2 2 0 x 1 jGvar 2 1 col coordinate of G 2 iGfun 3 2 row coordinate of G 3 8 0 x 2 jGvar 3 2 col coordinate of G 3 iGfun 4 3 row coordinate of G 4 2 0 x 1 2 0 jGvar 4 1 col coordinate of G 4 iGfun 5 3 row coordinate of G 5 2 0 x 2 jGvar 5 2 col coordinate of G 5 If Derivative option 0 is specified iGfun and jGvar may be defined automatically by calling subroutine snJac p 20 12 SNOPT 7 User s Guide 3 3 Exploiting problem structure In many cases the vector F a is a sum of linear and nonlinear functions snOptA allows these terms to be specified separately so that the linear part is defined just once by the input arguments iAfun jAvar and A Only the nonlinear part is recomputed at each zx Suppose that each component of F x is of the form F a fila Aigts j l where
32. objective Note that in this example the exit condition gives a broad definition of what happened while the informational message is more specific about the cause of the termination The number associated with the informational message is the output value of the argument INFO Note that the number e associated with the exit condition may always be recovered from INFO by stripping off the least significant decimal digit The list of possible exit conditions are O Finished successfully 10 The problem appears to be infeasible 20 The problem appears to be unbounded 30 Resource limit error 40 Terminated after numerical difficulties 50 Error in the user supplied functions 60 Undefined user supplied functions 70 User requested termination 80 Insufficient storage allocated 90 Input arguments out of range 100 Finished successfully associated with SNOPT auxiliary routines 110 Errors while processing MPS data 120 Errors while estimating Jacobian structure 130 Errors while reading OPTIONS file 140 System error The exit conditions 0 20 arise when a solution exists though it may not be optimal A BASIS file may be saved and the solution will be output to the PRINT or SOLUTION files if requested Here we describe each message and suggest possible courses of action 96 SNOPT 7 User s Guide EXIT 0 Finished successfully INFO 1 optimality conditions satisfied INFO 2 feasible point found from option Feasi
33. objective and constraints into one routine npOpt Section 6 accepts the same problem format as NPSOL It is intended for moderate sized dense problems as is NPSOL 1 4 Files Every SNOPT interface reads or creates some of the following files PRINT file Section 8 is a detailed iteration log with error messages and perhaps listings of the options and the final solution SUMMARY file Section 8 9 is a brief iteration log with error messages and the final solution status Intended for screen output in an interactive environment SPECS file Section 7 is a set of run time options input by snSpec SOLUTION file Sections 8 7 8 8 keeps a separate copy of the final solution listing BASIS files Section 9 allow restarts Unit numbers for the PRINT SUMMARY and SPECS files are defined by input parameters to snInit and snSpec 1 Introduction 5 1 5 Overview of the package SNOPT is normally accessed via a sequence of subroutine calls For example the interface snOpta is invoked by the statements call snInit iPrint iSumm call snSpec iSpecs call snoptA Start nF n where snSpec reads a file of run time options if any Also individual run time options may be hard wired by calls to snSet snSeti and snSetr 1 6 Subroutine snInit Subroutine snInit must be called before any other SNOPT routine It defines the PRINT and SUMMARY files prints a title on both files
34. option 0 Similarly Max Dual infeas indicates which variable is most likely to be at a non optimal value Broadly speaking if Max Dual infeas Max pi 1074 8 Output 97 then the objective function would probably change in the dth significant digit if optimiza tion could be continued If d seems too large consider restarting with a smaller Major optimality tolerance Finally Nonlinear constraint violn shows the maximum infeasibility for nonlin ear rows If it seems too large consider restarting with a smaller Major feasibility tolerance If the requested accuracy could not be achieved a feasible solution has been found but the requested accuracy in the dual infeasibilities could not be achieved An abnormal termination has occurred but SNOPT is within 107 of satisfying the Major optimality tolerance Check that the Major optimality tolerance is not too small EXIT 10 The problem appears to be infeasible INFO 11 infeasible linear constraints INFO 12 infeasible linear equalities INFO 13 nonlinear infeasibilities minimized INFO 14 infeasibilities minimized This exit occurs if SNOPT is unable to find a point that satisfies the constraints When the constraints are linear the output messages are based on a relatively reliable indicator of infeasibility Feasibility is measured with respect to the upper and lower bounds on the variables and slacks Among all the points satisfying the general constraints Ar
35. point 63 unable to proceed into undefined region User requested termination 71 terminated during function evaluation 74 terminated from monitor routine Insufficient storage allocated 81 work arrays must have at least 500 elements 82 not enough character storage 83 not enough integer storage 84 not enough real storage Input arguments out of range 91 invalid input argument 92 basis file dimensions do not match this problem System error 141 wrong number of basic variables 142 error in basis package mincw miniw minrw say how much character integer and real storage is needed to solve the problem If snOptA terminates because of insufficient storage INFO 82 83 or 84 these values may be used to define better values of lencw leniw or lenrw If INFO 82 the work array cw lencw is too small snOptA may be called again with lencw mincw If INFO 83 or 84 the work arrays iw leniw or rw lenrw are too small snOptA may be called again with leniw or lenrw suitably larger than miniw or minrw The bigger the better because it is not certain how much storage the basis factorization needs ns is the final number of superbasic variables nInf sInf give the number and the sum of the infeasibilities of constraints that lie outside one of their bounds by more than the Minor feasibility tolerance before the solution is unscaled If the linear constraints are infeasible x minimizes the sum of the infeasibilities of the linear constraints subj
36. s 0 there is apparently no point that satisfies the bounds on x and s Violations as small as the Minor feasibility tolerance are ignored but at least one component of x or s violates a bound by more than the tolerance When nonlinear constraints are present infeasibility is much harder to recognize cor rectly Even if a feasible solution exists the current linearization of the constraints may not contain a feasible point In an attempt to deal with this situation when solving each QP subproblem SNOPT is prepared to relax the bounds on the slacks associated with nonlinear rows If a QP subproblem proves to be infeasible or unbounded or if the Lagrange multiplier estimates for the nonlinear constraints become large SNOPT enters so called nonlinear elastic mode The subproblem includes the original QP objective and the sum of the infeasibilities suitably weighted using the Elastic weight parameter In elastic mode some of the bounds on the nonlinear rows elastic i e they are allowed to violate their specified bounds Variables subject to elastic bounds are known as elastic variables An elastic variable is free to violate one or both of its original upper or lower bounds If the original problem has a feasible solution and the elastic weight is sufficiently large a feasible point eventually will be obtained for the perturbed constraints and optimization can continue on the subproblem If the nonlinear problem has no feasible
37. solution SNOPT will tend to determine a good infeasible point if the elastic weight is sufficiently large If the elastic weight were infinite SNOPT would locally minimize the nonlinear constraint violations subject to the linear constraints and bounds Unfortunately even though SNOPT locally minimizes the nonlinear constraint violations there may still exist other regions in which the nonlinear constraints are satisfied Wherever possible nonlinear constraints should be defined in such a way that feasible points are known to exist when the constraints are linearized EXIT 20 The problem appears to be unbounded INFO 21 unbounded objective INFO 22 constraint violation limit reached For linear problems unboundedness is detected by the simplex method when a nonbasic variable can be increased or decreased by an arbitrary amount without causing a basic 98 SNOPT 7 User s Guide variable to violate a bound A message prior to the EXIT message will give the index of the nonbasic variable Consider adding an upper or lower bound to the variable Also examine the constraints that have nonzeros in the associated column to see if they have been formulated as intended Very rarely the scaling of the problem could be so poor that numerical error will give an erroneous indication of unboundedness Consider using the Scale option For nonlinear problems SNOPT monitors both the size of the current objective function and the size o
38. the state of each variable They are intended for restarting the solution of a problem at a point that was reached by an earlier run on the same problem or a related problem with the same dimensions Perhaps the Iterations limit was previously too small or some other objective row is to be used As illustrated in Figure 3 the following information is recorded in a NEW BASIS file 1 A line containing the problem name the iteration number when the file was created the status of the solution Optimal Soln Infeasible Unbounded Excess Itns Error Condn or Proceeding the number of infeasibilities and the current objective value or the sum of infeasibilities 2 A line containing the OBJECTIVE RHS RANGES and BOUNDS names M m the number of rows in the constraint matrix N n the number of columns in the constraint matrix and SB the number of superbasic variables 3 A set of n m 1 80 1 lines indicating the state of the n column variables and the m slack variables in that order One character hs j is recorded for each j 1 n m as follows written with format 80i1 9 Basis Files 107 hs j State of the jth variable 0 Nonbasic at lower bound 1 Nonbasic at upper bound 2 Superbasic 3 Basic If variable j is nonbasic it may be fixed lower bound upper bound or free infinite bounds or it may be strictly between its bounds In such cases hs j 0 Free variables will almost always be basic A set of
39. the twin effects of resetting all options to their default values and reprint ing the SNOPT banner unless iPrint 0 and iSumm 0 are set for the PRINT and SUMMARY files 50 SNOPT 7 User s Guide 5 The snOptc interface The snOptC interface is identical to snOptB except that both objective and constraint func tions are provided in a single routine usrfun instead of being computed separately in funobj and funcon This arrangement may be more convenient when the objective and constraint functions depend on common data that is difficult to share between separate routines 5 1 Subroutine sn0ptC Problem SparseNP is solved by a call to subroutine snOptC whose parameters are defined here Note that most machines use double precision declarations as shown but some machines use real The same applies to the user routines funobj and funcon subroutine sn0ptC amp Start m n neA nName amp nnCon nn0bj nnJac amp i0bj ObjAdd Prob amp usrfun amp Acol indA locA bl bu Names amp hs x pi rc amp INFO mincw miniw minrw amp nS nInf sInf Obj amp cu lencu iu leniu ru lenru amp cw lencw iw leniw rw lenrw external amp usrfun integer amp INFO i0bj lencu leniu lenru lencw leniw lenrw amp mincw miniw minrw m n neA nName nS nInf nnCon amp nn0bj nnJac indA neA hs n m locA n 1 iu leniu amp iw leniw double precision amp Obj ObjAdd sInf Acol
40. updates are discarded and the updating process starts again Broadly speaking the more updates stored the better the quality of the approximate Hessian However the more vectors stored the greater the cost of each QP iteration The default value is likely to give a robust algorithm without significant expense but faster convergence can sometimes be obtained with significantly fewer updates e g i 5 Insert file f Default 0 If f gt 0 this references a file containing basis information in the format of Section 9 2 e The file will usually have been output previously as a PUNCH file e The file will not be accessed if an OLD BASIS file is specified Infinite bound size r Default 1 0e 20 If r gt 0 r defines the infinite bound infBnd in the definition of the problem constraints Any upper bound greater than or equal to infBnd will be regarded as plus infinity and similarly for a lower bound less than or equal to infBnd If r lt 0 the default value is used Iterations limit k Default max 10000 20m This is the maximum number of minor iterations allowed i e iterations of the simplex method or the QP algorithm summed over all major iterations Linesearch tolerance t Default 0 9 This controls the accuracy with which a steplength will be located along the direction of search each iteration At the start of each line search a target directional derivative for the merit function is identified This param
41. user subroutines funobj and funcon i Meaning 72 SNOPT 7 User s Guide 3 All objective and constraint gradients are known 2 All constraint gradients are known but some or all components of the objective gra dient are unknown 1 The objective gradient is known but some or all of the constraint gradients are un known 0 Some components of the objective gradient are unknown and some of the constraint gradients are unknown The value i 3 should be used whenever possible It is the most reliable and will usually be the most efficient If i 0 or 2 SNOPT will estimate the missing components of the objective gradient using finite differences This may simplify the coding of subroutine funobj However it could increase the total run time substantially since a special call to funobj is required for each missing element and there is less assurance that an acceptable solution will be located If the nonlinear variables are not well scaled it may be necessary to specify a nonstandard Difference interval see below If i 0 or 1 SNOPT will estimate missing elements of the Jacobian For each column of the Jacobian one call to funcon is needed to estimate all missing elements in that column if any If Jacobian sparse and the sparsity pattern of the Jacobian happens to be Ox where indicates known gradients and indicates unknown elements SNOPT will use one call to funcon to estimate the missing eleme
42. 000 iPrint iSumm Errors Restriction len buffer lt 72 snSet or lt 55 snSeti and snSetr ivalue is an integer value associated with the keyword in buffer Use snSeti if it is convenient to define the value at run time For example the following allows the iterations limit to be computed itnlim 1000 if m gt 500 itnlim 8000 call snSeti Iterations itnlim iPrint iSumm Errors rvalue is a real value associated with the keyword in buffer The following illustrates how the LU stability tolerance could be defined at run time factol 100 0d 0 if illcon factol 5 0d 0 call snSetr LU factor tol factol iPrint iSumm Errors iPrint isa file number for printing each line of data along with any error messages iPrint 0 suppresses this output iSumm is a file number for printing any error messages iSumm 0 suppresses this output Errors is the cumulative number of errors so it should be 0 before the first call in a group of calls to option setting routines 68 SNOPT 7 User s Guide On exit cw lencw iw leniw rw lenrw record the specified option Errors is the number of errors encountered so far 7 Optional parameters 69 7 5 Subroutines snGet snGetc snGeti snGetr These routines obtain the current value of a single option amp amp amp amp amp amp amp integer function snGet buffer Errors cw lencw iw leniw rw len
43. 10 the same items are printed during the QP solution whenever the current B is factorized Label Description Factorize The number of factorizations since the start of the run Demand A code giving the reason for the present factorization Code Meaning O First LU factorization 1 The number of updates reached the Factorization Frequency 2 The nonzeros in the updated factors have increased significantly 7 Not enough storage to update factors 10 Row residuals too large see the description of Check Frequency 11 Ill conditioning has caused inconsistent results Itn The current minor iteration number Nonlin The number of nonlinear variables in the current basis B 8 Output 93 Linear Slacks The number of linear variables in B The number of slack variables in B B BR BS or BT factorize The type of LU factorization m n Elems Amax Density Merit lenL Cmpressns Incres Utri lenU Ltol Umax Ugrwth B Periodic factorization of the basis B BR More careful rank revealing factorization of B using threshold rook pivot ing This occurs mainly at the start if the first basis factors seem singular or ill conditioned Followed by a normal B factorize BS Bg is factorized to choose a well conditioned B from the current B S Followed by a normal B factorize BT Same as BS except the current B is tried first and accepted if it appears to be not much more ill conditioned than after the previous BS fac
44. Gvar lenG define the coordinates i j of the nonzero elements of G the lenG neG nxname ObjAdd ObjRow Prob usrfun nonlinear part of the derivatives J x G x A of the function F x f x Az The actual elements of G are assigned in the subroutine usrfun The coordinates can define the elements of G in any order However subroutine usrfun must define the actual elements of G in the exactly the same order as defined by the coordinates iGfun jGvar is the dimension of the coordinate arrays iGfun and jGvar that define the varying Jacobian elements i j Gij lenG gt 1 is the number of nonzero entries in G neG gt 0 nFname give the number of variable and constraint names provided in the character arrays xname and Fname If nxname 1 and nFname 1 no variable and constraint names are provided Generic names will be used in the printed solution Otherwise nxname and nFname must be given the values nxname n and nFname nF and all names must be provided is a constant that will be added to the objective row F Objrow for printing pur poses Typically ObjAdd 0 0d 0 says which row of F is to act as the objective function If there is no such vector ObjRow 0 and snOptA will attempt to find a point such that lp lt F x lt up and ly lt lt Uz 0 lt ObjRow lt nF is an 8 character name for the problem Prob is used in the printed solution and in some routines that output BASIS files
45. O 51 incorrect objective derivatives INFO 52 incorrect constraint derivatives This exit implies that there may be errors in the subroutines that define the problem ob jective and constraints If the objective derivatives appear to incorrect a check has been made on some individual elements of the objective gradient array at the first point that satisfies the linear constraints At least one component G k or g0bj j is being set to a value that disagrees markedly with its associated forward difference estimate 0fo Ox The relative difference between the computed and estimated values is 1 0 or more This exit is a safeguard since SNOPT will usually fail to make progress when the computed gradients are seriously inaccurate In the process it may expend considerable effort before terminating with INFO 41 above Check the function and gradient computation very carefully in usrfun or funobj A simple omission such as forgetting to divide fo by 2 could explain everything If fo or a component Ofo Ox is very large then give serious thought to scaling the function or the nonlinear variables If you feel certain that the computed g0bj j is correct and that the forward difference estimate is therefore wrong you can specify Verify level 0 to prevent individual elements from being checked However the optimization procedure may have difficulty If some constraint derivatives appear to be incorrect then at least one of the com puted con
46. OLD BASIS file could not be loaded properly In this situation New BASIS files cannot be saved and there is no solution to print On the first line of the OLD BASIS file the dimensions labeled m and n are different from those associated with the 8 Output 101 problem that has just been defined You have probably loaded a file that belongs to another problem Remember if you are using snOptA and you have added elements to A iAfun and jAvar or iGfun and jGvar you will have to alter m and n and the map beginning on the third line a hazardous operation It may be easier to restart with a PUNCH or DUMP file from an earlier version of the problem The basis file state vector will not match the current problem if for some reason the OLD BASIS file is incompatible with the present problem or is not consistent within itself The number of basic entries in the state vector i e the number of 3 s in the map is not the same as m on the first line or some of the 2 s in the map did not have a corresponding j xj entry following the map EXIT 140 System error INFO 141 wrong number of basic variables INFO 142 error in basis package These messages arise if either an OLD BASIS file could not be loaded properly or some fatal system error has occurred New BASIS files cannot be saved and there is no solution to print The problem is abandoned An inconsistency in the number of basic variables should nev
47. P solution the line search determines a step ax 0 lt ag lt 1 such that the new point Heat Tk Tk Tk Sk 1 Sk TOR Sk Sk 2 3 Tk 1 Tk Tk Tk gives a sufficient decrease in the merit function 2 2 When necessary the penalties in D are increased by the minimum norm perturbation that ensures descent for M 12 As in NPSOL sy is adjusted to minimize the merit function as a function of s prior to the solution of the QP subproblem For more details see 9 3 8 SNOPT 7 User s Guide 2 5 Treatment of constraint infeasibilities SNOPT makes explicit allowance for infeasible constraints First infeasible linear constraints are detected by solving the linear program FLP minimize e7 v w T v w subject to 1 7 E v gt 0 w20 rt v w where e is a vector of ones and the nonlinear constraint bounds are temporarily excluded from l and u This is equivalent to minimizing the sum of the general linear constraint violations subject to the bounds on xz The sum is the f norm of the linear constraint violations In the linear programming literature the approach is called elastic programming The linear constraints are infeasible if the optimal solution of FLP has v 0 or w 0 SNOPT then terminates without computing the nonlinear functions Otherwise all subsequent iterates satisfy the linear constraints Such a strategy allows linear constraints to be used to define a region in which the fun
48. SNOPT is most efficient if only some of the variables enter non linearly or if many constraints including simple bounds are active SNOPT requires relatively few evaluations of the problem functions Hence it is especially effective if the objective or constraint functions and their gradients are expensive to evaluate The source code for SNOPT is suitable for any machine with a Fortran compiler or the 2c translator SNOPT may be called from a driver program typically in Fortran C or MATLAB It can also be used as a stand alone package reading data in the MPS format used by commercial mathematical programming systems Keywords Nonlinear programming constrained optimization nonlinear constraints SQP methods limited storage quasi Newton updates Fortran software pgill ucsd edu http www cam ucsd edu peg walter stanford edu http www stanford edu walter saunders stanford edu http www stanford edu saunders Partially supported by National Science Foundation grants DMI 9204208 DMI 9500668 and CCR 9988205 and Office of Naval Research grants NO0014 96 1 0274 and N00014 02 1 0076 Contents Y Introduction LA Problem types ieee ps De eS OAR A AA AA 12 Implementado sso oraaa deh DEED eae eee E A L3 The SNORT imors o eop aaa a Be we ee REE A eS we ee IA Ba AA A we a Se ek Be aes 1 5 Overview of the package 2 ee ee LO ubromtme Srila o cs Ge ac ak ar ata kde aan wo af ae a a eh ee Description of the
49. SPECS file Basis file isthe same as start Cold but is more meaningful when a basis file is given Warm means that a basis is already defined in hs probably from an earlier call m is m the number of general constraints This is the number of rows in the full constraint matrix A in 4 2 m gt 0 Note that A must have at least one row If your problem has no constraints or only upper and lower bounds on the variables then you must include a dummy row with sufficiently wide upper and lower bounds See the discussion of the parameters Acol indA locA below 4 The snOptB interface 35 neA nName nnCon nn0bj nnJac i0bj Obj Add Prob funcon funobj is n the number of variables excluding slacks This is the number of columns in A n gt 0 is the number of nonzero entries in A including the Jacobian for any nonlinear constraints neA gt 0 is the number of column and row names provided in the character array Names If nName 1 there are no names Generic names will be used in the printed solution Otherwise nName n m and all names must be provided is m1 the number of nonlinear constraints nnCon gt 0 is n the number of nonlinear objective variables nnObj gt 0 is n the number of nonlinear Jacobian variables If nnCon 0 nnJac 0 If nnCon gt 0 nnJac gt 0 says which row of A is a free row containing a linear objective vector c If there is no such
50. SQP method 2 1 2 2 2 3 2 4 2 5 The 3 1 3 2 3 3 3 4 35 3 6 ds 3 8 The 4 1 4 2 4 3 4 4 A5 4 6 47 4 8 4 9 4 10 The 5 1 5 2 The 6 1 6 2 6 3 6 4 6 5 6 6 Constraints and slack variables 4 44045 gi taparar e eee eee ns Majat Keraton cad eae ee ee a ae eee Ee eR Re Po Minor aberations s sossar eda kee eee eA EERE RE EE ERE ES The merit TADEO s a a a aiae a a ee ee he eee Treatment of constraint infeasibilities 208 snOptA interface Subroutines associated with snOptA o o Getting Started lt e eas dotia ae da A e eS Exploiting problem structure o o e e eera eua Subrotimie SRODER cio o a a A cubre Sales cocos eee ra DuUbrOUtMe ESTU ec ar a A ee Example verte e a a IA A ESS Subroutine snMemA ociosas add a aa d snOptB interface Subroutines used by snOptB o o ee Identifying structure in the objective and constraints Problem dimensions usos a AAA AR ee Subroutine sn0ptB ici ee ee ey ee a EG User supplied routines required by snOptB DULPOUtIMG Euler a A DUDESUTME TUNED gt con hohe da Example 22 4 2 2 eee bs CRE ERE E e we a a EGE Goes a Constant Jacobian elements o o eee ee pubraiime saab o ose es ea a a ee a snOptC interface Subroutine CHOptG cca a a a AA PUDONG METER da As A npOpt interface Subroutines used by mpOpt s s o 6 0 6 5 ceo s m
51. User s Guide for SNOPT Version 7 A Fortran Package for Large Scale Nonlinear Programming Philip E GILL Department of Mathematics University of California San Diego La Jolla CA 92093 0112 Walter MURRAY and Michael A SAUNDERS Systems Optimization Laboratory Department of Management Science and Engineering Stanford University Stanford CA 94305 4026 August 28 2005 Abstract SNOPT is a general purpose system for constrained optimization It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints It is suitable for large scale linear and quadratic programming and for linearly constrained optimization as well as for general nonlinear programs SNOPT finds solutions that are locally optimal and ideally any nonlinear functions should be smooth and users should provide gradients It is often more widely useful For example local optima are often global solutions and discontinuities in the function gradients can often be tolerated if they are not too close to an optimum Unknown gradients are estimated by finite differences SNOPT uses a sequential quadratic programming SQP algorithm Search di rections are obtained from QP subproblems that minimize a quadratic model of the Lagrangian function subject to linearized constraints An augmented Lagrangian merit function is reduced along each search direction to ensure convergence from any starting point On large problems
52. a and A are said to define the general constraints of the problem SNOPT converts the general constraints to equalities by introducing a set of slack variables s 51 59 Sm For example the linear constraint 5 lt 211 3x2 lt 00 is replaced by 211 3x2 s 0 together with the bounded slack 5 lt s lt 00 SparseNP can therefore be written in the equivalent form minimize fo s 8 subject to 2 o l lt z lt u A s The general constraints become the equalities f x sy 0 and A s 0 where s and sy are known as the linear and nonlinear slacks 2 2 Major iterations The basic structure of the SQP algorithm involves major and minor iterations The major iterations generate a sequence of iterates xx that satisfy the linear constraints and converge to a point that satisfies the first order conditions for optimality At each iterate a QP subproblem is used to generate a search direction towards the next iterate k 4 1 The constraints of the subproblem are formed from the linear constraints A s 0 and the nonlinear constraint linearization Flor f ee a k sw 0 where f x denotes the Jacobian matrix whose elements are the first derivatives of f x evaluated at k The QP constraints therefore comprise the m linear constraints f x 2 8y f k f re xe ALT s 0 where x and s are bounded above and below by u and l as before If the m x n ma
53. al derivatives need to be estimated However this reduces the reliability of the optimization algorithms and it can be very expensive if there are many such variables x As a compromise snOptB allows you to code as many gradients as you like This option is implemented as follows Just before a function routine is called each element of the gradient array is initialized to a specific value On exit any element retaining that value must be estimated by finite differences Some rules of thumb follow 1 For maximum reliability compute all function and gradient values 2 If the gradients are expensive to compute specify Nonderivative linesearch and use the input parameter mode to avoid computing them on certain entries Don t compute gradients if mode 0 3 If not all gradients are known you must specify Derivative level lt 3 You should still compute as many gradients as you can It often happens that some of them are constant or even zero 4 Again if the known gradients are expensive don t compute them if mode 0 5 Use the input parameter nState to test for special actions on the first or last entries 6 While the function routines are being developed use the Verify option to check the computation of gradient elements that are supposedly known The Start and Stop options may also be helpful 7 The function routines are not called until the linear constraints and bounds on g are satisfied This helps confine x to
54. always overlap in the sense that the shorter vector is always the beginning of the other In the example the nonlinear Jacobian variables u v are an ordered subset of the nonlinear objective variables u v w In other cases it could be the other way round whichever is the most convenient but the first way keeps J 2 smaller Together the nonlinear objective and nonlinear Jacobian variables comprise the nonlinear variables The number of nonlinear variables is therefore the larger of the dimensions of x and z 4 The snOptB interface 33 4 3 Problem dimensions The following picture illustrates the problem structure just described nnJac W gt nnCon The dimensions are all input parameters to subroutine snOptB see the next section For linear programs nnCon nnJac and nn0bj are all zero If a linear objective term exists i0bj points to one of the bottom rows nnCon lt i0bj lt m The dashed boxes indicate that a nonlinear objective function fo x may involve either a subset or a superset of the variables in the nonlinear constraint functions f x counting from the left Thus nnObj lt nnJac or vice versa Sometimes the objective and constraints really involve disjoint sets of nonlinear variables We then recommend ordering the variables so that nn0bj gt nnJac and 2 x x where the objective is nonlinear in just the last vector x Subroutine funobj sho
55. am at compile time It is available for users wishing to allocate storage dynamically in f90 or C The actual storage required also depends on the values of the following options Hessian full or Hessian limited memory and Hessian updates Reduced Hessian dimension Superbasics limit If these options have not been set default values are assumed Ideally the correct values should be set before the call to snMemA subroutine snMemA amp INFO nF n nxname nFname neA neG amp mincw miniw minrw amp cw lencw iw leniw rw lenrw integer amp INFO lencw leniw lenrw mincw miniw minrw n neA neG amp nF nFname nxname iw leniw double precision amp rw lenrw character amp cw lencw 8 The arguments nF n nxname nFname neA neG define the problem being solved and are identical to the arguments used in the call to snOptA see Section 3 4 For a sequence of problems snMemA may be called once with overestimates of these quantities On entry lencw leniw lenrw must be of length at least 500 cw lencw iw leniw rw lenrw are 8 character integer and real arrays of workspace for snMemA On exit INFO reports the result of the call to snMemA Here is a summary of possible values Further details are in Section 8 6 Insufficient storage allocated 81 work arrays must have at least 500 elements Finished successfully 104 memory requirements estimated mincw miniw minrw estimate how much characte
56. ant they are estimated by finite differences at significant expense 4 10 Subroutine snMemB This routine estimates the size of the workspace arrays cw iw rw required to solve an optimization problem of given dimensions snMemB is not strictly needed in f77 because all workspace must be defined explicitly in the driver program at compile time It is available for users wishing to allocate storage dynamically in f90 or C The actual storage required also depends on the values of the following options Hessian full or Hessian limited memory and Hessian updates Reduced Hessian dimension Superbasics limit If these options have not been set default values are assumed Ideally the correct values should be set before the call to snMemB subroutine snMemB amp INFO m n neA negCon amp nnCon nnJac nnObj amp mincw miniw minrw amp cw lencw iw leniw rw lenrw integer amp INFO lencw leniw lenrw m mincw miniw minrw n neA amp negCon nnCon nnJac nn0bj iw leniw double precision amp rw lenrw character amp cw lencw 8 The arguments m n neA nnCon nnJac nn0bj define the problem being solved and are identical to the arguments used in the call to snOptB see Section 4 4 For a sequence of problems snMemB may be called once with overestimates of these quantities On entry negCon is the number of nonzeros in the Jacobian gCon negCon lt nnCon nnJac lencw leniw lenrw must be of len
57. arse form The value of L will steadily increase whereas the value of U may fluctuate up or down Thus in general the value of L U may fluctuate up or down in general it will tend to increase ncp The number of compressions required to recover storage in the data structure for U This includes the number of compressions needed during the previous basis factorization Normally ncp should increase very slowly If not the amount of integer and real workspace available to SNOPT should be increased by a significant amount As a suggestion the work arrays iw and rw should be extended by L U elements ns The current number of superbasic variables The heading is not printed if the problem is linear cond Hz See the major iteration log The heading is not printed if the problem is linear 8 4 Basis factorization statistics If Major print level gt 10 the following items are output to the PRINT file whenever the basis B or the rectangular matrix Bs B S is factorized before solution of the next QP subproblem Note that Bs may be factorized at the start of just some of the major iterations It is immediately followed by a factorization of B itself Gaussian elimination is used to compute a sparse LU factorization of B or Bs where PLP and PUQ are lower and upper triangular matrices for some permutation matrices P and Q Stability is ensured as described under LU factor tolerance in Section 7 6 IfMinor print level gt
58. atives of the function f x lenG is the length of the coordinate arrays iGvar and jGfun in the call to snOpta needG indicates if G must be assigned during this call of usrfun e If needG 0 G is not required and is ignored e If needG gt 0 the partial derivatives of f x must be calculated and assigned to G For each k 1 1enG the value of G k should be 0f x 0x where i iGfun k j jGvar k cu lencu iu leniu ru lenru are the character integer and real arrays of user work space provided to snOptA They may be used to pass information into the function routines and to preserve data between calls In special applications the functions may depend on some of the internal variables stored in snOptA s workspace arrays cw iw rw For example the 8 character prob lem name Prob is stored in cw 51 and the dual variables are stored in rw 1FMul onward where 1FMul iw 329 These will be accessible to usrfun if snOptA is called with parameters cu iu ru the same as cw iw rw If you still require workspace elements rw 501 maxru and rw maxrw 1 lenru are set aside for this purpose where maxru iw 2 Similarly for workspace in cw and rw See the Total and User workspace options On exit Status may be used to indicate that you are unable to evaluate f or its gradients at the f nF G neG current x For example the problem functions may not be defined there During the line search f x is evaluated
59. ay be read using format i8 2x 2a4 1x al 1x a3 5e16 6 i7 adapted to suit the occasion The end of the ROWS section is marked by a record that starts with a 1 and is otherwise blank If this and the next 4 records are skipped the COLUMNS section can then be read under the same format There should be no need for backspace statements 8 9 The SUMMARY file If Summary file gt 0 the following information is output to the SUMMARY file It is a brief form of the PRINT file All output lines are less than 72 characters e The Begin line from the SPECS file if any e The basis file loaded if any A brief Major iteration log A brief Minor iteration log The EXIT condition and a summary of the final solution The following SUMMARY file is from the example of Section 3 2 using Major print level 1 and Minor print level 0 amp Output 105 SNOPT 7 2 1 Jul 2 005 Nonzero derivs Jij 5 Non constant Jij s 4 Constant Jij s 1 SNJAC EXIT 100 finished successfully SNJAC INFO 102 Jacobian structure estimated Nonlinear constraints Nonlinear variables Jacobian variables Total constraints WNNN The user has defined o out of Linear constraints Linear variables Objective variables Total variables NOOR 4 first derivatives Major Minors Step nCon Feasible Optimal MeritFunction nS Penalty 0 2 1 4 1E 01 5 0E 01 1 0000000E 00 2 r 1 1 1 0E 00 2 0 0E 00 5 0E 01 0 0000000E 00 2 nr 2
60. ble point only INFO 3 requested accuracy could not be achieved This message should be the cause of guarded optimism It is certainly preferable to every other message and we naturally want to believe what it says In all cases a distinct level of caution is in order For example if the objective value is much better than expected we may have obtained an optimal solution to the wrong problem Almost any item of data could have that effect if it has the wrong value Verifying that the problem has been defined correctly is one of the more difficult tasks for a model builder It is good practice in the function subroutines to print any data that is input during the first entry If nonlinearities exist one must always ask the question could there be more than one local optimum When the constraints are linear and the objective is known to be convex e g a sum of squares then all will be well if we are minimizing the objective a local minimum is a global minimum in the sense that no other point has a lower function value However many points could have the same objective value particularly if the objective is largely linear Conversely if we are maximizing a convex function a local maximum cannot be expected to be global unless there are sufficient constraints to confine the feasible region Similar statements could be made about nonlinear constraints defining convex or concave regions However the functions of a problem are more likely
61. contains a set of initial values for the problem functions F See the following discussion of Fstate Fstate nF sometimes contains a set of initial states for the problem functions F 1 If Start 0 cold start or Start 1 basis file and a BASIS file of some sort is to be input an OLD BASIS file INSERT file or LOAD file then Fstate and F need not be set 2 Otherwise Fstate and F must be defined for a Cold start If nothing special is known about the problem or if there is no wish to provide special information you may set Fstate i 0 F i 0 0 for all i 1 nF All rows will be eligible for the initial basis Less trivially to say that the optimal value of row i will probably be equal to one of its bounds set Fstate i 4 and F i Flow i or Fstate i 5 and F i Fupp i as appropriate 16 SNOPT 7 User s Guide 3 For Cold starts with no basis file a CRASH procedure is used to select an initial basis The initial basis matrix will be triangular ignoring certain small entries in each column The values xstate 0 1 2 3 4 5 have the following meaning Fstate 1 State of row during CRASH 0 1 3 Eligible for the basis 3 is given preference 2 4 5 Ignored After CRASH rows for which Fstate i 2 are made superbasic Other en tries not selected for the basis are made nonbasic at the value F i if Flow i lt F i lt Fupp i or at the value Flow i or Fupp i closest to F i
62. ctions can be safely evalu ated SNOPT proceeds to solve SparseNP as given using search directions obtained from the sequence of QP subproblems 2 1 If a QP subproblem proves to be infeasible or unbounded or if the dual variables m for the nonlinear constraints become large SNOPT enters elastic mode and thereafter solves the problem NP y minimize fo x yeT v w x subject to L lt f z v w lt u v gt 0 w gt 0 ArT where y is a nonnegative parameter the elastic weight and fo x ye v w is called a composite objective the 4 penalty function for the nonlinear constraints The value of y may increase automatically by multiples of 10 if the optimal v and w continue to be nonzero If y is sufficiently large this is equivalent to minimizing the sum of the nonlinear constraint violations subject to the linear constraints and bounds A similar l formulation of SparseNP is fundamental to the S QP algorithm of Fletcher 5 See also Conn 1 The initial value of y is controlled by the optional parameters Elastic mode and Elastic weight p 74 3 The snOptA interface 9 3 The snOptA interface The snOpta interface accepts a format that allows the constraints and variables to be defined in any order The optimization problem is assumed to be in the form NPA minimize Fop z subject to ly lt lt us lp lt F x lt Up where the upper and lower bounds are consta
63. ctors L and U on completion of the QP subproblem If nonlinear constraints are present the basis factorization B LU is computed at the start of the first minor iteration At this stage LU lenL lenU where lenL the number of subdiagonal elements in the columns of a lower triangular matrix and lenU is the number of diagonal and superdiagonal elements in the rows of an upper triangular matrix As columns of B are replaced during the minor iterations LU may fluctuate up or down but in general will tend to increase As the solution is approached and the minor iterations decrease towards zero LU will reflect the number of nonzeros in the LU factors at the start of the QP subproblem If the constraints are linear refactorization is subject only to the Factorize frequency and LU will tend to increase between factorizations The number of columns of the basis matrix B that were swapped with columns of S to improve the condition of B The swaps are determined by an LU fac torization of the rectangular matrix Bg B S with stability being favored more than sparsity The current number of superbasic variables An estimate of the condition number of RTR an estimate of ZTH Z the reduced Hessian of the Lagrangian It is the square of the ratio of the largest and small est diagonals of the upper triangular matrix R which is a lower bound on the condition number of RT R Cond Hz gives a rough indication of whether or not the optimizatio
64. d for variables j in the superbasic set During Phase 2 this norm will be approximately zero after a unit step The heading is not printed if the problem is linear LPobjective QPobjective Elastic QPobj The QP objective function after the present iteration In elastic mode the heading is changed to Elastic QPobj In either case the value printed decreases monotonically SBS The variable jq selected by PRICE to be added to the superbasic set SBS The superbasic variable chosen to become nonbasic BS The variable removed from the basis if any to become nonbasic Pivot If column a replaces the rth column of the basis B Pivot is the rth element of a vector y satisfying By ag Wherever possible Step is chosen to avoid extremely small values of Pivot since they cause the basis to be nearly singular In rare 92 SNOPT 7 User s Guide cases it may be necessary to increase the Pivot tolerance to exclude very small elements of y from consideration during the computation of Step L U The number of nonzeros representing the basis factors L and U Immediately after a basis factorization B LU this is lenL lenU the number of subdiagonal elements in the columns of a lower triangular matrix and the number of diagonal and superdiagonal elements in the rows of an upper triangular matrix Further nonzeros are added to L when various columns of B are later replaced As columns of B are replaced the matrix U is maintained explicitly in sp
65. d A is an estimate of the optimal Lagrange multipliers Hess must be a positive definite matrix is an initial estimate of the solution iw leniw rw lenrw are integer and real arrays of workspace for npOpt Both leniw and lenrw must be at least 500 In general leniw and lenrw should be as large as possible because it is uncertain how much storage will be needed for the basis factors As an estimate leniw should be about 100 m n or larger and lenrw should be about 200 m n or larger Appropriate values may be obtained from a preliminary run with leniw lenrw 500 If Print level is positive the required amounts of workspace are printed before npOpt terminates with INFO 43 or 44 On exit INFO reports the result of the call to npOpt Here is a summary of possible values for a detailed description see Section 8 6 Finished successfully 1 optimality conditions satisfied 2 feasible point found 3 requested accuracy could not be achieved The problem appears to be infeasible 11 infeasible linear constraints 12 infeasible linear equalities 13 nonlinear infeasibilities minimized 14 infeasibilities minimized The problem appears to be unbounded 21 unbounded objective 22 constraint violation limit reached Resource limit error 58 SNOPT 7 User s Guide iter istate 31 iteration limit reached 32 major iteration limit reached 33 the superbasics limit is too small Terminated after numerical di
66. d in Section 9 3 Elastic mode No Default Elastic mode Yes Normally SNOPT initiates elastic mode only when it seems necessary Option Yes causes elastic mode to be entered from the beginning Elastic weight w Default 10 This keyword determines the initial weight y associated with problem NP y on p 8 At major iteration k if elastic mode has not yet started a scale factor op 1 g9 2x loo is defined from the current objective gradient Elastic mode is then started if the QP subproblem is infeasible or the QP dual variables are larger in magnitude than o w The QP is re solved in elastic mode with y opw Thereafter major iterations continue in elastic mode until they converge to a point that is optimal for problem NP y If the point is feasible for SparseNP v w 0 it is declared locally optimal Otherwise y is increased by a factor of 10 and major iterations continue If y has already reached a maximum allowable value SparseNP is declared locally infeasible Expand frequency 1 Default 10000 This option is part of the EXPAND anti cycling procedure 11 designed to make progress even on highly degenerate problems For linear models the strategy is to force a positive step at every iteration at the expense of violating the bounds on the variables by a small amount Suppose that the Minor feasibility tolerance is 9 Over a period of i iterations the tolerance actually used by SNOPT increases from 0 50 to 6 in steps
67. ds to solve more easily than the general case with nonlinear constraints NC For both cases SNOPT applies a sparse sequential quadratic programming SQP method 8 using limited memory quasi Newton approximations to the Hessian of the Lagrangian The merit function for steplength control is an augmented Lagrangian as in the dense SQP solver NPSOL 9 12 In general SNOPT requires less matrix computation than NPSOL and fewer evaluations of the functions than the nonlinear algorithms in MINOS 14 15 Tt is suitable for nonlinear problems with thousands of constraints and variables and is efficient if many constraints and bounds are active at a solution Thus ideally there should not be thousands of degrees of freedom 1 2 Implementation SNOPT is implemented as a set of callable Fortran subroutines The source code is com patible with all known Fortran 77 90 and 95 compilers and can be converted to C code by the 2c translator 4 All routines in SNOPT are intended to be re entrant as long as the compiler allocates local variables dynamically Hence they may be used in a parallel or multi threaded envi ronment They may also be called recursively 4 SNOPT 7 User s Guide 1 3 The SNOPT interfaces SNOPT contains several interfaces between the user and the underlying solver allowing problems to be specified in various formats New users are encouraged to use the snOptA interface This allows linear and nonlinear const
68. e Function precision ER Default e 3 7e 11 The relative function precision er is intended to be a measure of the relative accuracy with which the nonlinear functions can be computed For example if f x is computed as 1000 56789 for some relevant x and if the first 6 significant digits are known to be correct the appropriate value for eg would be 1 0e 6 Ideally the functions f x or F x should have magnitude of order 1 If all functions are substantially less than 1 in magnitude er should be the absolute precision For example if f x 1 23456789e 4 at some point and if the first 6 significant digits are known to be correct the appropriate value for eg would be 1 0e 10 e The default value of e is appropriate for simple analytic functions e In some cases the function values will be the result of extensive computation possibly involving an iterative procedure that can provide rather few digits of precision at rea sonable cost Specifying an appropriate Function precision may lead to savings by allowing the line search procedure to terminate when the difference between function values along the search direction becomes as small as the absolute error in the values Hessian dimension i Default min 1000 n 1 see Reduced Hessian dimension Hessian full memory Default Full if n lt 75 Hessian limited memory These options select the method for storing and updating the approximate Hessian SNOPT uses a quasi Newton
69. e coded so that the derivatives are not computed when needG 0 The selection of Nonderivative linesearch for snOptB means that funobj and funcon are called with mode 0 in the line search Once the linesearch is completed the problem 7 Optional parameters 73 functions are called again with mode 2 If the potential savings provided by a nonderivative linesearch are to be realized it is essential that funobj and funcon be coded so that the derivatives are not computed when mode 0 Derivative option 1 Default 1 This option is intended for sn0ptA only and should not be used with any other interface The Derivative option specifies which nonlinear function gradients are known analytically and will be supplied to snOptA by the user subroutine usrfun a Meaning O Some problem derivatives are unknown 1 All problem derivatives are known The value 1 should be used whenever possible It is the most reliable and will usually be the most efficient If i 0 snOptA will estimate the missing components of G x using finite differences This may simplify the coding of subroutine usrfun However it could increase the total run time substantially since a special call to usrfun is required for each column of the Jacobian that has a missing element and there is less assurance that an acceptable solution will be located If the nonlinear variables are not well scaled it may be necessary to specify a nonstandard Difference interval
70. e function calculation Termination because of a singular basis is highly unlikely to occur The first factorization attempt will have found the basis to be structurally or numerically singular Some diagonals of the triangular matrix U were respectively zero or smaller than a certain tolerance The associated variables are replaced by slacks and the modified basis is refactorized but singularity persists This must mean that the problem is badly scaled or the LU factor tolerance is too much larger than 1 0 If the general constraints cannot be satisfied an LU factorization of the basis has just been obtained and used to recompute the basic variables xs given the present values of the superbasic and nonbasic variables A step of iterative refinement has also been applied to increase the accuracy of xg However a row check has revealed that the resulting solution does not satisfy the current constraints Ax s 0 sufficiently well This probably means that the current basis is very ill conditioned If there are some linear constraints and variables try Scale option 1 if scaling has not yet been used For certain highly structured basis matrices notably those with band structure a sys tematic growth may occur in the factor U Consult the description of Umax Umin and Growth in Section 8 4 and set the LU factor tolerance to 2 0 or possibly even smaller but not less than 1 0 EXIT 50 Error in the user supplied functions INF
71. e retained if Name is a Jacobian variable 7 Partial basis Let m be the number of rows in the problem If fewer than m variables are specified to be basic a tentative basis list will be constructed by adding the requisite number of slacks starting from the first row and taking those that were not previously specified to be basic or superbasic If the resulting basis proves to be singular the basis factorization routine will replace a number of basic variables by other slacks 8 Too many basics If m variables have already been specified as basic any further BS keys will be treated as though they were SB This feature may be useful for combining solutions to smaller problems 110 SNOPT 7 User s Guide NAME sqdat2 DUMP LOAD LL 100 0 00000E 00 BS 101 3 89064E 02 BS 102 6 19233E 02 LL 103 1 00000E 02 SB 104 4 33462E 02 BS 105 3 00048E 02 BS 106 1 58194E 02 NAME sqdat2 PUNCH INSERT LL 107 2 00000E 03 XL 100 aegis OL 3 89064E 02 BS 108 4 83627E 01 XU 101 Jany O2 6 19233E 02 UL 109 1 00000E 02 LL 102 03 1 00000E 02 BS 110 3 24241E 01 SB 105 04 4 33462E 02 BS 111 1 60065E 01 XL 5107 05 3 00048E 02 LL 112 1 50000E 03 XE soe tI 416006 1 58194E 02 jh O e Ec 2 50000E 02 ENDATA BS 114 2 90022E 06 ENDATA Figure 4 Format of PUNCH INSERT files Figure 5 Format of DUMP LOAD files References 111 References 1 10 11 12 13 14
72. e snOptc interface 53 fObj must contain the computed value of fo x except perhaps if mode 1 g0bj nn0bj must contain the known components of the gradient vector g x i e g0bj J contains the partial derivative Of 0x except perhaps if mode 0 fCon nnCon contains the computed constraint vector f x except perhaps if mode 1 gCon nnCon nnJac or gCon neJac contains the computed Jacobian f x except per haps if mode 0 These gradient elements must be stored in gCon in exactly the same positions as implied by the definitions of snOptC s arrays Acol indA locA There is no internal check for consistency except indirectly via the Verify option so great care is essential 54 SNOPT 7 User s Guide 6 The npOpt interface The npOpt interface is designed for the solution of small dense problems The calling se quences of npOpt and its associated user defined functions are designed to be similar to those of the dense SQP code NPSOL Gill et al 9 For the case of npOpt it is convenient to restate the problem NPsparse with the constraints reordered as DenseNP minimize fo x x subject to L lt A x lt u f x where l and u are constant lower and upper bounds fo is a smooth scalar objective function A is a matrix and f x is a vector of smooth nonlinear constraint functions f a The interface npOpt is designed to handle problems for which the objective and constraint gra dien
73. e the maximum nonlinear constraint violation normalized by the size of the solution It is required to satisfy rowerr max viol z lt er 7 1 where viol is the violation of the ith nonlinear constraint i 1 nnCon In the major iteration log rowerr appears as the quantity labeled Feasib1 If some of the problem functions are known to be of low accuracy a larger Major feasibility tolerance may be appropriate Major optimality tolerance d Default 1 0e 6 This specifies the final accuracy of the dual variables On successful termination SNOPT will have computed a solution x s 7 such that maxComp max Comp 7 lt ea 7 2 j where Comp is an estimate of the complementarity slackness for variable j j 1 n m The values Comp are computed from the final QP solution using the reduced gradients dj gj nTa where g is the jth component of the objective gradient a is the associated column of the constraint matrix A I and r is the set of QP dual variables 7 dj min z Li 1 if dj gt 0 Comp f 7 d min u 25 1 if dj lt 0 7 Optional parameters 79 In the major iteration log maxComp appears as the quantity labeled Optimal Major iterations limit k Default max 1000 m This is the maximum number of major iterations allowed It is intended to guard against an excessive number of linearizations of the constraints Major print level p Default 00001 This contro
74. ect to the upper and lower bounds being satisfied In 3 The snOptA interface 19 this case nInf gives the number of components of A x lying outside their upper or lower bounds The nonlinear constraints are not evaluated Otherwise x minimizes the sum of the infeasibilities of the nonlinear constraints subject to the linear constraints and upper and lower bounds being satisfied In this case nInf gives the number of components of F x lying outside their upper or lower bounds by more than the Minor feasibility tolerance Again this is before the solution is unscaled 20 SNOPT 7 User s Guide 3 5 Subroutine snJac If you set Derivative option 0 and your function routine usrfun provides none of the derivatives you may call subroutine snJac to determine the input arrays iAfun jAvar A iGfun and jGvar for snOptA These define the pattern of nonzeros in the Jacobian matrix A typical sequence of calls is call snInit iPrint iSumm call snJac INFO iPrint call snSet Derivative option 0 call snOptA Start nF n The Derivative option could also be set in the SPECS file Subroutine snJac determines the sparsity pattern for the Jacobian and identifies the constant elements automatically To do so snJac approximates F x at three random perturbations of the given initial point x If an element of the approximate Jacobian is the same at all three points then it is taken to be constant If
75. ection 9 2 For linear programs this format is compatible with various commercial systems 7 Optional parameters 83 QPSolver Cholesky Default QPSolver CG QPSolver QN Specifies the active set algorithm used to solve the QP subproblem QPSolver Cholesky holds the full Cholesky factor R of the reduced Hessian Z7 HZ As the QP iterations pro ceed the dimension of R changes with the number of superbasic variables If it is necessary that the number of superbasic variables increases beyond the value of Reduced Hessian dimension the reduced Hessian cannot be stored and the solver switches to QPSolver CG The Cholesky solver is reactivated if the number of superbasics stabilizes at a value less than Reduced Hessian dimension QPSolver QN solves the QP subproblem using a quasi Newton method similar to MINOS In this case R is the factor of a quasi Newton approximate Hessian QPSolver CG uses an active set method similar to QPSolver QN but uses the conjugate gradient method to solve all systems involving the reduced Hessian e The Cholesky QP solver is the most robust but may require a significant amount of computation if the number of superbasics is large e The quasi Newton QP solver does not require the computation of the R at the start of each QP and may be appropriate when the number of superbasics is large but each QP subproblem requires relatively few minor iterations e The conjugate gradient QP solver is appropriate for problems
76. ed to compute the boundaries of any user defined workspace in cw iw or rw The next step is to call snMemB to obtain mincw miniw minrw as estimates of the storage needed by snOptB call snMemB amp INFO m n neA negCon amp nnCon nnJac nnObj amp mincw miniw minrw amp cw ltmpcw iw ltmpiw rw ltmprw The output values of mincw miniw minrw may now be used to define the lengths of the snOptB work arrays lencw mincw leniw miniw lenrw minrw These values may be used in f90 or C to allocate the final work arrays for the problem One last step is needed before snOptB is called The current upper limits 1ltmpcw 1ltmpiw ltmprw must be replaced by the estimates mincw miniw minrw This is done using the option setting routine snSeti as follows 4 The snOptB interface 49 Errors 0 Counts the number of errors iPrt 0 Suppress print output iSum 0 Suppress summary output call snSeti amp Total character workspace lencw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw call snSeti amp Total integer workspace leniw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw call snSeti amp Total real workspace lenrw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw An alternative way is to call snInit again with arguments lencw leniw lenrw call snlnit amp iPrint iSumm cw lencw iw leniw rw lenrw However this has
77. ee the following discussion of x x n contains a set of initial values for z 1 If Start 0 or 1 and a BASIS file of some sort is to be input an OLD BASIS INSERT or LOAD file then xstate and x need not be set 2 Otherwise xstate and x must be defined for a Cold start If nothing special is known about the problem or if there is no wish to provide special information you may set xstate j 0 x j 0 0 for all j 1 n All variables will be eligible for the initial basis Less trivially to say that the optimal value of variable j will probably be equal to one of its bounds set xstate j 4 and x j xlow j or xstate j 5 and x j xupp j as appropriate 3 For Cold starts with no basis file a CRASH procedure is used to select an initial basis The initial basis matrix will be triangular ignoring certain small entries in each column The values xstate j 0 1 2 3 4 5 have the following meaning xstate j State of variable j during CRASH 0 1 3 Eligible for the basis 3 is given preference 2 4 5 Ignored After CRASH columns for which xstate j 2 are made superbasic Other variables not selected for the basis are made nonbasic at the value x j if xlow j lt x j lt xupp j or at the value xlow j or xupp j closest to x j See the description of xstate below on exit 4 For Warm starts xstate 1 n must be 0 1 2 or 3 probably from some previous call F nF sometimes
78. enA gt 1 3 The snOptA interface 21 lenA should be an overestimate of the number of elements in the linear part of the Jacobian The value lenA nF x n is an upper bound on the length of A lenG isthe dimension of the coordinate arrays iGfun and jGvar that define the nonlinear Jacobian elements i j Gij lenG gt 1 lenG should be an overestimate of the number of elements in the nonlinear part of the Jacobian The value lenG nF x n is an upper bound on the length of iGfun and jGvar On exit iAfun lenA jAvar lenA A lenA define the coordinates i j of the nonzero elements neA of the linear part A of the function F x f x Az The neA triples iAfun k jAvar k A k define the row and column indices i iAfun k and j jAvar x of the element A A k is the number of nonzeros in A such that F x f x Ax neA gt 0 iGfun lenG jGvar lenG define the coordinates i j of the nonzero elements of the neG INFO mincw nonlinear part G of the derivatives F x f x A G x A of the function F x f x 4x The actual elements of G are assigned in the subroutine usrfun is the number of nonzero entries in G neG gt 0 reports the result of the call to snJac 102 Satisfactory coordinates were found 61 User indicates that the functions are undefined at the initial point 71 User requested termination by returning mode lt 1 from usrfun 82 Not enough 8 character
79. er happen It may indicate that the wrong SNOPT source files have been compiled or incorrect parameters have been used in the call to one of the SNOPT interfaces Check that all integer variables and arrays are declared integer in your calling program and that all real variables and arrays are declared consistently They should be double precision on most machines If there is an error in basis package a preceding message will describe the error in more detail One such message says that the current basis has more than one element in row i and column j This could be caused by a corresponding error in the input parameters i e the arrays A iAfun jAvar iGfun and jGvar for snOptA or indA Acol and locA for snOptB 8 7 Solution output At the end of a run the final solution is output to the PRINT file in accordance with the Solution keyword Some header information appears first to identify the problem and the final state of the optimization procedure A ROWS section and a COLUMNS section then follow giving one line of information for each row and column The format used is similar to certain commercial systems though there is no industry standard An example of the printed solution is given in Section 8 In general numerical values are output with format 16 5 The maximum record length is 111 characters including the first carriage control character To reduce clutter a dot is printed for any nu
80. erations in which no BFGS update could be made The diagonals of the approximate Hessian are retained if at least one update has been done since the last reset Otherwise the approximate Hessian is reset to the identity matrix A self scaled BFGS update was performed This update is used when the Hessian approximation is diagonal and hence always follows a Hessian reset The minor iterations were terminated because of the Minor iterations limit The minor iterations were terminated because of the New superbasics limit The QP subproblem was unbounded A weak solution of the QP subproblem was found The Superbasics limit was reached 8 Output 91 8 3 The minor iteration log If Minor print level gt 0 one line of information is output to the PRINT file every kth minor iteration where k is the specified Minor print frequency default k 1 A heading is printed before the first such line following a basis factorization The heading contains the items described below In this description a PRICE operation is defined to be the process by which a nonbasic variable is selected to become superbasic in addition to those already in the superbasic set The selected variable is denoted by jq Variable jq often becomes basic immediately Otherwise it remains superbasic unless it reaches its opposite bound and returns to the nonbasic set If Partial price is in effect variable jq is selected from App or pp the ppth segments of the constra
81. eter determines the accuracy to which this target value is approximated e must be a real value in the range 0 0 lt t lt 1 0 e The default value t 0 9 requests just moderate accuracy in the line search e If the nonlinear functions are cheap to evaluate a more accurate search may be ap propriate try t 0 1 0 01 or 0 001 The number of major iterations might decrease e If the nonlinear functions are expensive to evaluate a less accurate search may be appropriate If all gradients are known try t 0 99 The number of major iterations might increase but the total number of function evaluations may decrease enough to compensate 7 Optional parameters 77 e If not all gradients are known a moderately accurate search remains appropriate Each search will require only 1 5 function values typically but many function calls will then be needed to estimate missing gradients for the next iteration Load file f Default 0 If f gt 0 this references a file containing basis information in the format of Section 9 3 e The file will usually have been output previously as a DUMP file e The file will not be accessed if an OLD BASIS file or an INSERT file is specified Log frequency k Default 100 see Print frequency LU factor tolerance r Default 100 0 LP or 3 99 NLP LU update tolerance r2 Default 10 0 LP or 3 99 NLP These tolerances affect the stability and sparsity of the basis factorization B LU dur
82. evel 0 Timing level 3 End of SPECS file checklist A KA XK XX XX XX XX XX k w XX XX XX XX Xk XX kk XA XX XX XX almost full accuracy Function precision Function precision controls early termination of QPs row number of objective in F x initial penalty parameter satisfies linear constraints near xo or Superbasics limit if that is less unscaled constraint violation limit default if n lt 75 default if n gt 75 for full Hessian never reset for limited memory Hessian no flushing test row residuals Ax s for anti cycling procedure 100 for LPs save basis map limits size of multipliers in L the same during updates default pivot strategy use rook pivoting for the LU use complete pivoting for the LU input basis map output basis map output basis map input in industry format output INSERT data input names and values output LOAD data different from printed solution for developers prints cpu times 66 SNOPT 7 User s Guide 7 3 Subroutine snSpec Subroutine snSpec may be called to input a SPECS file to specify options for a subsequent call of SNOPT subroutine snSpec amp iSpecs INFO cw lencw iw leniw rw lenrw integer amp iSpecs INFO lencw leniw lenrw iw leniw double precision amp rw lenrw character amp cw lencw 8 On entry iSpecs is a unit number for the SPECS file iSpecs gt 0 Typically iSpecs 4
83. f x is a nonlinear function possibly zero and the elements A are constant The nF xn Jacobian of F x is the sum of two sparse matrices of the same size F x G x A where G x f x and A is the matrix with elements A The two matrices must be non overlapping in the sense that every element of the Jacobian F 1 G x A is an element of G x or an element of A but not both For example the function 321 e224 r2 4z4 3 T5 F x 2 22 sin 24 325 T T3 can be written as e 2 g4 22 424 321 T3 T5 F x f x Ar 23 sin z4 La 325 0 1 T3 in which case 3 e 2r 2x 1 e 2 4 1 F x 0 1 213 cos t4 3 1 0 0 0 0 can be written as F x f x A G x A where O e24 222 0 e 4 0 3 Gel 0 4 G x 0 0 213 costs 0 A 0 1 0 0 3 0 0 0 0 0 i 0 1 0 0 The nonzero elements of A and G are provided to snOptA in coordinate form The elements of A are entered as triples i j Ai in the arrays iAfun jAvar A The sparsity pattern of G is entered as pairs i j in the arrays iGfun jGvar The corresponding entries Gij any that are known are assigned to appropriate array elements G k in the user s subroutine usrfun The elements of A and G may be stored in any order Duplicate entries are ignored As mentioned iGfun and jGvar may be defined automatically by subroutine snJac p 20 when Derivative option 0 is specified and usrfun does not provide any
84. f the change in the variables at each step If either of these is very large as judged by the Unbounded parameters see Section 7 6 the problem is terminated and declared unbounded To avoid large function values it may be necessary to impose bounds on some of the variables in order to keep them away from singularities in the nonlinear functions The second informational message indicates an abnormal termination while enforcing the limit on the constraint violations This exit implies that the objective is not bounded below in the feasible region defined by expanding the bounds by the value of the Violation limit EXIT 30 Resource limit error INFO 31 iteration limit reached INFO 32 major iteration limit reached INFO 33 the superbasics limit is too small Either the Iterations limit or the Major iterations limit was exceeded before the required solution could be found Check the iteration log to be sure that progress was being made If so restart the run using a basis file that was saved or should have been saved at the end of the run If the superbasics limit is too small then the problem appears to be more nonlinear than anticipated The current set of basic and superbasic variables have been optimized as much as possible and a PRICE operation is necessary to continue but there are already Superbasics limit superbasics and no room for any more EXIT 40 Terminated after numerical difficulties INFO 41 current p
85. fficulties 41 current point cannot be improved 42 singular basis 43 cannot satisfy the general constraints 44 illconditioned null space basis Error in the user supplied functions 51 incorrect objective derivatives 52 incorrect constraint derivatives Undefined user supplied functions 61 undefined function at the first feasible point 62 undefined function at the initial point 63 unable to proceed into undefined region User requested termination 71 terminated during function evaluation 74 terminated from monitor routine Insufficient storage allocated 81 work arrays must have at least 500 elements 82 not enough character storage 83 not enough integer storage 84 not enough real storage Input arguments out of range 91 invalid input argument 92 basis file dimensions do not match this problem System error 141 wrong number of basic variables 142 error in basis package is the number of major iterations performed describes the status of the constraints lt r x lt u in problem NP For the jth lower or upper bound 7 1 to nctotl the possible values of istate j are as follows see Figure 1 6 is the appropriate feasibility tolerance 2 Region 1 The lower bound is violated by more than 1 Region 5 The upper bound is violated by more than 6 0 Region 3 Both bounds are satisfied by more than Region 2 The lower bound is active to within Region 4 The upper bound is active to
86. function fo x and optionally their gradients for a speci fied n vector x The arguments funcon and funobj must be declared as external in the routine that calls npOpt For a detailed description of funcon and funobj see Section 6 3 istate nctotl is an integer array that need not be initialized if npOpt is called with a Cold Start the default option For a Warm start every element of istate must be set If npOpt has just been called on a problem with the same dimensions istate already contains valid values Otherwise istate j should indicate whether either of the constraints r x gt 0 or r x lt uj is expected to be active at a solution of DenseNP The ordering of istate is the same as for b1 bu and r x i e the first n components of istate refer to the upper and lower bounds on the variables the next nclin refer to the bounds on A x and the last ncnln refer to the bounds on f x Possible values for istate j follow 0 Neither r x gt 4 nor r x lt u is expected to be active 1 r a gt is expected to be active 2 rj x lt uj is expected to be active 3 This may be used if uj Normally an equality constraint r x 0 uj is active at a solution The values 1 2 or 3 all have the same effect when bl j bu j If necessary npOpt will override the user s specification of istate so that a poor choice will not cause the algorithm to fail gCon 1dg is an array of dimension 1dg k
87. gradients 3 The snOptA interface 13 3 4 Subroutine snOptA Problem NPA is solved by a call to subroutine snOptA whose parameters are defined here Note that most machines use double precision declarations as shown but some machines use real The same applies to the function routine usrfun and all other routines subroutine snOptA amp Start nF n nxname nFname amp ObjAdd ObjRow Prob usrfun amp iAfun jAvar lenA neA A amp iGfun jGvar lenG neG amp xlow xupp xnames Flow Fupp Fnames amp x xstate xmul F Fstate Fmul amp INFO mincw miniw minrw amp nS ninf sInf amp cu lencu iu leniu ru lenru amp cw lencw iw leniw rw lenrw external amp usrfun integer amp INFO lenA lencu lencw lenG leniu leniw lenru lenrw amp mincw miniw minrw n neA neG nF nFname ninf nS amp nxname ObjRow Start iAfun lenA iGfun lenG iu leniu amp iw leniw jAvar lenA jGvar lenG xstate n Fstate nF double precision amp ObjAdd sInf A lenA F nF Fmul nF Flow nF Fupp nF amp ru lenru rw lenrw x n xlow n xmul n xupp n character amp Prob 8 cu lencu 8 cw lencw 8 amp Fnames nFname 8 xnames nxname 8 On entry Start is an integer that specifies how a starting basis and certain other items are to be obtained Start 0 Cold start requests that the CRASH procedure be used to choose an initial basis unless a basis file i
88. gth at least 500 cw lencw iw leniw rw lenrw are 8 character integer and real arrays of workspace for snMemB 48 SNOPT 7 User s Guide On exit INFO reports the result of the call to snMemB Here is a summary of possible values Further details are in Section 8 6 Insufficient storage allocated 81 work arrays must have at least 500 elements Finished successfully 104 memory requirements estimated mincw miniw minrw estimate how much character integer and real storage is needed to solve the problem To use snMemB the first step is to allocate the work arrays These may be temporary arrays tmpcw tmpiw tmprw say or the snOptB arrays cw iw rw which will be reallocated after the storage limits are known Here we illustrate the use of snMemB using the same arrays for snMemB and snOptB Note that the snMemB arrays are used to store the optional parameters and so any temporary arrays must be copied into the final cw iw rw arrays in order to retain the options The work arrays must have length at least 500 so we define ltmpcw 500 ltmpiw 500 ltmprw 500 As with all SNOPT routines snInit must be called to initialize the optional parameters to their default values call snlnit amp iPrint iSumm cw ltmpcw iw ltmpiw rw ltmprw This installs ltmpcw ltmpiw ltmprw as the default internal upper limits on the snOptB workspace see the description of Total real workspace in Section 7 6 They are us
89. he above example if an optimum solution is found at iteration 2050 or if the iteration limit is 2050 the final basis on file 12 will correspond to iteration 2050 but the last basis saved on file 11 will be the one for iteration 2000 Central difference interval r Default 3 6 0e 6 When Derivative option 0 with the snOptA interface or Derivative level lt 3 with snOptB or sn0ptC the central difference interval r is used near an optimal solution to obtain more accurate but more expensive estimates of gradients Twice as many function evaluations are required compared to forward differencing The interval used for the jth variable is h r 1 x The resulting derivative estimates should be accurate to O r unless the functions are badly scaled Check frequency 1 Default 60 Every ith minor iteration after the most recent basis factorization a numerical test is made to see if the current solution x satisfies the general linear constraints including linearized nonlinear constraints if any The constraints are of the form Ag s b where s is the set of slack variables To perform the numerical test the residual vector r b Ax s is computed If the largest component of r is judged to be too large the current basis is refactorized and the basic variables are recomputed to satisfy the general constraints more accurately Check frequency 1 is useful for debugging purposes but otherwise this option should not be
90. he first and last entries subroutine funcon amp mode nnCon nnJac neJac amp x fCon gCon nState amp cu lencu iu leniu ru lenru integer amp lencu leniu lenru mode neJac nnCon nnJac nState amp iu leniu double precision amp fCon nnCon gCon nnCon nnJac ru lenru x nnJac character amp cu lencu 8 Toy NLP problem with dense Jacobian integer amp nout double precision amp x1 x2 nout 9 x1 x 1 x2 x 2 if nState eq 1 then First entry if nout gt 0 write nout a This is problem Toy end if if mode eq 0 or mode eq 2 then fCon 1 x1 2 x2 2 fCon 2 x2 4 end if if mode ge 1 then gCon 1 1 2 0d 0 x1 Jacobian elements for column 1 gCon 2 1 0 0d 0 Can t be omitted gCon 1 2 2 0d 0 x2 Jacobian elements for column 2 gCon 2 2 4 0d 0 x2 3 end if if State ge 2 then Last entry if nout gt 0 write nout a gt Finished problem Toy end if end subroutine funcon 46 SNOPT 7 User s Guide Now we treat the Jacobian as a sparse matrix stored column wise Note that gCon has only 3 entries because we intentionally omit the zero entry in column 1 The first column of the Acol indA locA data structure must also have that entry deleted subroutine funcon amp mode nnCon nnJac neJac amp x fCon gCon nState amp cu lencu iu leniu ru lenru integer amp lencu leniu lenru mode neJac
91. herefore be used only if a a good starting point is provided and b the problem is not highly nonlinear Scale tolerance affects how many passes might be needed through the constraint ma trix On each pass the scaling procedure computes the ratio of the largest and smallest nonzero coefficients in each column pj max aij min aij aiz 0 If max p is less than r times its previous value another scaling pass is performed to adjust the row and column scales Raising r from 0 9 to 0 99 say usually increases the number of scaling passes through A At most 10 passes are made Scale Print causes the row scales r i and column scales c j to be printed The scaled matrix coefficients are aj c j r i and the scaled bounds on the variables and slacks are lj 1 c j j u c j where c j r j n if j gt n Solution Yes Solution No Solution If Optimal Infeasible or Unbounded Solution file f Default 0 The first four options determine whether the final solution obtained is to be output to the PRINT file The file option operates independently if f gt 0 the final solution will be output to file f whether optimal or not e For the first and third options floating point numbers are printed in 16 5 format and infinite bounds are denoted by the word None e For the File option all numbers are printed in 1p e16 6 format including infinite bounds which will have magnitude 1 000000e 20 e To
92. ication Minimize Feasible point Infinite Bound size Convergence Tolerances Major feasibility tolerance Major optimality tolerance Minor feasibility tolerance Derivative checking Verify level Start objective Stop objective Start constraint check check check check at at at at Stop constraint Scaling Scale option Scale tolerance Scale Print Other Tolerances Crash tolerance Linesearch tolerance Pivot tolerance QP subproblems QPSolver Crash option Elastic mode Elastic weight Iterations limit Partial price SQP method Major iterations Minor iterations Major step limit Superbasics limit Derivative level Derivative option Derivative linesearch limit limit col col col col nN OrR fF 100 100 Yes No 1 0e 20 Pp 0e 6 0e 6 0e 6 e e wo co Te 11 Cholesky w XX XX XX XX XX kk one line major iteration log one line minor iteration log typically the screen minor iterations log on PRINT file minor iterations log on SUMMARY file on the PRINT file default options are listed prints more system information opposite of Maximize alternative to Max or Min XxX x target nonlinear constraint violation target complementarity gap for satisfying the QP bounds cheap check on gradients NOT ALLOWED IN snOpta NOT ALLOWED IN snOptaA NOT ALLOWED IN snOptaA NOT ALLOWED IN snOptaA linear constraints and variables default scales are n
93. ine of output is 3 1 250000D 01 BS 1 1 00000E 00 4 2 00000E 00 which would mean that x3 is basic at value 12 5 and the third column of the Jacobian has elements of 1 0 and 2 0 in rows 1 and 4 Major print level 0 suppresses most output except for error messages Major step limit r Default 2 0 This parameter limits the change in x during a line search It applies to all nonlinear problems once a feasible solution or feasible subproblem has been found 1 A line search determines a step a over the range 0 lt a lt 8 where 8 is 1 if there are nonlinear constraints or the step to the nearest upper or lower bound on z if all the constraints are linear Normally the first steplength tried is a min 1 3 2 In some cases such as f x ae or f x ax even a moderate change in the components of x can lead to floating point overflow The parameter r is therefore used to define a limit P r 1 x p where p is the search direction and the first evaluation of f a is at the potentially smaller steplength a min 1 8 6 80 SNOPT 7 User s Guide 3 Wherever possible upper and lower bounds on x should be used to prevent evalua tion of nonlinear functions at meaningless points The Major step limit provides an additional safeguard The default value r 2 0 should not affect progress on well behaved problems but setting r 0 1 or 0 01 may be helpful when rapidly vary ing functions are present
94. ing refactorization and updating respectively They must satisfy r1 ro gt 1 0 The matrix L is a product of matrices of the form 1 me 1 where the multipliers y satisfy u lt r Smaller values of r favor stability while larger values favor sparsity The default values usually strike a good compromise e For large and relatively dense problems r 5 0 say may give a useful improvement in stability without impairing sparsity to a serious degree e For certain very regular structures e g band matrices it may be necessary to reduce r and or rg in order to achieve stability For example if the columns of A include a submatrix of the form 4 1 1 4 1 1 4 1 1 4 1 1 4 both r and r should be in the range 1 0 lt r lt 4 0 LU Partial Pivoting Default LU Rook Pivoting LU Complete Pivoting The LU factorization implements a Markowitz type search for a pivot that locally minimizes the fill in subject to a threshhold pivoting stability criterion The default option is to use 78 SNOPT 7 User s Guide threshhold partial pivoting The options LU rook pivoting and LU complete pivoting are more expensive than partial pivoting but are more stable and better at revealing rank LU complete pivoting is the default for the npOpt interface LU density tolerance r Default 0 6 LU singularity tolerance r2 Default e 3 3 2e 11 The density tolerance r is used during LU factorization of the basis matrix
95. int matrix A I Label Description Itn The current iteration number RedCost QPmult This is the reduced cost or reduced gradient of the variable jq selected by PRICE at the start of the present iteration Algebraically dj is dj gj m7 a for j jq where gj is the gradient of the current objective function 7 is the vector of dual variables for the QP subproblem and a is the jth column of A T Note that dj is the 1 norm of the reduced gradient vector at the start of the iteration just after the PRICE operation LPstep QPstep The step length a taken along the current search direction p The variables x have just been changed to x ap If a variable is made superbasic during the current iteration SBS gt 0 Step will be the step to the nearest bound During Phase 2 the step can be greater than one only if the reduced Hessian is not positive definite nInf The number of infeasibilities after the present iteration This number will not increase unless the iterations are in elastic mode SumInf If nInf gt 0 this is sInf the sum of infeasibilities after the present iteration It usually decreases at each nonzero Step but if nInf decreases by 2 or more SumInf may occasionally increase In elastic mode the heading is changed to Composite Obj and the value printed decreases monotonically rgNorm The norm of the reduced gradient vector at the start of the iteration It is the norm of the vector with elements
96. ints and bounds on x are satisfied This helps confine x to regions where the functions f a are likely to be defined However be aware of the Minor feasibility tolerance if the functions have singularities on the constraint boundaries 8 Set Status 1 if some of the functions are undefined The line search will shorten the step and try again 9 Set Status lt 1 if you want snOptA to stop 3 The snOptA interface 23 amp amp amp amp subroutine usrfun Status n x needf nF f needG lenG G cu lencu iu leniu ru lenru integer lencu lenG leniu lenru n needf needG nF Status iu leniu double precision f nF G lenG ru lenru x n character cu lencu 8 On entry Status x n needf indicates the first and last calls to usrfun If Status 0 there is nothing special about the current call to usrfun If Status 1 snOpta is calling your subroutine for the first time Some data may need to be input or computed and saved If Status gt 2 snOptA is calling your subroutine for the last time You may wish to perform some additional computation on the final solution In general the last call is made with Status 2 INFO 10 where INFO is the integer returned by snOptA see p 17 In particular if Status 2 the current x is optimal if Status 3 the problem appears to be infeasible if Status 4 the problem appears to be unbounded if Status 5 an iterati
97. iplier for the ith constraint The full vector m always satisfies BIr gp where B is the current basis matrix and gg contains the associated gradients for the current objective function I The constraint number i The COLUMNS section Here we talk about the column variables xj 7 1 n We assume that a typical variable has bounds a lt x lt 2 Label Description Number The column number j This is the internal number used to refer to x in the iteration log Column The name of zj State The state of x relative to the bounds a and The various states possible are as follows LL a is nonbasic at its lower limit a UL xj is nonbasic at its upper limit EQ x is nonbasic and fixed at the value a FR x is nonbasic at some value strictly between its bounds a lt a lt P BS 2 is basic Usually a lt a lt B SBS xj is superbasic Usually a lt x lt A key is sometimes printed before the State to give some additional information about the state of zj A Alternative optimum possible The variable is nonbasic but its reduced gradi ent is essentially zero This means that if x were allowed to start moving from its current value there would be no change in the objective function The values of the basic and superbasic variables might change giving a genuine alternative solution The values of the dual variables might also change D Degenerate x is basic but it is equal to or very close to one
98. is the non overlapping matrix 34 2 x1 23 14 0 2 11 z3 24 2 21 3 24 0 0 2x3 204 GG 0 0 0 0 0 0 0 4x3 The calling program must assign many parameters for input to snOptA including nF 4 n 4 ObjRow 1 neA 5 neG 6 lenG 6 gt neG Some of these parameters are passed to subroutine usrfun next page Note that usrfun works only with the nonlinear variables 11 13 4 that appear in f and G The array f is set to f x excluding the term Ax which is evaluated separately by snOptA The array G is set to all nonzero entries of G x excluding the matriz A For illustration we test needF and needG to economize on function and gradient eval uations even though they are cheap here Note that Nonderivative linesearch would have to be specified otherwise all entries would have needG 1 We also test State to print a message on the first and last entries 26 SNOPT 7 User s Guide subroutine usrfun amp Status n x amp needF nF f amp needG lenG G amp cu lencu iu leniu ru lenru integer amp lencu lenG leniu lenru n needF needG nF Status amp iu leniu double precision amp f nF G lenG x n ru lenru character amp cu lencu 8 Computes the nonlinear objective and constraint terms for the toy problem featured in the SNOPT user s guide in
99. it is zero it is taken to be identically zero Since the random points are not chosen close together the heuristic will correctly classify the Jacobian elements in the vast majority of cases G x Az In general snJac finds that the Jacobian can be permuted to the form Az As X where Az A3 A4 are constant Note that G x might contain elements that are also constant but snJac must classify them as nonlinear This is because snOptA removes linear variables from the calculation of F by setting them to zero before calling usrfun A knowledgeable user would be able to move such elements from usrfun s F x and enter them as part of iAfun jAvar A for snOpta subroutine snJac amp INFO iPrint iSumm nF n usrfun amp iAfun jAvar lenA neA A amp iGfun jGvar lenG neG amp x xlow xupp mincw miniw minrw amp cu lencu iu leniu ru lenru amp cw lencw iw leniw rw lenrw external amp usrfun integer amp INFO iPrint iSumm nF n neA lenA neG lenG mincw amp miniw minrw lencu lencw leniu leniw lenru lenrw amp iAfun lenA jAvar lenA iGfun lenG jGvar lenG amp iu leniu iw leniw double precision amp A lenA x n xlow n xupp n ru lenru rw lenrw character amp cu lencu 8 cw lencw 8 On entry Most arguments are identical to those of snOpta lenA is the dimension of the coordinate arrays iAfun jAvar and A that hold the coordi nates i j Aij l
100. ix that is essentially triangular A column is assigned to pivot on a particular row if the column contains a suitably large element in a row that has not yet been assigned The pivot elements ultimately form the diagonals of the triangular basis For remaining unassigned rows slack variables are inserted to complete the basis The Crash tolerance r allows the starting procedure CRASH to ignore certain small nonzeros in each column of A If max is the largest element in column j other nonzeros a in the column are ignored if a lt dmax X r To be meaningful r should be in the range 0O lt r lt 1l When r gt 0 0 the basis obtained by CRASH may not be strictly triangular but it is likely to be nonsingular and almost triangular The intention is to obtain a starting basis containing more columns of A and fewer arbitrary slacks A feasible solution may be reached sooner on some problems For example suppose the first m columns of A are the matrix shown under LU factor tolerance i e a tridiagonal matrix with entries 1 4 1 To help CRASH choose all m columns for the initial basis we would specify Crash tolerance r for some value of r gt 1 4 Derivative level i Default 3 This keyword is used by the snOptB snOptC and npOpt interfaces It should not be used when calling snOptA The keyword Derivative level specifies which nonlinear function gradients are known analytically and will be supplied to SNOPT by the
101. king storage needed and the amount available e Some statistics about the problem being solved e The storage available for the LU factors of the basis matrix e A summary of the scaling procedure if Scale option gt 0 e Notes about the initial basis resulting from a CRASH procedure or a BASIS file e The major iteration log e The minor iteration log e Basis factorization statistics e The EXIT condition and some statistics about the solution obtained e The printed solution if requested The last five items are described in the following sections 8 2 The major iteration log If Major print level gt 0 one line of information is output to the PRINT file every kth minor iteration where k is the specified Print frequency default k 1 Label Description Itns The cumulative number of minor iterations Major The current major iteration number Minors is the number of iterations required by both the feasibility and optimality phases of the QP subproblem Generally Minors will be 1 in the later iterations since theoretical analysis predicts that the correct active set will be identified near the solution see Section 2 Step The step length a taken along the current search direction p The variables x have just been changed to x ap On reasonably well behaved problems the unit step will be taken as the solution is approached nCon The number of times subroutines usrfun or funcon have been called to evaluate the nonli
102. kspace in cw and rw See the Total and User workspace options On exit fCon nnCon contains the computed constraint vector f x except perhaps if mode 1 gCon nnCon nnJac or gCon neJac contains the computed Jacobian f x except per mode haps if mode 0 These gradient elements must be stored in gCon consistently with the arrays Acol indA locA that define the sparsity pattern of f x and Aa in 4 2 excluding the elements of Az There is no internal check for consistency except indirectly via the Verify option so great care is essential may be used to indicate that you are unable to evaluate f or its gradients at the current x For example the problem functions may not be defined there During the line search f x is evaluated at points k ap for various steplengths a where f xp has already been evaluated satisfactorily For any such x if you set mode 1 snOptB will reduce a and evaluate f again closer to k where it is more likely to be defined If for some reason you wish to terminate the current problem set mode lt 2 4 The snOptB interface 43 4 7 Subroutine funobj This subroutine must calculate the nonlinear objective function fo x and optionally its gradient g x Ofo x Ox where x is the current value of the objective variables 2 subroutine funobj amp mode nn0bj amp x fObj g0bj nState amp cu lencu iu leniu ru lenru integer amp
103. l of funcon 0 lt mode lt 2 This parameter can be ignored if Derivative linesearch is selected the default and if Derivative level 2 or 3 In this case mode will always have the value 2 and all elements of fCon and gCon must be assigned except perhaps constant elements of gCon Otherwise snOptB will call funcon with mode 0 1 or 2 You may test mode to decide what to do e If mode 2 assign fCon and the known components of gCon e If mode 1 assign the known components of gCon fCon is ignored e If mode 0 only Con need be assigned gCon is ignored nnCon is the number of nonlinear constraints nnCon gt 0 These must be the first nnCon constraints in the problem nnJac is the number of variables involved in f x 0 lt nnJac lt n These must be the first nnJac variables in the problem neJac is the number of nonzero elements in gCon If gCon is stored as a two dimensional array then neJac nnCon x nnJac x nnJac contains the nonlinear Jacobian variables x The array x must not be altered 42 SNOPT 7 User s Guide nState indicates the first and last calls to funcon If nState 0 there is nothing special about the current call to funcon If nState 1 snOptB is calling your subroutine for the first time Some data may need to be input or computed and saved Note that if there is a nonlinear objective the first call to funcon will occur before the first call to funobj If nState gt 2 snOptB i
104. les Ideally should be set slightly larger than the number of degrees of freedom expected at an optimal solution For linear programs an optimum is normally a basic solution with no degrees of freedom The number of variables lying strictly between their bounds is no more than m the number of general constraints The default value of i is therefore 1 For nonlinear problems the number of degrees of freedom is often called the number of independent variables Normally need not be greater than n 1 where n is the number of nonlinear variables For many problems may be considerably smaller than n This will save storage if n is very large Suppress Parameters Normally SNOPT prints the SPECS file as it is being read and then prints a complete list of the available options and their final values The Suppress Parameters option tells SNOPT not to print the full list Total real workspace maxrw Default lenrw Total integer workspace maxiw Default leniw Total character workspace maxcw Default lencw User real workspace maxru Default 500 User integer workspace maxiu Default 500 User character workspace maxcu Default 500 These options may be used to confine SNOPT to certain parts of its workspace arrays cw iw rw The arrays are defined by the last six parameters of SNOPT The Total options place an upper limit on SNOPT s workspace They may be useful on machines with virtual memory For example so
105. lines of the form j Tj written with format i8 ip e24 14 and terminated by an entry with j 0 where j denotes the jth variable and x is a real value The jth variable is either the jth column or the j n th slack if j gt n Typically hs j 2 superbasic When nonlinear constraints are present this list of superbasic variables is extended to include all basic nonlinear variables The Jacobian matrix can then be reconstructed exactly for a restart The list also includes nonbasic variables that lie strictly between their bounds Loading a NEW BASIS file A file that has been saved as an OLD BASIS file may be input at the beginning of a later run as a NEW BASIS file The following notes are relevant l 2 The first line is input and printed but otherwise not used The values labeled M and N on the second line must agree with m and n for the problem that has just been defined The value labeled SB is input and printed but is not used The next set of lines must contain exactly m values hs j 3 denoting the basic variables The list of 7 and x values must include an entry for every variable whose state is hs j 2 the superbasic variables Further j and x values may be included in any order For any j in this list if hs j 3 basic the value z will be recorded for nonlinear variables but the variable will remain basic If hs j 3 variable j will be initialized at the value x and its state will be re
106. ls the amount of output to the PRINT and SUMMARY files each major iteration Major print level 1 gives normal output for linear and nonlinear problems and Major print level 11 gives addition details of the Jacobian factorization that commences each major iteration In general the value being specified may be thought of as a binary number of the form Major print level JFDXbs where each letter stands for a digit that is either O or 1 as follows s a single line that gives a summary of each major iteration This entry in JFDXbs is not strictly binary since the summary line is printed whenever JFDXbs gt 1 b BASIS statistics i e information relating to the basis matrix whenever it is refactor ized This output is always provided if JFDXbs gt 10 k the nonlinear variables involved in the objective function or the constraints Tk the dual variables for the nonlinear constraints F t the values of the nonlinear constraint functions a H O px J xk the Jacobian matrix To obtain output of any items JFDXbs set the corresponding digit to 1 otherwise to 0 If J 1 the Jacobian matrix will be output column wise at the start of each major iteration Column j will be preceded by the value of the corresponding variable x and a key to indicate whether the variable is basic superbasic or nonbasic Hence if J 1 there is no reason to specify X 1 unless the objective contains more nonlinear variables than the Jacobian A typical l
107. me systems allow a very large array rw lenrw to be declared at compile time with no overhead in saving the resulting object code At run time when various problems of different size are to be solved it may be sensible to restrict SNOPT to the lower end of rw in order to reduce paging activity slightly However SNOPT accesses storage contiguously wherever possible so the benefit may be slight In general it is far better to have too much storage than not enough If SNOPT s user parameters ru lenru happen to be the same as rw lenrw the nonlinear function routines will be free to use ru maxrw 1 lenru for their own purpose Similarly for the other work arrays The User options place a lower limit on SNOPT s workspace not counting the first 500 elements Again if SNOPT s parameters ru lenru happen to be the same as 86 SNOPT 7 User s Guide rw lenrw the function routines will be free to use ru 501 maxru for their own purpose Similarly for the other work arrays System Information No Default System Information Yes This option allows the knowledgeable user to print some additional information on the progress of the major and minor iterations Timing level 1 Default 3 i 0 suppresses output of cpu times Intended for installations with dysfunctional timing routines Unbounded objective value fmax Default 1 0e 15 Unbounded step size Qax Default 1 0e 18 These parameters are intended to detect unbou
108. merical value that is exactly zero The values 1 are also printed specially as 1 0 and 1 0 Infinite bounds 10 or larger are printed as None Note If two problems are the same except that one minimizes an objective fo x and the other maximizes f x their solutions will be the same but the signs of the dual variables mi and the reduced gradients dj will be reversed 102 SNOPT 7 User s Guide The ROWS section General linear constraints take the form lt Ax lt u The ith constraint is therefore of the form a lt ar lt B and the value of afz is called the row activity Internally the linear constraints take the form Ax s 0 where the slack variables s should satisfy the bounds l lt s lt u For the ith row it is the slack variable s that is directly available and it is sometimes convenient to refer to its state Slacks may be basic or nonbasic but not superbasic Nonlinear constraints a lt fi w aTx lt 8 are treated similarly except that the row activity and degree of infeasibility are computed directly from f 1 afz rather than s Label Description Number The value n i This is the internal number used to refer to the ith slack in the iteration log Row The name of the ith row State The state of the ith row relative to the bounds a and 8 The various states possible are as follows LL The row is at its lower limit a UL The row is at its upper limit 6 EQ The limits a
109. mincw leniw miniw lenrw minrw These values may be used in f90 or C to allocate the final work arrays for the problem One last step is needed before snOpta is called The current upper limits 1tmpcw 1tmpiv ltmprw must be replaced by the estimates mincw miniw minrw This can be done using the option setting routine snSeti as follows Errors 0 Counts the number of errors iPrt 0 Suppress print output iSum 0 Suppress summary output call snSeti amp Total character workspace lencw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw call snSeti amp Total integer workspace leniw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw call snSeti amp Total real workspace lenrw iPrt iSum Errors amp cw ltmpcw iw ltmpiw rw ltmprw 30 SNOPT 7 User s Guide An alternative way is to call snInit again with arguments lencw leniw lenrw call snlnit amp iPrint iSumm cw lencw iw leniw rw lenrw However this has the twin effects of resetting all options to their default values and reprint ing the SNOPT banner unless iPrint 0 and iSumm 0 are set for the PRINT and SUMMARY files 4 The snOptB interface 31 4 The snOptB interface snOptB is the basic user interface with arguments identical to versions of SNOPT up to version 5 3 4 The optimization problem is assumed to be in the form of SparseNP p 3 with the data ordered so that
110. mount bounded by sInf if scaling was not used contains the final values of the variables x xmul ne is the vector of dual variables for the simple bound constraints ly lt lt Ug F nF is the final value of the vector F of problem functions Fmul nF is the vector of dual variables Lagrange multipliers for the general constraints INFO lp lt F x lt Up reports the result of the call to snOptA Here is a summary of possible values Further details are in Section 8 6 Finished successfully 1 optimality conditions satisfied 2 feasible point found 3 requested accuracy could not be achieved The problem appears to be infeasible 11 infeasible linear constraints 12 infeasible linear equalities 13 nonlinear infeasibilities minimized 14 infeasibilities minimized The problem appears to be unbounded 21 unbounded objective 22 constraint violation limit reached Resource limit error 31 iteration limit reached 32 major iteration limit reached 33 the superbasics limit is too small Terminated after numerical difficulties 18 SNOPT 7 User s Guide 41 current point cannot be improved 42 singular basis 43 cannot satisfy the general constraints 44 illcconditioned null space basis Error in the user supplied functions 51 incorrect objective derivatives 52 incorrect constraint derivatives Undefined user supplied functions 61 undefined function at the first feasible point 62 undefined function at the initial
111. mponents must be defined If nothing is known about A set pi i 0 0 i 1 nnCon need not be specified for Cold starts but should retain its value from a previous call when a Warm start is used cu lencu iu leniu ru lenru are 8 character integer and real arrays of user work space They may be used to pass data or workspace to your function routines funcon and funobj which have the same parameters They are not touched by snOptB If the function routines don t reference these parameters you may use any arrays of the appropriate type such as cw iw rw see next paragraph Alternatively you should use the latter arrays if funcon and funobj need to access snOptB s workspace cw lencw iw leniw rw lenrw are 8 character integer and real arrays of workspace for snOptB lencw leniw lenrw must all be at least 500 In general lencw 500 is appropriate but leniw and lenrw should be as large as possible because it is uncertain how much storage will be needed for the basis factorization As an estimate leniw should be about 100 m n or larger and lenrw should be about 200 m n or larger Appropriate values may be obtained from a preliminary run with lencw leniw lenrw 500 If Print level is positive the required amounts of workspace are printed before snOptB terminates with INFO 82 83 or 84 The values are returned in mincw miniw and minrw On exit hs n m is the final state vector The elements of h
112. ms the pivot tolerance is used to prevent columns entering the basis if they would cause the basis to become almost singular e When z changes to x ap for some search direction p a ratio test is used to determine which component of x reaches an upper or lower bound first The corresponding element of p is called the pivot element e Elements of p are ignored and therefore cannot be pivot elements if they are smaller than the pivot tolerance r e It is common for two or more variables to reach a bound at essentially the same time In such cases the Minor Feasibility tolerance say t provides some freedom to maximize the pivot element and thereby improve numerical stability Excessively small values of t should therefore not be specified e To a lesser extent the Expand frequency say f also provides some freedom to maximize the pivot element Excessively large values of f should therefore not be specified Print file f Default 15 Print frequency k Default 100 If f gt 0 and Minor print level gt 0 a line of the QP iteration log will be printed on file f every kth minor iteration Proximal point method 1 Default 1 i 1 or 2 specifies minimization of a xo or lla xo 3 when the starting point xo is changed to satisfy the linear constraints where xp refers to nonlinear variables Punch file f Default 0 If f gt 0 the final solution obtained will be output to file f in the format described in S
113. n iw leniw double precision amp fObj AC1dA bl n nclin ncnln bu ntnclintncnln amp cMul ntnclintncnln fCon gCon ldg gO0bj n amp Hess 1dH rw lenrw x n On entry n is n the number of variables in the problem n gt 0 nclin is m the number of general linear constraints nclin gt 0 56 SNOPT 7 User s Guide ncnln is my the number of nonlinear constraints ncnln gt 0 1dA is the row dimension of the array A 1dA gt 1 1dA gt nclin ldg is the row dimension of the array gCon ldg gt 1 ldg gt ncn1n 1dH is the row dimension of the array Hess 1dH gt n A is an array of dimension 1dA k for some k gt n It contains the matrix A for the linear constraints If nclin 0 A is not referenced In that case A may be dimensioned 1dA 1 with 1dA 1 or it could be any convenient array bl nctotl bu nctotl contain the lower and upper bounds for r x in problem NP To specify a non existent lower bound l oo set b1 j lt infBnd where infBnd is the Infinite Bound whose default value is 102 Similarly a non existent upper bound uj 00 can be any bu j gt infBnd To specify an equality constraint say rj x 8 set b1 j bu j 6 where 6 lt infBnd For the data to be meaningful it is required that b1 j lt bu j for all j funcon funobj are the names of subroutines that calculate the nonlinear constraint func tions f x the objective
114. n x fObj gU0bj nState integer amp mode n nState double precision amp fObj x n g0bj n On entry mode is set by npOpt to indicate which values are to be assigned during the call of funobj If Derivative level 1 or Derivative level 3 then all components of the objective gradient are defined by the user and mode will always have the value 2 If some gradient elements are unspecified npOpt will call funobj with mode 0 1 or 2 e If mode 2 assign f0bj and the known components of g0bj e If mode 1 assign all available components of g0bj fObj is not required e If mode 0 only fObj needs to be assigned g0bj is ignored n is the number of variables i e the dimension of x The actual parameter n will always be the same Fortran variable as that input to npOpt and must not be altered by funobj x n is an array containing the values of the variables x for which fp must be evaluated The array x must not be altered by funobj nState allows the user to save computation time if certain data must be read or calculated only once If nState 1 npOpt is calling funobj for the first time If there are nonlinear constraints the first call to funcon will occur before the first call to funobj On exit mode may be used to indicate that you are unable or unwilling to evaluate the objective function at the current x Similarly for the constraint functions During the linesearch the functions are evaluated at points of the
115. n procedure is having difficulty If e is the relative precision of the machine being used the SQP algorithm will make slow progress if Cond Hz becomes as large as e71 2 108 and will probably fail to find a better solution if Cond Hz reaches e 10 To guard against high values of Cond Hz attention should be given to the scaling of the variables and the constraints In some cases it may be necessary to add upper or lower bounds to certain variables to keep them a reasonable distance from singularities in the nonlinear functions or their derivatives is the Euclidean norm of the vector of penalty parameters used in the augmented Lagrangian merit function not printed if there are no nonlinear constraints The summary line may include additional code characters that indicate what happened during the course of the major iteration 90 SNOPT 7 User s Guide Code Meaning Central differences have been used to compute the unknown components of the objective and constraint gradients A switch to central differences is made if either the line search gives a small step or x is close to being optimal In some cases it may be necessary to re solve the QP subproblem with the central difference gradient and Jacobian During the line search it was necessary to decrease the step in order to obtain a maximum constraint violation conforming to the value of Violation limit The norm wise change in the variables was limited by the value
116. ncw iw leniw rw lenrw contain the required option value 70 SNOPT 7 User s Guide 7 6 Description of the optional parameters The following is an alphabetical list of the options that may appear in the SPECS file and a description of their effect In the description of the options we use the notation of the problem format SparseNP to refer to the objective and constraint functions Backup Basis file 1 Default 0 This is intended as a safeguard against losing the results of a long run Suppose that a NEW BASIS file is being saved every 100 iterations and that SNOPT is about to save such a basis at iteration 2000 It is conceivable that the run may be interrupted during the next few milliseconds in the middle of the save In this case the basis file will be corrupted and the run will have been essentially wasted To eliminate this risk both a NEW BASIS file and a BACKUP BASIS file may be specified The following would be suitable for the above example OLD BASIS file 11 or 0 BACKUP BASIS file 11 NEW BASIS file 12 Save frequency 100 The current basis will then be saved every 100 iterations first on file 12 and then immediately on file 11 If the run is interrupted at iteration 2000 during the save on file 12 there will still be a usable basis on file 11 corresponding to iteration 1900 Note that a NEW BASIS will be saved at the end of a run if it terminates normally but there is no need for a further BACKUP BASIS In t
117. ndedness in nonlinear problems They may not achieve that purpose During a line search fo is evaluated at points of the form x ap where x and p are fixed and a varies if fo exceeds fmax or a exceeds Qmax iterations are terminated with the exit message Problem is unbounded or badly scaled If singularities are present unboundedness in fo x may be manifested by a floating point overflow during the evaluation of fo x ap before the test against fmax can be made Unboundedness in x is best avoided by placing finite upper and lower bounds on the variables Verify level l Default 0 This option refers to finite difference checks on the derivatives computed by the user provided routines Derivatives are checked at the first point that satisfies all bounds and linear constraints l Meaning O Only a cheap test will be performed requiring 2 calls to usrfun for snOptA and 2 calls to funcon and 3 calls to funobj for snOptB 1 Individual gradients will be checked with a more reliable test A key of the form OK or Bad indicates whether or not each component appears to be correct 2 Individual columns of the problem Jacobian will be checked 3 Options 2 and 1 will both occur in that order 1 Derivative checking is disabled Verify level 3 should be specified whenever a new function routine is being developed The Start and Stop keywords may be used to limit the number of nonlinear variables checked Mis
118. neA bl ntm bu ntm pi m amp rc n m ru lenru rw lenrw x n m characterx x amp Start character amp Prob 8 Names nName 8 cu lencu 8 cw lencw 8 All arguments except usrfun are the same as those for the snOptB interface The description of usrfun follows 5 2 Subroutine usrfun This subroutine must calculate the nonlinear problem functions fo a and f x and op tionally their derivatives g x and f x The objective derivatives are stored in the output array g0bj Constraint derivatives are stored column wise in the output array gCon Recall that f x is the top left corner of a larger matrix A that is stored column wise in snOptB s input arrays Acol indA locA see 5 The snOptC interface 51 4 2 and Sections 4 3 4 4 Jacobian elements must be stored in gCon in the same order as the corresponding parts of Acol indA locA For small problems or large dense ones it is convenient to treat the Jacobian as a dense matrix and declare gCon as a two dimensional array gCon which is stored column wise in Fortran It is then simple to compute the Jacobian by rows or by columns For problems with sparse Jacobians it is essential to use a one dimensional array gCon in order to conserve storage Thus funcon should use just one of the declarations double precision gCon nnCon nnJac double precision gCon neJac according to convenience subroutine usrfun amp mode nn0bj nnCon nnJac
119. near problem functions Evaluations needed for the estimation of the derivatives by finite differences are not included nCon is printed as a guide to the amount of work required for the line search Feasible is the value of rowerr the maximum component of the scaled nonlinear con straint residual 7 1 The solution is regarded as acceptably feasible if Feasible is less than the Major feasibility tolerance In this case the entry is con tained in parenthesis 8 Output 89 Optimal If the constraints are linear all iterates are feasible and this entry is not printed is the value of maxgap the maximum complementarity gap 7 2 It is an estimate of the degree of nonoptimality of the reduced costs Both Feasbl and Optimal are small in the neighborhood of a solution MeritFunction is the value of the augmented Lagrangian merit function see 2 2 This L U BSwap ns CondHz Penalty function will decrease at each iteration unless it was necessary to increase the penalty parameters see Section 2 As the solution is approached Merit will converge to the value of the objective at the solution In elastic mode the merit function is a composite function involving the con straint violations weighted by the elastic weight If the constraints are linear this item is labeled Objective the value of the objective function It will decrease monotonically to its optimal value The number of nonzeros representing the basis fa
120. needed 7 Optional parameters 71 Crash option a Default 3 Crash tolerance r Default 0 1 Except on restarts a CRASH procedure is used to select an initial basis from certain rows and columns of the constraint matrix A I The Crash option i determines which rows and columns of A are eligible initially and how many times CRASH is called Columns of I are used to pad the basis where necessary a Meaning 0 The initial basis contains only slack variables B I 1 CRASH is called once looking for a triangular basis in all rows and columns of the matrix A 2 CRASH is called twice if there are nonlinear constraints The first call looks for a triangular basis in linear rows and the iteration proceeds with simplex iterations until the linear constraints are satisfied The Jacobian is then evaluated for the first major iteration and CRASH is called again to find a triangular basis in the nonlinear rows retaining the current basis for linear rows 3 CRASH is called up to three times if there are nonlinear constraints The first two calls treat linear equalities and linear inequalities separately As before the last call treats nonlinear rows before the first major iteration If i gt 1 certain slacks on inequality rows are selected for the basis first If i gt 2 numerical values are used to exclude slacks that are close to a bound CRASH then makes several passes through the columns of A searching for a basis matr
121. ng a statement of the form if nState ge 2 return at the start of the subroutine cu lencu iu leniu ru lenru are the character integer and real arrays of user work space provided to snOptC They may be used to pass information into the function routines and to preserve data between calls In special applications the functions may depend on some of the internal variables stored in snOptC s workspace arrays cw iw rw For example the 8 character prob lem name Prob is stored in cw 51 and the dual variables are stored in rw 1xMul onward where 1xMul iw 316 These will be accessible to usrfun if snOptC is called with parameters cu iu ru the same as cw iw rw If you still require user workspace elements rw 501 maxru and rw maxrw 1 lenru are set aside for this purpose where maxru iw 2 Similarly for workspace in cw and rw See the Total and User workspace options On exit mode may be used to indicate that you are unable or unwilling to evaluate the problem functions at the current x During the linesearch the functions are evaluated at points of the form z k apx after they have already been evaluated satisfactorily at zg At any such a if you set mode to 1 snOptC will evaluate the functions at some point closer to x where they are more likely to be defined If for some reason you wish to terminate solution of the current problem set mode to a negative value other than 1 5 Th
122. ng items are output to the PRINT file when Start Cold and no basis file is loaded They refer to the number of columns that the CRASH procedure selects during several passes through A while searching for a triangular basis matrix Label Description Slacks is the number of slacks selected initially Free cols is the number of free columns in the basis including those whose bounds are rather far apart Preferred is the number of preferred columns in the basis i e hs j 3 for some j lt n It will be a subset of the columns for which hs j 3 was specified Unit is the number of unit columns in the basis Double is the number of columns in the basis containing 2 nonzeros Triangle is the number of triangular columns in the basis with 3 or more nonzeros Pad is the number of slacks used to pad the basis to make it a nonsingular triangle 8 6 EXIT conditions When any solver or auxliliary routine in the SNOPT package terminates a message is printed that summarizes what happened during the run The general form of the output message is SOLVER EXIT e exit condition SOLVER INFO i informational message where e is an integer that labels the particular exit condition and i is one of several al ternative informational messages that elaborate on the exit condition For example solver snOptA may print the message 8 Output 95 SNOPTA EXIT 20 the problem appears to be unbounded SNOPTA INFO 21 unbounded
123. nonbasic at its upper bound LL Make variable Name1 nonbasic at its lower bound UL Make variable Name1 nonbasic at its upper bound SB Make variable Name1 superbasic at the specified Value Note that Name1 may be a column name or a row name but on XL and XU lines Name2 must be a row name In all cases row names indicate the associated slack variable and if Namel is a nonlinear variable then its Value is recorded for possible use in defining the initial Jacobian matrix The key SB is an addition to the standard MPS format to allow for nonbasic solutions Notes on PUNCH data 1 Variables are output in natural order For example on the first XL or XU line Name1 will be the first basic column and Name2 will be the first row whose slack is not basic 2 LL lines are not output for nonbasic variables if the corresponding lower bound value is zero Notes on INSERT data 1 Before an INSERT file is read column variables are made nonbasic at their smallest bound in absolute magnitude and the slack variables are made basic 2 Preferably an INSERT file should be an unmodified PUNCH file from an earlier run on the same problem If some rows have been added to the problem the INSERT file need not be altered The slacks for the new rows will be in the basis 3 Entries will be ignored if Name is already basic or superbasic XL and XU lines will be ignored if Name2 is not basic 4 SB lines may be added before the ENDATA line to specif
124. nonlinear constraints and variables come first A typical invocation of snOptB is call snInit iPrint iSumm call snSpec call snOptB Start m n ne Subroutine snOpt is identical to snOptB and the analogous call provides compatibility with previous versions of SNOPT call snOpt Start m n ne 4 1 Subroutines used by sn0ptB snOptB is accessed via the following routines snTnit Section 1 6 must be called before any other snOptB routines snSpec Section 7 3 may be called to input a SPECS file a list of run time options snSet snSeti snSetr Section 7 4 may be called to specify a single option snGet snGetc snGeti snGetr Section 7 5 may be called to obtain an option s current value funcon funobj Section 4 5 are supplied by the user and called by snOptB They define the constraint functions f x and objective function fo x snOptB snOpt Section 4 4 are the main solvers They are identical snMemB Section 4 10 computes the size of the workspace arrays cw iw rw required for given problem dimensions Intended for Fortran 90 and C drivers that reallocate workspace if necessary The user routines funcon and funobj have a fixed parameter list but may have any conve nient name They are passed to snOptB and snOpt as parameters 4 2 Identifying structure in the objective and constraints Consider the following nonlinear optimization problem with four variables x
125. not be reduced to zero the QP subproblem is declared infeasible SNOPT is then in elastic mode thereafter with only the linearized nonlinear constraints defined to be elastic See the Elastic options Minor print level k Default 1 This controls the amount of output to the PRINT and SUMMARY files during solution of the QP subproblems The value of k has the following effect O No minor iteration output except error messages gt 1 A single line of output each minor iteration controlled by Print frequency and Summary frequency IV 10 Basis factorization statistics generated during the periodic refactorization of the basis see Factorization frequency Statistics for the first factorization each major iteration are controlled by the Major print level New basis file f Default 0 If f gt 0 a basis map will be saved on file f every kth iteration where k is the Save frequency The first line of the file will contain the word Proceeding if the run is still in progress At the end of a run a further basis map will be saved with some other word indicating the final solution status New superbasics limit a Default 99 This option causes early termination of the QP subproblems if the number of free variables has increased significantly since the first feasible point If the number of new superbasics is greater than 7 the nonbasic variables that have not yet moved are frozen and the resulting smaller QP is solved to optimality
126. nt F x is a vector of smooth linear and nonlinear constraint functions F x and F4 x is one of the components of F to be minimized as specified by the input parameter ObjRow The option maximize specifies that Fosj x should be maximized instead of minimized snOptA reorders the variables and constraints so that the problem is in the form SparseNP Ideally the first derivatives gradients of F should be known and coded by the user If only some gradients are known sn0ptA estimates the missing ones with finite differences Note that upper and lower bounds are specified for all variables and functions This form allows full generality in specifying various types of constraint Special values are used to indicate absent bounds l oo or uj 00 for appropriate j Free variables and free constraints free rows are ones that have both bounds infinite Fixed variables and equality constraints have l uj In general the components of F are structured in the sense that they are formed from sums of linear and nonlinear functions of just some of the variables This structure can be exploited by snOptA see Section 3 3 3 1 Subroutines associated with snOptA snOptA is accessed via the following routines snTnit Section 1 6 must be called before any other snOptA routines snSpec Section 7 3 may be called to input a SPECS file a list of run time options snSet snSeti snSetr Section 7 4 may be called to specify a
127. nt in column 2 and another call to estimate both missing elements in column 3 No calls are needed for columns 1 and 4 At times central differences are used rather than forward differences Twice as many calls to funobj and funcon are then needed This is not under the user s control Derivative linesearch Default Nonderivative linesearch At each major iteration a line search is used to improve the merit function A Derivative linesearch uses safeguarded cubic interpolation and requires both function and gradient values to compute estimates of the step az If some analytic derivatives are not provided or a Nonderivative linesearch is specified SNOPT employs a line search based upon safeguarded quadratic interpolation which does not require gradient evaluations A nonderivative line search can be slightly less robust on difficult problems and it is recommended that the default be used if the functions and derivatives can be computed at approximately the same cost If the gradients are very expensive relative to the functions a nonderivative line search may give a significant decrease in computation time If Nonderivative linesearch is selected snOptA signals the evaluation of the line search by calling usrfun with needG 0 Once the line search is completed the problem functions are called again with needF 0 and needG 0 If the potential savings provided by a nonderivative line search are to be realized it is essential that usrfun b
128. of 0 50 3 For nonlinear models the same procedure is used for iterations in which there is only one superbasic variable Cycling can occur only when the current solution is at a vertex of the feasible region Thus zero steps are allowed if there is more than one superbasic variable but otherwise positive steps are enforced Increasing helps reduce the number of slightly infeasible nonbasic variables most of which are eliminated during a resetting procedure However it also diminishes the freedom to choose a large pivot element see Pivot tolerance Factorization frequency k Default 50 At most k basis changes will occur between factorizations of the basis matrix e With linear programs the basis factors are usually updated every iteration The default k is reasonable for typical problems Higher values up to k 100 say may be more efficient on problems that are extremely sparse and well scaled e When the objective function is nonlinear fewer basis updates will occur as an optimum is approached The number of iterations between basis factorizations will therefore increase During these iterations a test is made regularly according to the Check frequency to ensure that the general constraints are satisfied If necessary the basis will be refactorized before the limit of k updates is reached 7 Optional parameters 75 Feasibility tolerance t Default 1 0e 6 see Minor feasibility tolerance Feasible point see Minimiz
129. of its bounds I Infeasible x is basic and is currently violating one of its bounds by more than the Feasibility tolerance N Not precisely optimal x is nonbasic Its reduced gradient is larger than the Major optimality tolerance Note If Scale option gt 0 the tests for assigning A D I N are made on the scaled problem because the keys are then more likely to be meaningful Activity The value of the variable zj Obj Gradient gj the jth component of the gradient of the linear or nonlinear objective function If any x is infeasible gj is the gradient of the sum of infeasibilities Lower limit a the lower bound on zj Upper limit the upper bound on zj Reduced gradnt The reduced gradient dj gj 7 aj where aj is the jth column of the constraint matrix or the jth column of the Jacobian at the start of the final major iteration M J The value m j 104 SNOPT 7 User s Guide 8 8 The SOLUTION file The information in a printed solution Section 8 7 may be output as a SOLUTION file according to the Solution file option which may refer to the PRINT file if so desired Infinite bounds appear as 10 rather than None Other numerical values are output with format 1p e16 6 A SOLUTION file is intended to be read from disk by a self contained program that extracts and saves certain values as required for possible further computation Typically the first 14 records would be ignored Each subsequent record m
130. of the Major step limit If this output occurs repeatedly during later iterations it may be worthwhile increasing the value of Major step limit If SNOPT is not in elastic mode an i signifies that the QP subproblem is infeasible This event triggers the start of nonlinear elastic mode which remains in effect for all subsequent iterations Once in elastic mode the QP subproblems are associated with the elastic problem NP y 4 If SNOPT is already in elastic mode an i indicates that the minimizer of the elastic subproblem does not satisfy the linearized constraints In this case a feasible point for the usual QP subproblem may or may not exist An extra evaluation of the problem functions was needed to define an acceptable positive definite quasi Newton update to the Lagrangian Hessian This modifica tion is only done when there are nonlinear constraints This is the same as M except that it was also necessary to modify the update to include an augmented Lagrangian term No positive definite BFGS update could be found The approximate Hessian is unchanged from the previous iteration The approximate Hessian has been reset by discarding all but the diagonal el ements This reset will be forced periodically by the Hessian frequency and Hessian updates keywords However it may also be necessary to reset an ill conditioned Hessian from time to time The approximate Hessian was reset after ten consecutive major it
131. oint cannot be improved INFO 42 singular basis INFO 43 cannot satisfy the general constraints INFO 44 ill conditioned null space basis Several circumstances may lead to SNOPT not being able to improve on a non optimal point 1 Subroutines usrfun funobj or funcon could be returning accurate function values but inaccurate gradients or vice versa This is the most likely cause Study the comments given for INFO 51 and 52 and do your best to ensure that the coding is correct 2 The function and gradient values could be consistent but their precision could be too low For example accidental use of a real data type when double precision was intended would lead to a relative function precision of about 10 instead of something like 10715 The default Major optimality tolerance of 10 would need to be raised to about 107 for optimality to be declared at a rather suboptimal point Of course it is better to revise the function coding to obtain as much precision as economically possible 3 If function values are obtained from an expensive iterative process they may be ac curate to rather few significant figures and gradients will probably not be available 8 Output 99 One should specify Function precision t Major optimality tolerance vit but even then if t is as large as 107 or 1078 only 5 or 6 significant figures the same exit condition may occur At present the only remedy is to increase the accuracy of th
132. ons limit was reached If the functions are expensive to evaluate it may be desirable to do nothing on the last call The first executable statement could be if Status ge 2 return is n the number of variables as defined in the call to snOpta contains the variables x at which the problem functions are to be calculated The array x must not be altered nF f nF concern the calculation of f z nF is the length of the full vector F x f x Az as defined in the call to snOpta needf indicates if must be assigned during this call of usrfun e If needf 0 f is not required and is ignored e If needf gt 0 the components of f x corresponding to the nonlinear part of F x must be calculated and assigned to f If F x is linear and completely defined by A then the associated value of fi x is ignored and need not be assigned However if F 1 has a nonlinear portion f that happens to be zero at x then it is still necessary to set f a 0 If the linear part A of a nonlinear F x is provided using the snOptA arrays iAFun jAvar A then it must not be computed as part of f x 24 SNOPT 7 User s Guide To simplify the code you may ignore the value of needf and compute f a on every entry to usrfun needf may also be ignored with Derivative linesearch and Derivative option 1 both defaults In this case needf is always 1 and f must always be assigned needG lenG G lenG concern the calculation of the deriv
133. ot printed KA XX kk smaller for more accurate search 2 3 default first basis is essentially triangular until it seems necessary used only during elastic mode or 20m if that is more 10 for large LPs or m if that is more or 3m if that is more NOT ALLOWED IN snOpta ONLY FOR sn0ptA 7 Optional parameters 65 Nonderivative linesearch Function precision Difference interval Central difference interval New superbasics limit Objective row Penalty parameter Proximal point method Reduced Hessian dimension Violation limit Unbounded step size Unbounded objective 3 0e 13 5 5e 7 6 7e 5 99 ObjRow 0 0 1 1000 10 0 1 0e 18 1 0e 15 Hessian approximation Hessian full memory Hessian limited memory Hessian frequency 999999 Hessian updates 20 Hessian flush 999999 Frequencies Check frequency 60 Expand frequency 10000 Factorization frequency 50 Save frequency 100 LU options LU factor tolerance 10 0 LU update tolerance 10 0 LU singularity tolerance 3 2e 11 LU partial pivoting LU rook pivoting LU complete pivoting BASIS files OLD BASIS file 0 NEW BASIS file 0 BACKUP BASIS file 0 INSERT file 0 PUNCH file 0 LOAD file 0 DUMP file 0 SOLUTION file 0 Partitions of cw iw rw Total character workspace lencw Total integer workspace leniw Total real workspace lenrw User character workspace 500 User integer workspace 500 User real workspace 500 Miscellaneous Debug l
134. pper or lower case or a mixture of both Some of the keywords have synonyms and certain abbreviations are allowed as long as there is no ambiguity Blank lines and comments may be used to improve readability A comment begins with an asterisk which may appear anywhere on a line All subsequent characters on the line are ignored It may be useful to include a comment on the first Begin line of the file This line is echoed to the SUMMARY file and appears on the screen in an interactive environment Most of the options described in the next section should be left at their default values for any given model If experimentation is necessary we recommend changing just one option at a time 7 2 SPECS file checklist and defaults The following example SPECS file shows all valid keywords and their default values The keywords are grouped according to the function they perform Some of the default values depend on e the relative precision of the machine being used The values given here correspond to double precision arithmetic on most current machines e 2 22 x 10716 Similar values would apply to any machine having about 15 decimal digits of precision 64 SNOPT 7 User s Guide BEGIN checklist of SPECS file parameters and their default values Printing Major print level Minor print level Print file Summary file Print frequency Summary frequency Solution Suppress options listing System information Problem specif
135. r integer and real storage is needed to solve the problem 3 The snOptA interface 29 To use snMemA the first step is to allocate the work arrays These may be temporary arrays tmpcw tmpiw tmprw say or the snOptA arrays cw iw rw which will be reallocated after the storage limits are known Here we illustrate the use of snMemA using the same arrays for snMemA and snOptA Note that the snMemA arrays are used to store the optional parameters and so any temporary arrays must be copied into the final cw iw rw arrays in order to retain the options The work arrays must have length at least 500 so we define ltmpcw 500 ltmpiw 500 ltmprw 500 As with all SNOPT routines snInit must be called to initialize the optional parameters to their default values call snlnit amp iPrint iSumm cw ltmpcw iw ltmpiw rw ltmprw This installs ltmpcw ltmpiw ltmprw as the default internal upper limits on the snOptA workspace see the description of Total real workspace in Section 7 6 They are used to compute the boundaries of any user defined workspace in cw iw or rw The next step is to call snMemA to obtain mincw miniw minrw as estimates of the storage needed by snOpta call snMemA amp INFO nF n nxname nFname neA neG amp mincw miniw minrw amp cw ltmpcw iw ltmpiw rw ltmprw The output values of mincw miniw minrw may now be used to define the lengths of the snOptA work arrays lencw
136. raints and variables to be entered in arbitrary order and allows all nonlinear functions to be defined in one user routine It may also be used with SnadiOpt 7 which provides gradients by automatic differentiation of the problem functions For efficiency reasons the solver routines require nonlinear variables and constraints to come before linear variables and constraints and they treat nonlinear objective functions separately from nonlinear constraints snOptB the basic interface imposes these distinc tions and was used by all versions of SNOPT prior to Version 6 In some applications the objective and constraint functions share data and computation The snOptC interface allows the functions to be combined in one user routine Finally npOpt is an interface that accepts problem data written in the same format as the dense SQP code NPSOL It permits NPSOL users to upgrade with minimum effort A summary of the SNOPT interfaces follows snOptA Section 3 is recommended for new users of SNOPT The variables and constraints may be coded in any order Nonlinear objective and constraint functions are defined by one user routine May use SnadiOpt to compute gradients snOptB Section 4 is the basic interface to the underlying solver Nonlinear constraints and variables must appear first A nonlinear objective is defined separately from any nonlinear constraints snOptC Section 5 is the same as snOptB except the user combines the nonlinear
137. re in Section 8 6 Finished successfully 1 optimality conditions satisfied 2 feasible point found 3 requested accuracy could not be achieved The problem appears to be infeasible 11 infeasible linear constraints 12 infeasible linear equalities 13 nonlinear infeasibilities minimized 14 infeasibilities minimized The problem appears to be unbounded 21 unbounded objective 22 constraint violation limit reached Resource limit error 31 iteration limit reached 32 major iteration limit reached 33 the superbasics limit is too small Terminated after numerical difficulties 41 current point cannot be improved 42 singular basis 43 cannot satisfy the general constraints 44 illconditioned null space basis Error in the user supplied functions 51 incorrect objective derivatives 52 incorrect constraint derivatives Undefined user supplied functions 61 undefined function at the first feasible point 62 undefined function at the initial point 63 unable to proceed into undefined region 4 The snOptB interface 39 mincw ns User requested termination 72 terminated during constraint evaluation 73 terminated during objective evaluation 74 terminated from monitor routine Insufficient storage allocated 81 work arrays must have at least 500 elements 82 not enough character storage 83 not enough integer storage 84 not enough real storage Input arguments out of range 91 invalid input argument 92 basis file dimen
138. re the same a 5 BS The constraint is not binding s is basic A key is sometimes printed before the State to give some additional information about the state of the slack variable A Alternative optimum possible The slack is nonbasic but its reduced gradient is essentially zero This means that if the slack were allowed to start moving from its current value there would be no change in the objective function The values of the basic and superbasic variables might change giving a genuine alternative solution The values of the dual variables might also change D Degenerate The slack is basic but it is equal to or very close to one of its bounds I Infeasible The slack is basic and is currently violating one of its bounds by more than the Feasibility tolerance N Not precisely optimal The slack is nonbasic Its reduced gradient is larger than the Major optimality tolerance Note If Scale option gt 0 the tests for assigning A D I N are made on the scaled problem because the keys are then more likely to be meaningful Activity The row value afz or f x a x for nonlinear rows y Slack activity The amount by which the row differs from its nearest bound For free rows it is taken to be minus the Activity Lower limit a the lower bound on the row Upper limit 5 the upper bound on the row 8 Output 103 Dual activity The value of the dual variable 7 often called the shadow price or simplex mult
139. regions where the nonlinear functions are likely to be defined However be aware of the Minor feasibility tolerance if the functions have singularities 8 Set mode 1 if the functions are undefined The linesearch will shorten the step and try again 9 Set mode lt 2 if you want snOptB to stop 4 The snOptB interface 41 4 6 Subroutine funcon This subroutine must compute the nonlinear constraint functions f x and optionally their gradients f x where x is the current value of the Jacobian variables x The jth column of the Jacobian matrix f x is the vector Of Ox For small problems or large dense ones it is convenient to treat the Jacobian as a dense matrix and declare gCon as a two dimensional array gCon stored column wise in Fortran It is then simple to compute the Jacobian by rows or by columns For sparse Jacobians it is essential to use a one dimensional array gCon to conserve storage amp amp amp amp amp subroutine funcon mode nnCon nnJac neJac x fCon gCon nState cu lencu iu leniu ru lenru integer lencu leniu lenru mode neJac nnCon nnJac nState iu leniu double precision amp fCon nnCon ru lenru x nnJac character amp cu lencu 8 11 double precision gCon nnCon nnJac Dense Choose ONE of these double precision gCon neJac Sparse On entry mode indicates whether fCon or gCon or both must be assigned during the present cal
140. rs of magnitude larger it may be advisable to reduce the LU factor tolerance to 5 0 4 0 3 0 or 2 0 say but bigger than 1 0 As long as Lmax is not large say 10 0 or less max Amax Umax DUmin gives an estimate of the condition number of B If this is extremely large the basis is nearly singular Slacks are used to replace suspect columns of B and the modified basis is refactored 94 SNOPT 7 User s Guide Ltri is the number of triangular columns of B or Bs at the left of L densel is the number of columns remaining when the density of the basis matrix being factorized reached 0 3 Lmax The actual maximum subdiagonal element in L bounded by Lto1 Akmax The largest nonzero generated at any stage of the LU factorization Values much larger than Amax indicate instability growth The ratio Akmax Amax Values much larger than 100 say indicate instability bump is the size of the bump or block to be factorized nontrivially after the trian gular rows and columns of B or Bs have been removed dense2 is the number of columns remaining when the density of the basis matrix being factorized reached 0 6 The Markowitz pivot strategy searches fewer columns at that stage DUmax The largest diagonal of PUQ DUmin The smallest diagonal of PUQ condU The ratio DUmax DUmin which estimates the condition number of U and of B if Ltol is less than 100 say 8 5 Crash statistics If Major print level gt 10 the followi
141. rw subroutine snGetc buffer cvalue Errors cw lencw iw leniw rw lenrw subroutine snGeti buffer ivalue Errors cw lencw iw leniw rw lenrw subroutine snGetr buffer rvalue Errors cw lencw iw leniw rw lenrw character buffer integer Errors ivalue lencw leniw lenrw iw leniw character cvalue 8 cw lencw 8 double precision amp rvalue rw lenrw On entry buffer is a string to be decoded Restriction len buffer lt 72 Errors is the cumulative number of errors so it should be 0 before the first call in a group of calls to option getting routines On exit snGet cvalue ivalue rvalue Errors is 1 if the option contained in buffer has been set otherwise 0 Use snGet to find if a particular optional parameter has been set For example if i snGet Hessian limited memory Errors then 7 will be 1 if SNOPT is using a limited memory approximate Hessian is a string associated with the keyword in buffer Use snGetc to obtain the names associated with an MPS file For example for the name of the bounds section use call snGetc Bounds MyBounds Errors is an integer value associated with the keyword in buffer Example call snGeti Iterations limit itnlim Errors is a real value associated with the keyword in buffer Example call snGetr LU factor tol factol Errors is the number of errors encountered so far cw le
142. s calling your subroutine for the last time You may wish to perform some additional computation on the final solution Note again that the last call to funcon will occur before the last call to funobj In general the last call is made with nState 2 INFO 10 where INFO is the integer returned by snOptB see p 38 In particular if nState 2 the current x is optimal if nState 3 the problem appears to be infeasible if nState 4 the problem appears to be unbounded if nState 5 an iterations limit was reached If the functions are expensive to evaluate it may be desirable to do nothing on the last call The first executable statement could be if Status ge 2 return cu lencu iu leniu ru lenru are the character integer and real arrays of user work space provided to snOptB They may be used to pass information into the function routines and to preserve data between calls In special applications the functions may depend on some of the internal variables stored in snOptB s workspace arrays cw iw rw For example the 8 character prob lem name Prob is stored in cw 51 and the dual variables are stored in rw 1xMul onward where 1xMul iw 316 These will be accessible to both funcon and funobj if snOptB is called with parameters cu iu ru the same as cw iw rw If you still require user workspace elements rw 501 maxru and rw maxrw 1 lenru are set aside for this purpose where maxru iw 2 Similarly for wor
143. s have the following meaning hs j State of variable j Usual value of x j 0 nonbasic bl j 1 nonbasic bu j 2 superbasic Between b1 j and bu j 3 basic Between b1 j and bu j Basic and superbasic variables may be outside their bounds by as much as the Minor feasibility tolerance Note that if scaling is specified the feasibility tolerance applies to the variables of the scaled problem In this case the variables of the original problem may be as much as 0 1 outside their bounds but this is unlikely unless the problem is very badly scaled Check the Primal infeasibility printed after the EXIT message Very occasionally some nonbasic variables may be outside their bounds by as much as the Minor feasibility tolerance and there may be some nonbasics for which x j lies strictly between its bounds 38 SNOPT 7 User s Guide If nInf gt 0 some basic and superbasic variables may be outside their bounds by an arbitrary amount bounded by sInf if scaling was not used x n m is the final variables and slacks x s pi m is the vector of dual variables 7 a set of Lagrange multipliers for the general constraints rc n m is a vector of reduced costs g A J z where g is the gradient of the objective if x is feasible or the gradient of the Phase 1 objective otherwise The last m entries are 7 INFO reports the result of the call to snOptB Here is a summary of possible values Further details a
144. s provided via OLD BASIS INSERT or LOAD in the SPECS file is the same as start 0 but is more meaningful when a basis file is given ll p Start il N Start Warm start means that a basis is already defined in xstate and Fstate probably from an earlier call nF is the number of problem functions in F x including the objective function if any and the linear and nonlinear constraints Simple upper and lower bounds on x can be defined using the parameters xLow and xUpp defined below and should not be included in F nF gt 0 This is the dimension of the problem vector F Since F includes the objective if any and all the general linear and nonlinear constraints F must include at least one row for the problem to be meaningful 14 SNOPT 7 User s Guide n is n the number of variables This is the number of columns of G and A n gt 0 iAfun lenA jAvar lenA A lenA define the coordinates i j and values A of the lenA neA nonzero elements of the linear part A of the function F x f x Az In particular the neA triples iAfun k jAvar k A k define the row and col umn indices iAfun k and j jAvar k of the element Aj A k The coordinates may define the elements of A in any order is the dimension of the coordinate arrays iAfun jAvar and A that hold i j Aij lenA gt 1 is the number of nonzeros in A such that F x f x Ax neA gt 0 iGfun lenG j
145. see more significant digits in the printed solution it is sometimes useful to make f refer to the PRINT file i e make it the same as the number specified by Print file Start Objective Check at Column k Default 1 Start Constraint Check at Column k Default 1 Stop Objective Check at Column l Default nj Stop Constraint Check at Column l Default nY These keywords are not allowed in the snOptA interface If Verify level gt 0 they may be used to abbreviate the verification of individual derivative elements computed by subroutines funobj funcon and usrfun For example e If the first 100 objective gradients appeared to be correct in an earlier run and if you have just found a bug in funobj that ought to fix up the 101 th component then you might as well specify Start Objective Check at Column 101 Similarly for columns of the Jacobian 7 Optional parameters 85 e If the first 100 variables occur nonlinearly in the constraints and the remaining vari ables are nonlinear only in the objective then funobj must set the first 100 components of g to zero but these hardly need to be verified The above option would again be appropriate Summary file f Default 6 Summary frequency k Default 100 If f gt 0 and Minor print level gt 0 a line of the QP iteration log will be output to file f every kth minor iteration Superbasics limit a Default n 1 This places a limit on the storage allocated for superbasic variab
146. set to 2 superbasic If the number of superbasic variables has already reached the Superbasics limit then variable j will be made nonbasic at its current value even if it is not equal to one of its bounds sqdat2 ITN 0 Optimal Soln NINF 0 OBJ 2 043665038075E 06 OBJ RHS RNG BND M 8 N 7 SB 1 033023303133003 5 4 33461578293999E 02 0 Figure 3 Format of NEW and OLD BASIS files 108 SNOPT 7 User s Guide 9 2 PUNCH and INSERT files These files provide compatibility with commercial mathematical programming systems The PUNCH file from a previous run may be used as an INSERT file for a later run on the same problem It may also be possible to modify the INSERT file and or problem and still obtain a useful advanced basis The standard MPS format has been slightly generalized to allow the saving and reloading of nonbasic solutions It is illustrated in Figure 4 Apart from the first and last line each entry has the following form Columns 2 3 5 12 15 22 25 36 Contents Key Namel Name Value The various keys are best defined in terms of the action they cause on input It is assumed that the basis is initially set to be the full set of slack variables and that column variables are initially at their smallest bound in absolute magnitude or zero for free variables Key Action to be taken during INSERT XL Make variable Name1 basic and slack Name2 nonbasic at its lower bound XU Make variable Name basic and slack Name2
147. sign 44 SNOPT 7 User s Guide m 4 n 4 nnCon 2 nn0bj 3 nnJac 2 i0bj 4 Subroutine funobj works with the nonlinear objective variables 11 12 83 Since 23 occurs only linearly in the constraints we have placed it after the Jacobian variables x x2 For interest we test mode to economize on gradient evaluations even though they are cheap here Note that Nonderivative linesearch would have to be specified otherwise all entries would have mode 2 subroutine funobj amp mode nn0bj amp x fObj gObj nState amp cu lencu iu leniu ru lenru integer amp mode nn0bj nState lencu leniu lenru iu leniu double precision amp f0bj x nn0bj g0bj nn0bj ru lenru character amp cu lencu 8 double precision sum sum x 1 x 2 x 3 if mode eq 0 or mode eq 2 then f0bj sum sum end if if mode eq 1 or mode eq 2 then sum 2 0d 0 sum g0bj 1 sum g0bj 2 sum g0bj 3 sum end if end subroutine funobj 4 The snOptB interface 45 Subroutine funcon involves only x1 22 First we treat the Jacobian as a dense matriz In Fortran it is preferable to access two dimensional arrays column wise as shown Each column of gCon contains two elements even though one of them is zero The Acol indA locA data structure must include these elements as well as other entries belonging to the linear constraints Since funcon is called before funobj we test nState for t
148. sing derivatives are not checked so they result in no overhead 7 Optional parameters 87 Violation limit T Default 10 This keyword defines an absolute limit on the magnitude of the maximum constraint viola tion after the line search On completion of the line search the new iterate 27 1 satisfies the condition vil k 1 lt Tmax 1 vi xo 7 3 where xo is the point at which the nonlinear constraints are first evaluated and v x is the ith nonlinear constraint violation v x max 0 l f x f x ui The effect of this violation limit is to restrict the iterates to lie in an expanded feasible region whose size depends on the magnitude of 7 This makes it possible to keep the iterates within a region where the objective is expected to be well defined and bounded below If the objective is bounded below for all values of the variables then 7 may be any large positive value 88 SNOPT 7 User s Guide 8 Output Subroutine snInit specifies unit numbers for the PRINT and SUMMARY files described in this section The files can be redirected with the Print file and Summary file options or suppressed 8 1 The PRINT file If Print file gt 0 the following information is output to the PRINT file during the solution process All printed lines are less than 131 characters e A listing of the SPECS file if any e A listing of the options that were or could have been set in the SPECS file e An estimate of the wor
149. single option snGet snGetc snGeti snGetr Section 7 5 may be called to obtain an option s current value snJac Section 3 5 may be called to find the coordinate stucture of the Jacobian usrfun Section 3 6 is supplied by the user and called by snOptA to define the functions F a and ideally their gradients snOptA Section 3 4 is the main solver snMemA Section 3 8 computes the size of the workspace arrays cw iw rw required for given problem dimensions Intended for Fortran 90 and C drivers that reallocate workspace if necessary The user routine usrfun has a fixed parameter list but may have any convenient name It is passed to snOptA as a parameter 10 SNOPT 7 User s Guide 3 2 Getting Started Consider the following nonlinear optimization problem with two variables z 11 12 and three inequality constraints minimize x2 T11 T2 subject to x 4x2 lt 4 3 1 x 2 23 5 T gt 0 In the format of problem NPA we have l lt lt uy and lp lt F x lt up as follows Tea 00 T2 00 l lt x 4a lt 4 Up oo 21 2 22 5 Let G x be the Jacobian matrix of partial derivatives so that G 1 0F 1 0x gives the gradients of F 1 as the ith row of G is 0 1 F x x da and G a 211 8x2 x 2 r2 2 11 2 2x2 Now we must provide snOptA the following information 1 The index Objrow of the objective row Here ObjRow 1
150. sions do not match this problem System error 141 wrong number of basic variables 142 error in basis package miniw minrw say how much character integer and real storage is needed to solve the problem If snOptB terminates because of insufficient storage INFO 82 83 or 84 these values may be used to define better values of lencw leniw or lenrw If INFO 82 the work array cw lencw was too small snOptB may be called again with lencw mincw If INFO 83 or 84 the work arrays iw leniw or rw lenrw are too small snOptB may be called again with leniw or lenrw suitably larger than miniw or minrw The bigger the better since it is not certain how much storage the basis factorization needs is the final number of superbasic variables nInf sInf give the number and the sum of the infeasibilities of constraints that lie outside Obj their bounds by more than the Feasibility tolerance If the linear constraints are infeasible x minimizes the sum of the infeasibilities of the linear constraints subject to the upper and lower bounds being satisfied In this case nInf gives the number of components of A x lying outside their upper or lower bounds The nonlinear constraints are not evaluated Otherwise x minimizes the sum of the infeasibilities of the nonlinear constraints subject to the linear constraints and upper and lower bounds being satisfied In this case nInf gives the number of components of f x lying outside their
151. straint derivatives is significantly different from an estimate obtained by forward differencing the vector F a Follow the advice given above for the objective function trying to ensure that the arrays F and G are being set correctly in usrfun or funcon 100 SNOPT 7 User s Guide EXIT 60 Undefined user supplied functions INFO 61 undefined function at the first feasible point INFO 62 undefined function at the initial point INFO 63 unable to proceed into undefined region If the user assigns the value Status 1 in any of the routines usrfun funobj or funcon computing the problem functions then the function is considered to be undefined at that point SNOPT attempts to evaluate the problem functions closer to a point at which the functions have already been computed INFO 61 and 62 indicate that SNOPT is unable to proceed because the functions are undefined at the initial point or first feasible point INFO 63 implies that repeated attempts to move into a region where the functions are not defined resulted in the change in variables being unacceptably small EXIT 70 User requested termination INFO 71 terminated during function evaluation INFO 72 terminated during constraint evaluation INFO 73 terminated during objective evaluation INFO 74 terminated from monitor routine These exits occur when Status lt 1 is set during some call to the user defined routines SNOPT assumes that you want the problem
152. teger amp neG Obj Out double precision amp sum x1 x3 x4 Se ek Stet A A ea oe SEES Out 15 Output unit number Obj 1 Objective row of F Print something on the first and last entry if Status eq 1 then First if Out gt 0 write Out a This is problem Toy else if Status ge 2 then Last if Out gt 0 write Out a Finished problem Toy return end if x1 x 1 x3 x 3 x4 x 4 sum x1 x3 x4 if meedF gt 0 then f 0bj 3 0d0 x1 sum 2 2 x3 2 x4 2 3 Linear constraint omitted 4 x4 4 end if neG 0 if meedG gt 0 then neG neG 1 G neG 2 0d0 sum 3 0d0 11 iGfun neG Obj Not used but included for clarity 1 jGvar neG 1 Not used neG neG 1 3 The snOptA interface 27 G neG iGfun neG jGvar neG neG G neG iGfun neG jGvar neG neG G neG iGfun neG jGvar neG neG G neG iGfun neG jGvar neG neG G neG iGfun neG jGvar neG end if 2 0d0 sum Obj 3 neG 1 2 0d0 sum Obj 4 neG 1 2 0d0 x3 2 3 neG 1 2 0d0 x4 2 4 neG 1 4 0d0 x4 3 4 4 end subroutine usrfun 28 SNOPT 7 User s Guide 3 8 Subroutine snMemA This routine estimates the size of the workspace arrays cw iw rw required to solve an optimization problem of given dimensions snMemA is not strictly needed in f77 because all workspace must be defined explicitly in the driver progr
153. to be abandoned forthwith If the following exits occur during the first basis factorization the primal and dual variables x and pi will have their original input values BASIS files will be saved if requested but certain values in the printed solution will not be meaningful EXIT 80 Insufficient storage allocated INFO 81 work arrays must have at least 500 elements INFO 82 not enough character storage INFO 83 not enough integer storage INFO 84 not enough real storage SNOPT cannot start to solve a problem unless the char int and real work arrays are at least 500 elements If the main character integer or real storage arrays cw iw and rw are not large enough for the current problem the routine declaring cw iw and rw should be recompiled with a larger dimensions for those arrays The new values should also be assigned to lencw leniw and lenrw An estimate of the additional storage required is given in messages preceding the exit If rw is not large enough be sure that the Hessian dimension is not unreasonably large EXIT 90 Input arguments out of range INFO 91 invalid input argument INFO 92 basis file dimensions do not match this problem This exit occurs if some data associated with the problem is out of range If INFO 91 at least one input argument for the interface is invalid The printed output provides more detail about which argument s must be modified If INFO 92 an
154. to be neither convex nor concave Our advice is always to specify a starting point that is as good an estimate as possible and to include reasonable upper and lower bounds on all variables in order to confine the solution to the specific region of interest We expect modelers to know something about their problem and to make use of that knowledge as they themselves know best One other caution about Optimality conditions satisfied Some of the variables or slacks may lie outside their bounds more than desired especially if scaling was requested Some information concerning the run can be obtained from the short summary given at the end of the print and summary files Here is an example from the problem Toy discussed in Section 3 2 SNOPTA EXIT 0 finished successfully SNOPTA INFO 1 optimality conditions satisfied Problem name Toy1 No of iterations 7 Objective value 1 0000000008E 00 No of major iterations 7 Linear objective 0 0000000000E 00 Penalty parameter 3 253E 02 Nonlinear objective 1 0000000008E 00 No of calls to funobj 9 No of calls to funcon 9 No of degenerate steps O Percentage 0 00 Max x 2 1 0E 00 Max pi 1 1 2E 01 Max Primal infeas 0 0 0E 00 Max Dual infeas 2 8 0E 10 Nonlinear constraint violn 6 4E 09 Max Primal infeas refers to the largest bound infeasibility and which variable is in volved If it is too large consider restarting with a smaller Minor feasibility tolerance say 10 times smaller and perhaps Scale
155. to estimate them by finite differences using a call to usrfun for each variable x for which some 0f 1x 0x needs to be estimated However this reduces the reliability of the optimization algorithm and it can be very expensive if there are many such variables xj As a compromise snOptA allows you to code as many gradients as you like This option is implemented as follows Just before the function routine is called each element of the derivative array G is initialized to a specific value On exit any element retaining that value must be estimated by finite differences Some rules of thumb follow 1 For maximum reliability compute all gradients 2 If the gradients are expensive to compute specify Nonderivative linesearch and use the value of the input parameter needG to avoid computing them on certain entries There is no need to compute gradients if needG 0 on entry to usrfun 3 If not all gradients are known you must specify Derivative option 0 You should still compute as many gradients as you can It often happens that some of them are constant or even zero 4 Again if the known gradients are expensive don t compute them if needG 0 on entry to usrfun 5 Use the input parameter Status to test for special actions on the first or last entries 6 While usrfun is being developed use the Verify option to check the computation of gradients that are supposedly known 7 usrfun is not called until the linear constra
156. to restart the run if necessary or to provide a good starting point for some closely related problem Three formats are available for saving basis descriptions They are invoked by SPECS lines of the following form New Basis file 10 Backup file 11 Punch file 20 Dump file 30 The file numbers may be whatever is convenient or zero for files that are not wanted NEW BASIS and BACKUP BASIS files are saved in that order every kth iteration where k is the Save frequency NEW BASIS PUNCH and DUMP files are saved at the end of a run in that order They may be re loaded at the start of a subsequent run by specifying SPECS lines of the following form Old Basis file 10 Insert file 20 Load file 30 Only one such file will actually be loaded If more than one positive file number is specified the order of precedence is as shown If no BASIS files are specified one of the Crash options takes effect Figures 3 5 illustrate the data formats used for BASIS files 80 character fixed length records are suitable in all cases 36 character records would be adequate for PUNCH and DUMP files The files shown correspond to the optimal solution for the economic growth model MANNE The problem has 10 nonlinear constraints 10 linear constraints and 30 variables Selected column numbers are included to define significant data fields 9 1 NEW and OLD BASIS files We sometimes call these files basis maps They contain the most compact representation of
157. tolerance t Default 1 0e 6 SNOPT tries to ensure that all variables eventually satisfy their upper and lower bounds to within the tolerance t This includes slack variables Hence general linear constraints should also be satisfied to within t Feasibility with respect to nonlinear constraints is judged by the Major feasibility tolerance not by t e If the bounds and linear constraints cannot be satisfied to within t the problem is declared infeasible Let sInf be the corresponding sum of infeasibilities If sInf is quite small it may be appropriate to raise t by a factor of 10 or 100 Otherwise some error in the data should be suspected e Nonlinear functions will be evaluated only at points that satisfy the bounds and linear constraints If there are regions where a function is undefined every attempt should be made to eliminate these regions from the problem For example if f x z log xg it is essential to place lower bounds on both variables If t 1 0e 6 the bounds z gt 107 and x2 gt 1074 might be appropriate The log singularity is more serious In general keep x as far away from singularities as possible 7 Optional parameters 81 e If Scale option gt 1 feasibility is defined in terms of the scaled problem since it is then more likely to be meaningful e In reality SNOPT uses t as a feasibility tolerance for satisfying the bounds on x and s in each QP subproblem If the sum of infeasibilities can
158. torize The number of rows in B or Bs ea The number of columns in B or Bs Preceded by or gt respectively The number of nonzero elements in B or Bg The largest nonzero in B or Bs The percentage nonzero density of B or Bs The average Markowitz merit count for the elements chosen to be the diagonals of PUQ Each merit count is defined to be c 1 r 1 where c and r are the number of nonzeros in the column and row containing the element at the time it is selected to be the next diagonal Merit is the average of n such quantities It gives an indication of how much work was required to preserve sparsity during the factorization The number of nonzeros in L The number of times the data structure holding the partially factored matrix needed to be compressed to recover unused storage Ideally this number should be zero If it is more than 3 or 4 the amount of workspace available to SNOPT should be increased for efficiency The percentage increase in the number of nonzeros in L and U relative to the number of nonzeros in B or Bs is the number of triangular rows of B or Bs at the top of U The number of nonzeros in U The maximum subdiagonal element allowed in L This is the specified LU factor tolerance or a smaller value that is currently being used for greater stability The maximum nonzero element in U The ratio Umax Amax which ideally should not be substantially larger than 10 0 or 100 0 If it is orde
159. trix A and m vector b are defined as pa a oa te Gey A 0 then the QP subproblem can be written as minimize q x subject to Ar s b I lt j lt u 2 1 8 Ss where q x is a quadratic approximation to a modified Lagrangian function 8 2 Description of the SQP method 7 2 3 Minor iterations Solving the QP subproblem is itself an iterative procedure The iterations of the QP solver are the minor iterations of the SQP method At each minor iteration the constraints Ax s b are conceptually partitioned into the form BI 57 Nay b where the basis matrix B is square and nonsingular The elements of s s and xy are called the basic superbasic and nonbasic variables respectively they are a permutation of the elements of x and s At a QP solution the basic and superbasic variables will lie somewhere between their bounds while the nonbasic variables will normally be equal to one of their bounds At each iteration s is regarded as a set of independent variables that are free to move in any desired direction namely one that will improve the value of the QP objective or the sum of infeasibilities The basic variables are then adjusted in order to ensure that x s continues to satisfy Ax s b The number of superbasic variables ns say therefore indicates the number of degrees of freedom remaining after the constraints have been satisfied In broad terms ns is a measure of how nonlinear the problem is
160. ts are dense i e they do not have a significant number of elements that are identically zero A typical invocation of npOpt would be call npInit iPrint iSumm call npSpec call npOpt n nclin ncnln where npSpec reads a file of optional parameter definitions Figure 1 illustrates the feasible region for the jth pair of constraints 0 lt rj x lt uj The quantity 6 is the optional parameter feasibility tolerance which can be set by the user see Section 7 The constraints l lt r lt uj are considered satisfied if rj lies in Regions 2 3 or 4 and inactive if r lies in Region 3 The constraint r gt is considered active in Region 2 and violated in Region 1 Similarly r lt uj is active in Region 4 and violated in Region 5 For equality constraints 4 uz Regions 2 and 4 are the same and Region 3 is empty O 18 U NON Pisa b Uj Tj x Figure 1 Illustration of the constraints 4 lt rj x lt uj The bounds and uj are considered satisfied if r x lies in Regions 2 3 or 4 where 6 is the feasibility tolerance The constraints r x gt 4j and r x lt uj are both considered inactive if rj x lies in Region 3 6 The npOpt interface 55 6 1 Subroutines used by npOpt npOpt is accessed via the following routines npInit Section 1 6 Must be called before any other npOpt routines npSpec Section 7 3 May be called to input a
161. tting its bounds to be bl n 1 infBnd and bu n 1 infBnd where infBnd is typically 1 0e 20 see the next paragraph b1 n m bu n m contains the lower and upper bounds l and u on the variables and slacks x s The first n entries of bl bu hs and x refer to the variables x The last m entries refer to the slacks s To specify a non existent lower bound l oo set bl j lt infBnd where infBnd is the Infinite Bound whose default value is 102 To specify a non existent upper bound uj 00 set bu j gt infBnd To make the th constraint an equality constraint say si 5 where 8 lt infBna set bl n i bu n i PB To fix the jth variable say x 6 where 8 lt infBnd set b1 7 bu j 2 For the data to be meaningful it is required that b1 j7 lt bu j for all j Names nName sometimes contains 8 character names for the variables and constraints If nName 1 Names is not used The printed solution will use generic names for the columns and row If nName n m Names j should contain the 8 character name of the jth variable j 1 n m If j n i the jth variable is the ith row hs n m sometimes contains a set of initial states for each variable x or for each variable and slack a s See the following discussion of x x n m sometimes contains a set of initial values for x or x s 1 If start Cold or Basis file and a BASIS file of some sort is to be input an OLD
162. ty Stanford CA 1986 Maintaining LU factors of a general sparse matriz Linear Algebra Appl 88 89 1987 pp 239 270 A practical anti cycling procedure for linearly constrained optimization Math Program 45 1989 pp 437 474 Some theoretical properties of an augmented Lagrangian merit function in Advances in Opti mization and Parallel Computing P M Pardalos ed North Holland North Holland 1992 pp 101 128 P E GILL W MURRAY AND M H WRIGHT Practical Optimization Academic Press London and New York 1981 B A MURTAGH AND M A SAUNDERS Large scale linearly constrained optimization Math Program 14 1978 pp 41 72 A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints Math Program 16 1982 pp 84 117 MINOS 5 4 User s Guide Report SOL 83 20R Department of Operations Research Stanford University Stanford CA Revised 1995 Acknowledgement We are grateful to Alan Brown of the Numerical Algorithms Group Ltd for helpful comments on the documentation for SNOPT We also thank Tom Aird Arne Drud David Gay Rocky Nelson and Ulf Ringertz for their feedback while running SNOPT on numerous examples
163. u v w 2 minimize u v w 3w 52 subject to v vu w 2 vt z 4 2u 4v gt 0 with bounds w gt 0 z gt 0 This problem has several characteristics that can be exploited e The objective function is the sum of a nonlinear function of the three variables x u v w and a linear function of potentially all variables x e The first two constraints are nonlinear and the third constraint is linear 32 SNOPT 7 User s Guide e Each nonlinear constraint involves the sum of a nonlinear function of the two variables x u v and a linear function of the remaining variables y w z The nonlinear terms are defined by user written subroutines funobj and funcon which involve only x and x the appropriate subsets of variables For the objective we define the function fo u v w u v w to include only the nonlinear terms The variables x u v w are known as nonlinear objective variables and their dimension is specified by the snOptB input parameter nn0bj 3 here The linear part 3w 5z of the objective is treated as an additional linear constraint whose row index is specified by the input parameter i0bj Thus the full objective has the form folz dfr where x is the first nnObj variables fo x is defined by subroutine funobj and d is a constant vector that forms row i0bj of the full Jacobian matrix Choosing i0bj 4 we think of the problem as minimize u v w s4
164. uld set g j 0 0 for j 1 nnJac It should then set as many remaining gradients as possible preferably all 34 SNOPT 7 User s Guide 4 4 Subroutine sn0ptB Problem SparseNP is solved by a call to subroutine snOptB whose parameters are defined here Note that most machines use double precision declarations as shown but some machines use real The same applies to the user routines funcon and funobj subroutine snOptB amp Start m n neA nName amp nnCon nn0bj nnJac amp i0bj ObjAdd Prob amp funcon funobj amp Acol indA locA bl bu Names amp hs x pi rc amp INFO mincw miniw minrw amp ns ninf sInf Obj amp cu lencu iu leniu ru lenru amp cw lencw iw leniw rw lenrw external amp funcon funobj integer amp INFO i0bj lencu lencw leniu leniw lenru lenrw m amp mincw miniw minrw n neA nInf nName nnCon nnJac nn0bj amp nS hs n m indA neA iu leniu iw leniw locA n 1 double precision amp Obj ObjAdd sInf Acol neA bl ntm bu ntm pi m amp rc n m ru lenru rw lenrw x n m character amp Start character amp Prob 8 cu lencu 8 cw lencw 8 Names nName 8 On entry start is a character string that specifies how a starting basis and certain other items are to be obtained Cold requests that the CRASH procedure be used to choose an initial basis unless a basis file is provided via OLD BASIS INSERT or LOAD in the
165. upper or lower bounds is the final value of the nonlinear part of the objective function If nInf 0 Obj is the nonlinear objective if any If nInf gt 0 but the linear constraints are feasible then Obj is the nonlinear objective If nInf gt 0 and the linear constraints are infeasible Obj is zero Note that Obj does not include contributions from the constant term ObjAdd or the objective row if there is one The final value of the objective being optimized is ObjAdd x n i0bj Obj where i0bj is the index of the objective row in A 40 SNOPT 7 User s Guide 4 5 User supplied routines required by snOptB The user must provide subroutines to define the nonlinear parts of the objective function and nonlinear constraints They are passed to snOptB as external parameters funobj and funcon A dummy subroutine must be provided if the objective or constraints are purely linear Be careful when coding the call to snOptB the parameters are ordered alphabetically as funcon funobj The first call to each function routine is also in that order In general these subroutines should return all function and gradient values on every entry except perhaps the last This provides maximum reliability and corresponds to the default setting Derivative level 3 In practice it is often convenient not to code gradients snOptB is able to estimate gradients by finite differences by making a call to funcon or funobj for each variable xj whose parti
166. vector i0bj 0 Otherwise this row must come after any nonlinear rows so that nnCon lt i0bj lt m is a constant that will be added to the objective for printing purposes Typically ObjAdd 0 0d 0 is an 8 character name for the problem Prob is used in the printed solution and in some routines that output BASIS files A blank name may be used is the name of a subroutine that calculates the vector of nonlinear constraint func tions f x and optionally its Jacobian for a specified vector x the first nnJac elements of x funcon must be declared external in the routine that calls snOptB For a detailed description of funcon see Section 4 6 is the name of a subroutine that calculates the objective function fo x and op tionally its gradient for a specified vector x the first nnObj elements of x funobj must be declared external in the routine that calls snOptB For a detailed description of funobj see Section 4 7 Acol neA indA neA locA n 1 define the nonzero elements of the constraint matrix A 4 2 including the Jacobian matrix associated with nonlinear constraints The nonzeros are stored column wise A pair of values Acol k indA k contains a matrix element and its corresponding row index and the array locA is a set of pointers to the beginning of each column of A within Acol and indA Thus for j 1 n the entries of column j are held in Acol k 1 and their corresponding row indices are in indA k 1
167. with large numbers of degrees of freedom Reduced Hessian dimension i Default min 1000 n 1 same as Hessian dimension This specifies that an r x r triangular matrix R is to be available for use by the Cholesky QP solver to define the reduced Hessian according to RTR ZTH Z Save frequency k Default 100 If a NEW BASIS file has been specified a basis map describing the current solution will be saved on the appropriate file every kth iteration A BACKUP BASIS file will also be saved if specified Scale option i Default 2 LP or 1 NLP Scale tolerance r Default 0 9 Scale Print Three scale options are available as follows a Meaning 0 No scaling This is recommended if it is known that x and the constraint matrix and Jacobian never have very large elements say larger than 1000 1 Linear constraints and variables are scaled by an iterative procedure that attempts to make the matrix coefficients as close as possible to 1 0 see Fourer 6 This will sometimes improve the performance of the solution procedures 84 SNOPT 7 User s Guide 2 All constraints and variables are scaled by the iterative procedure Also an additional scaling is performed that takes into account columns of A I that are fixed or have positive lower bounds or negative upper bounds If nonlinear constraints are present the scales depend on the Jacobian at the first point that satisfies the linear constraints Scale option 2 should t
168. within 6 The npOpt interface 59 Region 1 2 3 4 5 2 4 istate j 2 1 0 2 1 3 Printed solution LL FR UL EQ Figure 2 Labels used in the printed solution for the regions of Figure 1 3 Region 2 Region 4 The bounds are equal and the equality constraint is satisfied to within These values of istate are labeled in the printed solution according to the table in Figure 2 fCon is an array of dimension at least ncnln If ncnln 0 fCon is not accessed and may then be declared to be of dimension 1 or the actual parameter may be any convenient array If ncnln gt 0 fCon contains the values of the nonlinear constraint functions f x i 1 nen1n at the final iterate gCon contains the Jacobian matrix of the nonlinear constraints at the final iterate i e gCon i j contains the partial derivative of the ith constraint function with respect to the jth variable i 1 ncnln j 1 n See the discussion of gCon under funcon in Section 6 5 cMul contains the QP multipliers from the last QP subproblem cMul j should be non negative if istate j 1 and non positive if istate j 2 fObj is the value of the objective fo x at the final iterate g0bj n contains the objective gradient or its finite difference approximation at the final iterate Hess 1dH contains information about H the Hessian of the Lagrangian Hess is an estimate of the Hessian of the Lagrangian at x
169. workspace to solve the problem 83 Not enough integer workspace to solve the problem 84 Not enough real workspace to solve the problem miniw minrw say how much character integer and real storage is needed to build the arrays i j Aij and i j Gij If snJac terminates because of insufficient stor age INFO 82 83 or 84 these values may be used to define better values of lencw leniw or lenrw If INFO 82 the work array cw lencw was too small snJac may be called again with lencw mincw If INFO 83 or 84 the work arrays iw leniw or rw lenrw are too small snJac may be called again with leniw or lenrw suitably larger than miniw or minrw 22 SNOPT 7 User s Guide 3 6 Subroutine usrfun Your own version of subroutine usrfun is where you define the nonlinear portion f x of the problem functions F x f x Az along with its gradient elements G Ofi z Ox This subroutine is passed to snOptA as the external parameter usrfun A dummy subroutine is needed even if f x 0 and all functions are linear In general usrfun should return all function and gradient values on every entry except perhaps the last This provides maximum reliability and corresponds to the default setting Derivative option 1 The elements of G x are stored in the array G 1 lenG in the order specified by snOptA s input arrays iGFun and jGvar see Section 3 7 In practice it is often convenient not to code gradients snOpta is able
170. x contains the final estimate of the solution 6 3 User supplied subroutines for npOpt The user must provide subroutines that define the objective function and nonlinear con straints The objective function is defined by subroutine funobj and the nonlinear con straints are defined by subroutine funcon On every call these subroutines must return appropriate values of the objective and nonlinear constraints in fObj and fCon The user should also provide the available partial derivatives Any unspecified derivatives are ap proximated by finite differences see Section 7 for a discussion of the optional parameter Derivative level Just before either funobj or funcon is called each element of the cur rent gradient array g or gCon is initialized to a special value On exit any element that retains the given value is estimated by finite differences For maximum reliability it is preferable for the user to provide all partial derivatives see Chapter 8 of Gill Murray and Wright 13 for a detailed discussion If all gradients cannot be provided it is similarly advisable to provide as many as possible While developing the subroutines funobj and funcon the Verify parameter see Section 7 should be used to check the calculation of any known gradients 60 SNOPT 7 User s Guide 6 4 Subroutine funobj This subroutine must calculate the objective function fo x and optionally the gradient g a subroutine funobj amp mode
171. y additional superbasic columns or slacks 5 An SB line will not alter the status of Namel if the Superbasics limit has been reached However the associated Value will be retained 9 Basis Files 109 9 3 DUMP and LOAD files These files are similar to PUNCH and INSERT files but they record solution information in a manner that is more direct and more easily modified In particular no distinction is made between columns and slacks Apart from the first and last line each entry has the form Columns 2 3 5 12 25 36 Contents Key Name Value as illustrated in Figure 5 The keys LL UL BS and SB mean Lower Limit Upper Limit Basic and Superbasic respectively Notes on DUMP data 1 A line is output for every variable columns followed by slacks 2 Nonbasic variables between their bounds will be output with key LL and their current value Notes on LOAD data 1 Before a LOAD file is read all columns and slacks are made nonbasic at their smallest bound in absolute magnitude The basis is initially empty 2 BS causes Name to become basic SB causes Name to become superbasic at the specified Value gt LL or UL cause Name to be nonbasic at the specified Value 5 An entry will be ignored if Name is already basic or superbasic Thus only the first BS or SB line takes effect for any given Name 6 An SB line will not alter the status of Name if the Superbasics limit has been reached but the associated Value will b

User's Guide for SNOPT Version 7, A Fortran

Contents

Download Pdf Manuals

Related Search

Related Contents