5
$\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$
  • $\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. Jul 2 '17 at 19:30
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$
  • 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 Jun 30 '17 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 Jul 3 '17 at 21:03

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.