| |
Abstract:
Semi-infinite programming (SIP) problems are
characterized by having a finite number of
variables to be optimized subject to an infinite
number of constraints. SIP problems appear in
several engineering areas where constraints must
be satisfied for a period of time or in a given
region. Examples of application are robot
trajectory planning and air pollution control
problems, among others.
There are several ways for solving SIP problems.
The reduction technique is the one that produces
best numerical results. In spite of existing
several reduction type algorithms for SIP
proposed in the literature, no publicly or
commercial software using a reduction algorithm
is available.
The reduction type method consists of
transforming the SIP problem into a finite one
where the infinite number of constraints are
replaced by a finite set which corresponds to
the local and global optima of the infinite
constraints.
The major drawback of the reduction type methods
is the need to compute, at each iteration of the
algorithm, all the global and as much local
optima as possible of the infinite constraints.
To address the global optimization problem it is
necessary to extend available algorithms to
provide a multi-local optimization framework (to
compute all the global and local optima). Some
of the existent techniques for multi-local are
based on stochastic methods, namely the
evolutionary strategies with sharing. These
techniques proved to be parameter dependent, as
they require a priori knowledge of the number of
optima and they are not efficient in the general
case. Thus, extensions to particle swarm,
evolutionary strategies and simulating annealing
for multi-local optimization are to be addressed.
In
the finite optimization context, the trust
region sequential quadratic programming method
based on a filter approach that does not require
the use of a merit function, has been subject to
significant progress. The use of a linesearch
strategy instead of the trust region is yet to
be studied.
In
this context, the project has two innovative
goals: the developement of powerful multi-local
optimization algorithms to compute all the
global and some local optima of the infinite
constraints, using particle swarm, evolution
strategies and simulated annealing techniques,
and the analysis and implementation of a filter
SQP method based on a line search strategy for
solving the corresponding finite problem.
The final product will consist of a solver that
interfaces with the SIPAMPL modeling language,
allowing a fast and easy way to solve SIP
problems.
The solver will made be publicly available in an
internet web page to be developed.
|
|
| |
References:
Fletcher, R. and Leyffer, S. (2001), "Nonlinear
Programming without a penalty function", Dundee
University Numerical Analysis Report, NA 171 (September,
1997), published electronically in Mathematical
Programming (September, 2001).
Goberna, M.Á. and Lopez, M.A. (Eds.) (2001), "Semi-Infinite
Programming, Recent advances", Nonconvex
Optimization and its Applications series, Kluwer
Academic Publishers.
Hettich, R. and Kortanek, K.O. (1993), "Semi-infinite
programming: Theory, methods, and applications",
SIAM Review, 35(3):380-429. 1993.
Horn, J. (1997), "THE NATURE OF NICHING: GENETIC
ALGORITHMS AND THE EVOLUTION OF OPTIMAL,
COOPERATIVE POPULATIONS", Phd Thesis, University
of Illinois, USA.
Polak, E. (1987), "On the mathematical
foundations of nondifferentiable optimization in
engineering design", SIAM Review 29(1),
pp.21-89.
Reemtsen, R. and Rueckmann, J.-J. (Eds.) (1998)
"Semi-Infinite Programming", Nonconvex
Optimization and its Applications series, Kluwer
Academic Publishers.
Monteiro, M.T.T. (2004), "", Vaz, A.I.F.,
Fernandes, E.M.G.P. and Gomes, M.P.S.F., 2002, "NSIPS
V2.1: Nonlinear Semi-Infinite Programming
Solver", Technical report ALG/EF/5-2002,
http://www.norg.uminho.pt/aivaz.
Vaz, A.I.F., Fernandes, E.M.G.P. and Gomes,
M.P.S.F., 2004, "SIPAMPL: Semi-infinite
programming with AMPL", ACM Transactions on
Mathematical Software, 30(1):47-61.
|
|
