Project 2: Is Semidefinite Programming (SDP) Polynomial-Time Solvable?

Semidefinite Programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. SDP is an extension of Linear Programming (LP), with vector variables replaced by matrix variables and nonnegativity elementwise replaced by positive semidefiniteness. One may refer to these two papers [Poru20][Lova03] for more background on SDP.

It is known that LP is solvable in polynomial time. SDP shares some good properties of LP, yet it has more challenging difficulties. In 2014, the well-known TCS blog Gödel’s Lost Letter and P=NP posted one article about this topic: Could We Have Felt Evidence For SDP ≠ P?

In this project, we would like to collect theoretical obstacles that prevent us from getting a polynomial-time algorithm of SDP in different aspects and discuss how to make any new progress.

References

[Poru20] Porumbel, Daniel. Demystifying the characterization of SDP matrices in mathematical programming. No. 2530. EasyChair, 2020. link

[Lova03] Lovász, László. “Semidefinite programs and combinatorial optimization.” In Recent advances in algorithms and combinatorics, pp. 137-194. Springer, New York, NY, 2003. link

(1) The Complexity of Sum-of-square-roots

In 1976, Ron Graham, Michael Garey, and David Johnson could not show some geometric optimization problems such as Euclidean Traveling Salesman Problem is NP-complete or not (they can only show the problem is NP-hard), the reason is that they could not figure out whether the sum-of-square-roots problem is polynomial-time solvable or not. Ron Graham Gives a Talk

In 2019, Ron Graham [Grah19] listed this problem as one of his favorite problems and offered $10 for the following challenge:

Challenge 1: ($10) Show that two sums of square roots of integers cannot agree for exponentially many digits (measured by the size of the input). 

Actually, Yap and Sharma showed that the best known bounds for the required bit-precision of the input is exponential in [YaSh17] (chapter 45).  In the recent work,  Erickson, van der Hoog and  Miltzow [EHM19]  proved that under perturbations of the input of magnitude , the sum-of-square-roots can be computed on a real RAM with an expected bit-precision of per input variable.

Ron Graham presented it at the Fiftieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (SEICCGTC), March 4-8, 2019,  in the Student Union at Florida Atlantic University in Boca Raton, FL.  Fan Chung Graham (she was the most frequent invited female speaker of that conference, Paul Erdős was one of the most frequent male participants) was also the invited plenary speaker at that conference.  As always, his talk was mixed with fun, magic games, interesting problems and monetary prizes! There were two other special things of that talk: a sign language translator standing on the stage to help the audience in need (it is such a wonder to translate math into sign language!); Fan Chung Graham standing in front of the laptop table to help to switch slides pages due to technical problems (we all owed her a lot, with her kind help, the audience enjoyed a wonderful talk!) .

slides Ron Graham-A few of my favorite problems

(When we copied the slides, Ron Graham joked he was gonna square root those prizes, but he didn’t.)

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue: “Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms…The above algorithms produce a strictly feasible solution(or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible(exactly) is still open. A special case of semidefinite programming feasibility is the square-root-sum problem. The complexity of this problem is still open.” [Goem97]

The most remarkable progress towards this problem is by Allender et al. [ABKM03], they showed this problem lies in the 3rd level of the Counting Hierarchy (CH): .

In CCC 2019 workshop open problem session, I presented the sum-of-square-roots problem, Eric Allender was also in the audience, he commented “we still embarrassingly have little understanding of it. ”

I also asked Mihalis Yannakakis about the connection of square-root sum and PosSLP in Papafest, he kindly explained more details: 

“PosSLP is a problem, not a class, which encapsulates the essential power of the unit-cost arithmetic RAM model. Basically, the corresponding class is the class of decision problems solvable in polynomial time in the Blum-Shub-Smale model with rational constants.  The paper by Allender et al is the best reference for PosSLP. That paper introduced and studied thoroughly the problem. There is no further progress with respect to its relation to the classical complexity classes, like NP, Polynomial hierarchy, etc, as far as I know.

The square-root sum problem is reducible to PosSLP, but it is not known to be equivalent. That is if someone proves that the square-root sum problem is in P or NP (in the standard Turing model of complexity), it will not follow from this that PosSLP is also in P or NP, from what we know today.

There are some problems that are equivalent to PosSLP (i.e. reductions going both ways), for example, one is in my paper with Etessami on Recursive Markov chains in JACM 2009, another in the paper with Etessami and Stewart in our paper on Branching processes in SIAM J. Computing 2017.”

Kristoffer Arnsfelt Hansen mentioned Tarasov and Vyalyi (also cited by Allender et al.)  [TaVy08] proved that semidefinite feasibility is PosSLP-hard. However, based on the explanation of Yannakakis, one can see SDP is not equivalent to PosSLP. Thus, even PosSLP is in CH, there is still hope to solve SDP more efficiently.  Bahman Kalantari [Kala20] recently showed that SDP feasibility problem is equivalent to solving a convex hull relaxation (CHR) for a finite system of quadratic equations.

One may refer to the following two books for numerical algorithm and optimization techniques [Solo15] [NoSt06], the books [BCS13] and [BCSS98] for numerical complexity and algebraic complexity.

References

[Grah19] Graham, Ron. “Some of My Favorite Problems (I).” In 50 years of Combinatorics, Graph Theory, and Computing, pp. 21-35. Chapman and Hall/CRC, 2019. link

[YaSh17] Toth, C. D., O’Rourke, J., & Goodman, J. E. (Eds.). (2017). Handbook of discrete and computational geometry. CRC press. Link

[EHM19] Erickson, J., van der Hoog, I., & Miltzow, T. (2019). A Framework for Robust Realistic Geometric Computations. arXiv preprint arXiv:1912.02278. Link

[Goem97] Goemans, Michel X. “Semidefinite programming in combinatorial optimization.” Mathematical Programming 79, no. 1-3 (1997): 143-161. link

[ABPM03] Allender, Eric, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. “On the complexity of numerical analysis.” SIAM Journal on Computing 38, no. 5 (2009): 1987-2006. link

[TaVy08] Tarasov, Sergey P., and Mikhail N. Vyalyi. “Semidefinite programming and arithmetic circuit evaluation.” Discrete applied mathematics 156, no. 11 (2008): 2070-2078. link

[Kala20] Kalantari, Bahman. “On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations.” arXiv preprint arXiv:1911.03989 (2019). link

[Solo15] Solomon, Justin. Numerical algorithms: methods for computer vision, machine learning, and graphics. CRC press, 2015.

[NoSt06] Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.

[BCS13] Bürgisser, Peter, Michael Clausen, and Mohammad A. Shokrollahi. Algebraic complexity theory. Vol. 315. Springer Science & Business Media, 2013.

[BCSS98] Blum, Lenore, LENORE AUTOR BLUM, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998.

More links: 

complexity of square-root sum

TOPP Problem 33

The Curse of Euclidean Metric: Square Roots

(2) Logic and P 

In his Ph.D. thesis, Ronald Fagin created the area of Finite Model Theory and stated that the set of all properties expressible in existential second-order logic is precisely the complexity class NP (It is known as Fagin’s Theorem) [Fagi74].

It is a long open problem in descriptive complexity that what logic structure can capture P?  The logic FPC (Fixed-Point Logic with Counting) is a powerful and natural fragment of P, but it is not all of P.  Jin-Yi Cai, Martin Fürer and Neil Immerman found one counterexample [CFI92] . It is also known that FPC could not express the solvability of systems of linear equations over a finite field. However, Martin Grohe showed that for every surface, a property of graphs embeddable in that surface is decidable in polynomial time if and only if it is definable in FPC [Groh12].

Matthew Anderson, Anuj Dawar and  Bjarki Holm showed that the optimization of linear programs is expressible in FPC [ADH15]. Then, how about SDP?  Anuj Dawar and Pengming Wang showed the FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions) [DW16].

How does that new progress help us to understand the complexity of SDP? According to Rice’s Theorem,  it is undecidable to determine if a given problem is in P or not, which may limit the above approach.

References

[Fagi74] Fagin, Ronald. “Generalized first-order spectra and polynomial-time recognizable sets.” Complexity of computation 7 (1974): 43-73. Link

[CFI92] Cai, Jin-Yi, Martin Fürer, and Neil Immerman. “An optimal lower bound on the number of variables for graph identification.” Combinatorica 12, no. 4 (1992): 389-410. link

[Groh12] Grohe, Martin. “Fixed-point definability and polynomial time on graphs with excluded minors.” Journal of the ACM (JACM) 59, no. 5 (2012): 1-64. link

[ADH15] Anderson, Matthew, Anuj Dawar, and Bjarki Holm. “Solving linear programs without breaking abstractions.” Journal of the ACM (JACM) 62, no. 6 (2015): 1-26. link

[DW16] Dawar, Anuj, and Pengming Wang. “Lasserre lower bounds and definability of semidefinite programming.” arXiv preprint arXiv:1602.05409 (2016). link

(3) Semialgebraic Proof System 

In the recent paper Semialgebraic Proofs and Efficient Algorithm Design published on Foundations and Trends in Theoretical Computer Science, Noah Fleming, Pravesh Kothari and Toniann Pitassi [FKP19] bridge Semialgebraic Proofs and Efficient Algorithm Design. It is amazing that some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself! That paper mainly discusses two semialgebraic proof systems– Sherali-Adams and Sum-of-Squares, and shows up to an additive small error, SDP can be solvable in polynomial time (Corollary 3.12).

What proof system is strong enough to capture the nature of SPD? Is there any hope we can get a truly polynomial-time algorithm to solve SDP with it? Paul Beame discussed the limit of proof in the open lecture of the Simons Institute: The Limits of Proof.

References

[FKP19] Fleming, Noah, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design. now the essence of knowledge, 2019. link

(4) Tropical Geometry and Algebraic Geometry

In recent years, there has been some surprising new progress towards some fundamental open problems in linear programming with the help of tropical and algebraic geometry.  For example, Michael Joswig et al. [ABGJ18] disproved the continuous analogue of Hirsch conjecture and showed primal-dual log-barrier interior point methods are not strongly polynomial using an amazing new technique–Tropical Geometry.  Jesús A. De Loera gave a talk of their new contributions of simplicial polytopes and central path curvature with tropical and algebraic geometry tools in JMM 2019 video  slides.  Pablo A. Parrilo also showed the connection of SDP and convex algebraic geometry [BPT12] .

Can those tools help to get a truly polynomial-time algorithm of SDP (or give negative answers)?

References

[ABGJ18]  Allamigeon, Xavier, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. “Log-barrier interior point methods are not strongly polynomial.” SIAM Journal on Applied Algebra and Geometry 2, no. 1 (2018): 140-178.  link

[BPT12] Blekherman, Grigoriy, Pablo A. Parrilo, and Rekha R. Thomas, eds. Semidefinite optimization and convex algebraic geometry. Society for Industrial and Applied Mathematics, 2012.  link

(5) Number Theory and Lattice 

Qi Cheng (University of Oklahoma) suggested applying diophantine approximation from number theory [Habe18] to improve the sum-of-square-roots problem.

What is the minimum nonzero difference between two sums of square roots of integers? Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen [CMSC10] gave a tighter upper bound via lattice reduction.

References

[Habe18] Habegger, Philipp. “Diophantine approximations on definable sets.” Selecta Mathematica 24, no. 2 (2018): 1633-1675. link

[CMSC10] Cheng, Qi, Xianmeng Meng, Celi Sun, and Jiazhe Chen. “Bounding the sum of square roots via lattice reduction.” Mathematics of computation 79, no. 270 (2010): 1109-1122. link

(6) Circuit Lower Bound and Other Consequences of SDP=P

Noah Fleming proposed one interesting research direction: instead of trying to put SDP into P, it might also be interesting to prove that putting SDP in P is hard! So like show that if SDP=P, then we get circuit lower bounds or derandomization or something.

Noah Fleming recommended the paper showing that complexity class separations imply circuit lower bounds by Nissan-Wigderson Generator [NoWi94] and the Kabanets-Impagliazzo paper [KaIm04] . Noah also attempted to connect this problem to degree 2 polynomial and SETH.

Thanks to the brilliant idea by Noah Fleming, this problem would connect to the hardcore areas of TCS–Circuit Lower Bound and Pseudorandoness!

References

[NoWi94] Nisan, Noam, and Avi Wigderson. “Hardness vs randomness.” Journal of computer and System Sciences 49, no. 2 (1994): 149-167. Link

[KaIm04] Kabanets, Valentine, and Russell Impagliazzo. “Derandomizing polynomial identity tests means proving circuit lower bounds.” computational complexity 13, no. 1-2 (2004): 1-46. Link