An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix

References

• Anstreicher KM (1998) Toward a practical volumetric cutting plane method for convex programming. SIAM J. Optim. 9(1):190–206.Crossref, Google Scholar
• Anstreicher KM (2020) Testing copositivity via mixed–integer linear programming. Linear Algebra Appl. 609:218–230.Crossref, Google Scholar
• Anstreicher K, Burer S, Dickinson P (2012) An algorithm to compute the CP-factorization of a completely positive matrix. Working paper, University of Iowa, Iowa City.Google Scholar
• Anstreicher K, Burer S, Dickinson P (2017) An algorithm to compute the CP-factorization of a completely positive matrix. Oberwolfach Rep. 52:3079–3081.Google Scholar
• Atkinson DS, Vaidya PM (1995) A cutting plane algorithm for convex programming that uses analytic centers. Math. Programming 69(1–3):1–43.Crossref, Google Scholar
• Badenbroek R, de Klerk E (2019) Simulated annealing with hit-and-run for convex optimization: rigorous complexity analysis and practical perspectives for copositive programming. Preprint, submitted July 4, https://arxiv.org/abs/1907.02368.Google Scholar
• Berman A, Dur M, Shaked-Monderer N (2015) Open problems in the theory of completely positive and copositive matrices. Electronic J. Linear Algebra 29(1):46–58.Crossref, Google Scholar
• Bomze IM (2018) Building a completely positive factorization. Central Eur. J. Oper. Res. 26(2):287–305.Crossref, Google Scholar
• Bomze IM, De Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2):163–185.Crossref, Google Scholar
• Bomze IM, Jarre F, Rendl F (2011) Quadratic factorization heuristics for copositive programming. Math. Programming Comput. 3(1):37–57.Crossref, Google Scholar
• Boyd S, Vandenberghe L, Skaf J (2011) Analytic center cutting-plane method. Lecture notes, University of California, Los Angeles, Los Angeles.Google Scholar
• Bundfuss S, Dür M (2008) Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428(7):1511–1523.Crossref, Google Scholar
• Bundfuss S, Dür M (2009) An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1):30–53.Crossref, Google Scholar
• Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479–495.Crossref, Google Scholar
• Burer S, Dong H (2013) Separation and relaxation for cones of quadratic forms. Math. Programming 137(1–2):343–370.Crossref, Google Scholar
• de Klerk E, Pasechnik DV (2002) Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4):875–892.Crossref, Google Scholar
• Dickinson PJC (2019) A new certificate for copositivity. Linear Algebra Appl. 569:15–37.Crossref, Google Scholar
• Dickinson PJ, Dür M (2012) Linear-time complete positivity detection and decomposition of sparse matrices. SIAM J. Matrix Anal. Appl. 33(3):701–720.Crossref, Google Scholar
• Dickinson PJ, Gijben L (2014) On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2):403–415.Crossref, Google Scholar
• Elser V (2017) Matrix product constraints by projection methods. J. Global Optim. 68(2):329–355.Crossref, Google Scholar
• Fazel M, Hindi H, Boyd SP (2001) A rank minimization heuristic with application to minimum order system approximation. Zhu JJ, ed. Proc. 2001 Amer. Control Conf., vol. 6 (IEEE, Piscataway, NJ), 4734–4739.Google Scholar
• Gaddum JW (1958) Linear inequalities and quadratic forms. Pacific J. Math. 8(3):411–414.Crossref, Google Scholar
• Goffin JL, Vial JP (1993) On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm. Math. Programming 60(1–3):81–92.Crossref, Google Scholar
• Goffin JL, Vial JP (2002) Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optim. Methods Software 17(5):805–867.Crossref, Google Scholar
• Goffin JL, Luo ZQ, Ye Y (1996) Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J. Optim. 6(3):638–652.Crossref, Google Scholar
• Gondzio J, Yıldırım EA (2021) Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. J. Global Optim. 1–29.Google Scholar
• Groetzner P, Dür M (2020) A factorization method for completely positive matrices. Linear Algebra Appl. 591:1–24.Crossref, Google Scholar
• Hiriart-Urruty JB, Seeger A (2010) A variational approach to copositive matrices. SIAM Rev. 52(4):593–629.Crossref, Google Scholar
• Jarre F, Schmallowsky K (2009) On the computation of C* certificates. J. Global Optim. 45(2):281–296.Crossref, Google Scholar
• Kemperman J, Skibinsky M (1992) Covariance spaces for measures on polyhedral sets. Lecture Notes—Monograph Ser. 22:182–195.Google Scholar
• Kong Q, Lee CY, Teo CP, Zheng Z (2013) Scheduling arrivals to a stochastic service delivery system using copositive cones. Oper. Res. 61(3):711–726.Link, Google Scholar
• Lasserre JB (2014) New approximations for the cone of copositive matrices and its dual. Math. Programming 144(1–2):265–276.Crossref, Google Scholar
• Li X, Natarajan K, Teo CP, Zheng Z (2014) Distributionally robust mixed integer linear programs: Persistency models with applications. Eur. J. Oper. Res. 233(3):459–473.Crossref, Google Scholar
• Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Canadian J. Math. 17:533–540.Crossref, Google Scholar
• Murty KG, Kabadi SN (1987) Some NP-complete problems in quadratic and nonlinear programming. Math. Programming 39(2):117–129.Crossref, Google Scholar
• Natarajan K, Teo CP, Zheng Z (2011) Mixed 0-1 linear programs under objective uncertainty: A completely positive representation. Oper. Res. 59(3):713–728.Link, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Nie J (2014) The A-truncated K-moment problem. Foundations Comput. Math. 14(6):1243–1276.Crossref, Google Scholar
• Nie J, Yang Z, Zhang X (2018) A complete semidefinite algorithm for detecting copositive matrices and tensors. SIAM J. Optim. 28(4):2902–2921.Crossref, Google Scholar
• Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Unpublished PhD thesis, California Institute of Technology, Pasadena, CA.Google Scholar
• Peña J, Vera J, Zuluaga LF (2007) Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1):87–105.Crossref, Google Scholar
• Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Sikirić MD, Schürmann A, Vallentin F (2021) A simplex algorithm for rational cp-factorization. Math. Programming 187(1–2):25–45.Crossref, Google Scholar
• Sponsel J, Dür M (2014) Factorization and cutting planes for completely positive matrices by copositive projection. Math. Programming 143(1–2):211–229.Crossref, Google Scholar
• Xia W, Vera JC, Zuluaga LF (2020) Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. 32(1):40–56.Google Scholar
• Ycart B (1982) Extrémales du cône des matrices de type non négatif, à coefficients positifs ou nuls [in French]. Linear Algebra Appl. 48:317–330.Crossref, Google Scholar
• Yıldırım EA (2012) On the accuracy of uniform polyhedral approximations of the copositive cone. Optim. Methods Software 27(1):155–173.Google Scholar
• Yudin D, Nemirovskii A (1976) Informational complexity and effective methods of solution of convex extremal problems. (In Russian.) Ekonomika i Matematicheskie Metody 12:357–369.Google Scholar