4 Presentations

• 
  10:30 AM - 10:55 AM

  A Semidefinite Programming Model for the Continuous Facility Layout Problem

  • Elspeth Adams, presenter, Polytechnique Montréal
  • Miguel F. Anjos, GERAD, Polytechnique Montréal

  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 center-to-center rectilinear distance) is minimized. We consider a semidefinite programming model using quaternary variables and present computational results.

• 
  10:55 AM - 11:20 AM

  A Semidefinite Programming Approach for Complementarity Problems

  • Patricia Gillett, presenter, Polytechnique Montréal
  • Miguel F. Anjos, GERAD, Polytechnique Montréal

  A recent result of Ye and Zhang provides a semidefinite programming relaxation that is exact for a very special class of non-convex 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.

• 
  11:20 AM - 11:45 AM

  Conjugate Gradient with Subspace Optimization

  • Sahar Karimi, presenter, University of Waterloo
  • Stephen Vavasis, University of Waterloo

  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.

• 
  11:45 AM - 12:10 PM

  A Cutting Plane Method for Solving Convex Optimization Problems Over the Cone of Nonnegative Polynomials

  • Iurie Caraus, presenter, Moldova State University

  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.