The Semidefinite Relaxation Bounds for Bi-quadratic Optimization with Quadratic Constraints

摘要：

　　We establish the relationship between the so-called bi-quadratic optimization problem and its semidenite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an O(r)-approximation solution for the original bi-quadratic optimization problem, where the constant in O(r) does not involve the dimension of variables and the data of problems.

关键词： Bi-quadratic optimization semidefinite programming relaxation approximation solution probabilistic solution

作者: Xinzhen Zhang Chen Ling Liqun Qi

作者单位: Department of Applied Mathematics,The HongKong Polytechnic University, Hong Kong School of Science, Hangzhou Dianzi University, Hangzhou, China Department of Applied Mathematics,The Hong Kong Polytechnic University, Hong Kong

会议类型: 国际会议

会议名称: 第8届国际最优化方法及应用大会

会议地点: 上海

会议语种:英文

页码: 20-20

在线出版日期: 2010-12-10（万方平台首次上网日期，不代表论文的发表时间）