1. Introduction

Mathematical optimization

$$\begin{align}\min_x & f_o(x) \\ \text{s.t }& f_i(x) \le b_i, \ i = 1, \dots, m\end{align}$$

where

1. $x = (x_1, \dots, x_n)$: optimization variables

2. $f_o : R^n \to R$: objective function (a.k.a the function we want to minimize)

   💡

   In deep learning or machine learning perspective, the objective function corresponds to the loss function.

3. $f_i : R^n \to R$: constraint functions

💡

The direction of inequalities in the constraints is crucial, and it is also important to emphasize that minimizing the objective function is key, not maximizing it

• Optimal solution: $x^*$ has the smallest value of $f_0$ among all vectors that satisfy the constraints.

  💡

  The optimal solution can be called the global optimum

Solving optimization problems

General optimization problem

• very difficult to solve: classified as a NP-hard class

• methods involve some compromise
  1. very long computation time
  2. not always finding the solution

Exceptions

certain problem classes can be solved efficiently and reliably

1. Least-squares problems

   💡

   If the objective function is non-linear, it is quite difficult to solve and it may require some approximations (e.g. Gauss-Newton’s Method or Levenberg-Marquardt Method)

   Gauss–Newton algorithm

   The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

   https://en.wikipedia.org/wiki/Gauss–Newton_algorithm

   

   Levenberg-Marquardt-Algorithmus

   Der Levenberg-Marquardt-Algorithmus, benannt nach Kenneth Levenberg und Donald Marquardt, ist ein numerischer Optimierungsalgorithmus zur Lösung nichtlinearer Ausgleichs-Probleme mit Hilfe der Methode der kleinsten Quadrate. Das Verfahren kombiniert das Gauß-Newton-Verfahren mit einer Regularisierungstechnik, die absteigende Funktionswerte erzwingt.

   https://de.wikipedia.org/wiki/Levenberg-Marquardt-Algorithmus

2. Linear programming problems

3. Convex optimization problem

   💡

   This problem is quite easy to solve because we can guarantee that local optimum is equivalent to the global optimum

Linear least-squares problem

$$\min_x \|Ax - b\|_2^2$$

• analytical solution: $x^* = (A^TA)^{-1}A^Tb$

• reliable and efficient algorithms and software

• computation time proportional to $n^2k \; (A \in R^{k\times n}$); less if structured

  💡

  It is related to the time complexity of matrix multiplication

Linear programming

$$\begin{align}\min_x &c^Tx \\ \text{s.t. }&a_i^Tx\le b_i\; i = 1, \dots, m\end{align}$$

• no analytical formula for solution

• reliable and efficient algorithms and software

• computation time proportional to $n^2m$ if $m \ge n$

Convex optimization

$$\begin{align}\min_x &f_0(x) \\ \text{s.t. }&f_i(x)\le b_i\; i = 1, \dots, m\end{align}$$

• objective and constraint functions are convex

  $$f_i(\alpha x + \beta y) \le \alpha f_i(x) + \beta f_i(y)$$

  where $\alpha + \beta = 1, \alpha, \beta \ge 0$

• includes least-squares problems and linear programs as special cases.

• no analytical solution

• reliable and efficient algorithms

• computation time roughy proportional to $\max\{n^2, n^2m, F\}$, where $F$ is cost of evaluating $f_i$’s and their first and second derivatives.

💡

However, it is difficult to recognize the given optimization problem is a convex optimization problem.