HEC Montréal, Canada, 2  4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011
TA2 Optimisation continue et semidéfinie / Continuous and Semidefinite Optimization
3 mai 2011 10h30 – 12h10
Salle: Béton Grilli
Présidée par Miguel F. Anjos
4 présentations

10h30  10h55
A Semidefinite Programming Model for the Continuous Facility Layout Problem
The continuous facility layout problem consists of arranging a set of facilities so that no pair overlaps and the sum of the pairwise connection costs (which are proportional to the centertocenter rectilinear distance) is minimized. We consider a semidefinite programming model using quaternary variables and present computational results.

10h55  11h20
A Semidefinite Programming Approach for Complementarity Problems
A recent result of Ye and Zhang provides a semidefinite programming relaxation that is exact for a very special class of nonconvex quadratic problems with complementarity constraints. We consider extending this relaxation approach to more general classes of problems and discuss the quality of the relaxations obtained.

11h20  11h45
Conjugate Gradient with Subspace Optimization
We present an algorithm that is closely related to Conjugate Gradient (CG) and the algorithm Nemirovsky and Yudin proposed in 80’s with advantages from both. We call it CGSO for CG with subspace optimization. We discuss its complexity bound for certain class of problems as well as its practical efficiency.

11h45  12h10
A Cutting Plane Method for Solving Convex Optimization Problems Over the Cone of Nonnegative Polynomials
Many practical problems can be formulated as convex optimization problems over the cone of nonnegative univariate polynomials. We use a cutting plane method for solving this type of optimization problems in primal form. Therefore, we must be able to verify whether a polynomial is nonnegative, i.e. if it does not have real roots or all real roots are multiple of even order. In this paper an ef.cient method is derived to determine a scalar value for which the polynomial is negative and in the case that such a value exists a feasible cut is constructed. Our method is based on Sturm theorem, which allows to determine the number of distinct roots of a polynomial on a given interval, in combination with the bisection method. For numerical stability we construct the associated Sturm sequence using Chebyshev basis, and thus we can work with high degree polynomials, up to hundreds. Numerical results show the ef.ciency of our new approach.