Case
LGO_guide
- Module
- Amplide
- Institution
- Abacus College, Oxford
Case of 19 pages for the course Amplide at Abacus College, Oxford (LGO_guide)
[Show more]
Seller
Follow
Content preview
AMPL-LGO User's GuideWritten by
Janos D. Pinter
Pinter Consulting Services, Inc.
Contributions by
David M. Gay
AMPL Optimization, Inc.
Current document version: 2015-01-09
(C) COPYRIGHT NOTICE
AMPL - A Modeling Language for Mathematical Programming
(C) AMPL Optimization, Inc., www.ampl.com
LGO Solver Suite for Global and Local Nonlinear Optimization
(C) Pinter Consulting Services, Inc., www.pinterconsulting.com
All rights reserved.
Please contact Janos D. Pinter at janos.d.pinter@gmail.com if you wish
to cite or use the contents of this document in any form.
1) AMPL
AMPL is a language for mathematical programming that greatly facilitates
the formulation of optimization models and the generation of the requisite
computational data structures. AMPL enables optimization model development
in a natural, concise, and scalable fashion; it also supports the seamless
invocation of various solver engines to handle the resulting optimization
models.
AMPL integrates a modeling language for describing a model consisting of
variables, objectives, and constraints, all of which may involve sets and
parameters that can be supplied separately; facilities for supplying data
(values for sets and parameters in the model); a command language for
browsing models and analyzing results; and a scripting language for
gathering and manipulating data and for implementing iterative optimization
schemes. All listed language components use the same concepts and syntax
for streamlined application development, testing, deployment, and
maintenance.
AMPL has been extensively documented elsewhere. Therefore here we refer
only to the AMPL book by Fourer, Gay, and Kernighan (2003) - as the
primary source of information - and to the website of AMPL Optimization,
Inc., www.ampl.com.
From this website you can download a fully functional free AMPL trial
version, with model size limitations set by AMPL Optimization, as well
as all chapters of the AMPL book (in PDF file format).
Let us note that the AMPL trial version already supports the development
and exploration of non-trivial nonlinear optimization models.
,The AMPL software product is supported by AMPL Optimization, Inc. To
obtain a licensed copy of AMPL, contact info@ampl.com. All questions
related to AMPL should also be sent to info@ampl.com.
2) Nonlinear Optimization Using LGO
LGO is an integrated solver suite for general constrained nonlinear -
global and local - optimization (NLO). Here we present a short formal
introduction to the subject of NLO, and motivate the usage of a
global-local NLO tool as an AMPL solver engine option.
A large variety of quantitative decision problems in the applied sciences,
engineering and economics can be described by constrained optimization
models. In such models, the best decision is sought that satisfies all
stated feasibility constraints and minimizes or maximizes the value of
a given objective function.
A generic constrained optimization model can be concisely stated as follows.
(1) minimize f(x) s.t. x belongs to the feasible set D.
Here x is an n-vector of the real space R^n, and f is a scalar-valued
objective function, f: R^n -> R.
The set D is defined by box constraints and optionally defined general
constraints.
(2) D={x: l <= x <= u, g(x) <= 0}.
In (2) the vector inequalities are interpreted component-wise: both l and
u are n-vectors of R^n and g denotes an m-vector function g: R^n -> R^m.
Man-made objects and (manufacturing, transportation, distribution, crew
assignment, etc.) systems often can be described by linear models - at
least in their basic, without consideration given, e.g., to possible
yes/no decisions, nonlinear functional relations, stochastic system
features, and inherent fluctuations. In such cases, all model functions
f and g are assumed to be linear.
Natural - physical, chemical, biological, geological, environmental - as
well as economic and societal systems are frequently characterized by
nonlinear functional relations. Nonlinear decision models built upon such
a description could possess multiple optima. In such multi-modal scenarios
both the number and the quality of these (sub-)optima are often unknown.
Hence, it is natural to consider optimization strategies that enable
global scope search for the best possible numerical solution.
Obviously, linear models can be viewed as a specal case of the vast NLO
model-class. After suitable reformulation, the entire range of combinatorial
optimization models can be seen as NLO - namely, global optimization -
problems. (This fact per se hints at the theoretical complexity and
potential numerical challenge of solving global NLO model instances).
For the purposes of the present discussion, we will tacitly assume that in
(1)-(2) at least some of the model functions f, g are nonlinear. We will
also assume that all model functions f and g_1,...,g_m are continuous over
the finite box-constrained region [l, u], and that the set D is non-empty.
The set of box constraints is required, but the general constraints g may
, be absent.
Due to the generality of model (1)-(2), the corresponding model-class
includes many difficult instances. Some models can be highly nonlinear,
and - as a consequence - may have locally optimal solutions, in addition
to their true (global) solution(s).
The above postulated key analytical assumptions guarantee that the globally
optimal solution set X* of model (1)-(2) is non-empty. In other words, there
exists a solution set X* (a subset of D) such that for all pairs (x*,x),
where x* is chosen from X* and x is chosen from D, the relation f(x*) <= f(x)
is valid. In most well-posed, practically motivated NLO models - arguably
including the majority of real-world applications - X* consists only of a
single globally optimal solution vector x*. There are exceptions, however
when multiple global optima exist: in such cases additional considerations
may be needed to choose among these solutions.
In contrast to the definition of global optimality, a locally optimal solution
x*_l is the best solution of model (1)-(2) with respect to (only) a certain
neighbourhood of x*_l. Such a neighbourhood (a suitable subset of D) can be
defined, e.g., by the intersection of a sufficiently small n-sphere S(x*_l)
centered at x*_l and of the feasible set D.
Traditional local scope nonlinear solvers will only find the absolutely best
solution x* in an optimization model if launched from a point that lies in
the 'basin of attraction' B(x*) of the global solution. Since a 'sufficiently
close guess' of the global solution is not always available, local scope
NLO methods - in general - can not guarantee the finding of x* (elements of
X*) in highly nonlinear systems. We will illustrate this point later on by
numerical examples.
There exists a significant body of professional literature devoted to global
and/or local NLO. Global NLO is typically referred to as global optimization
(GO), while traditionally NLO was meant to deal with the topic of continuous
local optimization (LO). The most notable category of LO problems is convex
optimization and its generalizations: here all functions f and g are convex
or generalized convex functions, respectively.
To address the proper handling of - verifiably or potentially - multi-modal
optimization problems, the LGO solver suite seamlessly integrates a suite of
global and local search options. The acronym LGO abbreviates 'Lipschitz
Global Optimizer'. This name corresponds to the initially developed (first)
global solver component in LGO: over the years other algorithmic strategies
have been added, including space-covering sampling, stochastic search and
local constrained optimization methods.
For an in-depth discussion of the theory and algorithms that serve as the
basis of the globally convergent solver components in LGO, consult Pinter
(1996). For discussions of GO software, tests and a range of applications
cf. Pinter (1996, 2002, 2006, 2009), with many further references therein.
These references mostly focus on the more recent research area of GO. Local
scope NLO (LO) has been studied for a longer time, definitely so since the
beginnings of modern Operations Research, and there exist many good topical
books and other resources. The present discussion is mostly devoted to GO.
The LGO solver suite can be used in a stand-alone mode, without relying on
other solvers. LGO works directly with computable model function values,
without a requirement for using higher order (gradient, Hessian,...) analytical
information. As a rule, LGO will work robustly for models defined by (merely)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller 1097434525U. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
85443 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now