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.