5
$\begingroup$

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".

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ "Inner radius" = radius of largest enclosed ball? $\endgroup$
    – Joseph O'Rourke
    Commented Apr 16, 2015 at 11:19
  • $\begingroup$ yes, I have edited the question $\endgroup$
    – Michał Oszmaniec
    Commented Apr 16, 2015 at 11:59
  • $\begingroup$ you can edit the subject too... $\endgroup$
    – Dima Pasechnik
    Commented Apr 16, 2015 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
    Commented Apr 19, 2015 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
    Commented Apr 19, 2015 at 18:34

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Apr 19, 2015 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
    Commented Apr 19, 2015 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .