il 30/01/08
ore 10-11 Prof. Immanuel M. Bomze, University of
Vienna: " On the
road to tractability: from combinatorial optimization via
copositive programming to SDP-based approximation".
Abstract:
Quite many combinatorial and some important non-convex continuous
optimization problems admit a copositive representation, where the
complexity of solving non-convex programs is shifted towards the
complexity of sheer feasibility.
Using characterizations of
copositivity, one arrives at various
SDP-based approximations. However, not
all of these are tractable
with current technology. This talk addresses some
approaches on
which tractable semidefinite-programming (SDP) approximations
may
be based, along with specific strategies to generate interesting
test instances of intermediate complexity.
ore 11-11.30 coffee break
ore 11.30-12.30 Prof. Fabio Schoen, Università di Firenze:
"Practical Global Optimization: from the Circle Packing Contest to
Binary Atomic Clusters and beyond".
Abstract:
In this talk
we will review some recent computational results in
large scale global
optimization. Starting from the techniques we
used and which led our group
to win the Circle Packing Contest
(
http://www.recmath.org/contest/CirclePacking) we will explain how
that experience proved itself extremely useful in a quite
different
context, that of finding the global minimum energy
configuration of atomic
clusters composed by atoms of two
different types. Differently from
classical (e.g. Lennard-Jones or
Morse) potential energy optimization, for
the optimization of
binary clusters the combinatorial nature of the
problem has to be
taken into account. In fact, once the coordinates of N
atoms have
been decided, through the minimization of a smooth function,
exponentially many isomers can be defined, by assigning different
atom
types to different locations (some sort of a 3-dimensional
anagram). We will
present our quite simple strategy which led us
to find improved
configuration for at least 90 of the previously
known putative optima
deposited at the Cambridge Cluster Database.
Very recently we tried to apply
a similar algorithmic framework to
another, quite unrelated, contest:
finding the best departure and
travel times of a spacecraft which, starting
from Earth, should
visit some (3) asteroids to be chosen in a known group.
The
objective was to minimize a function of fuel consumption and of
the
stay time at each asteroid, with constraints on the maximum
length of the
mission (less than 10 years). Although quite
unexperienced in this field and
although the competition ran for
only one month, we ranked 10-th out of 23
participants: in the
talk we will briefly sketch our approach.
-----------------------------------------------
--
Open
WebMail Project (
http://openwebmail.org)