HEC Montréal, Canada, May 2  4, 2011
2011 Optimization Days
HEC Montréal, Canada, 2 — 4 May 2011
MB2 Relaxations semidéfinies et convexes pour l'optimisation discrète / Semidefinite and Convex Relaxations for Discrete Optimization Problems
May 2, 2011 03:30 PM – 05:10 PM
Location: Béton Grilli
Chaired by Miguel F. Anjos
4 Presentations

03:30 PM  03:55 PM
Nonconvex Quadratic Programming With Box Constraints
Nonconvex quadratic programming with box constraints is a fundamental continuous global optimization problem, which also appears as a substructure within many other problems. We study a certain nonpolyhedral convexification of this problem, detail some fundamental results, and describe several classes of strong cuts. We also show a close relationship to the Boolean quadric polytope, an important polytope in the field of polyhedral combinatorics.

03:55 PM  04:20 PM
Direct Representation of the Resolution Rule Via SemiDefinite Programming
We use the language of semidefinite programming (SDP) relaxations to describe the resolution rule process for determining whether a satisfiability (SAT) formula is satisfiable. More specifically, we represent one step of resolution using SDP. We also comment on how this may lead to new insights on the relationships between SDP relaxations and SAT.

04:20 PM  04:45 PM
Convex Relaxation for the Clique and Clustering Problems
Given a data set with known pairwise similarities, partitioning the data into disjoint clusters is equivalent to partitioning a particular graph into disjoint cliques. We consider the related problem of identifying the maximum subgraph comprised of k disjoint cliques of a given graph. This problem can be formulated as a semidefinite program with an additional rank constraint. This problem is NPhard yet we show that it can be solved exactly for certain input graphs by relaxing to a convex optimization problem by replacing rank with the nuclear norm. Specifically, the convex relaxation is exact in the case that the input graph consists of a collection of k disjoint cliques and a moderate amount of additional edges and nodes.

04:45 PM  05:10 PM
An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming
We propose an iterative scheme that improves the semidefinite relaxations without incurring exponential growth in their size by generating valid polynomial inequalities. For binary polynomial programs, we prove under mild conditions that the proposed scheme converges to the global optimal solution. We also present computational comparisons to other methods in the literature.