Convex min proof.

32 Views Asked by At

Suppose $f$ is convex and $x^*$ is a minimizer, and $x^* \in [a,b]$, and let $c,d$ be values such that $a < c < d < b$. Then

i) $f(c) \leq f(d) \implies x^* \in [a,d]$

ii) $f(c) = f(d) \implies x^* \in [c,d]$

I am having trouble proving (i), here is what I did.

WORK

i) If $x^* = c$, then we have $x^* = c$. So done, else we must have $f(x^*) < f(c)$ and assume that on the contrary that $x^* \in (d, b]$. Then $b = x^* + t(b-d)$ for some $t \in [0,1]$. So we have

$$f(b) \leq f(x^*) + tf(b) - tf(d) \leq f(x^*) + tf(b) - tf(c) $$

I am stuck at this point, I don't know how to arrive the contradiction that $f(c) \geq f(d)$

ii) if either $x^* = d$ or $c$, then we are done, otherwise $f(x^*) < f(c)$ without any loss of generality. Then $c = x^* + t(d - x^*)$ for some $t \in [0,1]$. So we get

$$f(c) = f(x^* + t(d - x^*)) \leq f(x^*)+ tf(d) - tf(x^*) \leq (1 - t)f(x^*) + tf(d) \leq (1 - t)f(d) + tf(d) = f(d).$$ A contradiction.

1

There are 1 best solutions below

1
On BEST ANSWER

(i) Continuing your start: If $f(x^*)<f(c)$, $x^*\in (d,b]$. The contradiction happens if you interpret $d$ as convex combination of $c$ and $x^*$: $d = c + t(x^*-c)$, $t\in (0,1)$, as $d\in(c,x^*)$: $$ f(d) = f(c + t(x^*-c)) \le (1-t)f(c) + t f(x^*) < (1-t) f(c) + tf(c) = f(c). $$ Hence, $f(d)<f(c)$ in contrary to the assumptions.