Document Open Access Logo

Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

Authors Khaled Elbassioni, Kazuhisa Makino

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.43.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Khaled Elbassioni
  • Khalifa University of Science and Technology, Masdar City Campus, P.O. Box 54224, Abu Dhabi, UAE
Kazuhisa Makino
  • Research Institute for Mathematical Sciences (RIMS), Kyoto University, Kyoto 606-8502, Japan

Cite As Get BibTex

Khaled Elbassioni and Kazuhisa Makino. Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.43

Abstract

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, that utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it maybe required to deal with SDP’s with exponentially or infinitely many constraints, which are accessible only via an oracle. In this paper, we give an efficient primal-dual algorithm to solve the problem in this case, which is an extension of a logarithmic-potential based algorithm of Grigoriadis, Khachiyan, Porkolab and Villavicencio (SIAM Journal of Optimization 41 (2001)) for packing/covering linear programs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Semidefinite programming
  • Theory of computation → Numeric approximation algorithms
Keywords
  • Semidefinite programs
  • packing and covering
  • logarithmic potential
  • primal-dual algorithms
  • approximate solutions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. F. Alizadeh. Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM Journal on Optimization, 5(1):13-51, 1995. Google Scholar
  2. Z. Allen-Zhu, Y. Tat Lee, and L. Orecchia. Using Optimization to Obtain a Width-independent, Parallel, Simpler, and Faster Positive SDP Solver. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1824-1831, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  3. Z. Allen-Zhu, Z. Liao, and L. Orecchia. Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 237-245, New York, NY, USA, 2015. ACM. Google Scholar
  4. S. Arora, E. Hazan, and S. Kale. Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method. In Proc. 46th Symp. Foundations of Computer Science (FOCS), pages 339-348, 2005. Google Scholar
  5. S. Arora, E. Hazan, and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(1):121-164, 2012. Google Scholar
  6. S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proc. 39th Symp. Theory of Computing (STOC), pages 227-236, 2007. Google Scholar
  7. S. Arora and S. Kale. A Combinatorial, Primal-Dual Approach to Semidefinite Programs. J. ACM, 63(2):12:1-12:35, May 2016. Google Scholar
  8. J. Batson, D. Spielman, and N. Srivastava. Twice-Ramanujan Sparsifiers. SIAM Review, 56(2):315-334, 2014. Google Scholar
  9. A. Ben-Tal, L. El Ghaoui, and A.S. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, October 2009. Google Scholar
  10. A. Ben-Tal and A. Nemirovski. Robust optimization - methodology and applications. Math. Program., 92(3):453-480, 2002. Google Scholar
  11. R. D. Carr and S. Vempala. Randomized metarounding. Random Struct. Algorithms, 20(3):343-352, 2002. Google Scholar
  12. K. Elbassioni and K. Makino. Finding Sparse Solutions for Packing and Covering Semidefinite Programs. CoRR, abs/1809.09698, 2018. URL: http://arxiv.org/abs/1809.09698.
  13. Dan Garber and Elad Hazan. Sublinear Time Algorithms for Approximate Semidefinite Programming. Math. Program., 158(1-2):329-361, July 2016. Google Scholar
  14. N. Garg and J. Könemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM Journal on Computing, 37(2):630-652, 2007. Google Scholar
  15. M. D. Grigoriadis and L. G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995. Google Scholar
  16. M. D. Grigoriadis, L. G. Khachiyan, L. Porkolab, and J. Villavicencio. Approximate max-min resource sharing for structured concave optimization. SIAM Journal of Optimization, 41:1081-1091, 2001. Google Scholar
  17. G. Iyengar, D. J. Phillips, and C. Stein. Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring. In Michael Jünger and Volker Kaibel, editors, Integer Programming and Combinatorial Optimization (IPCO), pages 152-166, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  18. G. Iyengar, D. J. Phillips, and C. Stein. Feasible and Accurate Algorithms for Covering Semidefinite Programs. In Haim Kaplan, editor, Algorithm Theory - SWAT 2010, pages 150-162, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  19. G. Iyengar, D. J. Phillips, and C. Stein. Approximating Semidefinite Packing Programs. SIAM J. on Optimization, 21(1):231-268, January 2011. Google Scholar
  20. R. Jain and P. Yao. A Parallel Approximation Algorithm for Positive Semidefinite Programming. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 463-471, 2011. Google Scholar
  21. R. Jain and P. Yao. A parallel approximation algorithm for mixed packing and covering semidefinite programs. CoRR, abs/1201.6090, 2012. URL: http://arxiv.org/abs/1201.6090.
  22. P. Klein and H.-I Lu. Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 338-347, New York, NY, USA, 1996. ACM. Google Scholar
  23. P. N. Klein and H.-I. Lu. Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. In K.-Y. Chwa and O. H. Ibarra, editors, Algorithms and Computation, pages 388-398, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. Google Scholar
  24. Y. T. Lee and H. Sun. An SDP-based Algorithm for Linear-sized Spectral Sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 678-687, New York, NY, USA, 2017. ACM. Google Scholar
  25. Z. Leyk and H. Woźniakowski. Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start. Numerical Linear Algebra with Applications, 5(3):147-164, 1999. Google Scholar
  26. Y. Nesterov. Quality of semidefinite relaxation for nonconvex quadratic optimization. CORE Discussion Papers 1997019, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), March 1997. Google Scholar
  27. Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127-152, May 2005. Google Scholar
  28. Y. Nesterov. Smoothing Technique and its Applications in Semidefinite Optimization. Mathematical Programming, 110(2):245-259, July 2007. Google Scholar
  29. Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994. Google Scholar
  30. R. Peng and K. Tangwongsan. Faster and Simpler Width-independent Parallel Algorithms for Positive Semidefinite Programming. In Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, pages 101-108, New York, NY, USA, 2012. ACM. Google Scholar
  31. R. Peng, K. Tangwongsan, and P. Zhang. Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming. CoRR, abs/1201.5135, 2016. URL: http://arxiv.org/abs/1201.5135.
  32. S. A. Plotkin, D. B. Shmoys, and É. Tardos. Fast Approximation Algorithms for Fractional Packing and Covering Problems. In Proc. 32nd Symp. Foundations of Computer Science (FOCS), pages 495-504, 1991. Google Scholar
  33. M. K. De Carli Silva, N. J. A. Harvey, and C. M. Sato. Sparse Sums of Positive Semidefinite Matrices. ACM Trans. Algorithms, 12(1):9:1-9:17, December 2015. Google Scholar
  34. L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review, 38(1):49-95, 1996. URL: http://www.jstor.org/stable/2132974.
  35. N. E. Young. Sequential and Parallel Algorithms for Mixed Packing and Covering. In Proc. 42nd Symp. Foundations of Computer Science (FOCS), pages 538-546, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact