10.1 Convexity
Definition 10.1.1. A function \(f\) on a convex set \(C\) is convex if \(f(\lambda x + (1 - \lambda )y) \leq \lambda f(x) + (1 - \lambda )f(y)\) for \(x, y \in C\) and \(0 \leq \lambda \leq 1\). A problem is a convex programme if \(f\) and all \(g_i\) are convex and all \(h_k\) are affine.
For a differentiable \(f\), convexity is equivalent to \(f(y) \geq f(x) + \nabla f(x)^{\mathsf T}(y - x)\) for all \(x, y\): the tangent plane lies below the graph. For a twice differentiable \(f\) it is equivalent to the Hessian \(\nabla ^2f(x)\) being positive semidefinite everywhere. The feasible set of a convex programme is convex, since each set \(\{g_i \leq 0\}\) is.
Theorem 10.1.2. For a convex programme, every local minimum is a global minimum, and the set of minima is convex.
Proof. If \(x\) is a local minimum and \(y\) is feasible with \(f(y) < f(x)\), then for small \(\lambda > 0\) the point \(x + \lambda (y - x)\) is feasible, close to \(x\), and \(f(x + \lambda (y - x)) \leq (1 - \lambda )f(x) + \lambda f(y) < f(x)\), a contradiction. If \(x\) and \(y\) are both minima with value \(f^*\), convexity gives \(f \leq f^*\) on the segment between them, so the segment consists of minima. □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.