Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/4766
Title: Biquadratic optimization over unit spheres and semidefinite programming relaxations
Authors: Ling, C
Nie, J
Qi, L 
Ye, Y
Keywords: Biquadratic optimization
Semidefinite programming
Approximate solution
Sum of squares
Polynomial time approximation scheme
Issue Date: 2009
Publisher: Society for Industrial and Applied Mathematics
Source: SIAM journal on optimization, 2009, v. 20, no. 3, p. 1286-1310 How to cite?
Journal: SIAM journal on optimization 
Abstract: This paper studies the so-called biquadratic optimization over unit spheres minₓε ℝ ⁿ, ᵧε ℝ ᵐ Σ 1≤i,k≤n, 1≤j,l≤m bijklxiyjxkyl, subject to ││x││ = 1, ││ y││ = 1. We show that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approximation bound. Then, we present various approximation methods based on semidefinite programming (SDP) relaxations. Our theoretical results are as follows: For general biquadratic forms, we develop a 1 / 2max{m,n}² -approximation algorithm under a slightly weaker approximation notion; for biquadratic forms that are square-free, we give a relative approximation bound 1 / nm; when min{n,m} is a constant, we present two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex. For practical computational purposes, we propose the first order SOS relaxation, a convex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included.
URI: http://hdl.handle.net/10397/4766
ISSN: 1052-6234
EISSN: 1095-7189
DOI: 10.1137/080729104
Rights: © 2009 Society for Industrial and Applied Mathematics
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Ling_Biquadratic_optimization_unit.pdf303.55 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record
PIRA download icon_1.1View/Download Contents

SCOPUSTM   
Citations

55
Last Week
0
Last month
1
Citations as of Jun 14, 2018

WEB OF SCIENCETM
Citations

54
Last Week
0
Last month
2
Citations as of Jun 22, 2018

Page view(s)

389
Last Week
3
Last month
Citations as of Jun 18, 2018

Download(s)

249
Citations as of Jun 18, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.