SOL SQOPT

From TomWiki
Revision as of 11:19, 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 SQOPT with TOMLAB.

Purpose

sqopt solves dense quadratic optimization problems defined as


where , , , and .

Calling Syntax

The full input matrix A has two parts A = [A; d']; The position of the row d' is iObj. iObj=0 means no linear part in A.

NOTE: There are two ways to give the linear objective: either explicit as vector c or as part of the sparse matrix A, as d (or both ways).

[xs, hs, pi, rc, Inform, nS, nInf, sInf, Obj, iwCount] = sqopt( A, bl, bu, H, c, hElast, 
iObj, optPar, Warm, hs, xs, nS, SpecsFile, PrintFile,  SummFile, ObjAdd, moremem, ProbName, 
Prob);

Description of Inputs

The following fields are used:
A Constraint matrix, m x n (SPARSE).
bl Lower bounds on (x,Ax,d').
bu Upper bounds on (x,Ax,d').
H Quadratic matrix, n x n, SPARSE or DENSE, empty if LP problem. If H is a string, H should be the name of a function routine, e.g if H = 'HxComp' then the function routine:

function Hx = HxComp(x, nState, Prob) should compute H * x. The user must define this routine. nState == 1 if calling for the first time, otherwise 0. Third argument, the Prob structure, should only be used if calling SQOPT with the additional input parameter Prob, see below.

Tomlab implements this callback to the predefined Matlab function HxFunc.m, using the call if Prob.SOL.callback == 1.

c Linear objective.
hElast Defines which bounds are elastic in elastic mode. hElast(j):

0 = variable j 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.

iObj Says which row of A is a free row containing a linear objective vector d. If there is no such vector, iObj = 0.
optPar Vector with optimization parameters overriding defaults and the optionally specified SPECS file. Set empty if only using default parameters.
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 variables:

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

xs Initial x vector (nx1), optionally including m slacks at the end. If Warm start, full n+m vector xs must be supplied.
nS # of superbasics. Used if a Warm Start, otherwise set to 0.
SpecsFile Name of the SPECS input parameter file.
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.
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 to 0.
ProbName Name of the problem. ¡=100 characters are used in the MEX interface. In the SQOPT solver the first 8 characters are used in the printed solution and in some routines that output BASIS files. Blank is OK.
Prob Sending the Prob structure is optional, only of use if sending H as a function string, see input H.

Description of Outputs

The following fields are used:
xs Solution vector (n+m by 1) with n decision variable values together with the m slack variables.
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 value of the optional parameter 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 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).

pi Lagrangian multipliers (dual solution vector) (m x 1 vector).
rc A 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.
Inform Result of SQOPT run.

0 finished successfully

1 optimality conditions satisfied

2 feasible point found

4 weak QP minimizer

10 the problem appears to be infeasible

11 infeasible linear constraints

12 infeasible linear equalities

14 infeasibilities minimized

20 the problem appears to be unbounded

21 unbounded objective

30 resource limit error

31 iteration limit reached

33 the superbasics limit is too small

40 terminated after numerical difficulties

42 singular basis

43 cannot satisfy the general constraints

44 ill-conditioned null-space basis

50 error in the user-supplied functions

53 the QP Hessian is indefinite

70 user requested termination

73 terminated during QP objective evaluation

74 terminated from monitor routine

80 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

90 input arguments out of range

91 invalid input argument

92 basis file dimensions do not match this problem

93 the QP Hessian is indefinite

140 system error

141 wrong number of basic variables

142 error in basis package

nS # of superbasics.
nInf Number of infeasibilities.
sInf Sum of infeasibilities.
Obj Objective function value at optimum.
iwCount Number of QP iterations in iwCount(1), number of Hx products.

Using TOMLAB

Purpose

sqoptTL solves nonlinear optimization problems defined as


where , , , and .

Calling Syntax

Using the driver routine tomRun :

Prob = ''o''Assign( ... );
Result = tomRun('sqopt', Prob ... );
or
Prob = ProbCheck( ... ); 
Result = sqoptTL(Prob);

Call Prob = oAssign( ... ) or Prob=ProbDef; to define the Prob for the second option.

Description of Inputs

Prob, The following fields are used:
x_L, x_U Bounds on variables.
b_L, b_U Bounds on linear constraints.
A Linear constraint matrix.
QP.c Linear coefficients in objective function.
QP.F Quadratic matrix of size nnObj x nnObj. nnObj < n is OK.
PriLevOpt Print level.
WarmStart If true, use warm start, otherwise cold start.
SOL.callback If 1, use a callback to Matlab to compute QP.F * x for different x. Faster when F is very large and almost dense, avoiding copying of F from Matlab to MEX.
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 SQOPT 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.
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;
v_k Lagrangian multipliers (for bounds + dual solution vector).
ExitFlag Exit status from sqopt.m (similar to TOMLAB).
Inform Result of SQOPT run.

0 finished successfully

1 optimality conditions satisfied

2 feasible point found

4 weak QP minimizer

10 the problem appears to be infeasible

11 infeasible linear constraints

12 infeasible linear equalities

14 infeasibilities minimized

20 the problem appears to be unbounded

21 unbounded objective

30 resource limit error

31 iteration limit reached

33 the superbasics limit is too small

40 terminated after numerical difficulties

42 singular basis

43 cannot satisfy the general constraints

44 ill-conditioned null-space basis

50 error in the user-supplied functions

53 the QP Hessian is indefinite

70 user requested termination

73 terminated during QP objective evaluation

74 terminated from monitor routine

80 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

90 input arguments out of range

91 invalid input argument

92 basis file dimensions do not match this problem

93 the QP Hessian is indefinite

140 system error

141 wrong number of basic variables

142 error in basis package

rc A 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.
Iter Number of iterations.
FuncEv Number of function evaluations. Set to Iter.
GradEv Number of gradient evaluations. Set to Iter.
ConstrEv Number of constraint evaluations. Set to 0.
QP.B Basis vector in TOMLAB QP standard.
Solver Name of the solver (sqopt).
SolverAlgorithm Description of the solver.
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 value of the optional parameter 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 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.hs State for variables and slacks in xs.
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 SQOPT, unless the value is altered in the SPECS file (input SpecsFile).

See TOMLAB User's Guide for the SPECS keywords and description.

Description of Inputs

# SPECS keyword text Lower Default Upper Comment
LP/QP Parameters I - Printing
2. PRINT LEVEL 0 0 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 PARAMETERS 0 0 1 1 = True
LP/QP Parameters II - Convergence Tolerances
11. FEASIBILITY TOLERANCE > 0 1E-6
12. OPTIMALITY TOLERANCE > 0 1E-6
Scaling
18. SCALE OPTION 0 2 2
19. SCALE TOLERANCE > 0 0.9 < 1
20. SCALE PRINT 0 0 1 1 = True
21. CRASH TOLERANCE 0 0.1 < 1
LU I
23. LU FACTOR TOLERANCE 1 100
24. LU UPDATE TOLERANCE 1 10
25. LU SWAP TOLERANCE > 0 1.22E-4 eps1/4
26. LU SINGULARITY TOLERANCE > 0 3.25E-11 eps0.67
LP/QP Parameters III
27. PIVOT TOLERANCE >' 0 3.25E-11 eps0.67
28. CRASH OPTION 0 0 3 0,1,2,3
29. ELASTIC WEIGHT 0 1
30. ITERATIONS LIMIT 0 10000
31. PARTIAL PRICE 1 10
32. MAXIMIZE 0 0 1 1=maximize
QP Objective
45. UNBOUNDED STEP SIZE
48. SUPERBASICS LIMIT > 0 > 0 1E20 min(500,1+nnObj)
LP/QP Parameters IV
49. ELASTIC MODE 0 1 0,1,2
50. ELASTIC OBJECTIVE 0 2 0,1,2
Frequencies II
51. CHECK FREQUENCY > 0 60
52. EXPAND FREQUENCY > 0 10000
53. FACTORIZATION FREQUENCY > 0 50
LU II
63. LU COMPLETE PIVOTING or LU PARTIAL PIVOTING 0 0 1 1=complete,

0=partial