SOL SNOPT

From TomWiki
Revision as of 10:18, 9 December 2011 by Elias (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Notice.png

This page is part of the SOL Manual. See SOL.

Direct Solver Call

A direct solver call is not recommended unless the user is 100 % sure that no other solvers will be used for the problem. Please refer to #Using TOMLAB for information on how to use SNOPT with TOMLAB.

Purpose

snopt solves sparse nonlinear optimization problems defined as


where , , , and .

Calling Syntax

The file 'funfdf.m' must be defined and contain: function [mode, f, g] = funfdf(x, Prob, mode, nstate) to compute the objective function f and the gradient g at the point x.

The file 'funcdc.m' must be defined and contain: function [mode ,c ,dcS] = funcdc(x, Prob, mode, nstate) to compute the nonlinear constraint value c and the constraint Jacobian dcS for the nonlinear constraints at the point x.

Note that Matlab has dynamic sparse matrix handling and Fortran has static handling. The returned vector of constraint gradient values must always match the pattern of nonzeros as defined in the call to snopt. One approach for a general solution to this is given in the Tomlab callback routine nlp cdcS.m, which calls the user defined 'funcdc' function.


The fields Prob.P and Prob.ConsPattern must be set, see below.

[hs, xs, pi, rc, Inform, nS, nInf, sInf, Obj, iwCount, gObj, fCon, gCon] = snopt( A, bl, bu, 
nnCon, nnObj, nnJac, Prob, iObj,  optPar, Warm, hs, xs, pi, nS, SpecsFile, PrintFile,  SummFile, PriLev,  ObjAdd,  moremem, Prob- Name);

Description of Inputs

The following fields are used:
A Constraint matrix, m x n SPARSE (A consists of nonlinear part, linear part and one row for the linear objective). m > 0 always.
bl Lower bounds on (x,g(x),Ax,c').
bu Upper bounds on (x,g(x),Ax,c'). nnCon Number of nonlinear constraints.
nnObj Number of nonlinear objective variables.
nnJac Number of nonlinear Jacobian variables.
Prob Must be a structure. No check is made in the MEX interface!

If TOMLAB calls snopt, then Prob is the standard TOMLAB problem struc- ture, otherwise the user should set:

Prob.P = ProblemNumber, where ProblemNumber is some integer. Prob.ConsPattern = []; or as the nonzero pattern for the constraint Jacobian as Prob.ConsPattern = ConsPattern;

ConsPattern is a nnCon x n zero-one sparse or dense matrix, where 0 values indicate zeros in the constraint Jacobian and ones indicate values that might be non-zero.

If the problem is a LP or QP problem (H defined), then the user does not have to specify anything more in the structure.

For a general nonlinear objective, or nonlinear constraints names of two user written routines must be given:

funfdf, actual name stored in Prob.FUNCS.fg, with syntax [mode, f, g] = funfdf(x, Prob, mode, nstate)

funcdc, actual name stored in Prob.FUNCS.cdc, with syntax [mode, c, dcS] = funcdc(x, Prob, mode, nstate)

SNOPT is calling the TOMLAB routines nlp fg.m and nlp cdcS.m in the call- back, and they call funfdf and funcdc, respectively.

If these fields in Prob are empty (Prob.FUNCS.fg, Prob.FUNCS.cdc), the TOMLAB callback routines calls the usual function routines. Then the Prob struct should be normally defined, and the fields Prob.FUNCS.f, Prob.FUNCS.g, Prob.FUNCS.c, Prob.FUNCS.dc be set in the normal way (e.g. by the routine mFiles.m).

If the mode parameter is 0, funfdf should return f, otherwise both f and the gradient vector g. If the mode parameter is 0, funcdc should return c, otherwise both c and dcS. Note that each row in dcS corresponds to a constraint, and that dcS must be a SPARSE matrix.

The user could also write his own versions of the routines nlp fg.m and nlp cdcS.m and put them before in the path.

iObj Says which row of A is a free row containing a linear objective vector c. If there is no such vector, iObj = 0. Otherwise, this row must come after any nonlinear rows, so that nnCon <= iObj <= m.
optPar Vector with optimization parameters overriding defaults and the optionally specified SPECS file. If using only default options, set optPar as an empty matrix.
Warm Flag, if true: warm start. Default cold start (if empty). If 'Warm Start' xS, nS and hs must be supplied with correct values.
hs Basis status of variables + constraints (n+m x 1 vector). State of vari- ables: 0=nonbasic (on bl), 1=nonbasic (on bu) 2=superbasic (between bounds), 3=basic (between bounds).
xs Initial vector, optionally including m slacks at the end. If warm start, full xs must be supplied.
pi Lagrangian multipliers for the nnCon nonlinear constraints. If empty, set as 0.
nS # of superbasics. Only used if calling again with a Warm Start.
SpecsFile Name of the SPECS input parameter file, see SNOPT User's Guide.
PrintFile Name of the Print file. Name includes the path, maximal number of characters = 500.
SummFile Name of the Summary file. Name includes the path, maximal number of characters = 500.
PriLev Printing level in the snopt m-file and snopt MEX-interface.

= 0 Silent

= 1 Summary information

= 2 More detailed information

ObjAdd Constant added to the objective for printing purposes, typically 0.
moremem Add extra memory for the sparse LU, might speed up the optimization. 1E6 is 10MB of memory. If empty, set as 0.
ProbName Name of the problem. ¡=100 characters are used in the MEX interface. In the SNOPT solver the first 8 characters are used in the printed solution and in some routines that output BASIS files. Blank is OK.

Description of Outputs

The following fields are used:
hs Basis status of variables + constraints (n+m x 1 vector). State of variables:

0=nonbasic (on bl), 1=nonbasic (on bu), 2=superbasic (between bounds),

3=basic (between bounds).

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.

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 xs(j) lies strictly between its bounds.

If nInf > 0, some basic and superbasic variables may be outside their bounds by an arbitrary amount (bounded by sInf if scaling was not used).

xs Solution vector (n+m by 1) with n decision variable values together with the m slack variables.
pi The vector of dual variables p (a set of Lagrange multipliers for the general constraints). (m x 1 vector).
rc Vector of reduced costs, g -( A -I )T p, where g is the gradient of the objective if xs is feasible (or the gradient of the Phase-1 objective otherwise). The last m entries are p. The vector is n+m. If nInf=0, last m == pi.
Inform Result of SNOPT run.

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 ill-conditioned 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

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 dimensions do not match this problem

System error

141 wrong number of basic variables

142 error in basis package

nS The final number of superbasic variables.
nInf Gives the number and the sum (next parameter) of the infeasibilities of constraints that lie outside their bounds by more than the Feasibility tolerance.

If the linear constraints are infeasible, xs 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 AL x lying outside their upper or lower bounds. The nonlinear constraints are not evaluated.

Otherwise, xs minimizes the sum of the infeasibilities of the nonlinear con- straints 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.

sInf Sum of infeasibilities. See nInf above.
Obj Objective function value at optimum.
iwCount Number of iterations minor (iwCount(1)) and major (iwCount(2)), function (iwCount(3:6)) and constraint (iwCount(7:10)) calls.
gObj Gradient of the nonlinear objective.
fCon Nonlinear constraint vector.
gCon Gradient vector (non-zeros) of the nonlinear constraint vector.

Using TOMLAB

Purpose

snoptTL solves nonlinear optimization problems defined as

where , , , and .

Calling Syntax

Using the driver routine tomRun :

Prob = ''o''Assign( ... );
Result = tomRun('snopt', Prob ... );

Description of Inputs

Prob, The following fields are used:
x_L, x_U Bounds on variables.
b_L, b_U Bounds on linear constraints.
c_L, c_U Bounds on nonlinear constraints.
A Linear constraint matrix.
QP.c Linear coefficients in objective function.
PriLevOpt Print level.
WarmStart If true, use warm start, otherwise cold start.
SOL.xs Solution and slacks from previous run.
SOL.hs State for solution and slacks from previous run.
SOL.nS Number of superbasics from previous run.
SOL.hElastic Defines which variables are elastic in elastic mode. hElastic(j):

0 = variable j is non-elastic and cannot be infeasible.

1 = variable j can violate its lower bound.

2 = variable j can violate its upper bound.

3 = variable j can violate either its lower or upper bound.

SOL.moremem Add more memory if SNOPT stops with not enough storage message. 1E6 is 10MB of memory. Default 0.
SOL.SpecsFile Name of user defined SPECS file, read BEFORE optPar() is used.
SOL.PrintFile Name of SOL Print file. Amount and type of printing determined by SPECS parameters or optPar parameters.
SOL.SummFile Name of SOL Summary File.
SOL.optPar Elements > -999 takes precedence over corresponding TOMLAB params. See Table 50.

Description of Outputs

Result, The following fields are used:
Result The structure with results (see ResultDef.m).
f_k Function value at optimum.
x_k Solution vector.
x_0 Initial solution vector.
g_k Gradient of the function.
c_k Nonlinear constraint residuals.
cJac Nonlinear constraint gradients.
xState State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bState State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
cState State of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
v_k Lagrangian multipliers (for bounds + dual solution vector).
ExitFlag Exit status from snoptTL.m (similar to TOMLAB).
Inform Result of SNOPT run.

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 ill-conditioned 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

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 dimensions do not match this problem

System error

141 wrong number of basic variables

142 error in basis package

rc Vector of reduced costs, g -( A -I )T p, where
g is the gradient of the objective if xs is feasible (or the gradient of the Phase-1 objective otherwise). The last m entries are p. The vector is n+m. If nInf=0, last m == pi.
Iter Number of iterations.
FuncEv Number of function evaluations. GradEv Number of gradient evaluations. ConstrEv Number of constraint evaluations.
QP.B Basis vector in TOMLAB QP standard.
MinorIter Number of minor iterations.
Solver Name of the solver (snopt).
SolverAlgorithm Description of the solver.
SOL.xs Solution vector (n+m by 1) with n decision variable values together with the m slack variables.
SOL.hs Basis status of variables + constraints (n+m x 1 vector). State of variables:

0=nonbasic (on bl), 1=nonbasic (on bu), 2=superbasic (between bounds),

3=basic (between bounds).

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.

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 xs(j) lies strictly between its bounds.

If nInf > 0, some basic and superbasic variables may be outside their bounds by an arbitrary amount (bounded by sInf if scaling was not used).

SOL.nS The final number of superbasic variables.
SOL.nInf Gives the number and the sum (next parameter) of the infeasibilities of constraints that lie outside their bounds by more than the Feasibility tolerance.

If the linear constraints are infeasible, xs 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 AL x lying outside their upper or lower bounds. The nonlinear constraints are not evaluated.

Otherwise, xs minimizes the sum of the infeasibilities of the nonlinear con- straints 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.

SOL.sInf Sum of infeasibilities. See nInf above.

optPar

Description

Use missing value (-999 or less), when no change of parameter setting is wanted. The default value will then be used by SNOPT, if not the value is altered in the SPECS file (input SpecsFile).

Definition: nnL = max(nnObj,nnJac)) - Used in #38 and #47.

Description of Inputs

The following fields are used:
# SPECS keyword text Lower Default Upper Comment
The SQP method I - Printing
1. MAJOR PRINT LEVEL 0 1 11111
QP subproblems I - Printing
2. MINOR PRINT LEVEL 0 1 10 0, 1 or 10
Frequencies I
5. PRINT FREQUENCY 0 100
6. SUMMARY FREQUENCY 0 100
7. SOLUTION YES/NO 0 1 1 1 = YES; 0 = NO
8. SUPPRESS OPTIONS LISTING

Also called SUPPRESS PARAMETERS

0 0 1 1 = True
The SQP Method II - Convergence Tolerances
9. MAJOR FEASIBILITY TOLERANCE > 0 1E-6
Nonlinear constraints I
10. MAJOR OPTIMALITY TOLERANCE

eps_R == optPar(41), Default relative function precision eps_R gives (10 * epsR )0 .5 = 1.73E - 6.

> 0 max(2E - 6, (10epsR )0.5 ) = 1.73E-6
QP subproblems II - Convergence Tolerances
11. MINOR FEASIBILITY TOLERANCE

Feasibility tolerance on linear constraints.

> 0 1E-6
12. MINOR OPTIMALITY TOLERANCE > 0 1E-6
Derivative checking
13. VERIFY LEVEL -1 -1 3 -1,0,1,2,3
14. START OBJECTIVE CHECK AT COL 0 1 nnObj
15. STOP OBJECTIVE CHECK AT COL 0 nnObj nnObj
16. START CONSTRAINT CHECK AT COL 0 1 nnJac
17. STOP CONSTRAINT CHECK AT COL 0 nnJac nnJac
QP subproblems III
18. SCALE OPTION 0 0 or 2 2 2 if LP,0 if NLP
19. SCALE TOLERANCE > 0 0.9 < 1
20. SCALE PRINT 0 0 1 1 = True
21. CRASH TOLERANCE 0 0.1 < 1
The SQP Method III
22. LINESEARCH TOLERANCE > 0 0.9 < 1
LU I
23. LU FACTORIZATION TOLERANCE 1 100/3.99 100 if LP
24. LU UPDATE TOLERANCE 1 10/3.99 10 if LP
25. LU SWAP TOLERANCE > 0 1.22E-4 eps( 1/4)
26. LU SINGULARITY TOLERANCE > 0 3.25E-11 eps0.67
QP subproblems IV
27. PIVOT TOLERANCE > 0 3.25E-11 eps( 0.67)
28. CRASH OPTION 0 3 3 0,1,2,3
29. ELASTIC WEIGHT 0 10000.0
30. ITERATIONS LIMIT 0 10000 or 20m, if more
Maximal sum of minor iterations
31. PARTIAL PRICE 0 10 or 1 10 for LP
The SQP Method IV
32. MAXIMIZE 0 0 1 1=maximize
33. FEASIBLE POINT 0 0 1 1=feasible pnt
Nonlinear constraints I
34. VIOLATION LIMIT > 0 1e6
The SQP Method V
35. MAJOR ITERATIONS LIMIT > 0 max(1000, 3 * max(n, m))
Maximal number of major iterations
36. MINOR ITERATIONS LIMIT > 0 500
Maximal number of minor iterations, i.e. in the solution of QP or simplex
37. MAJOR STEP LIMIT > 0 2
Hessian Approximation I
38. HESSIAN FREQUENCY > 0 99999999
The SQP Method VI
39. DERIVATIVE LEVEL 0 3 3 0,1,2,3
40. DERIVATIVE LINESEARCH

0 is quadratic - gives quadratic, without gradient values

1 is cubic - gives cubic, always using gradient values

Default: 0 if numerical derivatives, otherwise 1

0 1 1 0=NONDERIVATIVE
41. FUNCTION PRECISION >0 3.0E-13 eps0.8=epsR
42. DIFFERENCE INTERVAL >0 5.48E-7 eps0.4
43. CENTRAL DIFFERENCE INTERVAL >0 6.70E-5 eps0.8/3
44. PROXIMAL POINT METHOD

Minimize the 1-norm (or 2-norm) of ||</nowiki<(x-x<sub>0</sub><nowiki>|| to find an initial point that is feasible subject to simple bounds and linear contraints.

1 1 2 1,2
45. UNBOUNDED STEP SIZE >0 1E20
46. UNBOUNDED OBJECTIVE >0 1E15
Hessian Approximation II
47. HESSIAN FULL MEMORY

or HESSIAN LIMITED MEMORY

0 1 1 =1 if nnL <= 75 =0

if nnL > 75

The SQP Method VII
48. SUPERBASICS LIMIT

TOMLAB extension (to avoid termination with Superbasics Limit too small):

Set = n + 1 if n - size(A, 1) - length(cL ) > 450 and n <= 5000

If n > 5000: max(500, n - size(A, 1) - length(cL ))

Avoid setting REDUCED HESSIAN (number of columns in reduced Hessian).

It will then be set to the same value as the SUPERBASICS LIMIT by SNOPT.

> 0 max(500,n+1)
Hessian Approximation III
49. HESSIAN UPDATES

Maximum number of QN (Quasi-Newton) updates.

If HESSIAN FULL MEMORY, default is 99999999, otherwise 20.

> 0 20
50. HESSIAN FLUSH > 0 99999999
Frequencies II
51. CHECK FREQUENCY > 0 60
52. EXPAND FREQUENCY > 0 10000
53. FACTORIZATION FREQUENCY > 0 50
LU II
63. LU PARTIAL PIVOTING

or LU COMPLETE PIVOTING

or LU ROOK PIVOTING

or LU DIAGONAL PIVOTING

0 0 3 0=partial

1=complete

2=rook

3=diagonal

The SQP Method VIII
64. PENALTY PARAMETER

Initial penalty parameter.

>= 0 0.0
QP subproblems V
65. NEW SUPERBASICS

Also MINOR SUPERBASICS. Maximal number of new superbasics per major iteration.

> 0 99
66. QPSOLVER CHOLESKY

or QPSOLVER CG

or QPSOLVER QN

0 0 2 0=Cholesky

1=CG

2=Quasi-Newton CG

Conjugate-Gradient QP solver
67. CG TOLERANCE > 0 1e - 2
68. CG ITERATIONS > 0 100 Max number of CG iters
69. QPSOLVER CHOLESKY

also called QG PRECONDITIONING. Default 1 if QPSOLVER QN.

0 0 1 QN preconditioned CG
70. SUBSPACE

Quasi-Newton QP rg tolerance.

0 0.1 1 Subspace tolerance
The SQP Method IX
71. HESSIAN DIMENSION

also called REDUCED HESSIAN. Number of columns in Reduced Hessian.

> 0 min(2000, nnL+1) =1 if LP problem

(n upper limit)