TOMLAB: Difference between revisions

From TomWiki
Jump to navigationJump to search
(Created page with "==Introduction== ===What is TOMLAB?=== TOMLAB is a general purpose development, modeling and optimal control environment in Matlab for research, teaching and practical ...")
 
No edit summary
 
(24 intermediate revisions by 3 users not shown)
Line 1: Line 1:
==Introduction==
[[Category:Manuals]]
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.


===What is TOMLAB?===
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.


==Overall Design==
Overall Design presents the general design of TOMLAB.
*[[TOMLAB  Overall Design|Overall Design]]


TOMLAB  is a general purpose development, modeling and optimal control environment in Matlab for research, teaching
==Problem Types and Solver Routines==
 
Contains strict mathematical definitions of the optimization problem types.  All solver routines available in TOMLAB  are described.
and practical solution of optimization problems.
*[[TOMLAB Problem Types and Solver Routines|Problem Types and Solver Routines]]
 
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
==Defining Problems in TOMLAB==
*[[TOMLAB Defining Problems in TOMLAB|Defining Problems in TOMLAB]]


and utility functions. Other solvers, like  the Stanford Optimization Laboratory (SOL) solvers are not described,  
==Solving Linear, Quadratic and Integer Programming Problems==
Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.
*[[TOMLAB Solving Linear Quadratic and Integer Programming Problems|Solving Linear, Quadratic and Integer Programming Problems]]


but documentation is available for each solver.
==Solving Unconstrained and Constrained Optimization Problems==
Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.  
*[[TOMLAB  Solving Unconstrained and Constrained Optimization Problems|Solving Unconstrained and Constrained Optimization Problems]]


'''Section 12 '''describes the utility functions that can be used, for example ''tomRun ''and ''SolverList''.
==Solving Global Optimization Problems==
Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.
*[[TOMLAB Solving Global Optimization Problems|Solving Global Optimization Problems]]


==Solving Least Squares and Parameter Estimation Problems==
Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.
*[[TOMLAB Solving Least Squares and Parameter Estimation Problems|Solving Least Squares and Parameter Estimation Problems]]


==Multi Layer Optimization==
Shows how to setup and define multi layer optimization problems in TOMLAB.
*[[TOMLAB Multi Layer Optimization|Multi Layer Optimization]]


'''Section 13 '''introduces the different options for derivatives, automatic differentiation.
==Tomhelp - The Help Program==
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.  
*[[TOMLAB TomHelp|Tomhelp - The Help Program]]


==TOMLAB Solver Reference==


*[[TOMLAB Solver Reference]]


'''Section 14 '''discusses a number of special system features such as partially separable functions and user
==TOMLAB Utility Functions==
Describes the utility functions that can be used, for example tomRun and SolverList.


supplied parameter information for the function computations.
*[[TOMLAB Utility Functions]]


'''Appendix  A '''contains tables describing all elements defined in the problem structure. Some subfields are
==Approximation of Derivatives==
Introduces the different options for derivatives, automatic differentiation.  


either empty, or filled with  information if the particular  type  of optimization  problem is defined.  To be able
*[[TOMLAB Approximation of Derivatives|Approximation of Derivatives]]


to set different parameter options for the optimization solution, and change problem dependent information, the
==Special Notes and Features==
Discusses a number of special system features such as partially separable functions and user supplied parameter information for the function computations.
*[[TOMLAB Special Notes and Features|Special Notes and Features]]


user should consult the tables in this Appendix.
==Appendix A: Prob - the Input Problem Structure==
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
*[[TOMLAB Appendix A|Appendix A: Prob - the Input Problem Structure]]


solvers and driver routines.
==Appendix B: Result - the Output Result Structure==
Contains tables describing all elements defined in the output result structure returned from all solvers and driver routines.  
*[[TOMLAB Appendix B|Appendix B: Result - the Output Result Structure]]


'''Appendix D '''is concerned with the global variables used in TOMLAB and routines for handling important global
==Appendix C: TomSym - the Modeling Engine==
*[[TOMLAB Appendix C|Appendix C: TomSym - the Modeling Engine]]


variables enabling recursive calls of any depth.
==Appendix D: Global Variables and Recursive Calls==
This section is concerned with the global variables used in TOMLAB and routines for handling important global variables enabling recursive calls of any depth.  
*[[TOMLAB Appendix D|Appendix D: Global Variables and Recursive Calls]]


'''Appendix E '''describes the available set of interfaces to other optimization software, such as CUTE, AMPL,
==Appendix E: External Interfaces==
Describes the available set of interfaces to other optimization software, such as CUTE, AMPL, and The Mathworks' Optimization Toolbox.
*[[TOMLAB Appendix E|Appendix E: External Interfaces]]


and
==Appendix F: Motivation and Background to TOMLAB==
Gives some motivation for the development of TOMLAB.
*[[TOMLAB Appendix F|Appendix F: Motivation and Background to TOMLAB]]


The Mathworks' Optimization Toolbox.
==Appendix G: Performance Tests on Linear Programming Solvers==
*[[TOMLAB Appendix G|Appendix G: Performance Tests on Linear Programming Solvers]]


==Further  Reading==


TOMLAB  has been discussed in several papers and at several conferences. The main paper on TOMLAB  v1.0 is
<ref>
K. Holmström.
The TOMLAB Optimization Environment in Matlab.
''Advanced Modeling and Optimization'',
1(1):47-69, 1999.
</ref>
.
The use of TOMLAB  for nonlinear programming and parameter estimation is presented in
<ref>
K. Holmström and M. Björkman.
The TOMLAB NLPLIB Toolbox for Nonlinear Programming.
''Advanced Modeling and Optimization'',
1(1):70-86, 1999.
</ref>
, and the use of linear and discrete optimization is discussed in
<ref>
K. Holmström, M. Björkman, and E. Dotzauer.
The TOMLAB OPERA Toolbox for Linear and Discrete Optimization.
''Advanced Modeling and Optimization'',
1(2):1-8, 1999.
</ref>
. Global optimization routines are also implemented,  one is described in
<ref>
M. Björkman and K. Holmström.
Global Optimization Using the DIRECT Algorithm in Matlab.
''Advanced Modeling and Optimization'',
1(2):17-37, 1999.
</ref>.


'''Appendix F '''gives some motivation for the development of TOMLAB.
In all these papers TOMLAB  was divided into two toolboxes, the NLPLIB TB and the OPERA TB. TOMLAB  v2.0 was discussed in
<ref>
K. Holmström.
The TOMLAB v2.0 Optimization Environment.
In E. Dotzauer, M. Björkman, and K. Holmstöm, editors, ''Sixth Meeting of the Nordic Section of the Mathematical Programming Society''.
''Proceedings'', Opuscula 49, ISSN 1400-5468, Västerås, 1999. Mälardalen University, Sweden.</ref>
<ref>K. Holmström.
New Optimization Algorithms and Software.
''Theory of Stochastic Processes'',
5(21)(1-2):55-63, 1999.
</ref>
. and
<ref>
K. Holmström.
Solving applied optimization problems using TOMLAB.
In G. Osipenko, editor, ''Proceedings from MATHTOOLS  <nowiki>'</nowiki>99, the 2nd International Conference on Tools for Mathematical Modelling'',
pages 90-98, St.Petersburg,  Russia, 1999. St.Petersburg State Technical University.
</ref>
.  TOMLAB  v4.0 and how to solve practical optimization  problems  with TOMLAB  is discussed in
<ref>
K. Holmström. 
Practical Optimization  with the Tomlab Environment. 
In T. A. Hauge, B. Lie, R. Ergon, M. D. Diez, G.-O. Kaasa, A. Dale, B. Glemmestad, and A Mjaavatten, editors,
''Proceedings of the 42nd SIMS Conference'', 
pages 89-108, Porsgrunn, Norway, 2001. Telemark University College, Faculty of Technology.</ref>
.  


===Further  Reading===
The use of TOMLAB  for costly global optimization with industrial applications is discussed in  
 
<ref>
TOMLAB  has been discussed in several papers and at several conferences. The main paper on TOMLAB v1.0 is \[42\].  
M. Björkman and K. Holmström.   
 
Global Optimization  of Costly Nonconvex Functions Using Radial Basis Functions. ''Optimization and Engineering'',
The use of TOMLAB for nonlinear programming and parameter estimation is presented in \[45\], and the use of linear
1(4):373-397, 2000.
 
</ref>; costly global optimization with financial applications in
and discrete optimization is discussed in \[46\]. Global optimization routines are also implemented,  one is
<ref>
 
T. Hellström and K. Holmström.
described in \[8\].
Parameter Tuning in Trading Algorithms using ASTA.
 
In Y. S. Abu-Mostafa, B. LeBaron, A. W. Lo, and A. S. Weigend, editors, ''Computational Finance (CF99) - Abstracts of the Sixth International Conference, Leonard N. Stern School of Business, January 1999'', Leonard N. Stern School of Business, New York University, 1999. Department of Statistics and Operations Research.
In all these papers TOMLAB  was divided into two toolboxes, the NLPLIB TB and the OPERA TB. TOMLAB v2.0 was
</ref>
 
<ref>
discussed in \[43\], \[40\]. and \[41\]. TOMLAB  v4.0 and how to solve practical optimization  problems  with  
T. Hellström  and K. Holmström.
 
Parameter Tuning in Trading Algorithms using ASTA.
TOMLAB is discussed in \[44\].
In Y. S. Abu-Mostafa, B. LeBaron, A. W. Lo, and A. S. Weigend, editors, ''Computational Finance 1999'', Cambridge, MA, 1999. MIT Press.
 
</ref>
The use of TOMLAB  for costly global optimization with industrial applications is discussed in \[9\]; costly global
<ref>
 
T. Hellström and K. Holmström.  
optimization with financial applications in \[37, 38, 39\]. Applications of global optimization for robust control
Global Optimization of Costly Nonconvex Functions, with Financial Applications.
 
''Theory of Stochastic Processes'',
is presented in \[25, 26\]. The use of TOMLAB  for exponential fitting and nonlinear parameter estimation are  
7(23)(1-2):121-141, 2001.
 
</ref>. Applications of global optimization for robust control is presented in  
discussed in e.g. \[49, 4, 22, 23, 47, 48\].
<ref>
C. M. Fransson, B. Lennartson, T. Wik, and K. Holmström.
Multi Criteria Controller Optimization for Uncertain MIMO Systems Using Nonconvex Global Optimization.
In ''Proceedings of the 40th Conference on Decision and Control'', Orlando, FL, USA, December 2001.
</ref>
<ref>
C. M. Fransson, B. Lennartson, T. Wik, K. Holmström, M. Saunders, and P.-O. Gutmann.
Global Controller Optimization Using Horowitz Bounds.
In ''Proceedings of the 15th IFAC Conference'', Barcelona, Spain, 21th-26th July, 2002.
</ref>
. The use of TOMLAB  for exponential fitting and nonlinear parameter estimation are discussed in e.g.  
<ref>
K. Holmström and J. Petersson.
A Review of the Parameter Estimation Problem of Fitting  Positive Exponential Sums to Empirical Data.
''Applied Mathematics and Computations'',
126(1):31-61, 2002.
</ref>
<ref>
Jordan M. Berg and K. Holmström.  On Parameter Estimation Using Level Sets. ''SIAM Journal on Control and Optimization'', 37(5):1372-1393, 1999.
</ref>
<ref>
V. N. Fomin, K. Holmström,  and T. Fomina. 
Least squares and Minimax methods for inorganic chemical equilibrium analysis.
Research Report 2000-2, ISSN-1404-4978, 
Department  of Mathematics and Physics, Mälardalen University, Sweden, 2000.
</ref>
<ref>
T. Fomina, K. Holmström, and V. B. Melas.
Nonlinear parameter estimation for inorganic chemical equilib- rium analysis.
Research Report 2000-3, ISSN-1404-4978,
Department of Mathematics and Physics, Mälardalen University, Sweden, 2000.
</ref>
<ref>
K. Holmström and T. Fomina.
Computer Simulation for Inorganic Chemical Equilibrium Analysis.  In S.M. Ermakov, Yu. N. Kashtanov, and V.B.  Melas, editors, ''Proceedings  of the 4th St.Petersburg Workshop on''
''Simulation'', pages 261-266, St.Petersburg,  Russia, 2001.
NII Chemistry St. Peterburg University Publishers.
</ref>
<ref>
K. Holmström, T. Fomina, and Michael Saunders.
Parameter Estimation for Inorganic Chemical Equilibria by Least Squares and Minimax Models.
''Optimization and Engineering'', 4, 2003. Submitted.
</ref>
.


The manuals for the add-on solver packages are also recommended reading material.
The manuals for the add-on solver packages are also recommended reading material.


==Overall  Design==
==References==
 
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'''<hr />||||Type of optimization problem<hr />
|-
|'''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'''<hr />||'''probType'''<hr />||'''Description  of test problem set'''<hr />
 
|-
 
|'''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<hr/>||Purpose '''( ''o ''is any ''probSet'', e.g. ''o''='''con''')<hr/>
 
|-
 
|''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'')''/dx''2 .
 
|-
 
|''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'')''/dx''2
 
|-
 
|}
 
 
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 ''(''x''1 '', x''2 '', . . .''), 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.
 
<pre>
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);
</pre>
 
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
 
<pre>
ucSolve <==> nlp_f <==> ls_f <==> nlp_r <==> mgh_r
</pre>
 
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''.
 
<pre>
ucSolve <==> nlp_g <==> fdng <==> nlp_r <==> uc_f
</pre>
 
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:
 
<pre>
Prob.user.a=a;
Prob.user.B=B;
Prob.user.C=C;
</pre>
 
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:
 
<pre>
a = Prob.user.a;
B = Prob.user.B;
C = Prob.user.C;
</pre>
 
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'''<hr />||'''Description'''<hr/>
 
|-
 
|''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'')''/dx''2 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
 
 
<math>
\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}
</math>
 
 
where <math>$x, x_L, x_U \in \MATHSET{R}^n$</math> and <math>$f(x) \in \MATHSET{R}$</math> . For unbounded variables, the corresponding elements of <math>$x_L,x_U$</math> may be set to <math>$\pm \infty$</math>.
 
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
 
 
<math>
\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}
</math>
 
 
where <math>$c, x, x_L, x_U \in \MATHSET{R}^n$</math>, <math>$F \in \MATHSET{R}^{n \times n}$</math>, <math>$A \in \MATHSET{R}^{m_1 \times n}$</math>, and <math>$b_L,b_U \in \MATHSET{R}^{m_1}$</math>.
 
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
 
 
<math>
\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}
</math>
 
 
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
 
 
<math>
\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}
</math>
 
 
where <math>$x, x_L, x_U \in \MATHSET{R}^n$</math>, <math>$f(x) \in \MATHSET{R}$</math>, 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
 
 
<math>
\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}
</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>.
The variables <math>$x \in I$</math>, the index subset of <math>$1,...,n$</math>, 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
 
 
<math>
\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}
</math>
 
 
where <math>$c, x, x_L, x_U \in \MATHSET{R}^n$</math>,
<math>$A \in \MATHSET{R}^{m_1 \times n}$</math>, and <math>$b_L,b_U \in \MATHSET{R}^{m_1}$</math>.
 
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
 
 
<math>
\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}
</math>
 
 
where <math>$c, x, x_L, x_U \in \MATHSET{R}^n$</math>, <math>$A \in \MATHSET{R}^{m_1
\times n}$</math>, and <math>$b_L,b_U \in \MATHSET{R}^{m_1}$</math>. The variables <math>$x
\in I$</math>, the index subset of <math>$1,...,n$</math> are restricted to be
integers. Equality constraints are defined by setting the lower
bound equal to the upper bound, i.e. for constraint <math>$i$: $b_{L}(i)
=  b_{U}(i)$</math>.
 
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
 
 
<math>
\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}
</math>
 
 
where <math>$x, x_L, x_U \in \MATHSET{R}^n$</math>, <math>$d \in \MATHSET{R}^M$</math>,
<math>$C \in \MATHSET{R}^{M \times n}$</math>,
<math>$A \in \MATHSET{R}^{m_1 \times n}$, <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>.
 
 
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
 
 
<math>
\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}
</math>
 
 
where <math>$x, x_L, x_U \in \MATHSET{R}^n$</math>, <math>$r(x) \in \MATHSET{R}^M$</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>.
 
 
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
 
 
<math>
\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.
</math>
 
 
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.
<references />

Latest revision as of 08:59, 13 August 2011

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.

Overall Design

Overall Design presents the general design of TOMLAB.

Problem Types and Solver Routines

Contains strict mathematical definitions of the optimization problem types. All solver routines available in TOMLAB are described.

Defining Problems in TOMLAB

Solving Linear, Quadratic and Integer Programming Problems

Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.

Solving Unconstrained and Constrained Optimization Problems

Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.

Solving Global Optimization Problems

Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.

Solving Least Squares and Parameter Estimation Problems

Contains examples on the process of defining problems and solving them. All test examples are available as part of the TOMLAB distribution.

Multi Layer Optimization

Shows how to setup and define multi layer optimization problems in TOMLAB.

Tomhelp - The Help Program

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.

TOMLAB Solver Reference

TOMLAB Utility Functions

Describes the utility functions that can be used, for example tomRun and SolverList.

Approximation of Derivatives

Introduces the different options for derivatives, automatic differentiation.

Special Notes and Features

Discusses a number of special system features such as partially separable functions and user supplied parameter information for the function computations.

Appendix A: Prob - the Input Problem Structure

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: Result - the Output Result Structure

Contains tables describing all elements defined in the output result structure returned from all solvers and driver routines.

Appendix C: TomSym - the Modeling Engine

Appendix D: Global Variables and Recursive Calls

This section is concerned with the global variables used in TOMLAB and routines for handling important global variables enabling recursive calls of any depth.

Appendix E: External Interfaces

Describes the available set of interfaces to other optimization software, such as CUTE, AMPL, and The Mathworks' Optimization Toolbox.

Appendix F: Motivation and Background to TOMLAB

Gives some motivation for the development of TOMLAB.

Appendix G: Performance Tests on Linear Programming Solvers

Further Reading

TOMLAB has been discussed in several papers and at several conferences. The main paper on TOMLAB v1.0 is [1] . The use of TOMLAB for nonlinear programming and parameter estimation is presented in [2] , and the use of linear and discrete optimization is discussed in [3] . Global optimization routines are also implemented, one is described in [4].

In all these papers TOMLAB was divided into two toolboxes, the NLPLIB TB and the OPERA TB. TOMLAB v2.0 was discussed in [5] [6] . and [7] . TOMLAB v4.0 and how to solve practical optimization problems with TOMLAB is discussed in [8] .

The use of TOMLAB for costly global optimization with industrial applications is discussed in [9]; costly global optimization with financial applications in [10] [11] [12]. Applications of global optimization for robust control is presented in [13] [14] . The use of TOMLAB for exponential fitting and nonlinear parameter estimation are discussed in e.g. [15] [16] [17] [18] [19] [20] .

The manuals for the add-on solver packages are also recommended reading material.

References

  1. ↑ K. Holmström. The TOMLAB Optimization Environment in Matlab. Advanced Modeling and Optimization, 1(1):47-69, 1999.
  2. ↑ K. Holmström and M. Björkman. The TOMLAB NLPLIB Toolbox for Nonlinear Programming. Advanced Modeling and Optimization, 1(1):70-86, 1999.
  3. ↑ K. Holmström, M. Björkman, and E. Dotzauer. The TOMLAB OPERA Toolbox for Linear and Discrete Optimization. Advanced Modeling and Optimization, 1(2):1-8, 1999.
  4. ↑ M. Björkman and K. Holmström. Global Optimization Using the DIRECT Algorithm in Matlab. Advanced Modeling and Optimization, 1(2):17-37, 1999.
  5. ↑ K. Holmström. The TOMLAB v2.0 Optimization Environment. In E. Dotzauer, M. Björkman, and K. Holmstöm, editors, Sixth Meeting of the Nordic Section of the Mathematical Programming Society. Proceedings, Opuscula 49, ISSN 1400-5468, Västerås, 1999. Mälardalen University, Sweden.
  6. ↑ K. Holmström. New Optimization Algorithms and Software. Theory of Stochastic Processes, 5(21)(1-2):55-63, 1999.
  7. ↑ K. Holmström. Solving applied optimization problems using TOMLAB. In G. Osipenko, editor, Proceedings from MATHTOOLS '99, the 2nd International Conference on Tools for Mathematical Modelling, pages 90-98, St.Petersburg, Russia, 1999. St.Petersburg State Technical University.
  8. ↑ K. Holmström. Practical Optimization with the Tomlab Environment. In T. A. Hauge, B. Lie, R. Ergon, M. D. Diez, G.-O. Kaasa, A. Dale, B. Glemmestad, and A Mjaavatten, editors, Proceedings of the 42nd SIMS Conference, pages 89-108, Porsgrunn, Norway, 2001. Telemark University College, Faculty of Technology.
  9. ↑ M. Björkman and K. Holmström. Global Optimization of Costly Nonconvex Functions Using Radial Basis Functions. Optimization and Engineering, 1(4):373-397, 2000.
  10. ↑ T. Hellström and K. Holmström. Parameter Tuning in Trading Algorithms using ASTA. In Y. S. Abu-Mostafa, B. LeBaron, A. W. Lo, and A. S. Weigend, editors, Computational Finance (CF99) - Abstracts of the Sixth International Conference, Leonard N. Stern School of Business, January 1999, Leonard N. Stern School of Business, New York University, 1999. Department of Statistics and Operations Research.
  11. ↑ T. Hellström and K. Holmström. Parameter Tuning in Trading Algorithms using ASTA. In Y. S. Abu-Mostafa, B. LeBaron, A. W. Lo, and A. S. Weigend, editors, Computational Finance 1999, Cambridge, MA, 1999. MIT Press.
  12. ↑ T. Hellström and K. Holmström. Global Optimization of Costly Nonconvex Functions, with Financial Applications. Theory of Stochastic Processes, 7(23)(1-2):121-141, 2001.
  13. ↑ C. M. Fransson, B. Lennartson, T. Wik, and K. Holmström. Multi Criteria Controller Optimization for Uncertain MIMO Systems Using Nonconvex Global Optimization. In Proceedings of the 40th Conference on Decision and Control, Orlando, FL, USA, December 2001.
  14. ↑ C. M. Fransson, B. Lennartson, T. Wik, K. Holmström, M. Saunders, and P.-O. Gutmann. Global Controller Optimization Using Horowitz Bounds. In Proceedings of the 15th IFAC Conference, Barcelona, Spain, 21th-26th July, 2002.
  15. ↑ K. Holmström and J. Petersson. A Review of the Parameter Estimation Problem of Fitting Positive Exponential Sums to Empirical Data. Applied Mathematics and Computations, 126(1):31-61, 2002.
  16. ↑ Jordan M. Berg and K. Holmström. On Parameter Estimation Using Level Sets. SIAM Journal on Control and Optimization, 37(5):1372-1393, 1999.
  17. ↑ V. N. Fomin, K. Holmström, and T. Fomina. Least squares and Minimax methods for inorganic chemical equilibrium analysis. Research Report 2000-2, ISSN-1404-4978, Department of Mathematics and Physics, Mälardalen University, Sweden, 2000.
  18. ↑ T. Fomina, K. Holmström, and V. B. Melas. Nonlinear parameter estimation for inorganic chemical equilib- rium analysis. Research Report 2000-3, ISSN-1404-4978, Department of Mathematics and Physics, Mälardalen University, Sweden, 2000.
  19. ↑ K. Holmström and T. Fomina. Computer Simulation for Inorganic Chemical Equilibrium Analysis. In S.M. Ermakov, Yu. N. Kashtanov, and V.B. Melas, editors, Proceedings of the 4th St.Petersburg Workshop on Simulation, pages 261-266, St.Petersburg, Russia, 2001. NII Chemistry St. Peterburg University Publishers.
  20. ↑ K. Holmström, T. Fomina, and Michael Saunders. Parameter Estimation for Inorganic Chemical Equilibria by Least Squares and Minimax Models. Optimization and Engineering, 4, 2003. Submitted.
Retrieved from "http://tomwiki.com/index.php?title=TOMLAB&oldid=938"