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
USA
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.