{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:50:48Z","timestamp":1763643048763,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T00:00:00Z","timestamp":1609545600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T00:00:00Z","timestamp":1609545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17K18946","(B)19H02373"],"award-info":[{"award-number":["17K18946","(B)19H02373"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (Ann Oper Res 265:155\u2013182, 2018),\n we propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it. We prove that the polyhedral approximation using our expanded SD bases contains the set of all diagonally dominant matrices and is contained in the set of all scaled diagonally dominant matrices. We also prove that the set of all scaled diagonally dominant matrices can be expressed using an infinite number of expanded SD bases. We use our approximations as the initial approximation in cutting plane methods for solving a semidefinite relaxation of the maximum stable set problem. It is found that the proposed methods with expanded SD bases are significantly more efficient than methods using other existing approximations or solving semidefinite relaxation problems directly.<\/jats:p>","DOI":"10.1007\/s10589-020-00255-2","type":"journal-article","created":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T06:02:52Z","timestamp":1609567372000},"page":"893-913","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Polyhedral approximations of the semidefinite cone and their application"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1073-9138","authenticated-orcid":false,"given":"Yuzhu","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akihiro","family":"Tanaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akiko","family":"Yoshise","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,2]]},"reference":[{"key":"255_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/18M118935X","volume":"3","author":"AA Ahmadi","year":"2019","unstructured":"Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geom. 3, 193\u2013230 (2019)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"255_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.disopt.2016.04.004","volume":"24","author":"AA Ahmadi","year":"2017","unstructured":"Ahmadi, A.A., Dash, S., Hall, G.: Optimization over structured subsets of positive semidefinite matrices via column generation. Discrete Optim. 24, 129\u2013151 (2017)","journal-title":"Discrete Optim."},{"key":"255_CR3","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1137\/120890636","volume":"23","author":"N Arima","year":"2013","unstructured":"Arima, N., Kim, S., Kojima, M.: A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J. Optim. 23, 2320\u20132340 (2013)","journal-title":"SIAM J. Optim."},{"key":"255_CR4","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10589-016-9879-0","volume":"66","author":"N Arima","year":"2017","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.-C.: A robust Lagrangian-DNN method for a class of quadratic optimization problems. Comput. Optim. Appl. 66, 453\u2013479 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"255_CR5","first-page":"161","volume":"14","author":"N Arima","year":"2018","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.-C.: Lagrangian-conic relaxations, part i: a unified framework and its applications to quadratic optimization problems. Pac. J. Optim. 14, 161\u2013192 (2018)","journal-title":"Pac. J. Optim."},{"key":"255_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.2140\/pjm.1975.57.15","volume":"57","author":"G Barker","year":"1975","unstructured":"Barker, G., Carlson, D.: Cones of diagonally dominant matrices. Pac. J. Math. 57, 15\u201332 (1975)","journal-title":"Pac. J. Math."},{"key":"255_CR7","doi-asserted-by":"crossref","unstructured":"Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences, vol.\u00a09. SIAM, Philadelphia (1994)","DOI":"10.1137\/1.9781611971262"},{"key":"255_CR8","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0024-3795(97)00267-X","volume":"271","author":"L Bishan","year":"1998","unstructured":"Bishan, L., Lei, L., Harada, M., Niki, H., Tsatsomeros, M.J.: An iterative criterion for H-matrices. Linear Algebra Appl. 271, 179\u2013190 (1998)","journal-title":"Linear Algebra Appl."},{"key":"255_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2012)"},{"key":"255_CR10","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.laa.2005.03.029","volume":"405","author":"EG Boman","year":"2005","unstructured":"Boman, E.G., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric H-matrices. Linear Algebra Appl. 405, 239\u2013248 (2005)","journal-title":"Linear Algebra Appl."},{"key":"255_CR11","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","volume":"120","author":"S Burer","year":"2009","unstructured":"Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479\u2013495 (2009)","journal-title":"Math. Program."},{"key":"255_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.C.: A projected gradient algorithm for solving the maxcut SDP relaxation. Optim. Methods Softw. 15, 175\u2013200 (2001)","journal-title":"Optim. Methods Softw."},{"key":"255_CR13","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2, 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. Am."},{"key":"255_CR14","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/opre.7.1.58","volume":"7","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: On a linear-programming, combinatorial approach to the traveling-salesman problem. Oper. Res. 7, 58\u201366 (1959)","journal-title":"Oper. Res."},{"key":"255_CR15","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E De Klerk","year":"2002","unstructured":"De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"key":"255_CR16","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10589-013-9594-z","volume":"57","author":"PJ Dickinson","year":"2014","unstructured":"Dickinson, P.J., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57, 403\u2013415 (2014)","journal-title":"Comput. Optim. Appl."},{"key":"255_CR17","doi-asserted-by":"crossref","unstructured":"D\u00fcr, M.: Copositive programming\u2014a survey. In: Recent Advances in Optimization and Its Applications in Engineering. Springer, Berlin, pp.\u00a03\u201320 (2010)","DOI":"10.1007\/978-3-642-12598-0_1"},{"key":"255_CR18","first-page":"749","volume":"6","author":"SA Ger\u0161gorin","year":"1931","unstructured":"Ger\u0161gorin, S.A.: \u00dcber die abgrenzung der eigenwerte einer matrix. Bull. l\u2019Acad. Sci. l\u2019URSS Classe Sci. Math. 6, 749\u2013754 (1931)","journal-title":"Bull. l\u2019Acad. Sci. l\u2019URSS Classe Sci. Math."},{"key":"255_CR19","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"255_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Am. Math. Soc."},{"key":"255_CR21","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual. http:\/\/www.gurobi.com (2018). Accessed 20 Nov 2018"},{"key":"255_CR22","volume-title":"Matrix Analysis","author":"RA Horn","year":"1990","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)"},{"key":"255_CR23","doi-asserted-by":"crossref","unstructured":"Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In: Topics in Semidefinite and Interior-point Method. AMS. pp. 77\u201395 (1998)","DOI":"10.1090\/fic\/018\/06"},{"key":"255_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1025794313696","volume":"26","author":"S Kim","year":"2003","unstructured":"Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143\u2013154 (2003)","journal-title":"Comput. Optim. Appl."},{"key":"255_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10107-015-0874-5","volume":"156","author":"S Kim","year":"2016","unstructured":"Kim, S., Kojima, M., Toh, K.-C.: A lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156, 161\u2013187 (2016)","journal-title":"Math. Program."},{"key":"255_CR26","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10589-019-00153-2","volume":"75","author":"K Kobayashi","year":"2020","unstructured":"Kobayashi, K., Takano, Y.: A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems. Comput. Optim. Appl. 75, 493\u2013513 (2020)","journal-title":"Comput. Optim. Appl."},{"key":"255_CR27","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0377-0427(02)00424-7","volume":"146","author":"H Konno","year":"2002","unstructured":"Konno, H., Gotoh, J.-Y., Uno, T., Yuki, A.: A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis. J. Comput. Appl. Math. 146, 141\u2013154 (2002)","journal-title":"J. Comput. Appl. Math."},{"key":"255_CR28","unstructured":"Krishnan, K.: Linear programming approach to semidefinite programming problems. PhD thesis, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 (2002)"},{"key":"255_CR29","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10589-005-5958-3","volume":"33","author":"K Krishnan","year":"2006","unstructured":"Krishnan, K., Mitchell, J.E.: A semidefinite programming based polyhedral cut and price approach for the maxcut problem. Comput. Optim. Appl. 33, 51\u201371 (2006)","journal-title":"Comput. Optim. Appl."},{"key":"255_CR30","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1080\/10556780500065283","volume":"21","author":"K Krishnan","year":"2006","unstructured":"Krishnan, K., Mitchell, J.E.: A unifying framework for several cutting plane methods for semidefinite programming. Optim. Methods Softw. 21, 57\u201374 (2006)","journal-title":"Optim. Methods Softw."},{"key":"255_CR31","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0\u20131 programs. In: Aardal, K., Gerards, B. (eds.) Integer Programming and Combinatorial Optimization. Springer, Berlin, pp.\u00a0293\u2013303 (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"key":"255_CR32","unstructured":"Laurent, M., Vallentin, F.: Semidefinite optimization. Lecture Notes. http:\/\/page.mi.fu-berlin.de\/fmario\/sdp\/laurentv.pdf (2012). Accessed 20 Nov 2018"},{"issue":"1-2","key":"255_CR33","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10107-017-1191-y","volume":"172","author":"M Lubin","year":"2018","unstructured":"Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Polyhedral approximation in mixed-integer convex optimization. Math. Program. 172(1-2), 139\u2013168 (2018)","journal-title":"Math. Program."},{"key":"255_CR34","volume-title":"Geometrie der Zahlen","author":"H Minkowski","year":"1896","unstructured":"Minkowski, H.: Geometrie der Zahlen. Teubner, Leipzig (1896)"},{"key":"255_CR35","unstructured":"MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 8.1. Available at http:\/\/docs.mosek.com\/8.1\/toolbox\/index.html (2017). Accessed 1 Oct 2019"},{"key":"255_CR36","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"255_CR37","doi-asserted-by":"crossref","unstructured":"Permenter, F., Parrilo, P.\u00a0A.: Basis selection for SOS programs via facial reduction and polyhedral approximations. In: 53rd IEEE Conference on Decision and Control, CDC 2014, pp. 6615\u20136620 (2014)","DOI":"10.1109\/CDC.2014.7040427"},{"key":"255_CR38","unstructured":"Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone. Math. Program. 1\u201354 (2014)"},{"key":"255_CR39","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, London (1998)"},{"key":"255_CR40","doi-asserted-by":"crossref","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11, 625\u2013653 (1999)","DOI":"10.1080\/10556789908805766"},{"key":"255_CR41","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10479-017-2720-z","volume":"265","author":"A Tanaka","year":"2018","unstructured":"Tanaka, A., Yoshise, A.: LP-based tractable subcones of the semidefinite plus nonnegative cone. Ann. Oper. Res. 265, 155\u2013182 (2018)","journal-title":"Ann. Oper. Res."},{"key":"255_CR42","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0962492901000071","volume":"10","author":"MJ Todd","year":"2001","unstructured":"Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515\u2013560 (2001)","journal-title":"Acta Numer."},{"key":"255_CR43","doi-asserted-by":"crossref","unstructured":"Toh, K.-C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3\u2014a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11 ,545\u2013581 (1999)","DOI":"10.1080\/10556789908805762"},{"key":"255_CR44","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/s10957-012-0219-y","volume":"158","author":"H Waki","year":"2013","unstructured":"Waki, H., Muramatsu, M.: Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158, 188\u2013215 (2013)","journal-title":"J. Optim. Theory Appl."},{"key":"255_CR45","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF01292722","volume":"7","author":"H Weyl","year":"1935","unstructured":"Weyl, H.: Elementare theorie der konvexen polyeder. Comment. Math. Helvet. 7, 290\u2013306 (1935)","journal-title":"Comment. Math. Helvet."},{"key":"255_CR46","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, vol.\u00a027. Springer, Berlin (2012)"},{"key":"255_CR47","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0). Optim. Methods Softw. 18, 491\u2013505 (2003)","DOI":"10.1080\/1055678031000118482"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00255-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00255-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00255-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T17:30:01Z","timestamp":1614274201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00255-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,2]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["255"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00255-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2021,1,2]]},"assertion":[{"value":"28 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}