{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T10:07:27Z","timestamp":1790676447546,"version":"4.1.0"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) $\\min \\{ x^* C x \\mid x^* A_k x \\ge 1, k=0,1,\\ldots,m, x\\in\\mathbb{F}^n\\}$ and (2) $\\max \\{ x^* C x \\mid x^* A_k x \\le 1, k=0,1,\\ldots,m, x\\in\\mathbb{F}^n\\}$, where $\\mathbb{F}$ is either the real field $\\mathbb{R}$ or the complex field $\\mathbb{C}$, and $A_k,C$ are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the $A_k$'s are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by $O(m^2)$ when $\\mathbb{F}=\\mathbb{R}$, and by $O(m)$ when $\\mathbb{F}=\\mathbb{C}$. Moreover, when two or more of the $A_k$'s are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the $A_k$'s are indefinite while other $A_k$'s are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by $O(1\/\\log m)$ for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535\u2013560]. When two or more of the $A_k$'s in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight.<\/jats:p>","DOI":"10.1137\/070679041","type":"journal-article","created":{"date-parts":[[2008,6,16]],"date-time":"2008-06-16T18:03:40Z","timestamp":1213639420000},"page":"503-523","source":"Crossref","is-referenced-by-count":75,"title":["Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization"],"prefix":"10.1137","volume":"19","author":[{"given":"Simai","family":"He","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhi-Quan","family":"Luo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiawang","family":"Nie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,6,11]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/24.693785"},{"key":"R2","unstructured":"A. Beck and M. Teboulle,\n                      A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid\n                      , Math. Programming, to appear."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401392354"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"D. Bertsimas and Y. Ye,\n                      Semidefinite relaxations, multivariate normal distributions, and order statistics\n                      , in Handbook of Combinatorial Optimization, Vol. 3, D.Z. Du and P. M. Pardalos, eds., Kluwer Academic Publishers, Boston, 1998, pp. 1\u201319.","DOI":"10.1007\/978-1-4613-0303-9_24"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1046294309"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s004400050090"},{"key":"R7","unstructured":"D. R. Cox,\n                      Renewal Theory\n                      , John Wiley & Sons, New York, 1962."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1257"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012752110010"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0268"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9022-3"},{"key":"R13","unstructured":"H. Kl\u00e4ver and N. Schmitz,\n                      An inequality for the asymmetry of distributions and a Berry-Esseen theorem for random summation\n                      , J. Ineq. Pure Appl. Math., Vol. 7, No. 1, Article 2, 2006."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/050642691"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495297820"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050049"},{"key":"R17","unstructured":"E. Matskani, N. D. Sidiropoulos, Z.Q. Luo, and L. Tassiulas,\n                      Convex approximation techniques for joint multiuser downlink beamforming and admission control\n                      , IEEE Trans. Wireless Communication, to appear."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050100"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"R21","first-page":"335","volume":"34","author":"Prekopa A.","year":"1973","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2006.872578"},{"key":"R23","unstructured":"A. So, Y. Ye, and J. Zhang,\n                      A Unified Theorem on SDP Rank Reduction\n                      , working paper, 2006; available online from http:\/\/www.stanford.edu\/~yyye\/."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107980012a"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340139001X"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/04061341X"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070679041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:28:35Z","timestamp":1787333315000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070679041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/070679041"],"URL":"https:\/\/doi.org\/10.1137\/070679041","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}