Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

AMPL-LGO User's Guide Written by Janos D. Pinter Pinter Consulting Services, In

AMPL-LGO User's Guide Written 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) continuous functions, even without smoothness requirements. Therefore LGO is particularly suitable to handle optimization models in which the available analytical information may be limited to computable function values, in the possible presence of a multi-extremal model structure. For a more detailed description of LGO, consult Pinter (1996, 2002, 2009). Registered AMPL-LGO users have access also to the current LGO user guide (Pinter Consulting Services, 2014). This document discusses the following topics: - Global vs. Local Optimization - The LGO Program System - LGO Solver Options - LGO Program Structure - Connectivity to Modeling Environments - LGO Input and Output Information: Model Formulation, Solution and Result Analysis - Model Development and Solution Tips - LGO Benchmarking Test Results, Applications and Peer Reviews - References Hence, it can be a useful added source of information for AMPL-LGO users. Primary AMPL-LGO technical support is offered by AMPL Optimization, contact: support@ampl.com. For all specific questions, related to the LGO solver suite, contact: janos.d.pinter@gmail.com. 3) Getting Started with AMPL The following description refers primarily to using AMPL and uploads/Voyage/ lgo-guide.pdf