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

2013 Optimization Days

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

Schedule Authors My Schedule

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

May 8, 2013 10:30 AM – 12:10 PM

Location: Van Houtte

Chaired by Miguel F. Anjos

3 Presentations

  • 10:30 AM - 10:55 AM

    On the Sensitivity of Semidefinite Programs

    • Yuen-Lam Cheung, presenter, 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}$.

  • 10:55 AM - 11:20 AM

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

    • Elspeth Adams, presenter, 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.

  • 11:20 AM - 11:45 AM

    Generalized Trust Region Subproblem

    • Ting Kei Pong, presenter, 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.