HEC Montréal, Canada, 2  4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011
MB2 Relaxations semidéfinies et convexes pour l'optimisation discrète / Semidefinite and Convex Relaxations for Discrete Optimization Problems
2 mai 2011 15h30 – 17h10
Salle: Béton Grilli
Présidée par Miguel F. Anjos
4 présentations

15h30  15h55
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.

15h55  16h20
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.

16h20  16h45
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.

16h45  17h10
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.