### 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 f_{k}(X)=0, k=1,...,m, X=X^{T}>=0, and rank(X) <= r,

where f,f_{k}, 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'' J_{r}/J, where J and
J_{r} 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.
*