HEC Montréal, Canada, May 2 - 4, 2011

2011 Optimization Days

HEC Montréal, Canada, 2 — 4 May 2011

Schedule Authors My Schedule

MA8 Optimisation robuste I / Robust Optimization I

May 2, 2011 10:30 AM – 12:10 PM

Location: Nancy et Michel-Gaucher

Chaired by Martin Fuchs

4 Presentations

  • 10:30 AM - 10:55 AM

    A Geometric Characterization of the Power of Finite Adaptability in Multi-stage Stochastic Optimization

    • Xu Andy Sun, presenter, Massachusetts Institute of Technology
    • Dimitris Bertsimas, Massachusetts Institute of Technology
    • Vineet Goyal, Columbia University

    We show a significant role that geometric properties of the uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions in multi-stage stochastic and adaptive optimization problems. We propose good approximation solution policies with performance guarantees that depend on the geometric properties of the uncertainty sets. To the best of our knowledge, these are the first approximation results for the multi-stage problems in such generality.

  • 10:55 AM - 11:20 AM

    A Review of Techniques for Handling Model Uncertainty in Interval-Based Global Optimization Procedures

    • Ralph Baker Kearfott, presenter, University of Louisiana at Lafayette

    There are various options for handling uncertainties in parameters in the objective or constraints when interval techniques are used in the solution of global optimization problems. For instance, a traditional worst-case analysis may be done, resulting in a usual optimization problem that may be solved with interval techniques. Alternatively, one may view the problem with uncertain parameters as an entire set of problems, with interval techniques used to bound the set of all solutions and the set of all possible objective values. This gives the possibility to obtain ranges on the solution parameters as well as a range on the objective function. Also, even optimally sharp objective ranges obtained from the latter paradigm may differ from optimal objective values obtained with worst-case analysis. However, solving the entire set of problems by propagating intervals in the solution algorithm presents challenges requiring special consideration. Illustrative examples and solutions will be presented.

  • 11:20 AM - 11:45 AM

    Bilevel Derivative-Free Optimization and its Application to Robust Optimization

    • Luis Nunes Vicente, presenter, University of Coimbra
    • Andrew R. Conn, IBM Research

    We address bilevel programming problems when the derivatives of both the upper and the lower level objective functions are unavailable.

    The core algorithms used for both levels are trust-region interpolation-based methods, using minimum Frobenius norm quadratic models when the number of points is smaller than the number of basis components. We take advantage of the problem structure to derive conditions (related to the global convergence theory of the underlying trust-region methods, as far as possible) under which the lower level can be solved inexactly and sample points can be reused for model building.
    In addition, we indicate numerically how effective these expedients can be. A number of other issues are also discussed, from the extension to linearly constrained problems to the use of surrogate models for the lower level response.

    One important application of our work appears in the robust optimization of simulation-based functions, which may arise due to implementation variables or uncertain parameters. The robust counterpart of an optimization problem without derivatives falls in the category of the bilevel problems under consideration here. We provide numerical illustrations of the application of our algorithmic framework to such robust optimization examples.

  • 11:45 AM - 12:10 PM

    Simulated Polyhedral Clouds in Robust Optimization

    • Martin Fuchs, presenter, CERFACS

    Uncertainty handling with polyhedral clouds has already shown strength in dealing with higher dimensional uncertainties in robust optimization, even in case of partial ignorance of statistical information. However, the number of function evaluations available to propagate the uncertainties is too limited in many real-life applications. Inspired by the Cauchy deviates method, we propose a simulation based approach for optimization over a polyhedron that is able to meet the limits.