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.