期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 24, 期 2, 页码 163-185出版社
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1020209017701
关键词
approximation algorithms; stability number; semidefinite programming; copositive cone; standard quadratic optimization; linear matrix inequalities
The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据