Convex Optimization

Least squares (LS)
Linear programming (LP)
Convex optimization

A mathematical optimization problem can be expressed as

\begin{aligned} min & f_{0} (x) \\ subject to & f_{i} (x) \leq b_{i}, i = 1, \dots, m \end{aligned}

where

$x = (x_{1}, \dots, x_{n})$ are optimization variables.
$f_{0} : R^{n} \to R$ is objective function.
$f_{i} : R^{n} \to R, i = 1, \dots, m$ are constraints functions.

Optimal solution $x^{⋆}$ has the smallest value of $f_{0}$ among all vectors that satisfy the constraints.

In fact, a general optimization problem is very difficult to solve. Its solution cannot always be found. Even though it can, it suffers some compromise, e.g. very long computation time.

Fortunately, following three problems can be efficiently and reliably solved.

Least squares
Linear programming
Convex optimization

Least squares (LS)

\begin{array}{r} min ‖ A x - b ‖_{2}^{2} \end{array}

Analytical solution $x^{⋆} = (A^{T} A)^{- 1} A^{T} b$
Easy to recognize
A mature solution with reliable and efficient algorithms and softwares
Computation time proportional to $n^{2} k$ ( $A \in R^{k \times n}$ )

Linear programming (LP)

\begin{aligned} min & c^{T} x \\ subject to & a_{i}^{T} x \leq b_{i}, i = 1, \dots, m \end{aligned}

No analytical solution
Not as easy to recognize as LS problems
A mature solution with reliable and efficient algorithms and softwares
Computation time proportional to $n^{2} m$

Convex optimization

\begin{aligned} min & f_{0} (x) \\ subject to & f_{i} (x) \leq b_{i}, i = 1, \dots, m \end{aligned}

where

Objective and constraint functions are convex, i.e. $\forall α, β \geq 0$ , $α + β = 1$ , $f_{i} (α x + β y) \leq α f_{i} (x) + β f_{i} (y)$ , $i = 0, \dots, m$ .
LS and LP are included as special cases.

Generally, for convex optimization problems,

No analytical solution
Often difficult to recognize
Almost a technology with reliable and efficient algorithms
Computation time roughly proportional to $max {n^{3}, n^{2} m, F}$ , where $F$ is cost of evaluating $f_{i}$ 's and their first and second derivatives.

Convex Optimization

Table of Contents

Least squares (LS)

Linear programming (LP)

Convex optimization