Convex Optimization

In modern optimization, we usually focus on convex optimization problems. These problems are characterized by the following:

Convex Objective Function. $f_0$ is convex.
Convex Inequality Constraints. $f_i$ is convex for $i\in[m]$.
Affine Equality Constraints. $h_j$ is affine for $j \in [k]$.

$$ \begin{align*} \min_{x \in \R^n} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \le 0, \quad i \in [m] \\ & h_j(x) = 0, \quad j \in [k] \end{align*} $$

Feasible Set is Convex. The feasible set $\mathcal{X} \sube \R^n$ to a convex optimization problem is convex.

Proof </aside>

Local Minimums are Global Minimums. For any convex optimization problem, any local minimum $x^*$ is a global minimum and the set $\mathcal{X}^{\text{opt}}$ of all such minima is convex.

Proof </aside>

Strict Convexity Implies Sparse Solution Set. If $f_0(x)$ is strictly convex, then the associated constrained optimization problem has either one or no solutions.

Proof </aside>

Coercive Functions

A function $f : \R^n \rightarrow \R$ is coercive if $\lim_{||x|| \rightarrow \infty} f(x) = \infty$.

Unconstrained Problems have Finite Solutions. For coercive and continuous $f : \R^n \rightarrow \R$the optimization problem $\min _{x \in \R^n} f(x)$ has a finite solution.

</aside>

Constrained Problems with Closed Feasible Sets have Finite Solutions. For coercive and continuous $f : \R^n \rightarrow \R$, the optimization problem $\min _{x \in \R^n} f(x) \space s.t. \space x \in \mathcal{X}$ has a finite solution if $\mathcal{X}$ is closed and nonempty.

As a corollary, any optimization problem with a continuous, coercive objective function and continuous constraints has a finite solution.

</aside>

Weierstrass Theorem. The optimization problem $\min _{x\in \R^n} f(x) \space s.t. \space x\in \mathcal{X}$, for continuous $f$, has a finite solution if $\mathcal{X}$ is compact and nonempty.

</aside>