Optimization Online


On Solving Biquadratic Optimization via Semidefinite Relaxation

Yang Yuning (nk0310145***at***gmail.com)
Yang Qingzhi (qz-yang***at***nankai.edu.cn)

Abstract: In this paper, we study a class of biquadratic optimization problems. We first relax the original problem to its semidefinite programming (SDP) problem and discuss the approximation ratio between them. Under some conditions, we show that the relaxed problem is tight. Then we consider how to approximately solve the problems in polynomial time. Under several different constraints, we present variational approaches for solving them and give provable estimation for the approximation solutions. Some numerical results are reported at the end of this paper.

Keywords: biquadratic optimization, quadratic optimization, SDP relaxation, approximation algorithm.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )



Entry Submitted: 04/19/2011
Entry Accepted: 04/20/2011
Entry Last Modified: 10/18/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society