Let $\mathcal{V}\subset\mathbb{R}^n$ be a real compact algebraic variety. Let $\mathcal{V}^c$ be the convex hull of $\mathcal{V}$ and let us assume that $\mathcal{V}^c$ has nonzero n-dimensional Lesbegue measure.

Question: Are there any known lower bounds for the inner radius (=radius of largest enclosed ball) of $\mathcal{V}^c$ (for instance in terms of the polynomials that generate $\mathcal{V})$.

Informal remark: I am especially interested in cases when $\mathcal{V}$ is generated by only a few polynomials of "low degree".

  • 1
    $\begingroup$ "Inner radius" = radius of largest enclosed ball? $\endgroup$ – Joseph O'Rourke Apr 16 '15 at 11:19
  • $\begingroup$ yes, I have edited the question $\endgroup$ – Michał Oszmaniec Apr 16 '15 at 11:59
  • $\begingroup$ you can edit the subject too... $\endgroup$ – Dima Pasechnik Apr 16 '15 at 15:10
  • 2
    $\begingroup$ What about the polynomial $x_1^2 + \dots + x_n^2 - \epsilon$? It seems like a pretty "good" polynomial from most perspectives, but your radius is just $\epsilon$. How do you hope to exclude this sort of thing? $\endgroup$ – Will Sawin Apr 19 '15 at 1:33
  • $\begingroup$ Thanks for the comment. Notice however that I expicitely mentioned "..in terms of polynomials that generate $\mathcal{V}$". In the problems I am studying (they have origin in quantum information) I have different varieties that can be specified by different polynomials. The point is to be able to get the lower bounds for the inner radius of $\mathcal{V}^c$ in terms of these polynomials $\endgroup$ – Michał Oszmaniec Apr 19 '15 at 18:34

This is not a direct answer to your request for lower bounds; just some remarks.

Sometimes the center of the largest enclosed ball is called the Chebyshev center, and you can find literature under that name. (But beware: the Chebyshev center sometimes means instead the center of the smallest enclosing ball.) Sometimes it is called the ball center.

Your $\mathcal{V}^c$ is a convex set. Finding the largest enclosed ball in a convex set is a convex optimization problem. If you can approximate $\mathcal{V}^c$ with a convex polytope, then finding the biggest ball is a linear programming problem. E.g., these notes formulate that LP problem: PDF download notes.

A better source is

Stephen Boyd, Lieven Vandenberghe. Convex optimization. Cambridge. 2004. (PDF download book.)

They discuss the LP problem on p.148, and discuss the problem for a general convex set p.417ff. There they say,

Problem (8.16) is a convex optimization problem, since each function $g_i$ is the pointwise maximum of a family of convex functions of $x$ and $R$, hence convex. However, evaluating $g_i$ involves solving a convex maximization problem (either numerically or analytically), which may be very hard. In practice, we can find the Chebyshev center only in cases where the functions $g_i$ are easy to evaluate.

  • 1
    $\begingroup$ Thank you for the answer. I will try to google for "Chebyshev center". As for the Polytope approximation: obviously in principle you can do that but I can't find much licteature about "nice" approximations of Varieties via discrete nets. $\endgroup$ – Michał Oszmaniec Apr 19 '15 at 18:45
  • 1
    $\begingroup$ Moreover, for me it would seam to be more natural to first approximate $\mathcal{V}^c$ via spectrahedron (or its projection) and the use semidefinite programing. $\endgroup$ – Michał Oszmaniec Apr 19 '15 at 18:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.