{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:34:37Z","timestamp":1787333677391,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>We consider the NP\u2010hard problem of finding a minimum norm vector in n\u2010dimensional real or complex Euclidean space, subject to m concave homogeneous quadratic constraints. We show that a semidefinite programming (SDP) relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an $O(m^2)$ approximation in the real case and an $O(m)$ approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank 1 (namely, outer products of some given so\u2010called steering vectors) and the phase spread of the entries of these steering vectors are bounded away from $\\pi\/2$, we establish a certain \u201cconstant factor\u201d approximation (depending on the phase spread but independent of m and n) for both the SDP relaxation and a convex QP restriction of the original NP\u2010hard problem. Finally, we consider a related problem of finding a maximum norm vector subject to m convex homogeneous quadratic constraints. We show that an SDP relaxation for this nonconvex QP provides an $O(1\/\\ln(m))$ approximation, which is analogous to a result of Nemirovski et al. [Math. Program., 86 (1999), pp. 463\u2013473] for the real case.<\/jats:p>","DOI":"10.1137\/050642691","type":"journal-article","created":{"date-parts":[[2012,6,15]],"date-time":"2012-06-15T19:30:22Z","timestamp":1339788622000},"page":"1-28","source":"Crossref","is-referenced-by-count":176,"title":["Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints"],"prefix":"10.1137","volume":"18","author":[{"given":"Zhi\u2010Quan","family":"Luo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicholas D.","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Tseng","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":[[2007,2,2]]},"reference":[{"key":"R1","unstructured":"N. Alon and A. Naor,\n                      Approximating the Cut\u2010Norm via Grothendieck\u2019s inequality\n                      , Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, 2004, pp. 72\u201380."},{"key":"R2","unstructured":"H. H. Andersen, M. H\u00f8jbjerre, D. S\u00f8rensen, and P. S. Eriksen,\n                      Linear and Graphical Models for the Multivariate Complex Normal Distribution\n                      , Lecture Notes in Statist. 101, Springer\u2010Verlag, New York, 1995."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400374756"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.497.16392"},{"key":"R5","unstructured":"D. Bertsimas and Y. Ye,\n                      Semidefinite relaxations, multivarite normal distribution, and order statistics\n                      , in Handbook of Combinatorial Optim., Vol. 3, D. Z. Du and P. M. Pardalos, eds., Kluwer Academic Publishers, Boston, 1998, pp. 1\u201319."},{"key":"R6","unstructured":"B. Biswas and Y. Ye,\n                      Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization\n                      , Technical report, Department of Electrical Engineering, Stanford University, Stanford, CA, Sept. 2003;"},{"key":"R6","unstructured":"also available online from http:\/\/www.stanford.edu\/\u223cyyye\/."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.012"},{"key":"R9","unstructured":"Y. Huang and S. Zhang,\n                      Complex matrix decomposition and quadratic programming\n                      , Math. Oper. Res., to appear."},{"key":"R10","unstructured":"D. H. Johnson and D. E. Dugeon,\n                      Array Signal Processing: Concepts and Techniques\n                      , Simon & Schuster, New York, 1992."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309326"},{"key":"R13","first-page":"365","volume":"129","author":"Megretski A.","year":"2001","journal-title":"Oper. Theory Adv. Appl."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050100"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"R16","unstructured":"Y. Nesterov, H. Wolkowicz, and Y. Ye,\n                      Semidefinite programming relaxations of nonconvex quadratic optimization\n                      , in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer, Boston, 2000, pp. 360\u2013419."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0359-1"},{"key":"R19","first-page":"1","volume":"25","author":"Shor N. Z.","year":"1987","journal-title":"Soviet J. Comput. Systems Sci."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2006.872578"},{"key":"R21","unstructured":"A. So, J. Zhang, and Y. Ye,\n                      On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations\n                      , in Proceedings of the 11th Conference in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3509, M. Junger and V. Kaibel, eds., Springer\u2010Verlag, Berlin, 2005, pp. 125\u2013135."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401395899"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107980012a"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008370723217"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050006"},{"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\/050642691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:16:20Z","timestamp":1787332580000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050642691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/050642691"],"URL":"https:\/\/doi.org\/10.1137\/050642691","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}