Optimization and Systems Theory Seminar
Thursday, October 5, 2000, 14.30-15.30, Room 3721, Lindstedtsv. 25

Professor Alexandre Megretski
Laboratory for Information and Decision Systems
Massachusetts Institute of Technology
Cambridge, Massachusetts
E-mail: ameg@mit.edu

Relaxations in non-convex quadratic optimization

A number of optimization problems have the form of a non-convex quadratic program
max f(X) subject to fk(X)=0, k=1,...,m, X=XT>=0, and rank(X) <= r,
where f,fk, k=1,...,m, are affine functionals. Removing the rank constraint (i.e. ``relaxation'') yields an upper bound for the maximum, computable via semidefinite programming. Such upper bounds (of which the upper bound for the structured singular value and the upper bound for the MAX-CUT problem are quite well known) can be very valuable. In this talk, we concentrate on the issue of deriving upper bounds for the ``relaxation gap'' Jr/J, where J and Jr are the maximums in the original and relaxed problems respectively.
Calendar of seminars
Last update: October 3, 2000 by Anders Forsgren, anders.forsgren@math.kth.se.