Maximizing a convex function over an open convex set.

66 Views Asked by At

Let $f(x_1, ..., x_n)$ be a convex function. If I am maximizing the function over, say $[a_1, b_1]\times ... \times [a_n, b_n]$, then it is known that the maximum is attained at one of the extreme points of the hypercube (i.e $x^\ast = (x_1^\ast, ..., x_n^\ast)$ where $x_i^\ast \in \{a_i, b_i\}$).

My question is, what if I relax to maximizing over $(a_1, b_1)\times ... \times (a_n, b_n)$. Can we still say something about the maximum?

1

There are 1 best solutions below

3
On

Actually, in the case of $[a_1, b_1]\times ... \times [a_n, b_n]$, the set of points where the maximum is attained is a face of the hyperrectangle. Which necessarily includes at least one vertex, but can include more than one vertex and the face they generate; which can be the whole hyperrectangle when the function is constant.

Due to that, the intuition would immediately conclude that either the function is constant, or the function admits no maximum on $(a_1, b_1)\times ... \times (a_n, b_n)$. But this requires to prove 1) that any convex function on $(a_1, b_1)\times ... \times (a_n, b_n)$ can be prolongated to a convex function on $[a_1, b_1]\times ... \times [a_n, b_n]$, and 2) that suppressing the zone where the function on $[a_1, b_1]\times ... \times [a_n, b_n]$ admits its maximum implies the function on $(a_1, b_1)\times ... \times (a_n, b_n)$ admits no maximum. Two things uneasy to prove.

So here is a simpler proof.
Suppose $f$ on $R = (a_1, b_1)\times ... \times (a_n, b_n)$ admits a maximum on $x$, and $f$ is not constant.
Then $\exists y \ne x, f(y) < f(x)$.
As $x$ is in the interior of $f$ domain, $\exists$ a ball $B$ centered on $x$ with a non-null radius, and $B \subset R$.
Let $L$ be the line $(xy)$. This line intersects $B$'s surface on one point between $x$ and $y$, and another point opposite to $y$. Call this later point $z$.
$f(x)$ being maximum, $f(z) \le f(x)$.
Let $t=\frac {||zx||} {||zy||}$. We have $t \in (0,1)$.
$f$ being convex, $f(x) \le tf(y) + (1-t) f(z) \lt tf(x) + (1-t)f(x)=f(x)$.
Contradiction, so this proves either $f$ is constant, or admits no maximum.