SOL MINOS: Difference between revisions

From TomWiki
Jump to navigationJump to search
No edit summary
Line 228: Line 228:


''minosTL ''solves nonlinear optimization problems defined as
''minosTL ''solves nonlinear optimization problems defined as
<math>
\begin{array}{ll}
\min\limits_{x} & f(x) \\
&  \\
s/t & \begin{array}{lcccl}
x_{L} & \leq  & x    & \leq & x_{U}, \\
b_{L} & \leq  & A x  & \leq & b_{U} \\
c_{L} & \leq  & c(x) & \leq & c_{U} \\
\end{array}
\end{array}
</math>
where <math>x, x_L, x_U \in \MATHSET{R}^n</math>, <math>f(x) \in \MATHSET{R}</math>, <math>A
\in \MATHSET{R}^{m_1 \times n}</math>, <math>b_L,b_U \in \MATHSET{R}^{m_1}</math>
and <math>c_L,c(x),c_U \in \MATHSET{R}^{m_2}</math>.


===Calling  Syntax===
===Calling  Syntax===

Revision as of 12:54, 20 August 2011

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 subsection Using TOMLAB for information on how to use MINOS with TOMLAB.

Purpose

minos solves nonlinear optimization problems defined as


where Failed to parse (unknown function "\MATHSET"): {\displaystyle x \in \MATHSET{R}^n} , Failed to parse (unknown function "\MATHSET"): {\displaystyle f(x) \in \MATHSET{R}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle A \in \MATHSET{R}^{m_1 \times n}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle b_L,b_U \in \MATHSET{R}^{n+m_1+m_2}} and Failed to parse (unknown function "\MATHSET"): {\displaystyle c(x) \in \MATHSET{R}^{m_2}} .

or quadratic optimization problems defined as


where Failed to parse (unknown function "\MATHSET"): {\displaystyle c, x \in \MATHSET{R}^n} , Failed to parse (unknown function "\MATHSET"): {\displaystyle F \in \MATHSET{R}^{n \times n}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle A \in \MATHSET{R}^{m_1 \times n}} , and Failed to parse (unknown function "\MATHSET"): {\displaystyle b_L,b_U \in \MATHSET{R}^{m_1}} .

The full input matrix A has three parts A = [d/dx g(x); A; c'];

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: The matrix dcS MUST be a SPARSE MATLAB matrix. Do dcS = sparse(dcS); after dcS has been computed.

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

Description of Inputs

The following fields are used:

Input Description
H Matrix n x n in a quadratic programming (QP) problem. DENSE or SPARSE. Leave empty if LP, or NLP problem.
A Constraint matrix, m x n SPARSE (nonlinear, linear and objective) m > 0 always!!! Define dummy constraint for unconstrained problems.
bl Lower bounds on (x,g(x),Ax,c').
bu Upper bounds on (x,g(x),Ax,c').

NOTE! The bl and bu values for the last nonlinear constraint c must have reverse signs and be put in each other places: If cL <= c(x) <= cU , then bl = -cU and bu = -cL . This is because the bounds acts as the constraints on the slack variables for the nonlinear constraints.

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 minos, then Prob is the standard TOMLAB problem structure, otherwise the user should set:

Prob.P = ProblemNumber, where ProblemNumber is some integer.

If the problem is a LP or QP problem (H defined), the user does not have to specify anything else 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).

MINOS 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, or one of the Assign-routines like conAssign.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 TOMLAB.
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 char- acters = 500.
PriLev Printing level in the minos m-file and minos 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 MINOS 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:

Output Description
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).

Basic and superbasic variables may be outside their bounds by as much as the 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 Feasibility tolerance, and there may be some nonbasics for which xn(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 Lagrangian multipliers (dual solution vector) (m x 1 vector)
rc Vector of reduced costs, g - ( A I )Tp, where g is the gradient of the objective function if xn is feasible, or the gradient of the Phase-1 objective otherwise. If ninf = 0, the last m entries are -p. Reduced costs vector is of n+m length.
Inform Result of MINOS run.

0 Optimal solution found.

1 The problem is infeasible.

2 The problem is unbounded (or badly scaled).

3 Too many iterations.

4 Apparent stall. The solution has not changed for a large number of iterations (e.g. 1000).

5 The Superbasics limit is too small.

6 User requested termination (by returning bad value).

7 Gradient seems to be giving incorrect derivatives.

8 Jacobian seems to be giving incorrect derivatives.

9 The current point cannot be improved.

10 Numerical error in trying to satisfy the linear constraints (or the linearized nonlinear constraints). The basis is very ill-conditioned.

11 Cannot find a superbasic to replace a basic variable.

12 Basis factorization requested twice in a row. Should probably be treated as inform = 9.

13 Near-optimal solution found. Should probably be treated as inform = 9.

20 Not enough storage for the basis factorization.

21 Error in basis package.

22 The basis is singular after several attempts to factorize it (and add slacks where necessary).

30 An OLD BASIS file had dimensions that did not match the current problem.

32 System error. Wrong number of basic variables.

40 Fatal errors in the MPS file.

41 Not enough storage to read the MPS file.

42 Not enough storage to solve the problem.

nS # of superbasics.
nInf Number of infeasibilities.
sInf Sum of infeasibilities.
Obj Objective function value at optimum.
iwCount Number of iterations (major and minor), function and constraint calls.
gObj Gradient of the nonlinear objective.
fCon Nonlinear constraint vector.
gCon Gradient vector (non-zeros) of the nonlinear constraint vector.

Using TOMLAB

Purpose

minosTL solves nonlinear optimization problems defined as

where Failed to parse (unknown function "\MATHSET"): {\displaystyle x, x_L, x_U \in \MATHSET{R}^n} , Failed to parse (unknown function "\MATHSET"): {\displaystyle f(x) \in \MATHSET{R}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle A \in \MATHSET{R}^{m_1 \times n}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle b_L,b_U \in \MATHSET{R}^{m_1}} and Failed to parse (unknown function "\MATHSET"): {\displaystyle c_L,c(x),c_U \in \MATHSET{R}^{m_2}} .

Calling Syntax

Using the driver routine tomRun :

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

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.moremem Add more memory if MINOS stops with not enough storage message. 1E6 is 10MB of memory. Default n+m1+m2 (number of variables + linear + nonlin- ear constraints).
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 in SOL Using the SOL Solvers in TOMLAB.

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 minos.m (similar to TOMLAB).
Inform Result of MINOS run.

0 Optimal solution found.

1 The problem is infeasible.

2 The problem is unbounded (or badly scaled).

3 Too many iterations.

4 Apparent stall. The solution has not changed for a large number of iterations (e.g. 1000).

5 The Superbasics limit is too small.

6 User requested termination (by returning bad value).

7 Gradient seems to be giving incorrect derivatives.

8 Jacobian seems to be giving incorrect derivatives.

9 The current point cannot be improved.

10 Numerical error in trying to satisfy the linear constraints (or the linearized nonlinear constraints). The basis is very ill-conditioned.

11 Cannot find a superbasic to replace a basic variable.

12 Basis factorization requested twice in a row. Should probably be treated as inform = 9.

13 Near-optimal solution found. Should probably be treated as inform = 9.

20 Not enough storage for the basis factorization.

21 Error in basis package.

22 The basis is singular after several attempts to factorize it (and add slacks where necessary).

30 An OLD BASIS file had dimensions that did not match the current problem.

32 System error. Wrong number of basic variables.

40 Fatal errors in the MPS file.

41 Not enough storage to read the MPS file.

42 Not enough storage to solve the problem.

rc Vector of reduced costs, g-(AI)Tp, where g is the gradient of the objective function if xn is feasible, or the gradient of the Phase-1 objective otherwise. If ninf = 0, the last m entries are -p. Reduced costs vector is of n+m length.
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 (minos).
SolverAlgorithm Description of the solver.
SOL.xs Solution and slack variables.
SOL.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).

Basic and superbasic variables may be outside their bounds by as much as the 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 Feasibility tolerance, and there may be some nonbasics for which xn(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 # of superbasics.
SOL.nInf # of infeasibilities.
SOL.sInf Sum of infeasibilities.

optPar

Description

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

Definition: nnL = max(nnObj,nnJac))

Description of Inputs

<figtable id="tab:optPar">

The following fields are used:
# SPECS keyword text Lower Default Upper Comment
Printing
1. PRINT LEVEL 0 0 11111 JFLXB: Jac, fCon, lambda, x, B=LU stats
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 PARAMETERS 0 0 1 1 = True
Convergence Tolerances
9. ROW TOLERANCE > 0 1E-6
10. OPTIMALITY TOLERANCE > 0 max(1E - 6, (10epsR )0.5 ) = 1.73E-6
11. FEASIBILITY 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
Scaling
18. SCALE OPTION

See Section 6.2 for more information.

0 1 or 2 2 2 if LP,1 if NLP
19. SCALE TOLERANCE > 0 0.9 < 1
20. SCALE PRINT 0 0 1 1 = True
21. CRASH TOLERANCE 0 0.1 < 1
Other Tolerances
22. LINESEARCH TOLERANCE > 0 0.1 < 1
LU I
23. LU FACTORIZATION TOLERANCE 1 100 or 5 100 if LP
24. LU UPDATE TOLERANCE 1 10 or 5 10 if LP
25. LU SWAP TOLERANCE > 0 1.22E-4 eps^1/4
26. LU SINGULARITY TOLERANCE > 0 3.25E-11 eps^0.67
LP or LC subproblems
27. PIVOT TOLERANCE > 0 3.25E-11 eps^0.67
28. CRASH OPTION 0 3 3 0,1,2,3
29. WEIGHT ON LINEAR OBJECTIVE 0.0 0.0 during Phase 1
30. ITERATIONS LIMIT

m3=1 if length(Prob.QP.c) > 0, otherwise m3=0.

TOMLAB default: max(10000,3(m+m3) + 10nnL).

0 3(m+m3) + 10nnL
SLC method
32. MAXIMIZE 0 0 1 1=maximize
33. LAGRANGIAN 0 1 1 1=YES, 0=NO
34. PENALTY PARAMETER 0.0 1.0
35. MAJOR ITERATIONS LIMIT > 0 50
36. MINOR ITERATIONS LIMIT > 0 40
37. MAJOR DAMPING PARAMETER > 0 2.0
38. MINOR DAMPING PARAMETER > 0 2.0
39. DERIVATIVE LEVEL

Is always set by minosTL dependent on Prob.ConsDiff, Prob.NumDiff.

0 3 3 0,1,2,3
40. RADIUS OF CONVERGENCE 0.0 0.01
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.69E-5 eps0.8/3
44. COMPLETION 0 1 LC, 0 1

NC

0=PARTIAL

1=FULL

45. UNBOUNDED STEP SIZE > 0 1E10
46. UNBOUNDED OBJECTIVE > 0 1E20
Hessian approximation
47. HESSIAN DIMENSION 1 50 1+nnL
48. SUPERBASICS LIMIT 1 50 1+nnL

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

If n <= 5000: max(50, n + 1)

If n > 5000: max(500, n + 200 - 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 MINOS. 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

0 0 3 0=partial

1=complete

2=rook

Additional parameters
67. AIJ TOLERANCE

Elements |a(i, j)| < AI J TOLERANCE are set as 0

0 1E-10
70. SUBSPACE

Convergence tolerance in current subspace before consider moving off another constraint.

> 0 0.5 1 Subspace tolerance

</figtable>