Table of Contents
János D. Pintér, Pintér Consulting Services, Inc. Halifax, NS, Canada, B3M 1J2 email@example.com@.firstname.lastname@example.org@email@example.com@m.a, http://www.pinterconsulting.com
The Lipschitz-Continuous Global Optimizer 1) (LGO) 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 small LP models.
GAMS/LGO can be used in several search modes, providing a robust, effective, and flexible solver suite approach to a broad range of nonlinear models. The solver suite approach increases the reliability of the overall solution process. GAMS/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:
- Heuristic global scope scatter search method (HSS)
- Bound-constrained local search, based on the use of an exact penalty function (EPM)
- Constrained local search, based on sequential model linearization (SLP)
- Constrained local search, based on a generalized reduced gradient approach (GRG).
The overall solution approach followed by GAMS/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.
GAMS/LGO does not rely on any sub-solvers, and it does not require any 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. GAMS/LGO needs only computable function values (without a need for higher order analytical information). GAMS/LGO can even solve models having constraints involving continuous, but non-differentiable functions. Thus, within GAMS, LGO is well suited to solve DNLP models.
GAMS/LGO can also be used in conjunction with other GAMS solvers. For instance, the local solver CONOPT can be used after LGO is finished to verify the solution and/or to provide additional information such as marginal values. To call CONOPT, the user can specify the LGO solver option 'callConopt'. See the LGO Options section for details.
The LGO solver suite has been successfully applied to complex, large-scale models both in educational/research and commercial contexts for over a decade. Possible application areas include advanced engineering design, econometrics and finance, medical research and biotechnology, chemical and process industries, and scientific modeling. Tractable model sizes depend only on the available hardware, although LGO has a 3000 variable, 2000 constraint size limit.
For more information, we refer to
- GAMS/LGO Nonlinear Solver Suite: Key Features, Usage, and Numerical Performance
- Nonlinear Optimization with GAMS/LGO (2006)
GAMS/LGO is capable of solving the following model types: LP, RMIP, NLP, and DNLP. If LGO is not specified as the default solver for these models, it can be invoked by issuing the following command before the solve statement:
option (modeltype) = lgo;
(modeltype) stands for
LP, RMIP, NLP, or
GAMS/LGO works like other GAMS solvers, and many options can be set directly within the GAMS model. The most relevant GAMS options are
reslim, iterlim, and
optfile. For details on these and other options, see the section on GAMS Options.
In addition, LGO-specific options can be specified by using a solver option file. For details on creating and using solver options files, see the section basic option file usage. The options supported by the GAMS/LGO solver are detailed below.
Note that the local search operational mode (
opmode 0) is the fastest, and that it will work for convex, as well as for some 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. 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 would be the case using the defaults.
The GAMS/LGO log file gives much useful information about the current solver progress and its individual phases. To illustrate, we use the nonconvex model
mhw4d.gms from the GAMS model library:
$Title Nonlinear Test Problem (MHW4D,SEQ=84) $Ontext Another popular testproblem for NLP codes. Wright, M H, Numerical Methods for Nonlinearly Constrained Optimization. PhD thesis, Stanford University, 1976. $Offtext Variables m, x1, x2, x3, x4, x5; Equations funct, eq1, eq2, eq3; funct.. m =e= sqr(x1-1) + sqr(x1-x2) + power(x2-x3,3) + power(x3-x4,4) + power(x4-x5,4) ; eq1.. x1 + sqr(x2) + power(x3,3) =e= 3*sqrt(2) + 2 ; eq2.. x2 - sqr(x3) + x4 =e= 2*sqrt(2) - 2 ; eq3.. x1*x5 =e= 2 ; Model wright / all / ; x1.l = -1; x2.l = 2; x3.l = 1; x4.l = -2; x5.l = -2; Solve wright using nlp minimizing m;
Note that the solution given by LGO (shown on the next page) corresponds to the global minimum. For comparison, note that local scope nonlinear solvers will not find the global solution, unless started from a suitable neighbourhood (i.e., the model- and solver-specific region of attraction) of that solution.
In this example we use an option file to print out log information every 500 iterations, regardless of the elapsed time. Note that we set the
log_time option to 0 to ignore the
LGO 1.0 May 15, 2003 LNX.LG.NA 21.0 001.000.000.LXI Lib001-030502 LGO Lipschitz Global Optimization (C) Pinter Consulting Services, Inc. 129 Glenforest Drive, Halifax, NS, Canada B3M 1J2 E-mail : firstname.lastname@example.org Website: www.dal.ca/~jdpinter --- Using option file C:/GAMSPROJECTS/LGODOC/LGO.OPT > log_iter 500 > log_time 0 3 defined, 0 fixed, 0 free 6 +/- INF bound(s) have been reset 1 LGO equations and 3 LGO variables
The first part prints out information about the model size after presolve. In this particular problem, the original model had 4 rows, 6 columns, and 14 non-zeroes, of which 3 were defined constraints, meaning that they could be eliminated via GAMS/LGO presolve techniques. Note that none of these were fixed or free constraints. Furthermore, LGO presolve reduced the model size further to 1 row (LGO equations) and 3 columns (LGO variables).
The main log gives information for every n iterations about current progress. The main fields are given in the table below:
|Current objective function value.|
|Sum of constraint infeasibilities.|
|Maximum constraint infeasibility.|
|Current elapsed time in seconds.|
|Number of errors and type. Type can either be |
D/E: Evaluation error
B: Bound violation.
Iter Objective SumInf MaxInf Seconds Errors 500 4.515428E-01 5.76E-02 5.8E-02 0.007 1000 6.700705E-01 5.03E-05 5.0E-05 0.014 1500 2.765930E+00 6.25E-04 6.2E-04 0.020 2000 2.710653E+00 1.55E-02 1.6E-02 0.026 2500 4.016702E+00 1.44E-02 1.4E-02 0.032 3000 4.865399E+00 2.88E-04 2.9E-04 0.038 3500 4.858826E+00 3.31E-03 3.3E-03 0.044 4000 1.106472E+01 1.53E-02 1.5E-02 0.050 4500 1.595505E+01 1.56E-06 1.6E-06 0.055 5000 1.618715E+01 2.17E-05 2.2E-05 0.062 5500 1.618987E+01 3.45E-04 3.5E-04 0.067 6000 1.985940E+01 4.03E-04 4.0E-04 0.074 6500 1.624319E+01 5.64E-03 5.6E-03 0.079 7000 1.727653E+01 8.98E-05 9.0E-05 0.086 7500 1.727033E+01 3.03E-03 3.0E-03 0.091 7840 2.933167E-02 0.00E+00 0.0E+00 0.097
LGO then reports the termination status, in this case globally optimal, together with the solver resource time. The resource time is also disaggregated by the total time spent performing function evaluations and the number of milliseconds (ms) spent for each function evaluation.
--- LGO Exit: Terminated by solver - Global solution 0.047 LGO Secs (0.015 Eval Secs, 0.001 ms/eval)
A local solver such as CONOPT can be called to compute marginal values. To invoke a postsolve using CONOPT, the user specifies the
callConopt option with a positive value, indicating the number of seconds CONOPT is given to solve. See the LGO Options section for details.
R. Horst and P. M. Pardalos, Editors (1995) Handbook of Global Optimization. Vol. 1. Kluwer Academic Publishers, Dordrecht.
P. M. Pardalos and H. E. Romeijn, Editors (2002) Handbook of Global Optimization. Vol. 2. Kluwer Academic Publishers, Dordrecht.
J. D. Pintér (1996)Global Optimization in Action , Kluwer Academic Publishers, Dordrecht.
J. D. Pintér (2001)Computational Global Optimization in Nonlinear Systems: An Interactive Tutorial, Lionheart Publishing, Atlanta, GA.
J. D. Pintér (2002) Global optimization: software, tests and applications. Chapter 15 (pp. 515-569) in:Pardalos and Romeijn, Editors, Handbook of Global Optimization. Vol. 2. Kluwer Academic Publishers, Dordrecht.