{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:29:04Z","timestamp":1765232944468,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T00:00:00Z","timestamp":1599696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T00:00:00Z","timestamp":1599696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"H2020 Marie Sklodowska-Curie Actions","award":["MINOA 764759"],"award-info":[{"award-number":["MINOA 764759"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Alternating direction methods of multipliers (ADMMs) are popular approaches to handle large scale semidefinite programs that gained attention during the past decade. In this paper, we focus on solving doubly nonnegative programs (DNN), which are semidefinite programs where the elements of the matrix variable are constrained to be nonnegative. Starting from two algorithms already proposed in the literature on conic programming, we introduce two new ADMMs by employing a factorization of the dual variable. It is well known that first order methods are not suitable to compute high precision optimal solutions, however an optimal solution of moderate precision often suffices to get high quality lower bounds on the primal optimal objective function value. We present methods to obtain such bounds by either perturbing the dual objective function value or by constructing a dual feasible solution from a dual approximate optimal solution. Both procedures can be used as a post-processing phase in our ADMMs. Numerical results for DNNs that are relaxations of the stable set problem are presented. They show the impact of using the factorization of the dual variable in order to improve the progress towards the optimal solution within an iteration of the ADMM. This decreases the number of iterations as well as the CPU time to solve the DNN to a given precision. The experiments also demonstrate that within a computationally cheap post-processing, we can compute bounds that are close to the optimal value even if the DNN was solved to moderate precision only. This makes ADMMs applicable also within a branch-and-bound algorithm.<\/jats:p>","DOI":"10.1007\/s10288-020-00454-x","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T13:24:18Z","timestamp":1599744258000},"page":"415-448","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Improving ADMMs for solving doubly nonnegative programs through dual factorization"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-5917","authenticated-orcid":false,"given":"Martina","family":"Cerulli","sequence":"first","affiliation":[]},{"given":"Marianna","family":"De Santis","sequence":"additional","affiliation":[]},{"given":"Elisabeth","family":"Gaar","sequence":"additional","affiliation":[]},{"given":"Angelika","family":"Wiegele","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,10]]},"reference":[{"key":"454_CR1","volume-title":"Constrained optimization and Lagrange multiplier methods","author":"DP Bertsekas","year":"1982","unstructured":"Bertsekas DP (1982) Constrained optimization and Lagrange multiplier methods. Academic Press Inc., New York"},{"issue":"1\u20132","key":"454_CR2","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-014-0826-5","volume":"155","author":"C Chen","year":"2016","unstructured":"Chen C, He B, Ye Y, Yuan X (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math Program 155(1\u20132):57\u201379","journal-title":"Math Program"},{"issue":"5","key":"454_CR3","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/j.orl.2018.08.003","volume":"46","author":"M De Santis","year":"2018","unstructured":"De Santis M, Rendl F, Wiegele A (2018) Using a factored dual in augmented Lagrangian methods for semidefinite programming. Oper Res Lett 46(5):523\u2013528","journal-title":"Oper Res Lett"},{"key":"454_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-030-17953-3_16","volume-title":"Integer programming and combinatorial optimization","author":"E Gaar","year":"2019","unstructured":"Gaar E, Rendl F (2019) A bundle approach for SDPs with exact subgraph constraints. In: Lodi A, Nagarajan V (eds) Integer programming and combinatorial optimization. Springer, Berlin, pp 205\u2013218"},{"key":"454_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.endm.2013.05.088","volume":"41","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico M, Letchford AN, Rossi F, Smriglio S (2013) Approximating the Lov\u00e1sz $$\\theta $$ function with the subgradient method. Electron Notes Discret Math 41:157\u2013164. https:\/\/doi.org\/10.1016\/j.endm.2013.05.088","journal-title":"Electron Notes Discret Math"},{"issue":"1","key":"454_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J (1999) Clique is hard to approximate within $$n^{1 - \\varepsilon }$$. Acta Math 182(1):105\u2013142. https:\/\/doi.org\/10.1007\/BF02392825","journal-title":"Acta Math"},{"issue":"1","key":"454_CR7","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/050622870","volume":"46","author":"C Jansson","year":"2008","unstructured":"Jansson C, Chaykin D, Keil C (2008) Rigorous error bounds for the optimal value in semidefinite programming. SIAM J Numer Anal 46(1):180\u2013200. https:\/\/doi.org\/10.1137\/050622870","journal-title":"SIAM J Numer Anal"},{"key":"454_CR8","doi-asserted-by":"crossref","unstructured":"Johnson DJ, Trick MA (eds.) (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society","DOI":"10.1090\/dimacs\/026"},{"key":"454_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2-9","volume-title":"Complexity of computer computations, The IBM Research Symposia Series","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations, The IBM Research Symposia Series. Springer, USA, pp 85\u2013103. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2-9"},{"issue":"1","key":"454_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10589-019-00106-9","volume":"74","author":"DA Lorenz","year":"2019","unstructured":"Lorenz DA, Tran-Dinh Q (2019) Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence. Comput Optim Appl 74(1):67\u201392. https:\/\/doi.org\/10.1007\/s10589-019-00106-9","journal-title":"Comput Optim Appl"},{"issue":"1","key":"454_CR11","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1137\/070704575","volume":"20","author":"J Malick","year":"2009","unstructured":"Malick J, Povh J, Rendl F, Wiegele A (2009) Regularization methods for semidefinite programming. SIAM J Optim 20(1):336\u2013356","journal-title":"SIAM J Optim"},{"key":"454_CR12","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-1-4614-1927-3_17","volume-title":"Mixed integer nonlinear programming","author":"F Rendl","year":"2012","unstructured":"Rendl F (2012) Matrix relaxations in combinatorial optimization. In: Lee J, Leyffer S (eds) Mixed integer nonlinear programming. Springer, New York, pp 483\u2013511"},{"issue":"4","key":"454_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver A (1979) A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans Inf Theory 25(4):425\u2013429. https:\/\/doi.org\/10.1109\/TIT.1979.1056072","journal-title":"IEEE Trans Inf Theory"},{"key":"454_CR14","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/140964357","volume":"25","author":"D Sun","year":"2015","unstructured":"Sun D, Toh KC, Yang L (2015) A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J Optim 25:882\u2013915","journal-title":"SIAM J Optim"},{"issue":"3","key":"454_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s12532-010-0017-1","volume":"2","author":"Z Wen","year":"2010","unstructured":"Wen Z, Goldfarb D, Yin W (2010) Alternating direction augmented Lagrangian methods for semidefinite programming. Math Program Comput 2(3):203\u2013230","journal-title":"Math Program Comput"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00454-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-020-00454-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00454-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T14:10:48Z","timestamp":1631887848000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-020-00454-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,10]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["454"],"URL":"https:\/\/doi.org\/10.1007\/s10288-020-00454-x","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2020,9,10]]},"assertion":[{"value":"23 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}