6
$\begingroup$

A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations.

Now, if you want to minimize a linear function on $C$, you're dealing with semidefinite programming, and that's efficiently solvable. But what if you want to estimate the diameter of $C$? I can very well imagine that this is a difficult task, but can find no helpful reference (and I'm more willing to blame that on me not finding the right keywords than on the research not having been already done). I would consider estimating the diameter only up to some factor, large but at most slowly increasing in the dimension; so I'm interested in general in the hardness of approximating the diameter.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ I am not familiar with this problem, but you may be interested in Brieden, Gritzmann, Kannan, Klee, Lovász, and Simonovits (FOCS 1998), who showed several interesting results about approximating the diameter of a convex body in the model where the convex body can be accessed only via oracle. In addition, the introduction of this paper cites some other results for convex polytopes where the polytope is given as a set of linear equations and inequalities. $\endgroup$ – Tsuyoshi Ito Jan 2 '12 at 19:31
  • 6
    $\begingroup$ Follow-up to the above comment. A more recent and equally relevant paper: A. Brieden. Geometric optimization problems likely not contained in apx. Discrete and Computational Geometry, 28(2):201–209, 2002, states in theorem 1.2 that the diameter of a polytope given by linear equations is NP-hard to approximate. $\endgroup$ – Sylvain Peyronnet Jan 2 '12 at 22:50
  • 2
    $\begingroup$ How about having constraints that the non-diagonal entries are equal to zeros? Then, you essentially look at convex polytopes, and the comments above should be applicable for hardness. $\endgroup$ – Yoshio Okamoto Jan 3 '12 at 1:05
  • $\begingroup$ Thm. 7.1 of On the Randomized Complexity of Volume and Diameter: any randomized algorithm that approximates the diameter of a convex body within a factor of $n^{1/4}$, given a separation oracle for the body, makes at least $2^{n^{1/4}}$ calls to the oracle. The paper says only that the proof is a standard adversary argument. $\endgroup$ – Neal Young Aug 25 '18 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.