{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T06:06:21Z","timestamp":1781762781677,"version":"3.54.5"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T00:00:00Z","timestamp":1492041600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T00:00:00Z","timestamp":1492041600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["Young Investigator Program Award"],"award-info":[{"award-number":["Young Investigator Program Award"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s10107-017-1144-5","type":"journal-article","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T07:09:27Z","timestamp":1492067367000},"page":"69-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["DC decomposition of nonconvex polynomials with algebraic techniques"],"prefix":"10.1007","volume":"169","author":[{"given":"Amir Ali","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgina","family":"Hall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,13]]},"reference":[{"key":"1144_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. In: Proceedings of the 48th Annual Conference on Information Sciences and Systems. Princeton University (2014)","DOI":"10.1109\/CISS.2014.6814141"},{"key":"1144_CR2","unstructured":"Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. In preparation (2017)"},{"issue":"1\u20132","key":"1144_CR3","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"AA Ahmadi","year":"2013","unstructured":"Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Progr. 137(1\u20132), 453\u2013476 (2013)","journal-title":"Math. Progr."},{"issue":"1\u20132","key":"1144_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10107-011-0457-z","volume":"135","author":"AA Ahmadi","year":"2012","unstructured":"Ahmadi, A.A., Parrilo, P.A.: A convex polynomial that is not sos-convex. Math. Progr. 135(1\u20132), 275\u2013292 (2012)","journal-title":"Math. Progr."},{"key":"1144_CR5","unstructured":"Ahmadi, A.A., Parrilo, P.A.: A complete characterization of the gap between convexity and sos-convexity. SIAM J. Optim. 23(2), 811\u2013833 (2013). Also \n                    arXiv:1111.4587"},{"issue":"1","key":"1144_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-002-0339-5","volume":"95","author":"F Alizadeh","year":"2003","unstructured":"Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Progr. 95(1), 3\u201351 (2003)","journal-title":"Math. Progr."},{"issue":"11","key":"1144_CR7","doi-asserted-by":"publisher","first-page":"2984","DOI":"10.1109\/TSP.2014.2315167","volume":"62","author":"A Alvarado","year":"2014","unstructured":"Alvarado, A., Scutari, G., Pang, J.: A new decomposition method for multiuser dc-programming and its applications. Signal Process. IEEE Trans. 62(11), 2984\u20132998 (2014)","journal-title":"Signal Process. IEEE Trans."},{"key":"1144_CR8","doi-asserted-by":"crossref","unstructured":"Argyriou, A., Hauser, R., Micchelli, C.A., Pontil, M.: A DC-programming algorithm for kernel selection. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 41\u201348. ACM (2006)","DOI":"10.1145\/1143844.1143850"},{"issue":"2","key":"1144_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1023\/B:COAP.0000026886.61324.e4","volume":"28","author":"I Bomze","year":"2004","unstructured":"Bomze, I., Locatelli, M.: Undominated dc decompositions of quadratic functions and applications to branch-and-bound approaches. Comput. Optim. Appl. 28(2), 227\u2013245 (2004)","journal-title":"Comput. Optim. Appl."},{"key":"1144_CR10","unstructured":"Chapelle, O., Do, C.B., Teo, C.H., Le, Q.V., Smola, A.J.: Tighter bounds for structured estimation. In: Advances in Neural Information Processing Systems, pp. 281\u2013288 (2009)"},{"key":"1144_CR11","unstructured":"de\u00a0Klerk, E., Laurent, M.: On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems (2010). \n                    http:\/\/www.optimization-online.org\/DB-FILE\/2010\/11\/2800.pdf"},{"issue":"1","key":"1144_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s001860200232","volume":"57","author":"M D\u00fcr","year":"2003","unstructured":"D\u00fcr, M.: A parametric characterization of local optimality. Math. Methods Oper. Res. 57(1), 101\u2013109 (2003)","journal-title":"Math. Methods Oper. Res."},{"key":"1144_CR13","volume-title":"Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches","author":"C Floudas","year":"2013","unstructured":"Floudas, C., Pardalos, P.: Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches, vol. 40. Springer, New York (2013)"},{"issue":"5","key":"1144_CR14","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1080\/00029890.2001.11919774","volume":"108","author":"G Folland","year":"2001","unstructured":"Folland, G.: How to integrate a polynomial over a sphere. Am. Math. Month. 108(5), 446\u2013448 (2001)","journal-title":"Am. Math. Month."},{"issue":"1","key":"1144_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/10556780108805809","volume":"15","author":"G Fung","year":"2001","unstructured":"Fung, G., Mangasarian, O.: Semi-supervised support vector machines for unlabeled data classification. Optim. Methods Softw. 15(1), 29\u201344 (2001)","journal-title":"Optim. Methods Softw."},{"key":"1144_CR16","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)"},{"issue":"1","key":"1144_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1080\/02331930903500274","volume":"59","author":"N Gulpinar","year":"2010","unstructured":"Gulpinar, N., Hoai An, L.T., Moeini, M.: Robust investment strategies with discrete asset choice constraints using DC programming. Optimization 59(1), 45\u201362 (2010)","journal-title":"Optimization"},{"issue":"3","key":"1144_CR18","doi-asserted-by":"publisher","first-page":"707","DOI":"10.2140\/pjm.1959.9.707","volume":"9","author":"P Hartman","year":"1959","unstructured":"Hartman, P.: On functions representable as a difference of convex functions. Pac. J. Math 9(3), 707\u2013713 (1959)","journal-title":"Pac. J. Math"},{"issue":"1","key":"1144_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-008-0240-y","volume":"122","author":"JW Helton","year":"2010","unstructured":"Helton, J.W., Nie, J.: Semidefinite representation of convex sets. Math. Progr. 122(1), 21\u201364 (2010)","journal-title":"Math. Progr."},{"key":"1144_CR20","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/BF01443605","volume":"32","author":"D Hilbert","year":"1888","unstructured":"Hilbert, D.: \u00dcber die Darstellung Definiter Formen als Summe von Formenquadraten. Math. Ann. 32, 342\u2013350 (1888)","journal-title":"Math. Ann."},{"issue":"1","key":"1144_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01442883","volume":"6","author":"R Hillestad","year":"1980","unstructured":"Hillestad, R., Jacobsen, S.: Reverse convex programming. Appl. Math. Optim. 6(1), 63\u201378 (1980)","journal-title":"Appl. Math. Optim."},{"key":"1144_CR22","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty, J.B.: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. In: Convexity and Duality in Optimization, pp. 37\u201370. Springer (1985)","DOI":"10.1007\/978-3-642-45610-7_3"},{"issue":"3","key":"1144_CR23","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s11634-008-0030-7","volume":"2","author":"LT Hoai An","year":"2008","unstructured":"Hoai An, L.T., Le, H.M., Tao, P.D., et al.: A DC programming approach for feature selection in support vector machines learning. Adv. Data Anal. Classif. 2(3), 259\u2013278 (2008)","journal-title":"Adv. Data Anal. Classif."},{"issue":"3","key":"1144_CR24","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1023\/A:1008288411710","volume":"11","author":"LT Hoai An","year":"1997","unstructured":"Hoai An, L.T., Tao, P.D.: Solving a class of linearly constrained indefinite quadratic problems by dc algorithms. J. Glob. Optim. 11(3), 253\u2013285 (1997)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1144_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1021765131316","volume":"103","author":"R Horst","year":"1999","unstructured":"Horst, R., Thoai, N.: DC programming: overview. J. Optim. Theory Appl. 103(1), 1\u201343 (1999)","journal-title":"J. Optim. Theory Appl."},{"key":"1144_CR26","unstructured":"Lanckriet, G., Sriperumbudur, B.: On the convergence of the concave\u2013convex procedure. In: Advances in Neural Information Processing Systems, pp. 1759\u20131767 (2009)"},{"issue":"4","key":"1144_CR27","doi-asserted-by":"publisher","first-page":"1995","DOI":"10.1137\/080728214","volume":"19","author":"JB Lasserre","year":"2008","unstructured":"Lasserre, J.B.: Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4), 1995\u20132014 (2008)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1144_CR28","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1137\/080729104","volume":"20","author":"C Ling","year":"2009","unstructured":"Ling, C., Nie, J., Qi, L., Ye, Y.: Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20(3), 1286\u20131310 (2009)","journal-title":"SIAM J. Optim."},{"key":"1144_CR29","unstructured":"Lipp, T., Boyd, S.: Variations and extensions of the convex\u2013concave procedure (2014). \n                    http:\/\/web.stanford.edu\/~boyd\/papers\/cvx_ccv.html"},{"key":"1144_CR30","doi-asserted-by":"crossref","unstructured":"Lou, Y., Osher, S., Xin, J.: Computational aspects of constrained $$l_1-l_2$$ minimization for compressive sensing. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, pp. 169\u2013180. Springer (2015)","DOI":"10.1007\/978-3-319-18161-5_15"},{"key":"1144_CR31","unstructured":"Magnani, A., Lall, S., Boyd, S.: Tractable fitting with convex polynomials via sum of squares. In: Proceedings of the 44th IEEE Conference on Decision and Control (2005)"},{"key":"1144_CR32","unstructured":"Megretski, A.: SPOT: systems polynomial optimization tools (2013)"},{"key":"1144_CR33","unstructured":"MOSEK Reference Manual: Version 7. Latest version \n                    http:\/\/www.mosek.com\/\n                    \n                   (2013)"},{"key":"1144_CR34","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"issue":"2, Ser. B","key":"1144_CR35","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Progr. 96(2, Ser. B), 293\u2013320 (2003)","journal-title":"Math. Progr."},{"key":"1144_CR36","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1090\/dimacs\/060\/08","volume":"60","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions. Algor. Quant. Real Algebr. Geom. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 60, 83\u201399 (2003)","journal-title":"Algor. Quant. Real Algebr. Geom. DIMACS Ser. Discrete Math. Theor. Comput. Sci."},{"key":"1144_CR37","unstructured":"Piot, B., Geist, M., Pietquin, O.: Difference of convex functions programming for reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 2519\u20132527 (2014)"},{"key":"1144_CR38","doi-asserted-by":"crossref","unstructured":"Reznick, B.: Some concrete aspects of Hilbert\u2019s 17th problem. In: Contemporary Mathematics, vol. 253, pp. 251\u2013272. American Mathematical Society (2000)","DOI":"10.1090\/conm\/253\/03936"},{"key":"1144_CR39","unstructured":"Salakhutdinov, R., Roweis, S., Ghahramani, Z.: On the convergence of bound optimization algorithms. In: Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, pp. 509\u2013516. Morgan Kaufmann Publishers Inc. (2002)"},{"issue":"1","key":"1144_CR40","first-page":"289","volume":"22","author":"PD Tao","year":"1997","unstructured":"Tao, P.D., Hoai An, L.T.: Convex analysis approach to dc programming: theory, algorithms and applications. Acta Mathematica Vietnamica 22(1), 289\u2013355 (1997)","journal-title":"Acta Mathematica Vietnamica"},{"key":"1144_CR41","doi-asserted-by":"crossref","unstructured":"Tao, P.D.: Duality in dc (difference of convex functions) optimization. Subgradient methods. In: Trends in Mathematical Optimization, pp. 277\u2013293. Springer (1988)","DOI":"10.1007\/978-3-0348-9297-1_18"},{"key":"1144_CR42","doi-asserted-by":"publisher","first-page":"177","DOI":"10.24033\/msmf.269","volume":"60","author":"J Toland","year":"1979","unstructured":"Toland, J.: On subdifferential calculus and duality in non-convex optimization. M\u00e9moires de la Soci\u00e9t\u00e9 Math\u00e9matique de France 60, 177\u2013183 (1979)","journal-title":"M\u00e9moires de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"1144_CR43","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/S0304-0208(08)72403-4","volume":"129","author":"H Tuy","year":"1986","unstructured":"Tuy, H.: A general deterministic approach to global optimization via dc programming. N.-Holl. Math. Stud. 129, 273\u2013303 (1986)","journal-title":"N.-Holl. Math. Stud."},{"key":"1144_CR44","doi-asserted-by":"crossref","unstructured":"Tuy, H.: Global minimization of a difference of two convex functions. In: Nonlinear Analysis and Optimization, pp. 150\u2013182. Springer (1987)","DOI":"10.1007\/BFb0121159"},{"key":"1144_CR45","doi-asserted-by":"crossref","unstructured":"Tuy, H.: DC optimization: theory, methods and algorithms. In: Handbook of Global Optimization, pp. 149\u2013216. Springer (1995)","DOI":"10.1007\/978-1-4615-2025-2_4"},{"issue":"1\u20133","key":"1144_CR46","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01580762","volume":"41","author":"H Tuy","year":"1988","unstructured":"Tuy, H., Horst, R.: Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and dc optimization problems. Math. Progr. 41(1\u20133), 161\u2013183 (1988)","journal-title":"Math. Progr."},{"key":"1144_CR47","unstructured":"Wang, S., Schwing, A., Urtasun, R.: Efficient inference of continuous markov random fields with polynomial potentials. In: Advances in Neural Information Processing Systems, pp. 936\u2013944 (2014)"},{"key":"1144_CR48","first-page":"1033","volume":"2","author":"A Yuille","year":"2002","unstructured":"Yuille, A., Rangarajan, A.: The concave\u2013convex procedure (CCCP). Adv. Neural Inf. Process. Syst. 2, 1033\u20131040 (2002)","journal-title":"Adv. Neural Inf. Process. Syst."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1144-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1144-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1144-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:24:50Z","timestamp":1589646290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1144-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,13]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["1144"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1144-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,13]]},"assertion":[{"value":"19 September 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}