Chapter 3

Exercise 3.1

(Local minimum of convex functions) Let \(f: \mathcal{R}^n \rightarrow \mathcal{R}\) be a convex function and let \(S \in \mathcal{R}^n\) be a convex set. Let \(x^\ast\) be an element of \(S\). Suppose that \(x^\ast\) is a local optimum for the problem of minimizing \(f(x)\) over \(S\); that is, there exists some \(\epsilon>0\) such that \(f(x^\ast)\leq f(x)\) for all \(x\in S\) for which \(|x - x^\ast|\leq \epsilon\). Prove that \(x^\ast\) is globally optimal; that is, \(f(x^\ast)\leq f(x)\) for all \(x\in S\).

---

Solution:

We prove this problem by contradiction.

Proof.

Suppose that there exists a point \(x_0\in S\) in which \(f(x_0)<f(x^\ast)\). Since \(f(x)\) is a convex function, for any \(\lambda\in [0,1]\),

\[ f(\lambda x^\ast + (1-\lambda)x_0)\leq \lambda f(x^\ast) + (1-\lambda )f(x_0). \]

Since \(f(x_0)<f(x^\ast)\),

\[ f(\lambda x^\ast + (1-\lambda)x_0)< \lambda f(x^\ast) + (1-\lambda )f(x^\ast)=f(x^\ast). \]

We can find a \(\lambda\) that makes \(\lambda x^\ast + (1-\lambda)x_0\) locates at the neighbourhood of \(x^\ast\), i.e.,

\[ x^\ast-\epsilon\leq\lambda x^\ast + (1-\lambda)x_0\leq x^\ast+\epsilon; \]

i.e., we can make \(\lambda\) satisfies:

\[ -\epsilon\leq(1-\lambda)(x^\ast-x^0)\leq \epsilon; \]

i.e., we can make \(\lambda\) satisfies:

\[ 1-\lambda\leq \frac{\epsilon}{|x_0-x^\ast|}. \]

This \(\lambda\) does exist, so there will exists a point in the neigourhood of \(x^\ast\) but its function value is smaller than \(f(x^\ast)\), which contradicts that \(x^\ast\) is a local minimum.

\(\Box\)