# 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.