{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T07:12:13Z","timestamp":1791357133822,"version":"4.3.1"},"reference-count":65,"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":[[2012,1]]},"abstract":"<jats:p>In this paper we propose an efficient method for solving the spherically constrained homogeneous polynomial optimization problem. The new approach has the following three main ingredients. First, we establish a block coordinate descent type search method for nonlinear optimization, with the novelty being that we accept only a block update that achieves the maximum improvement, hence the name of our new search method: maximum block improvement (MBI). Convergence of the sequence produced by the MBI method to a stationary point is proved. Second, we establish that maximizing a homogeneous polynomial over a sphere is equivalent to its tensor relaxation problem; thus we can maximize a homogeneous polynomial function over a sphere by its tensor relaxation via the MBI approach. Third, we propose a scheme to reach a KKT point of the polynomial optimization, provided that a stationary solution for the relaxed tensor problem is available. Numerical experiments have shown that our new method works very efficiently: for a majority of the test instances that we have experimented with, the method finds the global optimal solution at a low computational cost.<\/jats:p>","DOI":"10.1137\/110834524","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T18:23:35Z","timestamp":1327429415000},"page":"87-107","source":"Crossref","is-referenced-by-count":144,"title":["Maximum Block Improvement and Polynomial Optimization"],"prefix":"10.1137","volume":"22","author":[{"given":"Bilian","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simai","family":"He","sequence":"additional","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":"351","published-online":{"date-parts":[[2012,1,24]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0304-7"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. F. Anjos and J. B. Lasserre,\n                      Handbook of Semidefinite, Conic and Polynomial Optimization\n                      , Springer, New York, 2011.","DOI":"10.1007\/978-1-4614-0769-0"},{"key":"R3","unstructured":"B. W. Bader and T. G. Kolda,\n                      Matlab Tensor Toolbox Version\n                      2.4, http:\/\/csmr.ca.sandia.gov\/~tgkolda\/TensorToolbox (2010)."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Barmpoutis, B. Jian, B. C. Vemuri, and T. M. Shepherd,\n                      Symmetric Positive 4th Order Tensors and Their Estimation from Diffusion Weighted MRI\n                      , Lecture Notes in Comput. Sci. 4584, N. Karssemijer and B. Lelieveldt, eds., Springer, New York, 2007, pp. 308\u2013319.","DOI":"10.1007\/978-3-540-73273-0_26"},{"key":"R5","unstructured":"D. P. Bertsekas,\n                      Nonlinear Programming\n                      , 2nd ed., Athena Scientific, Belmont, MA, 1999."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.4064\/sm-39-1-59-76"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592073"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02310791"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.026"},{"key":"R10","unstructured":"E. F. Gonzalez and Y. Zhang,\n                      Accelerating the Lee-Seung Algorithm for Nonnegative Matrix Factorization\n                      , preprint, Department of Computational and Applied Mathematics, Rice University, March 2005."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00074-7"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-007-0052-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.011"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898346995"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/070690730"},{"key":"R16","unstructured":"A. Ghosh, E. Tsigaridas, M. Descoteaux, P. Comon, B. Mourrain, and R. Deriche,\n                      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\n                      , in Proceedings of the Computational Diffusion MRI Workshop (CDMRI'08), New York, 2008."},{"key":"R17","unstructured":"M. Grant and S. Boyd,\n                      CVX: Matlab Software for Disciplined Convex Programming, version\n                      1.2, http:\/\/cvxr.com\/cvx (2010)."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L. Gurvits,\n                      Classical deterministic complexity of Edmonds' problem and quantum entanglement\n                      , in Proceedings of the 35th ACM Symposium on Theory of Computing, New York, 2003.","DOI":"10.1145\/780542.780545"},{"key":"R19","unstructured":"R. A. Harshman,\n                      Foundations of the PARAFAC procedure: Models and conditions for an \u201cexplanatory\u201d multi-modal factor analysis\n                      , UCLA Working Papers in Phonetics, 16 (1970), pp. 1\u201384; also available online from http:\/\/publish.uwo.ca\/~harshman\/wpppfac0.pdf."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.3934\/naco.2011.1.147"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0409-z"},{"key":"R22","unstructured":"S. He, Z. Li, and S. Zhang,\n                      General Constrained Polynomial Optimization: An Approximation Approach\n                      , Technical report SEEM2009-06, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, 2009."},{"key":"R23","unstructured":"S. He, Z. Li, and S. Zhang,\n                      Approximation Algorithms for Discrete Polynomial Optimization\n                      , Technical report SEEM2010-01, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, 2010."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779363"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1080\/10556780802699201"},{"key":"R26","unstructured":"C. J. Hillar and L.H. Lim,\n                      Most Tensor Problems are NP Hard\n                      , preprint; also available online from http:\/\/www.stat.uchicago.edu\/~lekheng\/work\/np.pdf (2010)."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1051\/cocv:2008040"},{"key":"R28","unstructured":"P. M. J. Hof, C. Scherer, and P. S. C. Heuberger,\n                      Model-Based Control: Bridging Rigorous Theory and Advanced Technology, Part\n                      1, Springer, New York, 2009, pp. 49\u201368."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"S. Khot and A. Naor,\n                      Linear equations modulo 2 and the $L_1$ diameter of convex bodies\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 318\u2013328.","DOI":"10.1109\/FOCS.2007.20"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801387413"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-01-02898-7"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/070693709"},{"key":"R36","unstructured":"Z. Li,\n                      Polynomial Optimization Problems\u2014Approximation Algorithms and Applications\n                      , Ph.D. thesis, The Chinese University of Hong Kong, 2011."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/080729104"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1155\/ASP\/2006\/24012"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/090772952"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2008.04.016"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"B. Mourrain and P. Tr\u00e9buchet,\n                      Generalized normal forms and polynomial system solving\n                      , in Proceedings of the International Symposium on Symbolic and Algebraic Computation, M. Kauers, ed., 2005, ACM Press, New York, pp. 253\u2013260.","DOI":"10.1145\/1073884.1073920"},{"key":"R42","unstructured":"Y. Nesterov,\n                      Random Walk in a Simplex and Quadratic Optimization over Convex Polytopes\n                      , CORE Discussion Paper, UCL, Louvain-la-Neuve, Belgium, 2003."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovski,\n                      Interior-Point Polynomial Algorithms in Convex Programming\n                      , SIAM Stud. Appl. Math., 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R44","unstructured":"Network-Enabled Optimization Systems (NEOS) Server for Optimization, http:\/\/www.neos-server.org\/neos."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2007.01.008"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2007.07.024"},{"key":"R47","unstructured":"P. A. Parrilo,\n                      Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization\n                      , Ph.D. dissertation, California Institute of Technology, 2000."},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"R49","unstructured":"S. Prajna, A. Papachristodoulou, and P. A. Parrilo,\n                      Introducing SOSTOOLS: A general purpose sum of squares programming solver\n                      , in Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, 2002."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.05.007"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584660"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2006.02.071"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024778309049"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0193-6"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/06065577"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0464-0"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijplas.2007.07.016"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.246.14485"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1145\/1377612.1377619"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1002\/nla.537"},{"key":"R63","unstructured":"S. Wright,\n                      Accelerated Block-Coordinate Relaxation for Regularized Optimization\n                      , SIAM J. Optim., to appear."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340139001X"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899352045"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110834524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:28:05Z","timestamp":1787329685000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110834524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110834524"],"URL":"https:\/\/doi.org\/10.1137\/110834524","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}