Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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$? –  Douglas Zare Oct 31 '11 at 9:59
    
@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. –  Ewan Delanoy Oct 31 '11 at 11:08
2  
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$. –  Sergei Ivanov Oct 31 '11 at 11:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.