TOMLAB Special Notes and Features

From TomWiki
Jump to navigationJump to search

{{#switch: | left =

{{#switch:{{#if: | {{{smallimage}}} | }} | none =

| #default =

}} {{#if:{{#if: | {{{smallimageright}}} | }} | {{#ifeq:{{#if: | {{{smallimageright}}} | }}|none | | }} }}

| #default =

{{#switch: | none =

| #default =

}}

{{#if: | {{#ifeq:|none

 | 
| }} }}

}}

Special Notes and Features

In this section several topics of general interest, which enables a more efficient use of TOMLAB are collected.

Speed and Solution of Optimization Subproblems

It is often the case that the full solution of an optimization problem involves the solution of subtasks, which themselves are optimization problems. In fact, most general solvers are constructed that way, they solve well- defined linear or quadratic subproblems as part of the main algorithm. TOMLAB has a standard way of calling a subsolver with the use of the driver routine tomSolve. The syntax is similar to the syntax of tomRun. Calling QPOPT to solve a QP sub problem is made with the call

Result  = tomRun('qpopt', Prob);

The big advantage is that tomSolve handles the global variables with a stack strategy, see Appendix D. Therefore it is possible to run any level of recursive calls with the TOMLAB TOM solvers, that all run in Matlab. Even if care has been taken in the MEX-file interfaces to avoid global variable and memory conflicts, there seem to be some internal memory conflicts occurring when calling recursively the same MEX-file solver. Luckily, because TOMLAB has several solver options, it should be possible to use different solvers. In one two-stage optimization, a control problem, even four solvers were used. glcSolve was used to find a good initial value for the main optimization and SNOPT was used to find the exact solution. In each iteration several small optimization problems had to be solved. Here glbSolve was used to find a good initial point close to the global optimum, and MINOS then iterated until good accuracy was found.

The general TOM solvers clsSolve, conSolve, cutplane, mipSolve, nlpSolve, qpSolve and sTrustr have all been designed so it shall be possible to change the subproblem solver. For example to solve the QP subproblems in conSolve there are several alternatives, QPOPT, qpSolve or even SNOPT. If using the BFGS update in conSolve, which guarantees that the subproblems are convex, then furthermore QLD or SQOPT could be used. The QP, LP, FP (feasible point) and DLP (dual LP) subproblems have special treatment. A routine CreateProbQP creates the Prob structure for the subproblem. The routine checks on the fields Prob.QP.SOL and Prob.QP.optParam and move these to the usual places Prob.SOL and Prob.optParam for the subproblem. Knowing this, the user may send his own choices of these two important subfields as input to conSolve and the other solvers mentioned. The choice of the subsolver is made by giving the name of the wanted subsolver as the string placed in Prob.SolverQP for QP subproblems and similar for the other subproblems. Note that the time consuming call to CreateProbQP is only done once in the solver, and after that only the fields necessary to be changed are altered in each iteration.

Note that if the user needs to cut CPU time as much possible, one way to save some time is to call tomSolve instead of tomRun. But no checks are made on the structure Prob, and such tricks should only be made at the production stage, when the code is known to be error free.

Another way to cut down CPU time for a nonlinear problem is to set

Prob.LargeScale = 1;

even if the problem is not that large (but time consuming). TOMLAB will then not collect information from iterations, and not try to estimate the search steps made. This information is only used for plotting, and is mostly not needed. Note that this change might lead to other choices of default solvers, because TOMLAB thinks the problem is large and sparse. So the default choices might have to be overridden.

User Supplied Problem Parameters

If a problem is dependent on a few parameters, it is convenient to avoid recoding for each change of these param- eters, or to define one problem for each of the different parameter choices. The user supplied problem parameters gives the user an easy way to change the creation of a problem. A field in the Prob structure, the field Prob.user is used to store the user supplied problem parameters. The field Prob.uP could be used when using Init Files.

Prob.uP, if set, is a numerical matrix or vector (recommended) with numbers. Its primary use is defining sizes and other vitals parameters, like initial value choices, in problems defined as Init Files. Prob.uP may not be a Matlab struct.

If ask == 1 is set, it is easy to change the values of Prob.uP in the test problems interactively. However, if setting Prob.uP directly (needed for batch runs) it is more difficult.

Three different ways to set Prob.uP are described below. Following these examples will get the problem setup correctly.

The first option assumes that the Probstructure is defined

Prob = ProbDef;
Prob.Name = 'Exponential problem (pseudorand)';
Prob.uPName = Prob.Name; % Special field used to identify the uP parameters
Prob.P = 14;
Prob.uP = \[60, 180\]; %   Increase the  problem  size  to  n=60,  m=180
Prob = probInit('ls_prob',14,-1,Prob);

The advantage is that other fields may also be set, however they could also be set after the probInit call. The second way avoid defining the full Prob structure. The field probFile must then also be initialized.

Prob	= \[\];
Prob.Name	= 'Exponential problem  (pseudorand)';
Prob.uPName	= Prob.Name; %   Special field used to  identify the  uP parameters
Prob.probFile = \[\]; Prob.P 	= 14;
Prob.uP 	= \[60, 180\]; %   Increase the  problem  size  to  n=60,  m=180
Prob	= probInit('ls_prob',14,-1,Prob);

In the third and final option the uP parameters could be sent directly as the 4th input to probInit, instead of the problem structure Prob.

Prob	= probInit('ls_prob',14,-1,\[60,  180\]);

Note: One must not change Prob.uP after executing probInit. Doing this will normally result in a crash in some routine, e.g. ls r or ls J or in erroneous results.

The best way to describe the User Supplied Problem Parameter feature inside Init Files is by an example. Assume that a problem with variable dimension needs to be created. If the user wants to change the dimension of the problem during the initialization of the problem, i.e. in the call to the Init File, the routine askparam is helpful. Problem 27 in cls prob is an example of the this:

...
...
elseif P==27
    Name='RELN';
    % n problem variables, n >= 1, default n = 10 uP = checkuP(Name,Prob);
    n = askparam(ask,  'Give   problem  dimension  ', 1,  \[\], 10,  uP);
    uP(1) = n;
    y = zeros(n,1); 
    x_0 = zeros(n,1); 
    x_opt = 3.5\*ones(n,1);
...
...

The routine checkuP is checking if the input Prob structure has the field Prob.uP defined, and if the Name of the problem is the same as the one set in Prob.Name. If this is true, uP is set to supplied value. When calling askparam, if ask <= 0, the dimension n is set to the default value 10 if uP is empty, otherwise to the value of uP. If ask > 0 is set by the user, askparam will ask the question Give problem dimension and set the value given by user. At the end of the Init File, the field Prob.uP is assigned the value of uP(1).

Using the routine checkuP, called after the Name variable is assigned, and the general question asking routine askparam, it is easy to add the feature of user supplied problem parameters to any user problem. Type help askparam for information about the parameters sent to askparam.

To send any amount of other information to the low-level user routines, it is recommended to use sub fields of Prob.user as described in Section 2.4.

In the other problem definition files, cls r and cls J in this example, the parameter(s) are "unpacked" and can be used e.g. in the definition of the Jacobian.

...
...
elseif P==27
    % 'RELN'
    n = Prob.uP(1);
...
...

If questions should be asked during the setup of the problem, in the Init File, the user must set the integer ask positive in the call to probInit. See the example below:

ask=1;
Prob = probInit('cls_prob',27,ask);

The system will now ask for the problem dimension, and assuming the choice of the dimension is 20, the output would be:

Current value = 10

Give problem dimension 20

Now call clsSolve to solve the problem,

Result=tomRun('clsSolve', Prob,  1);

As a second example assume that the user wants to solve the problem above for all dimensions between 10 and 30. The following code snippet will do the job.

for dim=10:30
   Prob       = []; 
   Prob.uP(1) = dim; 
   PriLev     = 0;
   Result     = tomRun('clsSolve', 'cls_prob', 27,  Prob,  PriLev);
end

User Given Stationary Point

Known stationary points could be defined in the problem definition files. It is also possible for the user to define the type of stationary point (minimum, saddle or maximum). When defining the problem RB BANANA (17) in the previous sections, x opt was set as (1, 1) in the problem definition files. If it is known that this point is a minimum point the definition of x opt could be extended to

x_opt = [1  1 StatPntType]; % Known optimal point (optional).

where StatPntType equals 0, 1, or 2 depending on the type of the stationary point (minimum, saddle or maximum). In this case set StatPntType to 0 since (1, 1) is a minimum point. The extension becomes

x_opt = [1  1 0]; % Known optimal point (optional).

If there is more than one known stationary point, the points are defined as rows in a matrix with the values of StatPntType as the last column. Assume that (-1, -1) is a saddle point, (1, -2) is a minimum point and (-3, 5) is a maximum point for a certain problem. The definition of x opt could then look like

x_opt = [ -1  -1   1
           1  -2   0
          -3   5   2 ];

Note that it is not necessary to define x opt. If x opt is defined it is not necessary to define StatPntType if all given points are minimum points.

Print Levels and Printing Utilities

The amount of printing is determined by setting different print levels for different parts of the TOMLAB system. The parameter is locally most often called PriLev. There are two main print levels. One that determines the output printing of the driver or menu routines, set in the input structure as Prob.PriLev. The other printing level, defined in Prob.PriLevOpt, determines the output in the TOM solvers and for the SOL solvers, the output in the Matlab part of the MEX file interface. In Table 132 the meaning of different print levels are defined.

The utility routine PrintResult prints the results of an optimization given the Result structure. The amount of printing is determined by a second input argument PriLev. The driver routine tomRun also makes a call to PrintResult after the optimization, and if the input parameter PriLev is greater than zero, the result will be the same as calling PrintResult afterwards.

PrintResult is using the global variables, MAX c, MAX x and MAX r to limit the lengths of arrays displayed. All Matlab routines in the SOL interfaces are also using these global variables. The global variables get default values by a call to tomlabInit, or if empty is set to default values by the different routines using them. The following example show the lines needed to change the default values.

global MAX_c   MAX_x MAX_r
MAX_x = 100; 
MAX_c =  50; 
MAX_r  = 200;

This code could either be executed at the command line, or in any main routine or script that the user defines.

Table 132: Print level in the TOM solvers, Prob.PriLevOpt
Value
Description
< 0 Totally silent.
0 Error messages and warnings.
1 Final results including convergence test results and minor warnings.
2 Each iteration, short output.
3 Each iteration, more output.
4 Line search or QP information.
5 Hessian output, final output in solver.

There is a wait flag field in optParam, optParam.wait. If this flag is set true, most of the TOM solvers uses the pause statement to avoid the output just flushing by. The user must press RETURN to continue execution. The fields in optParam is described in Table 141.

The TOM solvers routines print large amounts of output if high values for the PriLev parameter is set. To make the output look better and save space, several printing utilities have been developed.

For matrices there are two routines, mPrint and PrintMatrix. The routine PrintMatrix prints a matrix with row and column labels. The default is to print the row and column number. The standard row label is eight characters long. The supplied matrix name is printed on the first row, the column label row, if the length of the name is at most eight characters. Otherwise the name is printed on a separate row.

The standard column label is seven characters long, which is the minimum space an element will occupy in the print out. On a 80 column screen, then it is possible to print a maximum of ten elements per row. Independent on the number of rows in the matrix, PrintMatrix will first display A(:, 1 : 10), then A(:, 11 : 20) and so on.

The routine PrintMatrix tries to be intelligent and avoid decimals when the matrix elements are integers. It determines the maximal positive and minimal negative number to find out if more than the default space is needed. If any element has an absolute value below 10-5 (avoiding exact zeros) or if the maximal elements are too big, a switch is made to exponential format. The exponential format uses ten characters, displaying two decimals and therefore seven matrix elements are possible to display on each row.

For large matrices, especially integer matrices, the user might prefer the routine mPrint. With this routine a more dense output is possible. All elements in a matrix row is displayed (over several output rows) before next matrix row is printed. A row label with the name of the matrix and the row number is displayed to the left using the Matlab style of syntax.

The default in mPrint is to eight characters per element, with two decimals. However, it is easy to change the format and the number of elements displayed. For a binary matrix it is possible to display 36 matrix columns in one 80 column row.

Partially Separable Functions

The routine sTrustr implements a structured trust region algorithm for partially separable functions (psf). A definition of a psf is given below and an illustrative example of how such a function is defined and used in TOMLAB.

is partially separable if , where, for each there exists a subspace Failed to parse (unknown function "\MATHSET"): {\displaystyle $\MATHSET{N}_i \neq {0}$} such that, for all Failed to parse (unknown function "\MATHSET"): {\displaystyle $w \in \MATHSET{N}_i$} and for all Failed to parse (unknown function "\MATHSET"): {\displaystyle $x \in \MATHSET{X}$} , it holds that . Failed to parse (unknown function "\MATHSET"): {\displaystyle $\MATHSET{X}$} is the closed convex subset of Failed to parse (unknown function "\MATHSET"): {\displaystyle $\MATHSET{R}^n$} defined by the constraints.

Consider the problem DAS 2 in File: tomlab/testprob/con_prob:


Failed to parse (unknown function "\label"): {\displaystyle \label{eq:DAS2} \begin{array}{ll} \min\limits_{x} & f(x)= \frac{1}{2}\sum\limits_1^6 r_i(x)^2 \\s/t & Ax \geq b \\ & x \geq 0 \\ \end{array} }

where


The objective function in (22) is partially separable according to the definition above and the constraints are linear and therefore they define a convex set. DAS 2 is defined as the constrained problem 14 in con prob, con f, con g etc. as an illustrative example of how to define a problem with a partially separable objective function. Note the definition of pSepFunc in con prob.

One way to solve problem (22) with sTrustr is to define the following statements:

probFile = 'con_prob';        % Name of Init File
P = 14;                       % Problem number in con_prob
Prob = probInit(probFile, P); % Define a problem structure

Result      = tomRun('sTrustr', Prob,  0);

The sequence of statements are similar to normal use of TOMLAB. The only thing that triggers the use of the partial separability is the definition of the variable Prob.PartSep.pSepFunc. To solve the same problem, and avoiding the use of psf, the following statements could be used:

probFile = 'con_prob'; % Name of Init File

P = 14; % Problem number in con_prob
Prob = probInit(probFile,P); % Define a problem structure
Prob.PartSep.pSepFunc  = 0;  % Redefining number of separable functions

Result = tomRun('sTrustr', Prob,  0);

Another alternative is to set Prob.PartSep as empty before the call to sTrustr. This example, slightly expanded, is included in the distribution as psfDemo in directory examples.

Utility Test Routines

The utility routines listed in Table 133 run tests on a large set of test problems.

Table 133: System test routines.
Function
Description
Section
Page
runtest Runs all selected problems defined in a problem file for a given solver. 12.13 201
systest Runs big test for each probType in TOMLAB. 12.16 204

The runtest routine may also be useful for a user running a large set of optimization problems, if the user does not need to send special information in the Prob structure for each problem.