We now look at two results that help explain why convex sets are worth studying in the context of optimization. Recall that for \(\mathbf{y} \in \mathbb{R}^n\), \(\|\mathbf{y}\| = \sqrt{\mathbf{y}^\mathsf{T}\mathbf{y}}\).
Theorem 9.1. Let \(S \subseteq \mathbb{R}^n\) be convex and let \(\mathbf{c} \in \mathbb{R}^n\). Consider the optimization problem \(\min\{ \mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x}\in S \}\). Suppose there exists \(\mathbf{x}^* \in S\) such that for some \(\epsilon \gt 0\), \(\mathbf{c}^\mathsf{T}\mathbf{x}^* \leq \mathbf{c}^\mathsf{T}\mathbf{x}'\) for all \(\mathbf{x}' \in S\) satisfying \(\| \mathbf{x}'-\mathbf{x}^*\| \leq \epsilon\). Then \(\mathbf{x}^*\) is an optimal solution to the minimization problem.
In other words, if \(\mathbf{x}^*\) is a local optimum, then in fact it is a global optimum. This fact is what makes convex optimization attractive.
Proof. Let \(\nu = \mathbf{c}^\mathsf{T} \mathbf{x}^*\). Suppose that \(\mathbf{u}\in S\) is such that \(\mathbf{c}^\mathsf{T} \mathbf{u} \lt \nu\). Let \(\lambda \in (0,1)\) be small enough such that \(\mathbf{z}\) given by \((1-\lambda)\mathbf{x}^* + \lambda\mathbf{u}\) satisfies \(\|\mathbf{z} - \mathbf{x}^*\| \lt \epsilon\). Since \(\mathbf{z} \in S\), \(\mathbf{c}^\mathsf{T}\mathbf{z} \geq \nu\).
But \[\mathbf{c}^\mathsf{T}\mathbf{z} = (1-\lambda)\mathbf{c}^\mathsf{T}\mathbf{x}^* + \lambda \mathbf{c}^\mathsf{T}\mathbf{u} = (1-\lambda)\nu + \lambda \mathbf{c}^\mathsf{T}\mathbf{u} \lt (1-\lambda)\nu + \lambda \nu = \nu,\] a contradiction. Hence, \(\mathbf{u}\) could not possibly exist and the result follows.
Theorem 9.2. Let \(S \subseteq \mathbb{R}^n\). Let \(\mathbf{c} \in \mathbb{R}^n\). Suppose that the optimization problem \(\min \{\mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x} \in S\}\) has an optimal solution. Then \(\min \{\mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x} \in \operatorname{conv}(S)\}\) also has an optimal solution with the same optimal value.
Proof. Let \(\nu\) denote the optimal value of \(\min \{\mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x} \in S\}\). Let \(\mathbf{x}^*\) be an optimal solution. Clearly, \(\mathbf{x}^*\) is a feasible solution to \(\min \{\mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x} \in \operatorname{conv}(S)\}\) with objective function value \(\nu\). Hence, it suffices to show that \(\mathbf{c}^\mathsf{T}\mathbf{x} \geq \nu\) for all \(\mathbf{x} \in \operatorname{conv}(S)\).
Take \(\mathbf{x} \in \operatorname{conv}(S)\). By Theorem 8.9, there exist a positive integer \(k\), scalars \(\lambda_1,\ldots, \lambda_k \geq 0\), and \(\mathbf{u}^1,\ldots, \mathbf{u}^k \in S\) such that \(\lambda_1+\cdots+ \lambda_k = 1\) and \(\mathbf{x} = \lambda_1 \mathbf{u}^1+\cdots+ \lambda_k\mathbf{u}^k.\)
It follows that \begin{eqnarray*} \mathbf{c}^\mathsf{T} \mathbf{x} & = & \mathbf{c}^\mathsf{T} ( \lambda_1 \mathbf{u}^1+\cdots+ \lambda_k\mathbf{u}^k) \\ & = & \lambda_1 ( \mathbf{c}^\mathsf{T} \mathbf{u}^1) + \cdots + \lambda_k ( \mathbf{c}^\mathsf{T} \mathbf{u}^k) \\ & \geq & \lambda_1 \nu + \cdots + \lambda_k \nu \\ & = & \nu \end{eqnarray*} as desired.
Let \(S \subseteq \mathbb{R}^n\) and let \(f:\mathbb{R}^n \rightarrow \mathbb{R}\) be a function that is not necessarily linear. Let \((P)\) denote the optimization problem \(\min \{ f(\mathbf{x}) : \mathbf{x} \in S\}\). Suppose that \((P)\) has an optimal solution. Show that the optimization problem \(\min \{ z : f(\mathbf{x}) \leq z , ~\mathbf{x} \in S\}\) has the same optimal value as \((P)\). (This exercise shows that when working with an optimization problem, one may assume that the objective function is linear.)