3.1. Convex Optimization

Convex Optimization

A convex optimization problem is an optimization problem in which the objective function is convex and the feasible set is a convex set. Convex optimization is important because it guarantees that any local minimum is also a global minimum, which greatly simplifies both analysis and algorithms. In strictly convex functions, the global minimum is either unique or does not exist.

Formally, an optimization problem of the form
$\begin{array}{rl}{p}^{\ast }=\underset{x}{\min }& f_0(x)\\ \text{s.t.:}& f_i(x)\le 0,i=1,\dots ,m,\\ & h_j(x)=0,j=1,\dots ,p\end{array}$
is called a convex optimization problem if:

• The objective function $f_0:{\mathbb{R}}^n\to \mathbb{R}$ is convex.
• Each inequality constraint $f_i$ is convex.
• Each equality constraint $h_j$ is affine.

The set of optimal points ${\mathcal{X}}_{\text{opt}}$ of a convex optimization problem is also convex, and therefore cannot be split into multiple regions. This implies that if more than one optimal point exists, ${\mathcal{X}}_{\text{opt}}$ is one continuous global minimum region, not multiple isolated ones.

Examples

Make it Convex!

Consider the optimization problem

\min_{x \in \mathbb{R}^2} \quad & \left(\frac{1}{12}x_1^4 + a_3 x_1^3 + a_2 x_1^2 + a_1 x_1 + a_0\right) + x_2^{18} \\ \text{s.t.} \quad & a_2 x_1^2 + a_1 x_1 + a_0 \le -10x_2 + 5, \\ & a_1 x_1 + a_0 = x_2 + 1. \end{align}$$ >[!example]- Find all coefficients $a_{i}$ for which the problem is convex. >To proceed, we must ensure that the objective and constraints are convex, and the equality constraint is affine. We analyze the Hessian of the objective, such that >$$\nabla f_{0}(x)=\begin{bmatrix} \frac{1}{3}x_{1}^3+3a_{3}x_{1}^2+2a_{2}x_{1}+a_{1} \\ 18x_{2}^{17}\end{bmatrix},$$ >$$\nabla f_{1}(x)=\begin{bmatrix}2a_{2}x_{1}+a_{1} \\ 10\end{bmatrix},$$ >$$\nabla h_{1}(x)=\begin{bmatrix}a_{1} \\ -1\end{bmatrix}$$ >and therefore >$$\nabla^2f_{0}(x)= >\begin{bmatrix} >x_{1}^2+6a_{3}x_{1}+2a_{2} & 0 \\ >0 & 306x_{2}^{16} >\end{bmatrix}$$ >$$\nabla^2f_{1}(x)=\begin{bmatrix}2a_{2} & 0 \\ 0 & 0\end{bmatrix}$$ >$$\nabla^2 h_{1}(x)=0$$ >Since both Hessians are diagonal, we only need the diagonals to be nonnegative for the Hessians to be PSD and meet the second-order condition. Furthermore, all leading factors are even-squared, indicating that their values are always nonnegative. As such, the only constraint (setting $x_{1}=0$) is that the discriminant of the quadratic formula is non-positive, such that $(6a_{3})^2-4\cdot2 a_{2} \leq 0$, which indicates that the function has at most one root with a $y$-value of $0$. Therefore, the coefficients for which the problem is convex satisfy the inequality >$$36a_{3}^2 \leq 8a_{2} \iff 9a_{3}^2 \leq 2a_{2}.$$ >So the set of coefficients is >$$\left\{ a_{0}, a_{1}, a_{2}, a_{3} \mid \frac{9}{2}a_{3}^2 \leq a_{2} \right\}.$$ >Since $a_{3}^2 \geq 0$, we can ignore $2a_{2} \ge 0$.

Feasible & Optimal Sets

Consider the convex optimization problem

\min_{x \in \mathbb{R}^3} \quad &
e^{-x_1 - x_2 - x_3} + (x_1 + 2x_2 + 3x_3)^4 \
\text{s.t.} \quad
& x_1 - x_2 - x_3 = 1, \
& x_1^2 + x_2^2 + x_3^2 + x_1 x_2 + x_2 x_3 + x_1 x_3 \le 2, \
& 0 \le x_1 \le 1, \
& 0 \le x_2 \le 1, \
& 0 \le x_3 \le 1.
\end{aligned}$$

Prove that $x={\left[\begin{array}{ccc}1& 0& 0\end{array}\right]}^T$ is a feasible point. Since the point satisfies all the constraints of the problem, it is a feasible point. The solution to this is trivial.

Prove that the optimization problem has a solution using the Weierstrass theorem. $[0,1]$. As such, the feasible set is compact (closed + bounded), and has a solution.

Weierstrass theorem states that for a minimization problem, if the objective function is continuous and the feasible set is nonempty and compact, there is at least one global solution. Since all constraints are continuous, the feasible set is closed. We now prove that the feasible set is bounded. For this problem, this is done fairly easy by examining that all variables are bounded by

Prove that every local minimum of the above optimization problem is a global minimum. $e^x$ is convex by definition, and therefor a sum of exponentials is also convex. We also know that the first constraint is affine, whereas by taking the Hessian of the second constraint we find the eigenvalues of the Hessian $\lambda =\{4,1,3\}$, which are all positive. Therefore, the Hessian is PSD and the constraint is convex.

We know that

Local & Global Minima

Consider a convex function $f(x_1,x_2):{\mathbb{R}}^2\to \mathbb{R}$ such that:

• The points $(2,2)$ and $(-2,4)$ are both global minima of the function $f(x_1,x_2)$ with the property that $f(2,2)=5$.

• $f(0,0)=10$.

Prove that the point $(0,3)$ is a global minimum of the function $f(x_1,x_2)$. Since $f$ is convex and $(2,2)$, $(-2,4)$ are global minimizers, they have the same optimal value: $f(2,2)=f(-2,4)=5$. Observe that $(0,3)=\frac{1}{2}(2,2)+\frac{1}{2}(-2,4)$. By convexity, $f(0,3)=f\left(\frac{1}{2}(2,2)+\frac{1}{2}(-2,4)\right)\le \frac{1}{2}f(2,2)+\frac{1}{2}f(-2,4)=\frac{1}{2}\cdot 5+\frac{1}{2}\cdot 5=5.$ But $5$ is the global minimum value (attained at $(2,2)$), so $f(0,3)\ge 5$. Hence $f(0,3)=5$, so $(0,3)$ is a global minimizer.

Prove that the point $(0,-1)$ is not a local minimum of the function $f(x_1,x_2)$. From earlier, $(0,3)$ is a global minimizer with optimal value $f^{\text{*}}=5$. Assume for contradiction that $(0,-1)$ is a local minimizer. Since $f$ is convex, every local minimizer is also a global minimizer, so $(0,-1)$ would also be a global minimizer. By convexity, the entire line segment between $(0,-1)$ and $(0,3)$ would then consist of global minimizers; in particular, the point $(0,0)$ lies on this segment and would satisfy $f(0,0)=5$. This contradicts the given fact that $f(0,0)=10\ne 5$. Therefore, $(0,-1)$ cannot be a local minimizer of $f$.

Example