TOMLAB

Introduction

What is TOMLAB?

TOMLAB is a general purpose development, modeling and optimal control environment in Matlab for research, teaching

and practical solution of optimization problems.

TOMLAB has grown out of the need for advanced, robust and reliable tools to be used in the development of

algorithms and software for the solution of many different types of applied optimization problems.

There are many good tools available in the area of numerical analysis, operations research and optimization, but

because of the different languages and systems, as well as a lack of standardization, it is a time consuming and

complicated task to use these tools. Often one has to rewrite the problem formulation, rewrite the function

specifications, or make some new interface routine to make everything work. Therefore the first obvious and basic

design principle in TOMLAB is: Define your problem once, run all available solvers. The system takes care of

all interface problems, whether between languages or due to different demands on the problem specification.

In the process of optimization one sometimes wants to graphically view the problem and the solution process,

especially for ill-conditioned nonlinear problems. Sometimes it is not clear what solver is best for the particular

type of problem and tests on different solvers can be of use. In teaching one wants to view the details of the

algorithms and look more carefully at the different algorithmic steps. When developing new algorithms tests on

thousands of problems are necessary to fully access the pros and cons of the new algorithm. One might want to

solve a practical problem very many times, with slightly different conditions for the run. Or solve a control

problem looping in real-time and solving the optimization problem each time slot.

All these issues and many more are addressed with the TOMLAB optimization environment. TOMLAB gives easy access

to a large set of standard test problems, optimization solvers and utilities.

The Organization of This Guide

Section 2 presents the general design of TOMLAB.

Section 3 contains strict mathematical definitions of the optimization problem types. All solver routines

available in TOMLAB are described.

Section 4 describes the input format and modeling environment. The functionality of the modeling engine

TomSym is discussed in 4.3 and also in appendix C.

Sections 5, 6, 7 and 8 contain examples on the process of defining problems and solving them. All test

examples are available as part of the TOMLAB distribution.

Section 9 shows how to setup and define multi layer optimization problems in TOMLAB.

Section 11 contains detailed descriptions of many of the functions in TOMLAB. The TOM solvers, originally

developed by the Applied Optimization and Modeling (TOM) group, are described together with TOMLAB driver routine

and utility functions. Other solvers, like the Stanford Optimization Laboratory (SOL) solvers are not described,

but documentation is available for each solver.

Section 12 describes the utility functions that can be used, for example tomRun and SolverList.

Section 13 introduces the different options for derivatives, automatic differentiation.

Section 14 discusses a number of special system features such as partially separable functions and user

supplied parameter information for the function computations.

Appendix A contains tables describing all elements defined in the problem structure. Some subfields are

either empty, or filled with information if the particular type of optimization problem is defined. To be able

to set different parameter options for the optimization solution, and change problem dependent information, the

user should consult the tables in this Appendix.

Appendix B contains tables describing all elements defined in the output result structure returned from all

solvers and driver routines.

Appendix D is concerned with the global variables used in TOMLAB and routines for handling important global

variables enabling recursive calls of any depth.

Appendix E describes the available set of interfaces to other optimization software, such as CUTE, AMPL,

and

The Mathworks' Optimization Toolbox.

Appendix F gives some motivation for the development of TOMLAB.

Overall Design

The scope of TOMLAB is large and broad, and therefore there is a need of a well-designed system. It is also

natural to use the power of the Matlab language, to make the system flexible and easy to use and maintain. The

concept of structure arrays is used and the ability in Matlab to execute Matlab code defined as string expressions

and to execute functions specified by a string.

Structure Input and Output

Normally, when solving an optimization problem, a direct call to a solver is made with a long list of parameters in

the call. The parameter list is solver-dependent and makes it difficult to make additions and changes to the

system.

TOMLAB solves the problem in two steps. First the problem is defined and stored in a Matlab structure. Then the

solver is called with a single argument, the problem structure. Solvers that were not originally developed for the

TOMLAB environment needs the usual long list of parameters. This is handled by the driver routine tomRun.m

which can call any available solver, hiding the details of the call from the user. The solver output is collected

in a standardized result structure and returned to the user.

Introduction to Solver and Problem Types

TOMLAB solves a number of different types of optimization problems. The currently defined types are listed in

Table 1.

The global variable probType contains the current type of optimization problem to be solved. An optimization

solver is defined to be of type solvType, where solvType is any of the probType entries in Table 1. It

is clear that a solver of a certain solvType is able to solve a problem defined to be of another type. For

example, a constrained nonlinear programming solver should be able to solve unconstrained problems, linear and

quadratic programs and constrained nonlinear least squares problems. In the graphical user interface and menu

system an additional variable optType is defined to keep track of what type of problem is defined as the main

subject. As an example, the user may select the type of optimization to be quadratic programming (optType ==

2), then select a particular problem that is a linear programming problem (probType == 8) and then as the

solver choose a constrained NLP solver like MINOS (solvType == 3).

Table 1: The different types of optimization problems defined in TOMLAB.

probType		Type of optimization problem
uc	1	Unconstrained optimization (incl. bound constraints).
qp	2	Quadratic programming.
con	3	Constrained nonlinear optimization.
ls	4	Nonlinear least squares problems (incl. bound constraints).
lls	5	Linear least squares problems.
cls	6	Constrained nonlinear least squares problems.
mip	7	Mixed-Integer programming.
lp	8	Linear programming.
glb	9	Box-bounded global optimization.
glc	10	Global mixed-integer nonlinear programming.
miqp	11	Constrained mixed-integer quadratic programming.
minlp	12	Constrained mixed-integer nonlinear optimization.
lmi	13	Semi-definite programming with Linear Matrix Inequalities.
bmi	14	Semi-definite programming with Bilinear Matrix Inequalities.
exp	15	Exponential fitting problems.
nts	16	Nonlinear Time Series.
lcp	22	Linear Mixed-Complimentary Problems.
mcp	23	Nonlinear Mixed-Complimentary Problems.

Please note that since the actual numbers used for probType may change in future releases, it is recommended to

use the text abbreviations. See help for checkType for further information.

Define probSet to be a set of defined optimization problems belonging to a certain class of problems of type

probType. Each probSet is physically stored in one file, an Init File. In Table 2 the currently

defined problem sets are listed, and new probSet sets are easily added.

Table 2: Defined test problem sets in TOMLAB. probSets marked with * are not part of the standard

distribution

probSet	probType	Description of test problem set
uc	1	Unconstrained test problems.
qp	2	Quadratic programming test problems.
con	3	Constrained test problems.
ls	4	Nonlinear least squares test problems.
lls	5	Linear least squares problems.
cls	6	Linear constrained nonlinear least squares problems.
mip	7	Mixed-integer programming problems.
lp	8	Linear programming problems.
glb	9	Box-bounded global optimization test problems.
glc	10	Global MINLP test problems.
miqp	11	Constrained mixed-integer quadratic problems.
minlp	12	Constrained mixed-integer nonlinear problems.
lmi	13	Semi-definite programming with Linear Matrix Inequalities.
bmi	14	Semi-definite programming with Bilinear Matrix Inequalities.
exp	15	Exponential fitting problems.
nts	16	Nonlinear time series problems.
lcp	22	Linear mixed-complimentary problems.
mcp	23	Nonlinear mixed-complimentary problems.


mgh	4	More, Garbow, Hillstrom nonlinear least squares problems.
chs	3	Hock-Schittkowski constrained test problems.
uhs	1	Hock-Schittkowski unconstrained test problems.

The names of the predefined Init Files that do the problem setup, and the corresponding low level routines are

constructed as two parts. The first part being the abbreviation of the relevant probSet, see Table 2, and

the second part denotes the computed task, shown in Table 3. The user normally does not have to define the more

complicated functions o_d2c and o_d2r. It is recommended to supply this information when using solvers

which can utilize second order information, such as TOMLAB /KNITRO and TOMLAB /CONOPT.

Table 3: Names for predefined Init Files and low level m-files in TOMLAB.

Generic name	Purpose *( o is any probSet, e.g. o=*con)
o_prob	Init File that either defines a string matrix with problem names
o_f	Compute objective function f (x).
o_g	Compute the gradient vector g(x).
o_H	Compute the Hessian matrix H (x).
o_c	Compute the vector of constraint functions c(x).
o_dc	Compute the matrix of constraint normals, ?c(x)/dx.
o_d2c	Compute the 2nd part of 2nd derivative matrix of the Lagrangian function, ?i ?i ?2 ci (x)/dx2 .
o_r	Compute the residual vector r(x).
o_J	Compute the Jacobian matrix J (x).
o_d2r	Compute the 2nd part of the Hessian matrix, ?i ri (x)?2 ri (x)/dx2

The Init File has two modes of operation; either return a string matrix with the names of the problems in the

probSet or a structure with all information about the selected problem. All fields in the structure, named

Prob, are presented in tables in Section A. Using a structure makes it easy to add new items without too many

changes in the rest of the system. For further discussion about the definition of optimization problems in TOMLAB,

see Section 4.

There are default values for everything that is possible to set defaults for, and all routines are written in a

way that makes it possible for the user to just set an input argument empty and get the default.

The Process of Solving Optimization Problems

A flow-chart of the process of optimization in TOMLAB is shown in Figure 1. It is inefficient to use an interactive

system. This is symbolized withthe Standard User box in the figure, which directly runs the Optimization

Driver, tomRun. The direct solver call is possible for all TOMLAB solvers, if the user has executed

ProbCheck prior to the call. See Section 3 for a list of the TOMLAB solvers.

Depending on the type of problem, the user needs to supply the low-level routines that calculate the objective

function, constraint functions for constrained problems, and also if possible, derivatives. To simplify this

coding process so that the work has to be performed only once, TOMLAB provides gateway routines that ensure

that any solver can obtain the values in the correct format.

For example, when working with a least squares problem, it is natural to code the function that computes the vector

of residual functions ri (x1 , x2 , . . .), since a dedicated least squares solver probably

operates on the residual while a general nonlinear solver needs a scalar function, in this case f (x) = 1

rT (x)r(x). Such issues are automatically handled by the gateway functions.

Low Level Routines and Gateway Routines

Low level routines are the routines that compute:

The objective function value

The gradient vector

The Hessian matrix (second derivative matrix)

The residual vector (for nonlinear least squares problems)

The Jacobian matrix (for nonlinear least squares problems)

The vector of constraint functions

The matrix of constraint normals (the constraint Jacobian)

The second part of the second derivative of the Lagrangian function. The last three routines are only needed for

constrained problems.

The names of these routines are defined in the structure fields Prob.FUNCS.f, Prob.FUNCS.g, Prob.FUNCS.H

etc.

It is the task for the Assign routine to set the names of the low level m-files. This is done by a call to the

routine conAssign with the names as arguments for example. There are Assign routines for all problem types

handled by TOMLAB. As an example, see 'help conAssign' in MATLAB.

Prob = conAssign('f', 'g', 'H', HessPattern, x_L,  x_U, Name,x_0,... 
pSepFunc, fLowBnd, A,  b_L,  b_U, 'c', 'dc', 'd2c', ConsPattern,... 
c_L,  c_U, x_min,  x_max, f_opt, x_opt);

Only the low level routines relevant for a certain type of optimization problem need to be coded. There are dummy

routines for the others. Numerical differentiation is automatically used for gradient, Jacobian and constraint

gradient if the corresponding user routine is non present or left out when calling conAssign. However, the

solver always needs more time to estimate the derivatives compared to if the user supplies a code for them. Also

the numerical accuracy is lower for estimated derivatives, so it is recommended that the user always tries to code

the derivatives, if it is possible. Another option is automatic differentiation with TOMLAB /MAD.

TOMLAB uses gateway routines (nlp f, nlp g, nlp H, nlp c, nlp dc, nlp d2c, nlp r,

nlp J, nlp d2r). These routines extract the search directions and line search steps, count iterations,

handle separable functions, keep track of the kind of differentiation wanted etc. They also handle the separable

NLLS case and NLLS weighting. By the use of global variables, unnecessary evaluations of the user supplied routines

are avoided.

To get a picture of how the low-level routines are used in the system, consider Figure 2 and 3. Figure 2

illustrates the chain of calls when computing the objective function value in ucSolve for a nonlinear least

squares problem defined in mgh prob, mgh r and mgh J. Figure 3 illustrates the chain of calls when

computing the numerical approximation of the gradient (by use of the routine fdng) in ucSolve for an

unconstrained problem defined in uc_prob and uc_f.

Information about a problem is stored in the structure variable Prob, described in detail in the tables in

Appendix

A. This variable is an argument to all low level routines. In the field element Prob.user, problem specific

information

ucSolve <==> nlp_f <==> ls_f <==> nlp_r <==> mgh_r

Figure 2: The chain of calls when computing the objective function value in ucSolve for a nonlinear least

squares problem defined in mgh prob, mgh r and mgh J.

ucSolve <==> nlp_g <==> fdng <==> nlp_r <==> uc_f

Figure 3: The chain of calls when computing the numerical approximation of the gradient in ucSolve for an

unconstrained problem defined in uc prob and uc f.

needed to evaluate the low level routines are stored. This field is most often used if problem related questions

are asked when generating the problem. It is often the case that the user wants to supply the low-level routines

with additional information besides the variables x that are optimized. Any unused fields could be defined in

the structure Prob for that purpose. To avoid potential conflicts with future TOMLAB releases, it is

recommended to use subfields of Prob.user. It the user wants to send some variables a, B and C, then, after

creating the Prob structure, these extra variables are added to the structure:

Prob.user.a=a; 
Prob.user.B=B; 
Prob.user.C=C;

Then, because the Prob structure is sent to all low-level routines, in any of these routines the variables are

picked out from the structure:

a = Prob.user.a; 
B = Prob.user.B; 
C = Prob.user.C;

A more detailed description of how to define new problems is given in sections 5, 6 and 8. The usage of

Prob.user is described in Section 14.2.

Different solvers all have different demand on how information should be supplied, i.e. the function to optimize,

the gradient vector, the Hessian matrix etc. To be able to code the problem only once, and then use this

formulation to run all types of solvers, interface routines that returns information in the format needed for the

relevant solver were developed.

Table 4 describes the low level test functions and the corresponding Init File routine needed for the predefined

constrained optimization (con) problems. For the predefined unconstrained optimization (uc)

problems, the global optimization (glb, glc) problems and the quadratic programming problems (qp)

similar routines have been defined.

To conclude, the system design is flexible and easy to expand in many different ways.

Table 4: Generally constrained nonlinear (con) test problems.

Function	Description
con_prob	Init File. Does the initialization of the con test problems.
con_f	Compute the objective function f (x) for con test problems.
con_g	Compute the gradient g(x) for con test problems. x
con_H	Compute the Hessian matrix H (x) of f (x) for con test problems.
con_c	Compute the constraint residuals c(x) for con test problems.
con_dc	Compute the derivative of the constraint residuals for con test problems.
con_d2c	Compute the 2 nd part of 2 nd derivative matrix of the Lagrangian function, ?i ?i ?2 ci (x)/dx2 for con test problems.
con_fm	Compute merit function ?(xk ).
con_gm	Compute gradient of merit function ?(xk ).

Problem Types and Solver Routines

Section 3.1 defines all problem types in TOMLAB. Each problem definition is accompanied by brief suggestions on

suitable solvers. This is followed in Section 3.2 by a complete list of the available solver routines in TOMLAB and

the various available extensions, such as /SOL and /CGO.

Problem Types Defined in TOMLAB

The unconstrained optimization (uc) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:uc} \begin{array}{ll} \min\limits_{x} & f(x) \\ & \\ s/t & \begin{array}{lcccl} x_{L} & \leq & x & \leq & x_{U}, \\ \end{array} \end{array} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle $x, x_L, x_U \in \MATHSET{R}^n$} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle $f(x) \in \MATHSET{R}$} . For unbounded variables, the corresponding elements of $\$x_{L},x_{U}\$$ may be set to $\$\pm \infty \$$ .

Recommended solvers: TOMLAB /KNITRO and TOMLAB /SNOPT.

The TOMLAB Base Module routine ucSolve includes several of the most popular search step methods for unconstrained optimization. Bound constraints are treated as described in Gill et. al. \[28\]. The search step methods for unconstrained optimization included in ucSolve are: the Newton method, the quasi-Newton BFGS and DFP method, the Fletcher-Reeves and Polak-Ribiere conjugate-gradient method, and the Fletcher conjugate descent method. The quasi-Newton methods may either update the inverse Hessian (standard) or the Hessian itself. The Newton method and the quasi-Newton methods updating the Hessian use a subspace minimization technique to handle rank problems, see Lindstr¨om \[53\]. The quasi-Newton algorithms also use safe guarding techniques to avoid rank problem in the updated matrix.

Another TOMLAB Base Module solver suitable for unconstrained problems is the structural trust region algorithm sTrustr, combined with an initial trust region radius algorithm. The code is based on the algorithms in \[13\] and \[67\], and treats partially separable functions. Safeguarded BFGS or DFP are used for the quasi-Newton update, if the analytical Hessian is not used. The set of constrained nonlinear solvers could also be used for unconstrained problems.

The quadratic programming (qp) problem is defined as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \label{eq:qp} \begin{array}{ll} \min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x \\ & \\ s/t & \begin{array}{lcccl} x_{L} & \leq & x & \leq & x_{U}, \\ b_{L} & \leq & A x & \leq & b_{U} \\ \end{array} \end{array} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle $c, x, x_L, x_U \in \MATHSET{R}^n$} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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}$} .

Recommended solvers: TOMLAB /KNITRO, TOMLAB /SNOPT and TOMLAB /MINLP.

A positive semidefinite F -matrix gives a convex QP, otherwise the problem is nonconvex. Nonconvex quadratic programs are solved with a standard active-set method \[54\], implemented in the TOM routine qpSolve. qpSolve explicitly treats both inequality and equality constraints, as well as lower and upper bounds on the variables (simple bounds). It converges to a local minimum for indefinite quadratic programs.

In TOMLAB MINOS in the general or the QP-version (QP-MINOS), or the dense QP solver QPOPT may be used. In the TOMLAB /SOL extension the SQOPT solver is suitable for both dense and large, sparse convex QP and SNOPT works fine for dense or sparse nonconvex QP.

For very large-scale problems, an interior point solver is recommended, such as TOMLAB /KNITRO or TOMLAB /BARNLP.

TOMLAB /CPLEX, TOMLAB /Xpress and TOMLAB /XA should always be considered for large-scale QP problems.

The constrained nonlinear optimization problem (con) is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:con} \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} }

Recommended solvers: TOMLAB /SNOPT, TOMLAB /NPSOL and TOMLAB /KNITRO.

For general constrained nonlinear optimization a sequential quadratic programming (SQP) method by Schittkowski \[69\] is implemented in the TOMLAB Base Module solver conSolve. conSolve also includes an implementation of the Han-Powell SQP method. There are also a TOMLAB Base Module routine nlpSolve implementing the Filter SQP by Fletcher and Leyffer presented in \[21\].

Another constrained solver in TOMLAB is the structural trust region algorithm sTrustr, described above. Currently, sTrustr only solves problems where the feasible region, defined by the constraints, is convex. TOMLAB /MINOS solves constrained nonlinear programs. The TOMLAB /SOL extension gives an additional set of general solvers for dense or sparse problems.

sTrustr, pdco and pdsco in TOMLAB Base Module handle nonlinear problems with linear constraints only.

There are many other options for large-scale nonlinear optimization to consider in TOMLAB. TOMLAB /CONOPT, TOMLAB /BARNLP, TOMLAB /MINLP, TOMLAB /NLPQL and TOMLAB /SPRNLP.

The box-bounded global optimization (glb) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:glb} \begin{array}{ll} \min\limits_{x} & f(x) \\ & \\ s/t & \begin{array}{llcccll} -\infty < &x_{L} & \leq & x & \leq & x_{U}& < \infty , \\ \end{array} \end{array} }

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}$} , i.e. problems of the form \ref{eq:uc} that have finite simple bounds on all variables.

Recommended solvers: TOMLAB /LGO and TOMLAB /CGO with TOMLAB /SOL.

The TOM solver glbSolve implements the DIRECT algorithm \[14\], which is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. In glbSolve no derivative information is used. For global optimization problems with expensive function evaluations the TOMLAB /CGO routine ego implements the Efficient Global Optimization (EGO) algorithm \[16\]. The idea of the EGO algorithm is to first fit a response surface to data collected by evaluating the objective function at a few points. Then, EGO balances between finding the minimum of the surface and improving the approximation by sampling where the prediction error may be high.

The global mixed-integer nonlinear programming (glc) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:glc} \begin{array}{ll} \min\limits_{x} & f(x) \\ & \\ s/t & \begin{array}{llcccll} -\infty < &x_{L} & \leq & x & \leq & x_{U}& < \infty \\ &b_{L} & \leq & A x & \leq & b_{U}& \\ &c_{L} & \leq & c(x) & \leq & c_{U},& x_{j} \in \MATHSET{N}\ ~~\forall j \in $I$ \end{array} \end{array} }

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}$} . The variables $\$x\in I\$$ , the index subset of $\$1,...,n\$$ , are restricted to be integers.

Recommended solvers: TOMLAB /OQNLP.

The TOMLAB Base Module solver glcSolve implements an extended version of the DIRECT algorithm \[52\], that

handles problems with both nonlinear and integer constraints.

The linear programming (lp) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:LP} \begin{array}{ll} \min\limits_{x} & f(x) = c^T x \\ & \\ s/t & \begin{array}{lcccl} x_{L} & \leq & x & \leq & x_{U}, \\ b_{L} & \leq & A x & \leq & b_{U} \\ \end{array} \end{array} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle $c, x, x_L, x_U \in \MATHSET{R}^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}$} .

Recommended solvers: TOMLAB /CPLEX, TOMLAB /Xpress and TOMLAB /XA. The TOMLAB Base Module solver lpSimplex implements a simplex algorithm for lp problems.

When a dual feasible point is known in (6) it is efficient to use the dual simplex algorithm implemented in the TOMLAB Base Module solver DualSolve. In TOMLAB /MINOS the LP interface to MINOS, called LP-MINOS is efficient for solving large, sparse LP problems. Dense problems are solved by LPOPT. The TOMLAB /SOL extension gives the additional possibility of using SQOPT to solve large, sparse LP.

The recommended solvers normally outperforms all other solvers.

The mixed-integer programming problem (mip) is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:mip} \begin{array}{ll} \min\limits_{x} & f(x) = c^T x \\ & \\ s/t & \begin{array}{lcccl} x_{L} & \leq & x & \leq & x_{U}, \\ b_{L} & \leq & A x & \leq & b_{U}, ~x_{j} \in \MATHSET{N}\ ~~\forall j \in $I$ \\ \end{array} \end{array} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle $c, x, x_L, x_U \in \MATHSET{R}^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 variables $\$x\in I\$$ , the index subset of $\$1,...,n\$$ are restricted to be integers. Equality constraints are defined by setting the lower bound equal to the upper bound, i.e. for constraint $\$i\$:\$b_{L}(i)=b_{U}(i)\$$ .

Recommended solvers: TOMLAB /CPLEX, TOMLAB /Xpress and TOMLAB /XA.

Mixed-integer programs can be solved using the TOMLAB Base Module routine mipSolve that implements a standard branch-and-bound algorithm, see Nemhauser and Wolsey \[58, chap. 8\]. When dual feasible solutions are available, mipSolve is using the TOMLAB dual simplex solver DualSolve to solve subproblems, which is significantly faster than using an ordinary linear programming solver, like the TOMLAB lpSimplex. mipSolve also implements user defined priorities for variable selection, and different tree search strategies. For 0/1 - knapsack problems a round-down primal heuristic is included. Another TOMLAB Base Module solver is the cutting plane routine cutplane, using Gomory cuts. It is recommended to use mipSolve with the LP version of MINOS with warm starts for the subproblems, giving great speed improvement. The TOMLAB /Xpress extension gives access to the state-of-the-art LP, QP, MILP and MIQP solver Xpress-MP. For many MIP problems, it is necessary to use such a powerful solver, if the solution should be obtained in any reasonable time frame. TOMLAB /CPLEX is equally powerful as TOMLAB /Xpress and also includes a network solver.

The linear least squares (lls) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:lls} \begin{array}{ll} \min\limits_{x} & f(x) = \frac{1}{2} || C x - d || \\ & \\ s/t & \begin{array}{lcccl} x_{L} & \leq & x & \leq & x_{U}, \\ b_{L} & \leq & A x & \leq & b_{U} \\ \end{array} \end{array} }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle $x, x_L, x_U \in \MATHSET{R}^n$} , Failed to parse (unknown function "\MATHSET"): {\displaystyle $d \in \MATHSET{R}^M$} , Failed to parse (unknown function "\MATHSET"): {\displaystyle $C \in \MATHSET{R}^{M \times n}$} , Failed to parse (unknown function "\MATHSET"): {\displaystyle $A \in \MATHSET{R}^{m_1 \times n}$, <math>$b_L,b_U \in \MATHSET{R}^{m_1}$} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle $c_L,c(x),c_U \in \MATHSET{R}^{m_2}$} .

Recommended solvers: TOMLAB /LSSOL.

Tlsqr solves unconstrained sparse lls problems. lsei solves the general dense problems. Tnnls is

a fast and robust replacement for the Matlab nnls. The general least squares solver clsSolve may also be used.

In the TOMLAB

/NPSOL or TOMLAB /SOL extension the LSSOL solver is suitable for dense linear least squares problems.

The constrained nonlinear least squares (cls) problem is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:cls} \begin{array}{ll} \min\limits_{x} & f(x) = \frac{1}{2} r(x)^T r(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} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle $x, x_L, x_U \in \MATHSET{R}^n$} , Failed to parse (unknown function "\MATHSET"): {\displaystyle $r(x) \in \MATHSET{R}^M$} , 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}$} .

Recommended solvers: TOMLAB /NLSSOL.

The TOMLAB Base Module nonlinear least squares solver clsSolve treats problems with bound constraints in a similar way as the routine ucSolve. This strategy is combined with an active-set strategy to handle linear equality and inequality constraints \[7\].

clsSolve includes seven optimization methods for nonlinear least squares problems, among them: the Gauss-Newton method, the Al-Baali-Fletcher \[2\] and the Fletcher-Xu \[19\] hybrid method, and the Huschens TSSM method \[50\]. If rank problems occur, the solver uses subspace minimization. The line search algorithm used is the same as for unconstrained problems.

Another fast and robust solver is NLSSOL, available in the TOMLAB /NPSOL or the TOMLAB /SOL extension toolbox.

One important utility routine is the TOMLAB Base Module line search algorithm LineSearch, used by the solvers conSolve, clsSolve and ucSolve. It implements a modified version of an algorithm by Fletcher \[20, chap. 2\]. The line search algorithm uses quadratic and cubic interpolation, see Section 12.10. Another TOMLAB Base Module routine, preSolve, is running a presolve analysis on a system of linear qualities, linear inequalities and simple bounds. An algorithm by Gondzio \[36\], somewhat modified, is implemented in preSolve. See \[7\] for a more detailed presentation.

The linear semi-definite programming problem with linear matrix inequalities (sdp) is defined as

Failed to parse (unknown function "\label"): {\displaystyle \label{eq:sdp} \begin{array}{rccccl} \min\limits_{x} & \multicolumn{5}{l}{f(x) = {c^T}x} \\ & \\ s/t & x_{L} & \leq & x & \leq & x_{U} \\ & b_{L} & \leq & Ax & \leq & b_{U} \\ & \multicolumn{5}{r}{Q^{i}_0 + \Sum{k=1}{n} Q^{i}_{k}x_{k} \preccurlyeq 0,\qquad i=1,\ldots,m.} \\ \end{array} where $c, x, x_L, x_U \in \MATHSET{R}^n$, $A \in \MATHSET{R}^{m_l \times n}$, $b_L,b_U \in \MATHSET{R}^{m_l}$ and $Q^{i}_{k}$ are symmetric matrices of similar dimensions in each constraint $i$. If there are several LMI constraints, each may have it's own dimension. }

Recommended solvers: TOMLAB /PENSDP and TOMLAB /PENBMI.

The linear semi-definite programming problem with bilinear matrix inequalities (bmi) is defined

sim- ilarly to but with the matrix inequality

n n n

0 +

k=1

Qk xk +

) )

k=1 l=1

xk xl Kkl

o:: 0 (11)

The MEX solvers pensdp and penbmi treat sdp and bmi problems, respectively. These are

available in the

TOMLAB /PENSDP and TOMLAB /PENBMI toolboxes.

The MEX-file solver pensdp available in the TOMLAB /PENSDP toolbox implements a penalty method aimed at

large-scale dense and sparse sdp problems. The interface to the solver allows for data input in the sparse

SDPA input format as well as a TOMLAB specific format corresponding to.

The MEX-file solver penbmi available in the TOMLAB /PENBMI toolbox is similar to pensdp, with added

support for the bilinear matrix inequalities.

TOMLAB

Contents

Introduction

What is TOMLAB?

The Organization of This Guide

Further Reading

Overall Design

Structure Input and Output

Introduction to Solver and Problem Types

The Process of Solving Optimization Problems

Low Level Routines and Gateway Routines

Problem Types and Solver Routines

Problem Types Defined in TOMLAB

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools