7
$\begingroup$

Consider a convex polynomial $p$ such that $p(x_1,~x_2,\dots x_n)\geq 0~\forall x_1,~x_2,\dots x_n\in \mathbb{R}^n$. Does the polynomial reach its minimum value?

This is not true for non-convex polynomials like $(1-x_1x_2)^2+x_1^2$, see the response of J.P. McCarthy on a similar question on general polynomials. This is not true for general functions either. Function $e^x$ is infinitely differentiable, convex and bounded from below, but there is no $x$ that does reach the minimum value 0 (thanks to zhw for this simpler example).

$\endgroup$
1
  • $\begingroup$ There are no bounded convex functions on $\mathbb R$ except constants. Your example $\to \infty$ at $-\infty.$ So might as well use something simpler here, like $h(x)=e^x.$ $\endgroup$
    – zhw.
    Commented Jul 2, 2017 at 19:30

1 Answer 1

Reset to default
5
$\begingroup$

The restriction of $p$ to any straight line is a polynomial in one variable that is bounded below, therefore is either constant or goes to $\infty$ in both directions. If there is a line $L$ on which $p$ is constant, then using convexity it is easy to see that $p$ must be constant on all lines parallel to $L$, and by taking a cross-section we reduce the dimension by $1$. So we can assume wlog there is no line on which $p$ is constant.

Now consider $A = \{x \in \mathbb R^n: p(x) < C\}$ where $C > p(0)$.
This is a convex set. The restriction of $p$ to any ray through $0$ is a nonconstant polynomial in one variable and bounded below, therefore goes to $+\infty$ in both directions. Thus $A$ contains no ray through $0$. For each $s$ in the unit sphere $\mathbb S^{n-1}$, there is some $t > 0$ such that $p(ts) > C$ and by continuity this holds (with the same $t$) in some neighbourhood of $s$. Note that by convexity, $p(t' s) > C$ for all $t' > t$. Using compactness, we conclude that $A$ is bounded. And then the infimum of $p$ is the infimum of $p$ on the compact set $\overline{A}$, which is attained.

EDIT: As requested, I'll expand on "using compactness". For each $s \in \mathbb S^{n-1}$, there is $t > 0$ such that $p(ts) > C$. Thus the open sets $\{s \in \mathbb S^{n-1}: p(t s) > C\}$ for $t > 0$ form an open covering of $\mathbb S^{n-1}$. Because $\mathbb S^{n-1}$ is compact, this has a finite subcovering, i.e. $t_1, \ldots, t_k$ such that for every $s \in \mathbb S^{n-1}$, some $p(t_j s) > C$. But that says $p(x) > C$ for all $x$ with $\|x\| \ge \max(t_1, \ldots, t_k)$, i.e. $\|x\| < \max(t_1, \ldots, t_k)$ for all $x \in A$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the answer. Could you please develop a bit "Using compactness, we conclude that $A$ is bounded."? Anyways, I agree $A$ is bounded. For any $s$ in the unit ball $\mathbb S$, denote $t_s$ the minimum value s.t. $p(t_s s)\geq C$ and $p(t's)>C~\forall t'>t_s$. We can not have a sequence $(s_i)$ with $s_i\in \mathbb S$ and $\lim_{i\to \infty} t_{s_i}=\infty$, since the Bolzano–Weierstrass theorem states $\lim_{i\to\infty} s_{n_i}=s$ for some sub-sequence $(s_{n_i})$. Using what you said on $s$, there is a neighborhood/ball $N_s$ around $s$ such that $s'\in N_s\implies t_{s'}<t_s+1$. $\endgroup$
    – Daniel Porumbel
    Commented Jun 30, 2017 at 13:04
  • $\begingroup$ It could be useful to expand on "$p$ must be constant on all lines parallel to $L$". My solution is as follows. Consider $p(x+tL)=c~\forall t\in \mathbb{R}$. We investigate the value of $p(y+tL)~\forall t\in\mathbb{R}$. By convexity, we have $ p(y+\frac 12 tL) \leq \frac 12\left(p(x+tL)+p(2y-x)\right)=\frac12 \left(c+p(2y-x)\right)~\forall t\in\mathbb{R}$, and so, $p$ can not go to $\infty$ in either direction along $y+tL$ with $t\in\mathbb{R}$. As such, it needs to be constant on any line parallel to $L$. $\endgroup$
    – Daniel Porumbel
    Commented Jul 3, 2017 at 21:03

You must log in to answer this question.

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