1
$\begingroup$

Let $X$ be a finite subset of $\mathbb R$ and let $f : X \to {\mathbb R}$. Suppose we want to approximate $f$ by a polynomial $g$ of fixed degree $d\geq 1$ with the additional condition $g\geq f$. Let

$$ S=\lbrace h : X \to {\mathbb R} | h \geq f, \ h {\rm\ is \ the \ restriction \ of \ a \ polynomial \ } g {\rm \ of \ degree \ } d\rbrace $$

We equip $S$ with the usual partial ordering ( $h_1 \leq h_2$ iff $h_1(x) \leq h_2(x)$ for all $x\in X$). Let $M(S)$ denote the set of minimal elements of $S$. Is it true that $M(S)$is always finite ? Also, is there an effective bound for $|M(S)|$ in terms of $d$ ?

When $d=1$, it seems that $|M(S)| \leq 3$ (this bound is attained when the graph of the function is a trapezium for example).

UPDATE : as noted in the comment below, $M(S)$ is not finite. But $S$ is convex, so the convex hull $C(M(S))$ of $M(S)$ is contained in $S$, and it seems that the set of extremal points in $C(M(S))$ (denote it by $E(S)$) is finite.

Improve this question
$\endgroup$
3
  • $\begingroup$ If $d=1$ and $X=\{-1,0,1\}$ and $f(x) = -x^2$ on these points, then aren't all $h_c$ minimal where $h_c(x) = cx, -1 \le c \le 1$? $\endgroup$
    – Douglas Zare
    Commented Oct 31, 2011 at 9:59
  • $\begingroup$ @Douglas : you're absolutely right. Note that your family of examples is actually the convex hull between $h_{-1}$ and $h_1$, so perhaps looking at extremal elements inside those maximal elements yields a really finite set this time. $\endgroup$
    – Ewan Delanoy
    Commented Oct 31, 2011 at 11:08
  • 2
    $\begingroup$ For every fixed $x\in X$, the requirement that $h(x)\ge f(x)$ is a linear inequality on the coefficients of $f$. So $S$ is a convex polyhedral set and therefore has finitely many extremal points. And $M(S)$ is the boundary of $S$. $\endgroup$
    – Sergei Ivanov
    Commented Oct 31, 2011 at 11:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .