The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We use this observation to show that the exact feasibility problem for semidefinite programs is e...
Atserias, A.; Ochremiak, J. Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem. A: Annual ACM/IEEE Symposium on Logic in Computer Science. "Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science". New York: Association for Computing Machinery (ACM), 2018, p. 66-75.