Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems

References

• A.A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization, 48th Annual Conference on Information Sciences and Systems (CISS), IEEE, 2014, pp. 1–5.
   Google Scholar
• A.A. Ahmadi and A. Majumdar, Software for DSOS and SDSOS optimization, 2014. Available at https://github.com/spot-toolbox/spotless (accessed on September 25th, 2019).
   Google Scholar
• M. Alfaki, Models and solution methods for the pooling problem, PhD thesis, The University of Bergen, 2012.
   Google Scholar
• F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. 95(1) (2003), pp. 3–51.
   Web of Science ®Google Scholar
• K.M. Anstreicher, Recent advances in the solution of quadratic assignment problems, Math. Program. 97(1) (2003), pp. 27–42.
   Web of Science ®Google Scholar
• E. Balas, Projection, lifting and extended formulation in integer and combinatorial optimization, Ann. Oper. Res. 140(1) (2005), pp. 125.
   Web of Science ®Google Scholar
• X. Bao, N.V. Sahinidis, and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Math. Program. 129(1) (2011), pp. 129–157.
   Web of Science ®Google Scholar
• P. Biswas, T.-C. Lian, T.-C. Wang, and Y. Ye, Semidefinite programming based algorithms for sensor network localization, ACM. Trans. Sens. Netw. 2(2) (2006), pp. 188–220.
   Web of Science ®Google Scholar
• S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
   Google Scholar
• A. d'Aspremont and S. Boyd, Relaxations and randomized methods for nonconvex QCQPs, EE392o Class Notes, Stanford University, 2003.
   Google Scholar
• A. De Maio, Y. Huang, D.P. Palomar, S. Zhang, and A. Farina, Fractional QCQP with applications in ML steering direction estimation for radar detection, IEEE. Trans. Signal Process. 59(1) (2010), pp. 172–185.
   Web of Science ®Google Scholar
• J. Faraut and A. Koranyi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford, 1994.
   Google Scholar
• K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto, and M. Yamashita, User's manual for SparseCoLO: Conversion methods for sparse conic-form linear optimization problems, Research Report B-453, Dept. of Math. and Comp. Sci. Japan, Tech. Rep., 2009, pp. 152–8552.
   Google Scholar
• M. Fukuda, M. Kojima, K. Murota, and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: General framework, SIAM J. Optim. 11(3) (2001), pp. 647–674.
   Web of Science ®Google Scholar
• M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42(6) (1995), pp. 1115–1145.
   Web of Science ®Google Scholar
• R. Grone, C.R. Johnson, E.M. Sá, and H. Wolkowicz, Positive definite completions of partial hermitian matrices, Linear Algebra Appl. 58 (1984), pp. 109–124.
   Web of Science ®Google Scholar
• M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Vol. 2, Springer Science & Business Media, Berlin, 2012.
   Google Scholar
• Z.-H. Huang, D. Sun, and G. Zhao, A smoothing newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming, Comput. Optim. Appl. 35(2) (2006), pp. 199–237.
   Web of Science ®Google Scholar
• S. Kim and M. Kojima, Second order cone programming relaxation of nonconvex quadratic optimization problems, Optim. Methods Softw. 15(3–4) (2001), pp. 201–224.
   Web of Science ®Google Scholar
• S. Kim and M. Kojima, Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl. 26(2) (2003), pp. 143–154.
   Web of Science ®Google Scholar
• S. Kim, M. Kojima, M. Mevissen, and M. Yamashita, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, Math. Program. 129(1) (2011), pp. 33–68.
   Web of Science ®Google Scholar
• M. Kimizuka, S. Kim, and M. Yamashita, Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods, J. Global Optim. 75(3) (2019), pp. 631–654.
   Web of Science ®Google Scholar
• K. Kobayashi, S. Kim, and M. Kojima, Sparse second order cone programming formulations for convex optimization problems, J. Oper. Res. Soc. Japan 51(3) (2008), pp. 241–264.
   Google Scholar
• X. Kuang, B. Ghaddar, J. Naoum-Sawaya, and L.F. Zuluaga, Alternative sdp and socp approximations for polynomial optimization, EURO J. Comput. Optim. 7(2) (2019), pp. 153–175.
   Web of Science ®Google Scholar
• L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim. 1(2) (1991), pp. 166–190.
   Web of Science ®Google Scholar
• R.P. Mason and A. Papachristodoulou, Chordal sparsity, decomposing SDPs and the Lyapunov equation, 2014 American Control Conference, IEEE, 2014, pp. 531–537.
   Google Scholar
• Mosek ApS, The MOSEK optimization toolbox for MATLAB manual, 2015.
   Google Scholar
• T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of turán, Canad. J. Math. 17 (1965), pp. 533–540.
   Web of Science ®Google Scholar
• K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima, and K. Murota, Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results, Math. Program. 95(2) (2003), pp. 303–327.
   Web of Science ®Google Scholar
• A. Nemirovskii and K. Scheinberg, Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems, Math. Program. 72(3) (1996), pp. 273–289.
   Web of Science ®Google Scholar
• Y. Nesterov and A. Nemirovskii, Interior-point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, 1994.
   Google Scholar
• T. Nishi, A semidefinite programming relaxation approach for the pooling problem, Master's thesis, Kyoto University, 2010.
   Google Scholar
• S. Safarina, S. Moriguchi, T.J. Mullin, and M. Yamashita, Conic relaxation approaches for equal deployment problems, Discr. Appl. Math. 275 (2020), pp. 111–125.
   Web of Science ®Google Scholar
• S. Safarina, T.J. Mullin, and M. Yamashita, Polyhedral-based methods for mixed-integer SOCP in tree breeding, J. Oper. Res. Soc. Japan 62(4) (2019), pp. 133–151.
   Google Scholar
• J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw. 11(1–4) (1999), pp. 625–653.
   Web of Science ®Google Scholar
• L. Vandenberghe and M.S. Andersen, Chordal Graphs and Semidefinite Optimization, Now Publishers, Inc., Hanover, 2015.
   Google Scholar
• M. Yamashita and K. Nakata, Fast implementation for semidefinite programs with positive matrix completion, Optim. Methods Softw. 30(5) (2015), pp. 1030–1049.
   Web of Science ®Google Scholar
• M. Yamashita, T.J. Mullin, and S. Safarina, An efficient second-order cone programming approach for optimal selection in tree breeding, Optim. Lett. 12(7) (2018), pp. 1683–1697.
   Web of Science ®Google Scholar