LGO

Introduction

Overview

Welcome to the TOMLAB /LGO User's Guide. TOMLAB /LGO includes the LGO solver from Pintér Consulting Services and an interface to MATLAB, by MathWorks.

The Lipschitz-Continuous Global Optimizer (LGO) solver suite serves for the analysis and global solution of general nonlinear programming (NLP) models. The LGO solver system has been developed and gradually extended for more than a decade and it now incorporates a suite of robust and efficient global and local nonlinear solvers. It can also handle smaller LP models. LGO is documented elsewhere in detail: see for example, Pintér (1996, 2001, 2003). $1, 2, 3$ TOMLAB /LGO integrates the following global scope algorithms:

• Branch-and-bound (adaptive partition and sampling) based global search (BB)
• Adaptive global random search (GARS)
• Adaptive multistart global random search (MS) LGO also includes the following local solver strategies:
• Constrained local search, based on a generalized reduced gradient approach (GRG).

The overall solution approach followed by TOMLAB /LGO is based on the seamless combination of the global and local search strategies. This allows for a broad range of operations. In particular, a solver suite approach supports the flexible usage of the component solvers: one can execute fully automatic (global and/or local search based) optimization, and can design customized interactive runs.

TOMLAB /LGO does not rely on any sub-solvers, and it does not require any in-depth structural information about the model. It is particularly suited to solve even 'black box' (closed, confidential), or other complex models, in which the available analytical information may be limited. TOMLAB /LGO needs only computable function values (without a need for higher order analytical information). TOMLAB /LGO can even solve models having constraints involving continuous, but non-differentiable functions. Thus, within TOMLAB, LGO is well suited to solve nonlinear - global and convex - optimization models.

TOMLAB /LGO can also be used in conjunction with other TOMLAB solvers. Local solvers (when available) can be used to verify the solution found by LGO, and to provide additional local information.

Prerequisites

In this concise manual we assume that the user is familiar with global optimization and nonlinear programming, setting up problems in TOMLAB (in particular global constrained nonlinear (glc) problems) and with the Matlab language in general.

Using the Matlab Interface

The LGO solver package is accessed via the tomRun driver routine, which calls the lgoTL interface routine. The solver itself is located in the MEX file lgo.

The interface routines.
FunctionDescription
lgoTLThe interface routine called by the TOMLAB driver routine tomRun.

This routine then calls the MEX file lgo

Setting LGO Options

All control parameters can be set directly from Matlab.

Setting options using the Prob.LGO structure

The parameters can be set as subfields in the Prob.LGO structure. The following example shows how to set a limit on the maximum number of merit function evaluations before termination of global search phase.

Prob = glcAssign(...)                     %   Setup problem,  see help  glcAssign for  more information
Prob.LGO.options.g_maxfct  = 10000;       %   Setting the maximum number of  global search
%   phase model function evaluations.


In the cases where a solver specific parameter has a corresponding TOMLAB general parameter, the latter is used only if the user has not given the solver specific parameter.

A complete description of the available LGO parameters can be found in #lgoTL.

LGO Test Examples

There are several LGO test examples included in the TOMLAB /LGO distribution. The examples are located in the testprob folder in TOMLAB. lgo1 prob contains one dimensional test problems while lgo2 prob includes two- and higher-dimensional.

To test the solution of these problem sets by LGO, the following type of code can be used:

Prob = probInit('lgo1_prob', 1); Result  = tomRun('lgo', Prob,  1);


It is also possible to run all the problems located in glb prob and glc prob if no integer variables are defined.

LGO Solver Reference

A detailed description of the TOMLAB /LGO solver interface is given below. Also see the M-file help for lgoTL.m.

lgoTL

Purpose

Solves global and local (convex and mildly non-convex) constrained nonlinear programming problems. LGO solves problems of the form

$\begin{array}{ccccccl} \min\limits_{x} & f(x) & \\ \\ s/t & x_L & \leq & x & \leq & x_U & \\ {} & b_L & \leq & Ax & \leq & b_U & \\ {} & c_L & \leq & c(x) & \leq & c_U & \\ \end{array}$

where $x,x_L,x_U \in R^{n},\, A \in R^{m_1 \times n},\, b_L,b_U \in R^{m_1}$ and $c(x), c_L, c_U \in R^{m_2}$.

Calling Syntax

Prob = glcAssign( ... );
Result = tomRun('lgo',Prob,...);


Description of Inputs

Prob Problem description structure. The following fields are used:

InputDescription
ALinear constraints coefficient matrix.
x L, x_UBounds on variables.
b_L, b_UBounds on linear constraints.
c_L, c_UBounds on nonlinear constraints. For equality constraints (or fixed variables), set e.g. b L(k) == b U(k).
PriLevOptPrint level in MEX interface.
optParam.MaxFuncMaximum number of function evaluations. (Prob.LGO.options.g_maxfct)
LGO.PrintFileName of LGO Print file. Amount and type of printing determined by PriLevOpt.
LGO.SummFileName of LGO summary file.
LGO.optionsStructure with special fields for LGO optimization parameters. See #Description of Prob.LGO.options

Description of Outputs

Result Structure with result from optimization. The following fields are set:

OutputDescription
f_kFunction value at optimum.
x_kSolution vector.
x_0Initial solution vector.
c_kNonlinear constraint residuals.
xStateState of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bStateState of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
cStateState of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
AxValues of linear constraints.
ExitFlagExit status from LGO (TOMLAB standard).
ExitTextExit text from LGO.
InformLGO information parameter.

1 = Normal completion.

2 = Iteration interrupt.

3 = Time limit exceeded.

4 = Terminated by solver.

7 = Size limitation.

Other = Optimal solution found.

FuncEvNumber of function evaluations.
ConstrEvNumber of constraint evaluations. In the context of LGO, ConstrEv = FuncEv.
QP.BBasis vector in TOMLAB QP standard.
SolverName of the solver (LGO).
SolverAlgorithmDescription of the solver.
LGOSubfield with LGO specific results.
sstatSolver status.
mstatModel status.
runtimeTime spent, measured by LGO solver.

The following table shows all the options that the user can set for the solver. The TOMLAB /LGO options are divided into two main categories:

• General options
• Limits and tolerances

Description of Prob.LGO.options

User options for the TOMLAB /LGO solver. The following fields are used:

OptionDescriptionDefault
General options
opmodeSpecifies the algorithm to be used.3
0Local search from the given nominal solution without a preceding local search (LS)
1Global branch-and-bound search and local search (BB+LS)
2Global adaptive random search and local search (GARS+LS)
3Global multistart random search and local search (MS+LS)

Note that an option of 0 will work for many slightly nonconvex, as well as convex models. See note below this table.

tlimitTime limit in seconds.600
Limits and Tolerances
g_maxfctMaximum number of merit function evaluations before termination of global search phase (BB, GARS, or MS). The value of -1 uses 500(nvars+ncons), where nvars is the number of variables and ncons the number of constraints.

The difficulty of global optimization models varies greatly: for difficult models, g_maxfct can be increased as needed.

-1
l_maxfct Maximal number of function evaluations in local search phase.
max_nosucMaximum number of merit function evaluations in global search phase (BB, GARS, or MS) where no improvement is made. Global search terminates upon reaching this limit. The value of -1 uses 100(nvars+ncons), where nvars is the number of variables and ncons the number of constraints. For difficult models, this value can also be increased as deemed necessary.-1
penmultConstraint penalty multiplier. Global search phase merit function is defined as objective + the violated constraints weighted by penmult.100
g_targetGlobal search termination criterion parameter (acceptability threshold). The global search phase (BB, GARS, or MS) ends, if an overall merit function value found in the global search phase is less than g_target. If a good estimate is known, then its usage may results in a considerably faster search.-1.0E+10
l_targetTarget merit function value in local search phase.-1.0E+10
fi_tolLocal search merit function improvement tolerance.1.0E-06
con_tolMaximal admissible constraint violation in local search.1.0E-06
kt_tolKuhn-Tucker local optimality condition tolerance.1.0E-06
irngsRandom number seed. An arbitrary integer value can be used instead of the 0 default.

Note that the local search operational mode (opmode 0) is the fastest, and that it will work for convex, as well as for many mildly non-convex models. If the model has a highly non-convex (multiextremal) structure, then at least one of the global search modes should be used. In difficult or complex models, it may be a good idea to apply all three global search modes, to verify the global solution, or perhaps to find alternative good solutions. Usually, opmode 3 is the safest (and slowest), since it applies several local searches; opmodes 1 and 2 launch only a single local search from the best point found in the global search phase.

Note that if model-specific information is known (more sensible target objective/merit function value, tolerances, tighter variable bounds), then such information should always be used, since it may help to solve the model far more efficiently than by using 'blind' defaults