Notes | Mechatronic Systems and Laboratory

2.4 Convex programming

A particular class of nonlinear programs is that of convex programs:

Definition 2.13: Convex Program

Let $C$ be a nonempty convex set in $ℝ^{n}$ , and let $f : C \to ℝ$ be convex on $C$ . Then,

\min_{x \in C} f (x)

is said to be a convex program (or a convex optimization problem).

Convex programs possess nicer theoretical properties than general nonconvex problems. Theorem 2.2 is a fundamental result in convex programming:

Theorem 2.2

Let $x ⋆$ be a local minimum of a convex program. Then, $x ⋆$ is also a global minimum.

Proof. $x ⋆$ being a local minimum,

\exists 𝜀 > 0 such that f (x) \geq f (x ⋆), \forall x \in ℬ_{𝜀} (x ⋆)

By contradiction, suppose that $x ⋆$ is not a global minimum. Then,

\exists \bar{x} \in C such that f (\bar{x}) < f (x ⋆)

(2.3)

Let $λ \in (0, 1)$ be chosen such that $y : = λ \bar{x} + (1 - λ) x ⋆ \in ℬ_{𝜀} (x ⋆)$ . By convexity of $C$ , $y$ is in $C$ . Next, by convexity of $f$ on $C$ and 2.3,

f (y) \leq λ f (\bar{x}) + (1 - λ) f (x ⋆) < λ f (x ⋆) + (1 - λ) f (x ⋆) = f (x ⋆)

hence contradicting the assumption that $x ⋆$ is a local minimum. □

Example 2.7. Consider once again the NLP problem

\begin{matrix} \min_{x} {(x_{1} - 3)}^{2} + {(x_{2} - 2)}^{2} \\ s.t. x_{1}^{2} - x_{2} - 3 \leq & 0 \\ x_{2} - 1 \leq & 0 \\ - x_{1} & \leq 0 \end{matrix}

The objective function $f$ and the inequality constraints $g_{1}$ , $g_{2}$ and $g_{3}$ being convex, every local solution to this problem is also a global solution by theorem 2.2 . Henceforth, $x ⋆ = (1, 2)$ is a global solution and the global solution value is $f (x ⋆) = 4$ .

In convex programming, any local minimum is therefore a global minimum. This is a powerful result that makes any local optimization algorithm a global optimization algorithm when applied to a convex optimization problem. Yet, theorem 2.2 only gives a sufficient condition for that property to hold. That is, a nonlinear program with nonconvex participating functions may not necessarily have local minima that are not global minima.