SIMULTANEOUS LINEAR EQUATION IN TWO VARIABLE FOR CLASS TEN
free Algebra calculator for Rational Expression,
why use factoring to solve quadratic equations ,
multiplication division rational expressions problem solvers,
partial differential equation solution first order linear ,
addition and subtraction formulas solved problems ,
sat prep formulas square root,
online algebra calculator square root ,
solve quadratic equation for the specified variable ,
charts and graph on the comparison of substitution and linear combination ,
factorization fraction quadratic equations equation ,
Algebra help with factoring sums of cubes ,
Algebra, what are the difference between evaluation and simplification of an expression ,
algebra square cube roots interactive lessons ,
cube root calculator TI-83 plus how to do,
algebra square root solver ,
substitution method is easier than the addition method when one of the equations is very simple and can readily be solved for one of the variables ,
free solving equations with fractional coefficients help,
quadratic formula square root method ,
maple solve nonlinear multivariable two equations problems examples ,
free answers for comparing linear combination methods for solving systems of equation in a chart,
simplifying radicals absolute value ,
addition and subtraction of fractions worksheets lcd ,
ti 83 plus factoring complex number ,
Algebra expressions, what is the difference between evaluation and simplification of an expression?,
calculating a 3rd order polynomial with one variable ,
ti-89 convert number base 6 to number base 3 ,
algebra linear equations graphing worksheet ,
java code convert mixed fraction to decimal ,
math equations percent algebra formulas ,
java examples to find the number & sum of integers divisible by 7,
how to solve a 2nd order differential equations,
algebraic equation with fractional exponent ,
square root revision for calculator common entrance ,
solving solving binomial equations india
Thank you for visiting our site! You landed on this page because you entered a search term similar to this: simultaneous linear equation in two variable for class ten, here's the result:
Continuous Global Optimization Software: A Brief Review
János D. Pintér
(Reproduced by permission from: Optima 52 (1996), 1-8.)
1. Global Optimization Models and Solution Approaches
A large variety of quantitative decision issues, arising in the sciences,
engineering and economics, can be perceived and modelled as a constrained
optimization problem. According to this generic description, the best decision
often expressed by a real vector is sought which satisfies all stated
feasibility constraints and minimizes (or maximizes) the value of an objective
function. Applying standard mathematical programming notation, we shall
consider problems in the general form
The above formula in text format:
(1) min f(x) s.t. x belongs to a subset D of the Euclidean n-space
R^n.
The function f symbolizes the objective(s) in the decision problem,
and D denotes the (non-empty) set of feasible decisions. D is usually defined
by a finite number of functions; for the purposes of the present discussion,
we shall assume that
The above formula in text format:
(2) D={x is in R^n s.t. l<=x<=u; g_j(x)<=0 j=1,...,J}.
In (2) l and u are explicit (finite) bounds, and g j are given constraint
functions. Postulating now that all functions defined above are continuous,
the optimal solution set to problem (1)-(2) is non-empty. Most typically,
it is assumed that the decision problem modelled by (1)-(2) has a unique
locally and, at the same time, also globally optimal solution. Uniextremality
is often implied by the mathematical model structure (for example, by the
strict convexity of f, and the convexity of D). This paradigm corresponds
to the situation in which one, supposedly, has a sufficiently close initial
'guess' of the feasible region where the optimal solution x* is located.
Hence, the global optimality of the solution directly follows, having found
the single local optimum of f on D. For example, linear and convex nonlinear
programming models both, in essence, satisfying the mentioneduniextremality
assumption in most practical cases have been extensively applied in the
past decades to formulate and solve an impressive range of decision problems.
Although very important classes of models naturally belong to the above
category, there is also a broad variety of problems in which the property
of uniextremality cannot be simply postulated or verified. Consider, for
instance, the following general problem types:
nonlinear approximation, including the solution of systems of nonlinear
equations and inequalities
model fitting to empirical data (calibration, parameterization)
optimized design and operation of complex 'black box' ('oracle') systems,
e.g., in diverse engineering contexts
configuration/arrangement design (e.g., in various data classification,
facility location, resource allocation, or scientific modelling contexts)
Such problems together with numerous other prospective application
areas are discussed by Pintér (1996) and in the extensive list
of related references therein. For further applications consult, e.g.,
Pardalos and Rosen (1987), Törn and Zilinskas (1989), Floudas and
Pardalos (1990, 1992), Grossmann (1996), Bomze, Csendes, Horst and Pardalos
(1996), or special application-related issues of the Journal of Global
Optimization.
The emerging field of Global Optimization (GO) deals with mathematical
programming problems, in the (possible) presence of multiple local optima.
Observe that, typically, the number of local (pseudo)solutions is unknown
and it can be quite large. Furthermore, the quality of the various local
and global solutions may differ significantly. In the presence of such
structure often visualized by 'hilly landscapes' corresponding to projections
of the objective function into selected subspaces (given by coordinate-pairs
of the decision variable x) GO problems can be extremely difficult. Hence,
most classical numerical approaches are, generally speaking, not directly
applicable to solve them. For illustration, see Figure 1 which displays
a relatively simple composition of trigonometric functions with imbedded
polynomial arguments, in just two variables (denoted by x and y).
{At this point, a picture of the trigonometric function
0.2*[sin(x+4y)-2cos(2x+3y)-3sin(2x-y)+4cos(x-2y)]
is shown in the original article.}
Naturally, under such circumstances, it is essential to use a proper
global search strategy. Furthermore, instead of 'exact' solutions, most
typically one has to accept diverse numerical approximations to the globally
optimal solution (set) and optimum value.
Following early sporadic work related to GO (since the late fifties),
the present state-of-art is characterized by several dozen monographs,
a professional journal, and at least a few thousand research articles devoted
primarily to the subject. A few illustrative references are provided at
the end of this brief review.
The most important GO model-classes which have been extensively studied
include the following examples. (Please recall the general model form (1)-(2),
and note that the problem-classes listed below are not necessarily distinct;
in fact, several of them are hierarchically contained by more general problem-types
listed.)
Bilinear and biconvex programming (f is bilinear or biconvex, D is
convex)
Combinatorial optimization (problems which have discrete decision
variables in f and/or in g j can be equivalently reformulated as GO problems
in continuous variables)
Concave minimization (f is concave, D is convex)
Continuous global optimization (f is continuous, D is compact)
Differential convex (D.C.) optimization (f and g j can all be represented
as the difference of two corresponding convex functions)
Fractional programming (f is the ratio of two real functions, and
g j are convex)
Linear and nonlinear complementarity problems (f is the scalar product
of two vector functions, D is typically convex)
Lipschitz optimization (f and g j are arbitrary Lipschitz-continuous
functions)
Minimax problems (f is some minimax objective, the maximum is considered
over a discrete set or a convex set, D is convex)
Multilevel optimization (models non-cooperative games, involving hierarchies
of decision-makers, their conflicting criteria are aggregated by f; D is
typically assumed to be convex)
Multiobjective programming (e.g., when several conflicting linear
objectives are to be optimized over a polyhedron)
Multiplicative programming (f is the product of several convex functions,
and g j are convex, or more generally multiplicative functions) Naturally,
under such circumstances, it is essential to use a proper global search
strategy.
Network problems (f can be taken from several function-classes including
nonconvex ones, and g j are typically linear or convex)
Parametric nonconvex programming (the feasible region D and/or the
objective f may also depend on a parameter vector)
Quadratic optimization (f is an arbitrary indefinite quadratic
function; g j are linear or, in the more general case, can be arbitrary
quadratic functions)
Reverse convex programming (at least one of the functions g j expresses
a reverse convex constraint)
Separable global optimization (f is an arbitrary nonlinear in general,
nonconvex separable function, D is typically convex)
Various other nonlinear programming problems, including, e.g., nonconvex
stochastic models (in which the defining functions f, g j depend on random
factors, possibly in an implicit, 'black box' manner)
For detailed descriptions of most of these model-types and their connections
consult, e.g., Horst and Pardalos (1995), with numerous further references.
There are several main classes of algorithmic GO approaches which possess
strong theoretical convergence properties, and at least in principle
are straightforward to implement and apply. All such rigorous GO approaches
have an inherent computational demand which increases non-polynomially,
as a function of problem-size, even in the simplest GO instances. It should
be emphasized at this point that GO approaches are (should be) typically
completed by a 'traditional' local optimization phase at least when considering
also numerical efficiency issues. Global convergence, however, needs to
be guaranteed by the global-scope algorithm component which theoretically
should be used in a complete, 'exhaustive' fashion. These remarks indicate
the significant difficulty of developing robust and efficient GO software.
Without aiming at completeness, several of the most important GO strategies
are listed below; for details, consult, for instance, the corresponding
works from the list of references. (Note that the listing is not complete,
and its items are not necessarily mutally exclusive; some software implementations
combine ideas from several approaches.)
Adaptive partition and search strategies (including, e.g., branch-and-bound
algorithms, Bayesian approaches and interval arithmetic based methods)
(Forgó, 1988; Ratschek and Rokne, 1988; Mockus, 1989; Neumaier,
1990; Zhigljavsky, 1991; Hansen, 1992; Horst and Pardalos, 1995; Horst
and Tuy, 1996; Pintér, 1996; Kearfott, 1996)
Adaptive stochastic search algorithms (including random search, simulated
annealing, evolution and genetic algorithms) (van Laarhoven and Aarts,
1987; Zhigljavsky, 1991; Horst and Pardalos, 1995; Michalewicz, 1996; Pintér,
1996)
Enumerative strategies (for solving combinatorial problems, or certain
'structured' e.g., concave optimization problems) (Forgó, 1988;
Horst and Pardalos, 1995; Horst and Tuy, 1996)
'Globalized' local search methods (applying a grid search or random
search type global phase, and a local search algorithm) (Horst and Pardalos,
1995; Pintér, 1996) Heuristic strategies (deflation, tunneling,
filled function methods, approximate convex global underestimation, tabu
search, etc.) (Horst and Pardalos, 1995; Pintér, 1996)
Homotopy (parameter continuation) methods and related approaches (including
fixed point methods, pivoting algorithms, etc.) (Horst and Pardalos, 1995)
Passive (simultaneous) strategies (uniform grid search, pure random
search) (Zhigljavsky, 1991; Horst and Pardalos, 1995; Pintér, 1996)
Successive approximation (relaxation) methods (cutting plane, more
general cuts, minorant construction approaches, certain nested optimization
and decomposition strategies) (Forgó, 1988; Horst and Pardalos,
1995; Pintér, 1996)
Trajectory methods (differential equation model based, path-following
search strategies) (Horst and Pardalos, 1995)
In spite of a considerable progress related to the rigorous theoretical
foundations of GO, software development and 'standardized' use lag behind.
The main reason for this is, of course, the inherent numerical difficulty
of GO, even in the case of 'simpler' specific instances (such as, the indefinite
quadratic programming problem). In general, the difficulty of a global
optimization problem (GOP) can be expected to increase as some exponential
function of the problem dimension n. Consequently, dimensions 100, 50 or
even 10 can be considered as 'large', depending on the GOP type investigated.
In the remainder of this paper, an illustrative list of software products
to solve GOPs is reviewed.
2. GO Software: Information Sources and Some General Remarks
For the purposes of collecting information for this survey, GO software
authors have been asked (mainly by sending e-mail messages, and by placing
'electronic ads' at several prominent mathematical programming sites on
the WWW) to submit documentation related to their work. The information
or lack thereof summarized below is largely based on the responses
received. Additional information has been collected from the Internet,
from several GO books, and from the Journal of Global Optimization. Note
that though in many research publications reference is made to numerical
examples, or even to sophisticated specific applications, only such work
is reported below which is understood to be a general purpose and legally
distributable program system.
For obvious reasons, the present survey is far from being 'complete'
in any possible sense; rather, it is an attempt to provide a realistic
picture of the state-of-the-art, supported by instances of existing software.
This short review is not intended to be either comparative or 'judgemental':
one simple reason being that the information received from GO software
developers is used 'as is', mostly without the possibility of actual software
testing. By the same token, the accuracy of all information cannot be guaranteed
either. Further research in this direction including the preparation
of a more comprehensive and detailed survey is currently in progress.
The software list provided in the next section is simply alphabetical,
without categorization. For a more uniform presentation style, abbreviations
are associated with all software products listed, even when such names
were not given in the documentation available for this survey (existing
names were not changed, of course). The descriptions are almost formula-free
and extremely concise due to space restrictions. For the latter reason,
we decided not to include important classes of more specific GO approaches
and related methodology. In particular as reflected by the title pure
or mixed integer programming and more general combinatorial optimization
algorithms are not discussed here. Furthermore, although most of the available
top-of-the-line continuous nonlinear (convex) optimization software can
be applied with good taste and some luck to analyze GOPs, even the
most prominent such systems are excluded from this review. Again, a more
detailed survey is planned, appropriately discussing also the program system
types mentioned.
The hardware and software platform of the systems reviewed is also shown
when such information is available. In order to assist in obtaining additional
information, contact person(s), their e-mail addresses, ftp and/or WWW
sites are listed, whenever known to me. (For brevity, only a few such pointers
are provided in each case.)
The reader is assumed to have at least some basic familiarity with the
GO approaches mentioned; for related discussions, please consult the references.
3. Short Software Descriptions
\Alpha BB A GO Algorithm for General Nonconvex Problems
An implementation of a Branch-and-Bound (B&B) algorithm which is
based on the difference of convex functions (D.C.) transformation. Nonconvexities
are identified and categorized as of either special or generic structure.
Special nonconvex (such as bilinear or univariate concave) terms are convex
lower bounded using customized bounding functions. For generic nonconvex
terms, convex lower bounding functions are derived by utilizing the parameter
a (specified by the user or derived based on theory). aBB solves general
unconstrained and constrained problems; it requires MINOS and/or NPSOL
for the solution of linear or convex optimization subproblems. (Languages:
C and Fortran.) Contact:
ANNEAL Simulated Annealing
ANNEAL is based on the core SA approach, including several possibilities
for parameter adjustment and a deterministic solution refinement phase.
It has been applied to predict complex crystal structures. Workstation
implementation. Contact:
ASA CalTech Adaptive Simulated Annealing
ASA was developed to find the global optimum of a continuous non-convex
function over a multidimensional interval (box). This algorithm permits
an annealing schedule for 'temperature' decreasing exponentially in annealing
time. The introduction of re-annealing also permits adaptation to changing
sensitivities in the parameter-space. Some other adaptive options in ASA
include self-optimize (to find optimal starting conditions) and quenching
(to methodically find faster performance that might be useful for large
parameter-spaces). (Language: C.) Contact: L.
Ingber ,
#ASA-CODE.
B&B A Family of B&B Algorithms
This obvious acronym (by the present author) attempts to summarize several
B&B type algorithms developed to solve certain structured GOP classes.
These include (among others) indefinite quadratic, quasiconvex-concave,
and general Lipschitz problems. Workstation implementa-tions. (Language:
C.) Contact: R. Horst , M.
Nast , N.
Thoai .
BARON Branch-And-Reduce Optimization Navigator
Combines interval analysis and duality with enhanced B&B concepts.
The BARON modules can handle structured nonconvex problems up to thousands
of constraints and variables. The library of specialized modules includes
solvers for numerous specific GOP-classes. (For other, more general problems,
underestimation routines need to be provided by the user.) All modules
can solve also such problems in which some or all of the variables are
restricted to integer values. The specialized modules use OSL or MINOS
to solve interim subproblems. Workstations, UNIX type operating systems.
(Languages: Fortran and GAMS.) Contact: N.V. Sahinidis,
gma/ baron.html, .
BGO Bayesian Global Optimization
This program system includes four versions of Bayesian search, clustering,
uniform deterministic grid, and pure Monte Carlo search. Bound constraints
and more general constraints can be handled. Interactive DOS and UNIX versions
are available. (Languages: Fortran and C.) Contact: J.
Mockus , L.
Mockus .
cGOP Global Optimization Program
Solves structured GOPs which have an objective function of the form
a T x+b T y+x T Ay+f 1 (x)+f 2 (y) with convex f 1 , f 2 , and linear constraints.
Requires the presence of the commercial codes MINOS and/or CPLEX to solve
linear, mixed-integer linear and convex subproblems. cGOP has been used
to solve problems involving several hundred variables and constraints.
Versions are available for workstations. (Language: C.) Contact: .
CGU Convex Global Underestimator
This approach is designed to generate efficient approximations to the
global minimum of a multiextremal function, by fitting a convex function
to the set of all known (calculated) local minima. This heuristically attractive
strategy requires only the sequential solution of auxiliary LPs and some
rather elementary calculations. CGU has been applied to calculate molecular
structure predictions, up to several dozen variables. Implemented on parallel
workstations and supercomputers. Contact: K.A. Dill, A.T.
Phillips , J.B.
Rosen .
CRS Controlled Random Search
This is a recently developed variant of a popular class of random search
based methods which can be applied under very mild analytical conditions
imposed on the GOP. Several other related stochastic search methods have
also been developed by this group. Workstation implementations. Contact:
M.M. Ali, A. Törn ,
S. Viitanen .
CURVI Bound-Constrained Global Optimization
Windward Technologies (WTI) develops advanced numerical and visualization
software, for solving constrained and unconstrained nonlinear optimization
problems. One of their solvers, CURVI is aimed at solving bound-constrained
nonlinear programs which have a complicated possibly multiextremal
objective function. (Language: Fortran.) Contact: T.
Aird , .
DE Differential Evolution Genetic Algorithm for Bound Constrained
GO
DE won third place at the 1st International Contest on Evolutionary
Computation on a real-valued function test set. It was the best genetic
algorithm approach (the first two places of the contest were won by non-GA
algorithms). (Languages: Matlab and C.) Contact: R. Storn ,
storn/ code.html.
ESA Edge Searching Algorithm
An implementation of an edge search algorithm for finding the global
solution of linear reverse convex programs. ESA is based on an efficient
search technique and the use of fathoming criteria on the edges of the
polytope representing the linear constraints. In addition, the method incorporates
several heuristics, including a cutting plane technique which improves
the overall performance. Implemented for several UNIX platforms; the TPG
Test Problem Generator is also available. (Language: Fortran.) Contact:
K. Moshirvaziri ,
.
GA Genetic Algorithms
Genetic algorithms as a rule can be applied to GOPs under mild structural
requirements. Both general and specific information related to this popular
solver class is available from the following sources: A Commented List
of Genetic Algorithm Codes, ftp://
ftp.germany.eu.net/pub/research/softcomp/ec/faq/www/q20_1.htm GA
Archive,
alist/src/. Only a few illustrative examples are listed in the present
review.
GAS Genetic Algorithm
Unconstrained and bound-constrained versions are available. For DOS
and UNIX operating systems. (Language: C++.) Contact: . GAucsd
Genetic Algorithm
Developed and maintained at the University of California, San Diego.
GAucsd was written in C under Unix but should be easy to port to other
platforms. The package is accompanied by brief information and a User's
Guide. (Language: C.) Contact: .
GENERATOR Genetic Algorithm Solver
This method is aimed at solving a variety of (combinatorial and continuous
multiextremal) scientific and engineering optimization problems. It is
designed to interact with Excel which serves as a user interface. (Platform:
Excel.) Contact: New Light Industries
, .
GC Global Continuation
GC is a continuation approach to GO applying global smoothing in order
to derive a simpler approximation to the original objective function. GC
is applied by the authors to distance geometry problems, in the context
of molecular chemistry modelling. IBM SP parallel system implementation.
Contact: J.J.Moré ,
Z. Wu.
GENOCOP III Genetic Algorithm for Constrained Problems
Solves general GOPs, in the presence of additional constraints and bounds
(using quadratic penalty terms). System parameters, domains, and linear
inequalities are input via a data file. The objective function and any
nonlinear constraints are to be given in appropriate C files. (Language:
C.) Contact: Z. Michalewicz,
u/~zbyszek/gcreadme.html,
vol/genocopIII.tar.Z.
GEODES Minimum-Length Geodesic Computing
Approximating a minimum-length geodesic on a multidimensional manifold,
GEODES is differential geometry software. However, it has potential also
in the GO context. GEODES includes example manifolds and metrics; it is
implemented in Elements (a matrix and function oriented scientific modelling
environment) to compute and visualize geodesics on 2D surfaces plotted
in 3-space. Portable to various hardware platforms. (Languages: C, C++.)
Contact: .
GLO Global and Local Optimizer
GLO is a modular optimization system developed for 'black box' problems
in which objective function calculations may take a long time. Its methodology
is based on the coupling of global (genetic) and local (variable metric)
nonlinear optimization software with scientific applications software.
It has been applied to automated engineering design. Besides the modular
optimization control system, GLO also has a graphical user interface and
includes a preprocessor. Contact: M.J. Murphy,
, M. Brosius .
GLOBAL Multistart with Stochastic Clustering
GLOBAL can be used for the solution of the general bound-constrained
GOP which has a (measurable) real objective function. The algorithm is
a derivative-free implementation of the clustering stochastic multistart
method of Boender et al., supplemented with a quasi-Newton local search
routine and with a robust random local search method. Available for UNIX
machines, IBM-compatible mainframes and PCs. (Languages: Fortran and C.)
Contact: .
GLOBALIZER An Educational Program System for Global Optimization
Serves for solving univariate GOPs. After stating the problem, the user
can choose among various (random search, B&B based, or Bayesian partition
based) solver techniques. The software has interactive tutoring capabilities,
provides textual and graphical information. Works on PCs, under MS-DOS.
Contact: R.G. Strongin ,
V.P. Gergel, A.V. Tropichev.
GLOPT Constrained Global Optimization
Solves GOPs with a block-separable objective function subject to bound
constraints and block-separable constraints; it finds a nearly globally
optimal point that is near to a true local minimizer. GLOPT uses a B&B
technique to split the problem recursively into subproblems that are either
eliminated or reduced in their size. It includes a new reduction technique
for boxes and new ways for generating feasible points of constrained nonlinear
programs. The current implementation of GLOPT uses neither derivatives
nor simultaneous information about several constraints. (Language: Fortran.)
Contact: A. Neumaier ,
S. Dallwig and H. Schichl.
GOPP Global Optimization of Polynomial Problems using Gröbner
Bases
The (local) optimality conditions to polynomial optimization problems
lead to polynomial equations, under inequality constraints. Applying recent
Gröbner basis techniques, this approach is aimed at finding all solutions
to such systems, hence also finding global optima. (Language: Maple.) Contact:
.
GOT Global Optimization Toolbox
GOT combines random search and local (convex) optimization. DOS and
HP UX versions are available. (Language: Fortran.) Contact: A.V.
Kuntsevich . GOT Global Optimization Toolbox
GOT combines random search and local (convex) optimization. DOS and
HP UX versions are available. (Language: Fortran.) Contact: A.V.
Kuntsevich .
GSA Generalized Simulated Annealing
GSA is based on the generalized entropy by Tsallis. The algorithm obeys
detailed balance conditions and, at low 'temperatures', it reduces to steepest
descent. (Note that the members of the same research group have been involved
in the development of several SA type algorithms.) Contact:
IHR Improving Hit-and-Run
IHR is a random search based GO algorithm that can be used to solve
both continuous and discrete optimization problems. IHR generates random
points in the search domain by choosing a random direction and selecting
a point in that direction. Versions have been implemented, using different
distributions for the random direction, as well as several ways to randomly
select points along the search line. The algorithm can also handle inequality
constraints and a hierarchy of objective functions. IHR has been used to
solve GOPs in various disciplines such as in engineering design. Contact:
Z. Zabinsky ,
.
IMINBIS Interval Arithmetic Based GO
This method applies interval arithmetic techniques to isolate the stationary
points of the objective function. Next, a topological characterization
is used to separate minima from maxima and saddle points, followed by local
minimization (sub)searches to select the global solution. The method has
been applied also to 'noisy' problems. Workstation and PC implementations,
extensive related research. (Language: Fortran.) Contact: M.N.
Vrahatis , D.G.
Sotiropoulos , E.C. Triantaphyllou.
INTBIS Global Solver for Polynomial Systems of Equations
Finds all solutions of polynomial systems of equations, with rigorously
guaranteed results. The software package NTBIS is ACM-TOMS Algorithm 681;
it is available through NETLIB. Distributed with the package are four source
code files, sample input and output files, and a brief documentation file.
The source files consist of the following: interval arithmetic, stack management,
core INTBIS routines, and machine constants. (Language: Fortran.) Contact:
.
INTOPT_90 Verified (Interval) Global Optimization
Serves to the verified solution of nonlinear systems of equations and
unconstrained and bound-and-equality-constrained global optimization. Based
on exhaustive search, driven by a local optimizer, epsilon-inflation, interval
Newton methods, and interval exclusion principles; uses automatic differentiation.
Test results with hundreds of test examples. The underlying interval arithmetic
package (ACM TOMS Algorithm 737) is also distributed. Workstation and PC
implementations. (Language: Fortran.) Contact: .
INTGLO, INTGLOB Integral Global Optimization
These methods solve unconstrained and constrained, as well as discrete
GOPs by the integral method. They also include a discontinuous penalty
function approach for constrained problems. Problems up to one hundred
variables have been solved. A set of test problems is also available, including
box or unconstrained, constrained, concave minimization, discrete variable
programs and multicriteria programs. For IBM PCs. (Language: Fortran.)
Contact: Q. Zheng ,
D. Zhuang .
ISA Inductive Search Algorithm
ISA won first place at the 1st International Contest in Evolutionary
Computation on a real-valued function test-suite. (Language: C++.) Contact:
G. Bilchev, information available at h
ttp://solon.cma.univie.ac.at/~neum/glopt/test_results.html#bilchev.
LGO Continuous and Lipschitz Optimization
Solves bound-constrained and more general GOPs under mild structural
requirements; it can be applied also to 'black box' problems. LGO integrates
several global (adaptive partition and random search based) and local (conjugate
directions type) strategies: these can be activated in interactive or automatic
execution modes. The PC version has a menu interface to assist the application
development process, includes a concise information / tutoring session,
and has visualization capabilities. Available also for workstations. LGO
has been applied to problems with several 100 variables (and it can be
configured to encompass even larger sizes). Accompanied by a User's Guide
and sample problems. (Language: Fortran.) Contact: J.D.
Pintér , .
LOPS Lipschitz Optimization Program System
In all approaches listed below, the objective function is defined over
n-intervals. The Lipschitz-continuity of f or f' is also assumed. Problem-classes
and corresponding available versions include: one-dimensional GOPs (sequential
methods with local tuning, PC version (Language: C++) one-dimensional
GOPs, parallel solver implementations (Language: Alliant FX/80, parallel
Fortran) multi-dimensional GOPs: sequential and parallel algorithms using
Peano curves (Language: Alliant FX/80, parallel Fortran) Contact: Y.D.
Sergeyev .
MAGESTIC Data Fitting
Automatic global optimization based on a fast modified Gauss-Newton
approach combined with Monte Carlo search. MAGESTIC handles calibration
model variants (e.g., parameter and error masks for restricted sub-fitting,
implicit equation fitting without solving, etc.). Suitable for use also
with Lagrange multipliers for constrained optimization. Uses Excel as an
interface (under Windows) and for generating graphics. (Platform: Excel.)
Contact: Logix Consulting ,
.
MULTISTART Clustering Algorithm
This widely used approach is based on random search or some other
initial sampling in the feasible set combined with clustering and local
optimization launched from the most 'promising' point(s). Implemented on
SUN workstations. Several interesting applications in combination with
simulation models are related to the analysis of oil resources. (Language:
Fortran.) Contact: S. Buitrago .
UNICALC Interval Branch and Bound Algorithm
UNICALC serves for bound-constrained GO; accepts also inequality and/or
equality constraints and decision variables. Contact: A. Semenov, information
available at
lc.
VerGO Verified Global Optimization
VerGO is designed for rigorous bound (and approximate general constrained)
GO of a twice continuously differentiable objective function. VerGO features
include interval arithmetic, automatic differentiation, non-convexity test,
monotonicity test, and local optimization. Tested on problems up to over
30 variables. DOS, OS/2, Linux and workstation versions. (Language: C++.)
Contact: R. van Iwaarden ,
edu/~rvaniwaa/VerGO/VerGO.html.
VTT Interval Arithmetic Research
The goals of the Interval Arithmetic, Constraint Satisfaction and Probability
Project are summarized as follows: development of portable C++ libraries
for interval programming tasks; integration of the libraries to Microsoft
Excel; application in financial planning software products (Platforms:
C++, Excel.) Contact: S. De Pascale
, .
4. Acknowledgements
The software review presented here is based to a significant extent
on information kindly provided by colleagues working on GO and/or closely
related areas. I would like to especially thank Arnold Neumaier and Simon
Streltsov for the information collected on their WWW Global Optimization
Pages (respectively, http://
solon.cma.univie.ac.at/~neum/glopt/, and
). I also wish to thank Faiz Al-Khayyal for his valuable comments on the
manuscript.
The space (and time) limitations of this review certainly have made
it illusory to include 'all' existing software on this rapidly changing
area; omissions are entirely possible but absolutely unintentional. It
is planned to continue this work and to provide a more comprehensive and
informative picture of the state-of-the-art for the mathematical programming
community. Comments and suggestions are most welcome; they will contribute
to an 'unabridged' GO software review in the near future.
References
To avoid a superfluously long listing, the reference list is reduced
to the most topical journal, and to several GO monographs and handbooks
published in the past ten years.
Bomze, I.M., Csendes, T., Horst, R., and Pardalos, P.M., eds. (1996)
Developments in Global Optimization. Kluwer Academic Publishers, Dordrecht
/ Boston / London.
Floudas, C.A. and Pardalos, P.M. (1990) A Collection of Test Problems
for Constrained Global Optimization Algorithms. Lecture Notes in Computer
Science 455, Springer, Berlin / Heidelberg / New York.
Floudas, C.A. and Pardalos, P.M., eds. (1992) Recent Advances in Global
Optimization. Princeton University Press, Princeton.
Forgó, F. (1988) Nonconvex Programming. Akadémiai Kiadó,
Budapest.
Grossmann, I.E., ed. (1996) Global Optimization in Engineering Design.
Kluwer Academic Publishers, Dordrecht / Boston / London.
Hansen, E.R. (1992) Global Optimization Using Interval Analysis. Marcel
Dekker, New York.
Horst, R. and Tuy, H. (1996) Global Optimization - Deterministic Approaches.
Springer, Berlin / Heidelberg / New York. (3rd Edn.)
Horst, R. and Pardalos, P.M., eds. (1995) Handbook of Global Optimization.
Kluwer Academic Publishers, Dordrecht / Boston / London.
Journal of Global Optimization (published since 1991,
Publishers).
Kearfott, R.B. (1996) Rigorous Global Search: Continuous Problems. Kluwer
Academic Publishers, Dordrecht / Boston / London.
Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution
Programs. Springer, Berlin / Heidelberg / New York. (3rd Edn.)
Mockus, J. (1989) Bayesian Approach to Global Optimization. Kluwer Academic
Publishers, Dordrecht / Boston / London.
Neumaier, A. (1990) Interval Methods for Systems of Equations. Cambridge
University Press, Cambridge.
Pardalos, P.M. and Rosen, J.B. (1987) Constrained Global Optimization:
Algorithms and Applications. Lecture Notes in Computer Science 268, Springer,
Berlin / Heidelberg / New York.
Pintér, J.D. (1996) Global Optimization in Action. Kluwer Academic
Publishers, Dordrecht / Boston / London.
Ratschek, H. and Rokne, J.G. (1988) New Computer Methods for Global
Optimization. Ellis Horwood, Chichester.
Törn, A.A. and Zilinskas, A. (1989) Global Optimization. Lecture
Notes in Computer Science 350, Springer, Berlin / Heidelberg / New York.
Van Laarhoven, P.J.M. and Aarts, E.H.L. (1987) Simulated Annealing:
Theory and Applications. Kluwer Academic Publishers, Dordrecht / Boston
/ London.
Zhigljavsky, A.A. (1991) Theory of Global Random Search. Kluwer Academic
Publishers, Dordrecht / Boston / London.
