| Relaxations of Quadratic Programs (2001) | |||||||||||||||
Abstract | |||||||||||||||
| The paper describes a class of mathematical problems at an intersection of operator theory and combinatorics, and discusses their application in complex system analysis. The main object of study is duality gap bounds in quadratic programming which deals with problems of maximizing quadratic functionals subject to quadratic constraints. Such optimization is known to be universal, in the sense that many computationally hard questions can be reduced to quadratic programming. On the other hand, it is conjectured that an ecient algorithm of solving general non-convex quadratic programs exactly does not exist. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||