Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/4766
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Applied Mathematics | - |
dc.creator | Ling, C | - |
dc.creator | Nie, J | - |
dc.creator | Qi, L | - |
dc.creator | Ye, Y | - |
dc.date.accessioned | 2014-12-11T08:22:32Z | - |
dc.date.available | 2014-12-11T08:22:32Z | - |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | http://hdl.handle.net/10397/4766 | - |
dc.language.iso | en | en_US |
dc.publisher | Society for Industrial and Applied Mathematics | en_US |
dc.rights | © 2009 Society for Industrial and Applied Mathematics | en_US |
dc.subject | Biquadratic optimization | en_US |
dc.subject | Semidefinite programming | en_US |
dc.subject | Approximate solution | en_US |
dc.subject | Sum of squares | en_US |
dc.subject | Polynomial time approximation scheme | en_US |
dc.title | Biquadratic optimization over unit spheres and semidefinite programming relaxations | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.spage | 1286 | - |
dc.identifier.epage | 1310 | - |
dc.identifier.volume | 20 | - |
dc.identifier.issue | 3 | - |
dc.identifier.doi | 10.1137/080729104 | - |
dcterms.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. | - |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | SIAM journal on optimization, 2009, v. 20, no. 3, p. 1286-1310 | - |
dcterms.isPartOf | SIAM journal on optimization | - |
dcterms.issued | 2009 | - |
dc.identifier.isi | WOS:000277836500009 | - |
dc.identifier.scopus | 2-s2.0-73249147288 | - |
dc.identifier.eissn | 1095-7189 | - |
dc.identifier.rosgroupid | r46845 | - |
dc.description.ros | 2009-2010 > Academic research: refereed > Publication in refereed journal | - |
dc.description.oa | Version of Record | en_US |
dc.identifier.FolderNumber | OA_IR/PIRA | en_US |
dc.description.pubStatus | Published | en_US |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Ling_Biquadratic_optimization_unit.pdf | 303.55 kB | Adobe PDF | View/Open |
Page views
144
Last Week
1
1
Last month
Citations as of Apr 14, 2024
Downloads
308
Citations as of Apr 14, 2024
SCOPUSTM
Citations
97
Last Week
0
0
Last month
1
1
Citations as of Apr 19, 2024
WEB OF SCIENCETM
Citations
96
Last Week
1
1
Last month
2
2
Citations as of Apr 18, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.