<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-02T19:31:31.853Z
I am not familiar with this problem, but you may be interested in [Brieden, Gritzmann, Kannan, Klee, Lovász, and Simonovits (FOCS 1998)](http://dx.doi.org/10.1109/SFCS.1998.743451), 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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-02T22:50:36.797Z
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.
Sylvain Peyronnet
CC BY-SA 3.0
2012-01-03T01:05:10.117Z
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.
Yoshio Okamoto
CC BY-SA 4.0
2018-08-25T15:22:00.390Z
Thm. 7.1 of [On the Randomized Complexity of Volume and Diameter](https://doi.org/10.1109/SFCS.1992.267803): *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.
Neal Young
<ds.algorithms><approximation-hardness><semidefinite-programming><convex-geometry>
Approximating the diameter of a convex set defined by semidefinite constraints
Vincent Nesme
# Approximating the diameter of a convex set defined by semidefinite constraints

(Asked by: username_0 on 2012-01-02)

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.

**Tags:** ds.algorithms, approximation-hardness, semidefinite-programming, convex-geometry

> **Comments:**
> **username_1**: I am not familiar with this problem, but you may be interested in [Brieden, Gritzmann, Kannan, Klee, Lovász, and Simonovits (FOCS 1998)](http://dx.doi.org/10.1109/SFCS.1998.743451), 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: Thm. 7.1 of [On the Randomized Complexity of Volume and Diameter](https://doi.org/10.1109/SFCS.1992.267803): *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.  

---

## 0 answers

