1 paper accepted to CDC 21

Our paper on tight inner approximation of the positive-semidefinite cone [1] have been accepted to IEEE Conference on Decision and Control!

[1] T. Zheng, J. Guthrie, and E. Mallada, “Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings,” in 60th IEEE Conference on Decision and Control (CDC), 2021.
[Bibtex] [Abstract] [Download PDF]

We investigate the problem of finding tight innerapproximations of large dimensional positive semidefinite (PSD)cones. To solve this problem, we develop a novel decompositionframework of the PSD cone by means of conical combinationsof smaller dimensional sub-cones. We show that many innerapproximation techniques could be summarized within thisframework, including the set of (scaled) diagonally dominantmatrices, Factor-widthkmatrices, and Chordal Sparse ma-trices. Furthermore, we provide a more flexible family ofinner approximations of the PSD cone, where we aim toarrange the sub-cones so that they are maximally separatedfrom each other. In doing so, these approximations tend tooccupy large fractions of the volume of the PSD cone. Theproposed approach is connected to a classical packing problemin Riemannian Geometry. Precisely, we show that the problemof finding maximally distant sub-cones in an ambient PSD coneis equivalent to the problem of packing sub-spaces in a Grass-mannian Manifold. We further leverage existing computationalmethod for constructing packings in Grassmannian manifoldsto build tighter approximations of the PSD cone. Numericalexperiments show how the proposed framework can balancebetween accuracy and computational complexity, to efficientlysolve positive-semidefinite programs.

@inproceedings{zgm2021cdc,
  abstract = {We investigate the problem of finding tight innerapproximations of large dimensional positive semidefinite (PSD)cones. To solve this problem, we develop a novel decompositionframework of the PSD cone by means of conical combinationsof smaller dimensional sub-cones. We show that many innerapproximation techniques could be summarized within thisframework, including the set of (scaled) diagonally dominantmatrices, Factor-widthkmatrices, and Chordal Sparse ma-trices. Furthermore, we provide a more flexible family ofinner approximations of the PSD cone, where we aim toarrange the sub-cones so that they are maximally separatedfrom each other. In doing so, these approximations tend tooccupy large fractions of the volume of the PSD cone. Theproposed approach is connected to a classical packing problemin Riemannian Geometry. Precisely, we show that the problemof finding maximally distant sub-cones in an ambient PSD coneis equivalent to the problem of packing sub-spaces in a Grass-mannian Manifold. We further leverage existing computationalmethod for constructing packings in Grassmannian manifoldsto build tighter approximations of the PSD cone. Numericalexperiments show how the proposed framework can balancebetween accuracy and computational complexity, to efficientlysolve positive-semidefinite programs.},
  author = {Zheng, Tianqi and Guthrie, James and Mallada, Enrique},
  booktitle = {60th IEEE Conference on Decision and Control (CDC)},
  grants = {EPCN-1711188, CAREER-1752362, AMPS-1736448, TRIPODS-1934979},
  month = {7},
  pubstate = {accepted, submitted Mar. 2021},
  title = {Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings},
  url = {https://mallada.ece.jhu.edu/pubs/2021-Preprint-ZGM.pdf},
  year = {2021}
}