{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T01:31:26Z","timestamp":1788226286194,"version":"build-2803163510"},"reference-count":49,"publisher":"American Mathematical Society (AMS)","issue":"292","license":[{"start":{"date-parts":[[2015,7,24]],"date-time":"2015-07-24T00:00:00Z","timestamp":1437696000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>In this paper, we consider computational methods for optimizing a multivariate inhomogeneous polynomial function over a general convex set. The focus is on the design and analysis of polynomial-time approximation algorithms. The methods are able to deal with optimization models with polynomial objective functions in any fixed degrees. In particular, we first study the problem of maximizing an inhomogeneous polynomial over the Euclidean ball. A polynomial-time approximation algorithm is proposed for this problem with an assured (relative) worst-case performance ratio, which is dependent only on the dimensions of the model. The method and approximation ratio are then generalized to optimize an inhomogeneous polynomial over the intersection of a finite number of co-centered ellipsoids. Furthermore, the constraint set is extended to a general convex compact set. Specifically, we propose a polynomial-time approximation algorithm with a (relative) worst-case performance ratio for polynomial optimization over some convex compact sets, e.g., a polytope. Finally, numerical results are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated instances.<\/p>","DOI":"10.1090\/s0025-5718-2014-02875-5","type":"journal-article","created":{"date-parts":[[2014,7,24]],"date-time":"2014-07-24T09:17:18Z","timestamp":1406193438000},"page":"715-741","source":"Crossref","is-referenced-by-count":7,"title":["Inhomogeneous polynomial optimization over a convex set: An approximation approach"],"prefix":"10.1090","volume":"84","author":[{"given":"Simai","family":"He","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhening","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2014,7,24]]},"reference":[{"issue":"4","key":"1","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/S0097539704441629","article-title":"Approximating the cut-norm via Grothendieck\u2019s inequality","volume":"35","author":"Alon, Noga","year":"2006","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"2","doi-asserted-by":"crossref","unstructured":"G.M. de Athayde and R.G. Fl\u00f4res, Jr., Incorporating skewness and kurtosis in portfolio optimization: A multidimensional efficient set, in S. Satchell and A. Scowcroft (Eds.), Advances in Portfolio Construction and Implementation, Butterworth-Heinemann, Oxford, UK, Chapter 10, 243\u2013257, 2003.","DOI":"10.1016\/B978-075065448-7.50011-2"},{"key":"3","doi-asserted-by":"crossref","unstructured":"A. Barmpoutis, B. Jian, B. C. Vemuri, and T. M. Shepherd, Symmetric positive 4th order tensors & their estimation from diffusion weighted MRI, Proceedings of the 20th International Conference on Information Processing in Medical Imaging, 308\u2013319, 2007.","DOI":"10.1007\/978-3-540-73273-0_26"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"Boyd, Stephen","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0521833787"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/110834524","article-title":"Maximum block improvement and polynomial optimization","volume":"22","author":"Chen, Bilian","year":"2012","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2-3","key":"6","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.laa.2006.08.026","article-title":"A tensor product matrix approximation problem in quantum physics","volume":"420","author":"Dahl, Geir","year":"2007","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"7","unstructured":"A. Ghosh, E. Tsigaridas, M. Descoteaux, P. Comon, B. Mourrain, and R. Deriche, A Polynomial based approach to extract the maxima of an antipodally symmetric spherical function and its application to extract fiber directions from the orientation distribution function in diffusion MRI, Proceedings of the 11th International Conference on Medical Image Computing and Computer Assisted Intervention, 237\u2013248, 2008."},{"issue":"6","key":"8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans, Michel X.","year":"1995","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/780542.780545","article-title":"Classical deterministic complexity of Edmond\u2019s problem and quantum entanglement","author":"Gurvits, Leonid","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/1581136749"},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10107-010-0409-z","article-title":"Approximation algorithms for homogeneous polynomial optimization with quadratic constraints","volume":"125","author":"He, Simai","year":"2010","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"S. He, Z. Li, and S. Zhang, Approximation algorithms for discrete polynomial optimization, Journal of the Operations Research Society of China, 1, 3\u201336, 2013.","DOI":"10.1007\/s40305-013-0003-1"},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/070679041","article-title":"Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization","volume":"19","author":"He, Simai","year":"2008","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"4-5","key":"13","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","article-title":"GloptiPoly 3: moments, optimization and semidefinite programming","volume":"24","author":"Henrion, Didier","year":"2009","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"issue":"6","key":"14","doi-asserted-by":"publisher","first-page":"3104","DOI":"10.1137\/100790835","article-title":"Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube","volume":"20","author":"de Klerk, Etienne","year":"2010","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","unstructured":"S. Khot and A. Naor, Linear equations modulo 2 and the \ud835\udc3f\u2081 diameter of convex bodies, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 318\u2013328, 2007.","DOI":"10.1109\/FOCS.2007.20"},{"issue":"4","key":"16","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s10898-010-9529-5","article-title":"Partitioning procedure for polynomial optimization","volume":"48","author":"Kleniati, Polyxeni-Margarita","year":"2010","journal-title":"J. Global Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-5001","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1137\/S0895479801387413","article-title":"On the best rank-1 approximation of higher-order supersymmetric tensors","volume":"23","author":"Kofidis, Eleftherios","year":"2001","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"18","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1137\/07070111X","article-title":"Tensor decompositions and applications","volume":"51","author":"Kolda, Tamara G.","year":"2009","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","article-title":"Global optimization with polynomials and the problem of moments","volume":"11","author":"Lasserre, Jean B.","year":"2000","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1090\/S0002-9947-01-02898-7","article-title":"Polynomials nonnegative on a grid and discrete optimization","volume":"354","author":"Lasserre, Jean B.","year":"2002","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-0-387-09686-5_7","article-title":"Sums of squares, moment matrices and optimization over polynomials","author":"Laurent, Monique","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387096858"},{"key":"22","unstructured":"Z. Li, Polynomial Optimization Problems\u2014Approximation Algorithms and Applications, Ph.D. Thesis, The Chinese Univesrity of Hong Kong, Shatin, Hong Kong, 2011."},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1137\/080729104","article-title":"Biquadratic optimization over unit spheres and semidefinite programming relaxations","volume":"20","author":"Ling, Chen","year":"2009","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/050642691","article-title":"Approximation bounds for quadratic optimization with homogeneous quadratic constraints","volume":"18","author":"Luo, Zhi-Quan","year":"2007","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"4","key":"25","doi-asserted-by":"publisher","first-page":"1716","DOI":"10.1137\/090772952","article-title":"A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints","volume":"20","author":"Luo, Zhi-Quan","year":"2010","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1109\/TSP.2002.808112","article-title":"Blind constant modulus equalization via convex optimization","volume":"51","author":"Mari\u010di\u0107, Boris","year":"2003","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"issue":"2-3","key":"27","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10898-007-9224-3","article-title":"Global optimization of higher order moments in portfolio selection","volume":"43","author":"Maringer, Dietmar","year":"2009","journal-title":"J. Global Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-5001","issn-type":"print"},{"key":"28","unstructured":"A. Nemirovski, Lectures on Modern Convex Optimization, The H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 2005."},{"issue":"3","key":"29","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s101070050100","article-title":"On maximization of quadratic form over intersection of ellipsoids with common center","volume":"86","author":"Nemirovski, A.","year":"1999","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"1-3","key":"30","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1080\/10556789808805690","article-title":"Semidefinite relaxation and nonconvex quadratic optimization","volume":"9","author":"Nesterov, Yu.","year":"1998","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"31","unstructured":"Yu. Nesterov, Random Walk in a Simplex and Quadratic Optimization over Convex Polytopes, CORE Discussion Paper 2003\/71, Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgium, 2003."},{"issue":"5","key":"32","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1109\/TAC.2008.923679","article-title":"An eigenvalue method for testing positive definiteness of a multivariate form","volume":"53","author":"Ni, Qin","year":"2008","journal-title":"IEEE Trans. Automat. Control","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9286","issn-type":"print"},{"key":"33","doi-asserted-by":"crossref","unstructured":"J. Nie, An approximation bound analysis for Lasserre\u2019s relaxation in multivariate polynomial optimization, Journal of the Operations Research Society of China 1 (2013), 313\u2013332.","DOI":"10.1007\/s40305-013-0017-8"},{"key":"34","unstructured":"P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. Dissertation, California Institute of Technology, Pasadena, CA, 2000."},{"issue":"2","key":"35","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","article-title":"Semidefinite programming relaxations for semialgebraic problems","volume":"96","author":"Parrilo, Pablo A.","year":"2003","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"36","doi-asserted-by":"crossref","unstructured":"A. J. Prakash, C. H. Chang, and T. E. Pactwa, Selecting a portfolio with skewness: Recent evidence from US, European, and Latin American equity markets, Journal of Banking & Finance, 27, 1375\u20131390, 2003.","DOI":"10.1016\/S0378-4266(02)00261-3"},{"issue":"4","key":"37","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s10898-004-6875-1","article-title":"Extrema of a real polynomial","volume":"30","author":"Qi, Liqun","year":"2004","journal-title":"J. Global Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-5001","issn-type":"print"},{"issue":"2","key":"38","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1016\/j.jmaa.2006.02.071","article-title":"Eigenvalues and invariants of tensors","volume":"325","author":"Qi, Liqun","year":"2007","journal-title":"J. Math. Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-247X","issn-type":"print"},{"issue":"4","key":"39","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1023\/A:1024778309049","article-title":"Multivariate polynomial minimization and its application in signal processing","volume":"26","author":"Qi, Liqun","year":"2003","journal-title":"J. Global Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-5001","issn-type":"print"},{"issue":"1","key":"40","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1137\/S1052623403420857","article-title":"Global minimization of normal quartic polynomials based on global descent directions","volume":"15","author":"Qi, Liqun","year":"2004","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2","key":"41","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10107-011-0464-0","article-title":"Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems","volume":"129","author":"So, Anthony Man-Cho","year":"2011","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"2","key":"42","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1287\/moor.28.2.246.14485","article-title":"On cones of nonnegative quadratic functions","volume":"28","author":"Sturm, Jos F.","year":"2003","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"43","series-title":"Springer Optimization and Its Applications","isbn-type":"print","volume-title":"Optimization theory and methods","volume":"1","author":"Sun, Wenyu","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387249759"},{"issue":"2","key":"44","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10107980012a","article-title":"Approximating quadratic programming with bound and quadratic constraints","volume":"84","author":"Ye, Yinyu","year":"1999","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"1","key":"45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1008370723217","article-title":"Approximating global quadratic optimization with convex quadratic constraints","volume":"15","author":"Ye, Yinyu","year":"1999","journal-title":"J. Global Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-5001","issn-type":"print"},{"key":"46","isbn-type":"print","first-page":"271","article-title":"A review of trust region algorithms for optimization","author":"Yuan, Ya-xiang","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0198505140"},{"issue":"3","key":"47","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s101070050006","article-title":"Quadratic maximization and semidefinite relaxation","volume":"87","author":"Zhang, Shuzhong","year":"2000","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"3","key":"48","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1137\/04061341X","article-title":"Complex quadratic optimization and semidefinite programming","volume":"16","author":"Zhang, Shuzhong","year":"2006","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"279","key":"49","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1090\/S0025-5718-2012-02577-4","article-title":"The cubic spherical optimization problems","volume":"81","author":"Zhang, Xinzhen","year":"2012","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-292\/S0025-5718-2014-02875-5\/S0025-5718-2014-02875-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-292\/S0025-5718-2014-02875-5\/S0025-5718-2014-02875-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:16:01Z","timestamp":1776795361000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-292\/S0025-5718-2014-02875-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,24]]},"references-count":49,"journal-issue":{"issue":"292","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["S0025-5718-2014-02875-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02875-5","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2014,7,24]]}}}