Contacts:
- Michel Kieffer, L2S Supelec. michel.kieffer@lss.supelec.fr
- Leo Liberti, LIX Ecole Polytechnique. liberti@lix.polytechnique.fr
October 23, 2009
Interval-based Global Optimization (GO) techniques [8] provide
guaranteed global optima to complex nonlinear programming problems,
including Mixed-Integer Nonlinear Programming problems (MINLPs)
[1]. Thanks to recent developments [2,7,3,6] interval-based GO is
competitive (in terms of computing time) with respect to other
(non-guaranteed) techniques, at least for some classes of problems.
This property is particularly interesting when considering the problem
of parameter estimation from noisy measurements for systems described
by ODE- or PDE-based mathematical models that involve functions which
are nonlinear in their parameters [10]. For such systems, the
parameters may not necessarily be globally identifiable. Due to the
lack of identifiability, the cost function to be optimized may have a
globally optimal value attained by distinct parameter vectors. One way
for detecting such situations involves finding all globally optimal
parameter vectors [5,4,9]. Computational experience shows that the
computing times needed to obtain all global optima may be several
orders of magnitude larger than with conventional (non-guaranteed)
optimization techniques, even for very simple nonlinear models with
two or three parameters [10]. One of the reasons for this overhead is
due to difficulty to bound efficiently the range of the cost function
over some box in the parameter space. The aim of this post-doctoral
fellowship will be to determine the causes for interval-based GO
techniques inefficiencies in the context of parameter estimation, and
to propose tools, e.g., based on constraint propagation or on
sensitivity analysis to improve their efficiency.
If interested, the applicant may also consider applications in
communication and networking, such as elaborating routing strategies
for multicasting multimedia contents with guarantee on the quality of
service. Such problems may be cast into the framework of MINLP: routes
for packets have to be determined, which corresponds to the integer
part of the problems, and delay and distortion constraints have to be
satisfied at the receivers, which correspond to the continuous part of
the problem. The applicants should have a good background in numerical
methods for global optimization. No background in estimation nor in
communication and networking is required.
This one-year fellowship is funded by Digiteo, a very large research
cluster devoted to research in Science and Technology of Information
located close to Paris (see http://www.digiteo.fr/ for more
details). The net monthly salary is 2000EUR (French-style, which means
there may be some taxes to pay --- averaging 1500EUR --- at the end of
the fiscal year). The postdoctoral fellow will benefit from the close
links established between all participants to this cluster both in
terms of the theoretical and applied aspects of his or her scientific
research and in terms of opportunities for his or her future career.
References
[1] P. Belotti, J. Lee, L. Liberti, F. Margot, and
A. Waechter. Branching and bounds tightening techniques for non-convex
a MINLP. Optimization Methods and Software, 24(4):597–634, 2009.
[2] E. Carrizosa, P. Hansen, and F. Messine. Improving interval
analysis bounds by translations. Journal of Global Optimization,
29(2):157–172, 2004.
[3] R. B. Kearfott. GlobSol User Guide.
http://interval.louisiana.edu/GLOBSOL/what_is.html, 1999.
[4] Cha Kun Lee, Adam B. Singer, and Paul I. Barton. Global
optimization of linear hybrid systems with explicit
transitions. Systems & Control Letters, 51(5):363–375, 2004.
[5] Youdong Lin and Mark A. Stadtherr. Validated solutions of initial
value problems for parametric odes. Applied Numerical Mathematics,
57(10):1145–1162, 2007.
[6] J. Ninin and F. Messine. A metaheuristic methodology based on the
limitation of the memory of interval branch and bound
algorithms. Journal of Global Optimization, to appear.
[7] H. Schichl and A. Neumaier. Interval analysis on directed acyclic
graphs for global optimization. Journal of Global Optimization,
33(4):541–562, 2005.
[8] E. R. Hansen. Global Optimization Using Interval Analysis. Marcel
Dekker, New York, NY, 1992.
[9] L. Jaulin, M. Kieffer, O. Didrit, and E. Walter. Applied Interval
Analysis. Springer-Verlag, London, 2001.
[10] E. Walter and M. Kieffer. Guaranteed optimisation of the
parameters of continuous-time knowledge-based models. In C. Commault
and N. Marchand, editors, Positive Systems, volume 341 of LNCIS, pages
137–144, Heidelberg, 2006. Springer.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
