Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T23:53:22.897Z Has data issue: false hasContentIssue false
  • English
  • Français

Linear optimization over homogeneous matrix cones

Part of: Operations research, mathematical programming Special matrices

Published online by Cambridge University Press:  11 May 2023

Levent Tunçel  and
Lieven Vandenberghe Open the ORCID record for Lieven Vandenberghe [Opens in a new window]
Levent Tunçel
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada E-mail: [email protected]
Lieven Vandenberghe
Affiliation:
Department of Electrical and Computer Engineering, UCLA, Los Angeles, CA 90095-1594, USA E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone. Cones that are homogeneous and self-dual are called symmetric. Conic optimization problems over symmetric cones have been extensively studied, particularly in the literature on interior-point algorithms, and as the foundation of modelling tools for convex optimization. In this paper we consider the less well-studied conic optimization problems over cones that are homogeneous but not necessarily self-dual.

We start with cones of positive semidefinite symmetric matrices with a given sparsity pattern. Homogeneous cones in this class are characterized by nested block-arrow sparsity patterns, a subset of the chordal sparsity patterns. Chordal sparsity guarantees that positive define matrices in the cone have zero-fill Cholesky factorizations. The stronger properties that make the cone homogeneous guarantee that the inverse Cholesky factors have the same zero-fill pattern. We describe transitive subsets of the cone automorphism groups, and important properties of the composition of log-det barriers with the automorphisms.

Next, we consider extensions to linear slices of the positive semidefinite cone, and review conditions that make such cones homogeneous. An important example is the matrix norm cone, the epigraph of a quadratic-over-linear matrix function. The properties of homogeneous sparse matrix cones are shown to extend to this more general class of homogeneous matrix cones.

We then give an overview of the algebraic theory of homogeneous cones due to Vinberg and Rothaus. A fundamental consequence of this theory is that every homogeneous cone admits a spectrahedral (linear matrix inequality) representation.

We conclude by discussing the role of homogeneous structure in primal–dual symmetric interior-point methods, contrasting this with the well-developed algorithms for symmetric cones that exploit the strong properties of self-scaled barriers, and with symmetric primal–dual methods for general convex cones.

MSC classification

Primary: 90-02: Research exposition (monographs, survey articles) 90C25: Convex programming
Secondary: 15B48: Positive matrices and their generalizations; cones of matrices 65K05: Mathematical programming methods 90C22: Semidefinite programming 90C51: Interior-point methods
Type
Research Article
Information
Acta Numerica , Volume 32 , May 2023 , pp. 675 - 747
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2023. Published by Cambridge University Press

References

Agler, J., Helton, J. W., McCullough, S. and Rodman, L. (1988), Positive semidefinite matrices with a given sparsity pattern, Linear Algebra Appl. 107, 101–149.CrossRefGoogle Scholar
Andersen, M. S., Dahl, J. and Vandenberghe, L. (2010a), Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Math. Program. Comput. 2, 167–201.CrossRefGoogle Scholar
Andersen, M. S., Dahl, J. and Vandenberghe, L. (2013), Logarithmic barriers for sparse matrix cones, Optim. Methods Softw. 28, 396–423.CrossRefGoogle Scholar
Andersen, M. S., Vandenberghe, L. and Dahl, J. (2010b), Linear matrix inequalities with chordal sparsity patterns and applications to robust quadratic optimization, in Proceedings of the 2010 IEEE International Symposium on Computer-Aided Control System Design (CACSD), pp. 7–12.CrossRefGoogle Scholar
Andersson, S. A. and Wojnar, G. G. (2004), Wishart distributions on homogeneous cones, J. Theoret. Probab. 17, 781–818.CrossRefGoogle Scholar
Averkov, G. (2019), Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization, SIAM J. Appl. Algebra Geom. 3, 128–151.CrossRefGoogle Scholar
Bartholdi, J. J. III (1981/82), A good submatrix is hard to find, Oper . Res. Lett. 1, 190–193.Google Scholar
Ben-Tal, A. and Nemirovski, A. (2001), Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM.CrossRefGoogle Scholar
Ben-Tal, A., El Ghaoui, L. and Nemirovski, A. (2009), Robust Optimization, Princeton University Press.CrossRefGoogle Scholar
Benson, S. J., Ye, Y. and Zhang, X. (2000), Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim. 10, 443–461.CrossRefGoogle Scholar
Björck, Å. (1996), Numerical Methods for Least Squares Problems, SIAM.CrossRefGoogle Scholar
Blair, J. R. S. and Peyton, B. (1993), An introduction to chordal graphs and clique trees, in Graph Theory and Sparse Matrix Computation (George, A. et al., eds), Springer, pp. 1–29.Google Scholar
Boutouria, I., Hassairi, A. and Massam, H. (2011), Extension of the Olkin and Rubin characterization to the Wishart distribution on homogeneous cones, Infin . Dimens. Anal. Quantum Probab. Relat. Top. 14, 591–611.CrossRefGoogle Scholar
Boyd, S. and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.CrossRefGoogle Scholar
Burer, S. (2003), Semidefinite programming in the space of partial positive semidefinite matrices, SIAM J. Optim. 14, 139–172.CrossRefGoogle Scholar
Chares, P. R. (2009), Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. PhD thesis, Université Catholique de Louvain.Google Scholar
Chaudhuri, S., Drton, M. and Richardson, T. S. (2007), Estimation of a covariance matrix with zeros, Biometrika 94, 199–216.CrossRefGoogle Scholar
Chu, F. P. M. (2008), A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complement, Inform. Process. Lett. 107, 7–12.CrossRefGoogle Scholar
Chua, C. B. (2003), Relating homogeneous cones and positive definite cones via $T$ -algebras, SIAM J. Optim. 14, 500–506.Google Scholar
Chua, C. B. (2009), A $T$ -algebraic approach to primal–dual interior-point algorithms, SIAM J. Optim. 20, 503–523.CrossRefGoogle Scholar
Chua, C. B. and Tunçel, L. (2008), Invariance and efficiency of convex representations, Math. Program. 111, 113–140.CrossRefGoogle Scholar
Corneil, D. G. (2004), Lexicographic breadth first search: A survey, in Graph-Theoretic Concepts in Computer Science, Vol. 3353 of Lecture Notes in Computer Science, Springer, pp. 1–19.CrossRefGoogle Scholar
Dahl, J. and Andersen, E. D. (2022), A primal–dual interior-point algorithm for nonsymmetric exponential-cone optimization, Math. Program. 194, 341–370.CrossRefGoogle Scholar
Diamond, S. and Boyd, S. (2016), CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res. 17, 1–5.Google ScholarPubMed
Drton, M. and Richardson, T. S. (2008), Graphical methods for efficient likelihood inference in Gaussian covariance models, J. Mach. Learn. Res. 9, 893–914.Google Scholar
Duff, I. S. and Reid, J. K. (1983), The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Softw. 9, 302–325.CrossRefGoogle Scholar
Duff, I. S., Erisman, A. M. and Reid, J. K. (2017), Direct Methods for Sparse Matrices, Oxford University Press.CrossRefGoogle Scholar
El Ghaoui, L. and Lebret, H. (1997), Robust solutions to least-squares problems with uncertain data, SIAM J. Matrix Anal. Appl. 18, 1035–1064.CrossRefGoogle Scholar
El-Mallah, E. S. and Colbourn, C. J. (1988), The complexity of some edge deletion problems, IEEE Trans. Circuits Systems 35, 354–362.CrossRefGoogle Scholar
Fawzi, H. (2020), Lifts of convex sets, in Sum of Squares: Theory and Applications , Vol. 77 of Proceedings of Symposia in Applied Mathematics, American Mathematical Society, pp. 37–57.Google Scholar
Fawzi, H. and Saunderson, J. (2022), Optimal self-concordant barriers for quantum relative entropies. Available at arXiv:2205.04581.Google Scholar
Faybusovich, L. (2002), On Nesterov’s approach to semi-infinite programming, Acta Appl. Math. 74, 195–215.CrossRefGoogle Scholar
Faybusovich, L. and Zhou, C. (2022), Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications, Numer . Algebra Control Optim. 12, 445–467.CrossRefGoogle Scholar
Fu, A., Narasimhan, B. and Boyd, S. (2020), CVXR: An R package for disciplined convex optimization, J. Statist. Softw. 94, 1–34.CrossRefGoogle Scholar
Fukuda, M., Kojima, M., Murota, K. and Nakata, K. (2000/01), Exploiting sparsity in semidefinite programming via matrix completion, I: General framework, SIAM J. Optim. 11, 647–674.CrossRefGoogle Scholar
Fulkerson, D. R. and Gross, O. (1965), Incidence matrices and interval graphs, Pacific J. Math. 15, 835–855.CrossRefGoogle Scholar
George, A. and Liu, J. W. H. (1981), Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall.Google Scholar
Gindikin, S. (1992), Tube Domains and the Cauchy Problem, Vol. 111 of Translations of Mathematical Monographs, American Mathematical Society.CrossRefGoogle Scholar
Golub, G. H. and Plemmons, R. J. (1980), Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition, Linear Algebra Appl. 34, 3–27.CrossRefGoogle Scholar
Golumbic, M. C. (1978), Trivially perfect graphs, Discrete Math. 24, 105–107.CrossRefGoogle Scholar
Golumbic, M. C. (2004), Algorithmic Graph Theory and Perfect Graphs, second edition, Elsevier.Google Scholar
Gouveia, J., Parrilo, P. A. and Thomas, R. R. (2013), Lifts of convex sets and cone factorizations, Math. Oper. Res. 38, 248–264.CrossRefGoogle Scholar
M. Grant and Boyd, S. (2014), CVX: Matlab software for disciplined convex programming, version 2.1. Available at http://cvxr.com/cvx.Google Scholar
Griewank, A. and Toint, P. L. (1984), On the existence of convex decompositions of partially separable functions, Math. Program. 28, 25–49.CrossRefGoogle Scholar
Grone, R., Johnson, C. R., Sá, E. M. and Wolkowicz, H. (1984), Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58, 109–124.CrossRefGoogle Scholar
Güler, O. (1996), Barrier functions in interior point methods, Math. Oper. Res. 21, 860–885.CrossRefGoogle Scholar
Güler, O. (1997), Hyperbolic polynomials and interior point methods for convex programming, Math. Oper. Res. 22, 350–377.CrossRefGoogle Scholar
Güler, O. and Tunçel, L. (1998), Characterization of the barrier parameter of homogeneous convex cones, Math. Program. 81, 55–76.CrossRefGoogle Scholar
Habib, M., McConnell, R., Paul, C. and Viennot, L. (2000), Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoret . Comput. Sci. 234, 59–84.Google Scholar
Helton, J. W. and Nie, J. (2010), Semidefinite representation of convex sets, Math. Program. 122, 21–64.CrossRefGoogle Scholar
Helton, J. W. and Vinnikov, V. (2007), Linear matrix inequality representation of sets, Commun . Pure Appl. Math. 60, 654–674.CrossRefGoogle Scholar
Ishi, H. (2013), On a class of homogeneous cones consisting of real symmetric matrices, Josai Math. Monogr. 6, 71–80.Google Scholar
Ishi, H. (2015), Matrix realization of a homogeneous cone, in Geometric Science of Information (Nielsen, F. and Barbaresco, F., eds), Springer International Publishing, pp. 248–256.Google Scholar
Ishi, H. (2016), Explicit formula of Koszul–Vinberg characteristic functions for a wide class of regular convex cones, Entropy 18, 383.CrossRefGoogle Scholar
Jansen, B., Roos, C. and Terlaky, T. (1996), A polynomial primal–dual Dikin-type algorithm for linear programming, Math. Oper. Res. 21, 341–353.CrossRefGoogle Scholar
Karimi, M. and Tunçel, L. (2020a), Domain-driven solver (DDS) version 2.0: A MATLAB-based software package for convex optimization problems in domain-driven form. Available at arXiv:1908.03075 .Google Scholar
Karimi, M. and Tunçel, L. (2020b), Primal–dual interior-point methods for domain-driven formulations, Math. Oper. Res. 45, 591–621.Google Scholar
Khare, K. and Rajaratnam, B. (2011), Wishart distributions for decomposable covariance graph models, Ann . Statist. 39, 514–555.CrossRefGoogle Scholar
Khare, K. and Rajaratnam, B. (2012), Sparse matrix decompositions and graph characterizations, Linear Algebra Appl. 437, 932–947.CrossRefGoogle Scholar
Kočvara, M. (2021), Decomposition of arrow type positive semidefinite matrices with application to topology optimization, Math. Program. 190, 105–134.CrossRefGoogle Scholar
Kojima, M., Megiddo, N., Noma, T. and Yoshise, A. (1991), A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Vol. 538 of Lecture Notes in Computer Science, Springer.CrossRefGoogle Scholar
Kong, L., Tunçel, L. and Xiu, N. (2012), Existence and uniqueness of solutions for homogeneous cone complementarity problems, J. Optim. Theory Appl. 153, 357–376.CrossRefGoogle Scholar
Lasdon, L. S. (2002), Optimization Theory for Large Systems, Dover Publications. First published in 1970 by the Macmillan Company.Google Scholar
Letac, G. and Massam, H. (2007), Wishart distributions for decomposable graphs, Ann . Statist. 35, 1278–1323.CrossRefGoogle Scholar
Liu, J. W. H. (1990), The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11, 134–172.CrossRefGoogle Scholar
Liu, J. W. H. (1992), The multifrontal method for sparse matrix solution: Theory and practice, SIAM Review 34, 82–109.CrossRefGoogle Scholar
Liu, J. W. H., Ng, E. G. and Peyton, B. W. (1993), On finding supernodes for sparse matrix computations, SIAM J. Matrix Anal. Appl. 14, 242–252.CrossRefGoogle Scholar
Lofberg, J. (2004), YALMIP: A toolbox for modeling and optimization in MATLAB, in 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No. 04CH37508), IEEE, pp. 284–289.Google Scholar
Myklebust, T. and Tunçel, L. (2014), Interior-point algorithms for convex optimization based on primal–dual metrics. Available at arXiv:1411.2129.Google Scholar
Natanzon, A., Shamir, R. and Sharan, R. (2000), A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput. 30, 1067–1079.CrossRefGoogle Scholar
Nemirovski, A. (2007), Advances in convex optimization: Conic programming, in International Congress of Mathematicians Madrid 2006, Vol. I: Plenary Lectures and Ceremonies, European Mathematical Society, pp. 413–444.Google Scholar
Nemirovski, A. S. and Todd, M. J. (2008), Interior-point methods for optimization, Acta Numer. 17, 191–234.CrossRefGoogle Scholar
Nesterov, Y. (2000), Squared functional systems and optimization problems, in High Performance Optimization Techniques (Frenk, J. et al., eds), Kluwer Academic, pp. 405–440.CrossRefGoogle Scholar
Nesterov, Y. (2008), Parabolic target space and primal–dual interior-point methods, Discrete Appl. Math. 156, 2079–2100.CrossRefGoogle Scholar
Nesterov, Y. (2012), Towards non-symmetric conic optimization, Optim. Methods Softw. 27, 893–917.CrossRefGoogle Scholar
Nesterov, Y. and Nemirovskii, A. (1994), Interior-Point Polynomial Algorithms in Convex Programming , Vol. 13 of SIAM Studies in Applied Mathematics, SIAM. Google Scholar
Nesterov, Y. and Todd, M. J. (1997), Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22, 1–42.CrossRefGoogle Scholar
Nesterov, Y. and Todd, M. J. (1998), Primal–dual interior-point methods for self-scaled cones, SIAM J. Optim. 8, 324–364.CrossRefGoogle Scholar
Nesterov, Y. and Todd, M. J. (2002), On the Riemannian geometry defined by self-concordant barriers and interior-point methods, Found. Comput. Math. 2, 333–361.CrossRefGoogle Scholar
Nesterov, Y. and Tunçel, L. (2016), Local superlinear convergence of polynomial-time interior-point methods for hyperbolicity cone optimization problems, SIAM J. Optim. 26, 139–170.CrossRefGoogle Scholar
Papp, D. and Alizadeh, F. (2013), Semidefinite characterization of sum-of-squares cones in algebras, SIAM J. Optim. 23, 1398–1423.CrossRefGoogle Scholar
Papp, D. and Yldz, S. (2022), Alfonso: Matlab package for nonsymmetric conic optimization, INFORMS J. Comput. 34, 11–19.CrossRefGoogle Scholar
Pearl, J. and Wermuth, N. (1994), When can association graphs admit a causal interpretation?, in Selecting Models from Data, Springer, pp. 205–214.CrossRefGoogle Scholar
Renegar, J. (2001), A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, SIAM and Mathematical Programming Society (MPS).CrossRefGoogle Scholar
Renegar, J. and Sondjaja, M. (2014), A polynomial-time affine-scaling method for semidefinite and hyperbolic programming. Available at arXiv:1410.6734.Google Scholar
Rockafellar, R. T. (1970), Convex Analysis, Princeton University Press.CrossRefGoogle Scholar
Rose, D. J., Tarjan, R. E. and Lueker, G. S. (1976), Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5, 266–283.CrossRefGoogle Scholar
Rothaus, O. S. (1963), The construction of homogeneous convex cones, Bull. Amer. Math. Soc. 69, 248–250.CrossRefGoogle Scholar
Rothaus, O. S. (1966), The construction of homogeneous convex cones, Ann. of Math. ( 2 ) 83, 358–376.CrossRefGoogle Scholar
Rothaus, O. S. (1968), Correction to: ‘The construction of homogeneous convex cones’, Ann. of Math. ( 2 ) 87, 399.CrossRefGoogle Scholar
Roy, S. and Xiao, L. (2022), On self-concordant barriers for generalized power cones, Optim. Lett. 16, 681–694.CrossRefGoogle Scholar
Sagnol, G. and Stahlberg, M. (2022), PICOS: A Python interface to conic optimization solvers, J. Open Source Software 7, 3915.CrossRefGoogle Scholar
Saunders, M. A. (1972), Product form of the Cholesky factorization for large-scale linear programming. Technical report STAN-CS-72-301, Stanford University.Google Scholar
Scheiderer, C. (2018), Spectrahedral shadows, SIAM J. Appl. Algebra Geom. 2, 26–44.CrossRefGoogle Scholar
Schnabel, R. B. (1983), Quasi-Newton methods using multiple secant equations. Technical report, University of Colorado at Boulder.CrossRefGoogle Scholar
Skajaa, A. and Ye, Y. (2015), A homogeneous interior-point algorithm for nonsymmetric convex conic optimization, Math. Program. 150, 391–422.CrossRefGoogle Scholar
Sorensen, D. C. (1982), Collinear scaling and sequential estimation in sparse optimization algorithms, in Algorithms and Theory in Filtering and Control (Sorensen, D. C. and Wets, R. J.-B., eds), Vol. 18 of Mathematical Programming Studies, Springer, pp. 135–159.CrossRefGoogle Scholar
Srijuntongsiri, G. and Vavasis, S. (2004), A fully sparse implementation of a primal–dual interior-point potential reduction method for semidefinite programming. Available at arXiv.cs:0412009.Google Scholar
Sturm, J. F. and Zhang, S. (1999), Symmetric primal–dual path-following algorithms for semidefinite programming, Appl. Numer. Math. 29, 301–315.CrossRefGoogle Scholar
Tarjan, R. E. and Yannakakis, M. (1984), Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13, 566–579.CrossRefGoogle Scholar
Todd, M. J. (2009), Largest dual ellipsoids inscribed in dual cones, Math. Program. 117, 425–434.CrossRefGoogle Scholar
Truong, V. A. and Tunçel, L. (2004), Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers, Math. Program. 100, 295–316.CrossRefGoogle Scholar
Tunçel, L. (1998), Primal–dual symmetry and scale invariance of interior-point algorithms for convex optimization, Math. Oper. Res. 23, 708–718.CrossRefGoogle Scholar
Tunçel, L. (2001), Generalization of primal–dual interior-point methods to convex optimization problems in conic form, Found . Comput. Math. 1, 229–254.Google Scholar
Vandenberghe, L. and Andersen, M. S. (2014), Chordal graphs and semidefinite optimization, Found . Trends Optim. 1, 241–433.Google Scholar
Vinberg, E. B. (1965a), Structure of the group of automorphisms of a homogeneous convex cone, Trudy Moskov . Mat. Obšč. 13, 56–83.Google Scholar
Vinberg, E. B. (1965b), The theory of homogeneous cones, Trans. Moscow Math. Soc. 12, 340–403.Google Scholar
Wolk, E. S. (1962), The comparability graph of a tree, Proc . Amer. Math. Soc. 13, 789–795.CrossRefGoogle Scholar
Wolk, E. S. (1965), A note on ‘The comparability graph of a tree’, Proc. Amer. Math. Soc. 16, 17–20.Google Scholar
Yamasaki, T. and Nomura, T. (2015), Realization of homogeneous cones through oriented graphs, Kyushu J. Math. 69, 11–48.CrossRefGoogle Scholar
Yan, J.-H., Chen, J.-J. and Chang, G. J. (1996), Quasi-threshold graphs, Discrete Appl. Math. 69, 247–255.Google Scholar
Yannakakis, M. (1981), Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2, 77–79.CrossRefGoogle Scholar
Zheng, Y., Fantuzzi, G. and Papachristodoulou, A. (2021), Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization, Annu . Rev. Control 52, 243–279.CrossRefGoogle Scholar