{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T01:23:23Z","timestamp":1789176203777,"version":"build-2803163510"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We present a general semidefinite relaxation scheme for general n-variate quartic polynomial optimization under homogeneous quadratic constraints. Unlike the existing sum-of-squares approach which relaxes the quartic optimization problems to a sequence of (typically large) linear semidefinite programs (SDP), our relaxation scheme leads to a (possibly nonconvex) quadratic optimization problem with linear constraints over the semidefinite matrix cone in $\\mathbb{R}^{n\\times n}$. It is shown that each $\\alpha$-factor approximate solution of the relaxed quadratic SDP can be used to generate in randomized polynomial time an $O(\\alpha)$-factor approximate solution for the original quartic optimization problem, where the constant in $O(\\cdot)$ depends only on problem dimension. In the case where only one positive definite quadratic constraint is present in the quartic optimization problem, we present a randomized polynomial time approximation algorithm which can provide a guaranteed relative approximation ratio of $(1-O(n^{-2}))$.<\/jats:p>","DOI":"10.1137\/090772952","type":"journal-article","created":{"date-parts":[[2010,1,27]],"date-time":"2010-01-27T18:05:18Z","timestamp":1264615518000},"page":"1716-1736","source":"Crossref","is-referenced-by-count":59,"title":["A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization with Quadratic Constraints"],"prefix":"10.1137","volume":"20","author":[{"given":"Zhi-Quan","family":"Luo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,1,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1971.1099712"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.769"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(98)00100-7"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0138-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/5.720250"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"S. Kwapie\u0144 and W. A. Woyczy\u0144ski,\n                      Random Series and Stochastic Integrals: Single and Multiple\n                      , Birkh\u00e4user, Boston, Cambridge, MA, 1992.","DOI":"10.1007\/978-1-4612-0425-1"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2002.808112"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/050642691"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/070679041"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050100"},{"key":"R13","first-page":"1","volume":"12","author":"Nesterov Yu.","year":"1997","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"R14","unstructured":"Yu. Nesterov,\n                      Random walk in a simplex and quadratic optimization over convex polytopes\n                      , CORE discussion paper, The Catholic University of Leuven, Louvain-la-Neuve, Belgium, 2003."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.05.007"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.246.14485"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/1149283.1149286"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0326"},{"key":"R20","unstructured":"V. Vazirani,\n                      Approximation algorithms\n                      , Springer, New York, 2001."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090772952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:31:19Z","timestamp":1787333479000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090772952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090772952"],"URL":"https:\/\/doi.org\/10.1137\/090772952","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}