HEC Montréal, Canada, 6 - 8 mai 2013

Journées de l'optimisation 2013

HEC Montréal, Canada, 6 — 8 mai 2013

Horaire Auteurs Mon horaire

WA4 Théorie et applications de l'optimisation conique / Theory and Applications of Conic Optimization

8 mai 2013 10h30 – 12h10

Salle: Van Houtte

Présidée par Miguel F. Anjos

3 présentations

  • 10h30 - 10h55

    On the Sensitivity of Semidefinite Programs

    • Yuen-Lam Cheung, prés., University of Waterloo
    • Henry Wolkowicz, University of Waterloo

    Given a feasible conic program with finite optimal value that does not satisfy strong duality, a small perturbation of the problem data may lead to a relatively big change in the optimal value. We quantify the notion of big change in the case of semidefinite programs, by showing that a sufficiently small $\epsilon>0$ perturbation of the problem data can change the optimal value by at least a constant multiple of $\epsilon^{1/2}$.

  • 10h55 - 11h20

    Polytope Cuts for the Basic Semidefinite Relaxation of the Max-Cut Problem

    • Elspeth Adams, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Franz Rendl, Alpen-Adria Universitaet Klagenfurt
    • Angelika Wiegele, Alpen-Adria Universitaet Klagenfurt

    We introduce a cutting plane method for the basic semidefinite relaxation of the max-cut problem, specifically by defining a new class of linear cuts that are based on the cut polytope and describing methods for identifying violated cuts. We present theoretical and computational results.

  • 11h20 - 11h45

    Generalized Trust Region Subproblem

    • Ting Kei Pong, prés., postdoctoral fellow
    • Henry Wolkowicz, University of Waterloo

    We consider a generalized version of Trust Region Subproblem, where the constraint is replaced by a general quadratic constraint with both upper and lower bounds. We characterize optimality under a mild constraint qualification and extend the Rendl-Wolkowicz algorithm to this setting.