Unconstrained Optimization

In unconstrained optimization, we minimize an objective function that depends on real variables, and these variables have no restrictions.

min f(x)

where $x \in \mathbb{R}^n$ is a real vector with $n \ge 1$ components and $f : \mathbb{R}^n \to \mathbb{R}$ is a smooth function.

A Simple Example

f(x) = e^x + 2 \cdot x^2

1. Let’s find optimum of above function with brute force approach:
   • Optimum is attained at $x = -0.203$ with min value of $0.8987$.
   • If we search the interval $[-5, 5]$ with step size $10^{-4}$, then we have to evaluate $f(x)$ for $10^5$ times.
     • This is so inefficient.
2.  Let’s find optimum of above function using adaptive grid search:
   • We search interval $[-5, 5]$ with step size $0.1$.
   • At min point, we set new search interval as $[x – 2 \cdot \text{step size}, x + 2 \cdot \text{step size}]$ and we divide the step size by $10$.
   • We repeat this process until min point does not change then a tolerance value $10^{-4}$.
     • This approach is $224$ times better than brute force approach.
     • Can we do better ?

Local Minimizer

Local minimizer is a point that achieves the smallest value of $f$ in its neighbourhood.

• A point x is weak local minimizer if there is a neighbourhood of x such that

f(x^*) \leq f(x)

• A point x is strict (strong) minimizer if there is a neighbourhood of x such that

f(x^*) < f(x)

• For the constant value $f(x) = 2$, every point of x is a weak local minimizer.
• For the function $f(x) = (x-2)^2$ has a strict local minimizer at $x = 2$.
• To sum up, the formal definition is $f(x^*) \leq f(x)$.
• There will be too much local minimas and we cannot know whether we are in global or not.

Vector Derivatives

• First order derivative = Gradient.
• Second order derivative = Hessian.

The function is given by:

f(x) = x_1 x_2 + 2x_1^2 - x_3

The vector x is:

x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}

The gradient of $f(x)$ is:

\nabla f(x) = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1} \\ \frac{\partial f(x)}{\partial x_2} \\ \frac{\partial f(x)}{\partial x_3} \end{bmatrix}

By calculating the partial derivatives, the gradient is:

\nabla f(x) = \begin{bmatrix} x_2 + 4x_1 \\ x_1 \\ -1 \end{bmatrix}

The Hessian matrix ( H ) is defined as:

H = \nabla^2 f(x) = 
\begin{bmatrix} 
\frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_1 \partial x_2} & \frac{\partial^2 f(x)}{\partial x_1 \partial x_3} \\ 
\frac{\partial^2 f(x)}{\partial x_2 \partial x_1} & \frac{\partial^2 f(x)}{\partial x_2^2} & \frac{\partial^2 f(x)}{\partial x_2 \partial x_3} \\ 
\frac{\partial^2 f(x)}{\partial x_3 \partial x_1} & \frac{\partial^2 f(x)}{\partial x_3 \partial x_2} & \frac{\partial^2 f(x)}{\partial x_3^2} 
\end{bmatrix}

Observe that:

\frac{\partial^2 f(x)}{\partial x_1 \partial x_2} = \frac{\partial^2 f(x)}{\partial x_2 \partial x_1}

\frac{\partial^2 f(x)}{\partial x_1 \partial x_3} = \frac{\partial^2 f(x)}{\partial x_3 \partial x_1}

\frac{\partial^2 f(x)}{\partial x_2 \partial x_3} = \frac{\partial^2 f(x)}{\partial x_3 \partial x_2}

Example: The function is given by:

f(x) = x_1^2 + 2x_2^2 - 3x_1 x_2

The vector x is:

x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}

The gradient $\nabla f(x)$ is:

\nabla f(x) = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1} \\ \frac{\partial f(x)}{\partial x_2} \end{bmatrix} = \begin{bmatrix} 2x_1 - 3x_2 \\ 4x_2 - 3x_1 \end{bmatrix}

The Hessian matrix $\nabla^2f(x)$ is:

\nabla^2 f(x) = \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f(x)}{\partial x_2 \partial x_1} & \frac{\partial^2 f(x)}{\partial x_2^2} \end{bmatrix} = \begin{bmatrix} 2 & -3 \\ -3 & 4 \end{bmatrix}

Taylor’s Theorem

First order Taylor expansion:

f(x + p) = f(x)

Second order Taylor expansion:

f(x + p) = f(x) + \nabla f(x + tp)^T p

Quadratic Taylor expansion:

f(x + p) = f(x) + \nabla f(x)^T p + \frac{1}{2} p^T \nabla^2 f(x + tp) p

Where x is variable, p is direction and $t \in (0, 1)$

Example: Let’s use the Taylor theorem to approximate the function $f(x) = e^x$ around $a = 0$.

f(x) \approx f(0) + f'(0)x + \frac{f''(0)}{2!}x^2 + \cdots + \frac{f^{(n)}(0)}{n!}x^n

f(0) = 1

f'(x) = e^x \Rightarrow f'(0) = 1

f''(x) = e^x \Rightarrow f''(0) = 1

e^x \approx 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots

For example, let’s approximate $e^{0.1}$:

e^{0.1} \approx 1 + 0.1 + \frac{(0.1)^2}{2} = 1 + 0.1 + 0.005 = 1.105

Necessary Conditions

\nabla f(x^*) = 0

We call x* as stationary point if it gives above equality. Any local optimum must be stationary point.

Example: Find the stationary point of

f(x) = e^x - 4 \cdot x

\nabla f(x^*) = e^x - 4

e^x - 4 = 0 \rightarrow x^* = log(4)

Note: Gradient direction is always directed to increasing direction

Let’s proof the $\nabla f(x^*) = 0$ with proof by contradiction:

1. Assume that $\nabla f(x^*) \neq 0$.
2. Define vector $p = – \nabla f(x^*)$.
3. If we multiply $p^T$ with $\nabla f(x^*)$, we get $p^T \cdot \nabla f(x^*) = -|| \nabla f(x*)||^2 < 0$.
4. Because $\nabla f$ is continuous near $x^*$, $p^T \cdot \nabla f(x^* + t \cdot p) < 0 \text{\quad where \quad} t \in \mathbb [0, T] \text{\quad} T > 0$.
5. For any $\bar{t} \in \mathbb (0, T]$, we have a Taylor theorem that $f(x^* + \bar{t} \cdot p) = f(x^*) + \bar{t} \cdot p^T \cdot \nabla f(x^* + t \cdot p)$.
6. We showed that $p^T \cdot \nabla f(x^* + t \cdot p)$ is negative.
7. Therefore $f(x^* + \bar{t} \cdot p) < f(x^*)$ for all $\bar{t} \in \mathbb (0, T]$.
8. But this is a contradiction because by definition $x^*$ is the lowest point.

If we take derivative of these 3 points, all of them gives us 0, so how can we seperate them?

\nabla f(x^*) = 0

We can use second derivative:

• If $\nabla^2 f(x^*) > 0$, İt is minima.
• If $\nabla^2 f(x^*) < 0$, it is maxima.
• $\nabla^2 f(x^*) \geq 0$, then f is positive semidefinite.
• If $\nabla^2 f(x^*) = 0$, no conclusion at x (min, max or saddle point).

Example: For example, in above example the second derivative is

\nabla^2 f(x^*) = e^{\log(4)} =  4 > 0

which is a local minimum.

Convexity

• Sum of convex functions is also convex function.
• In convex functions, local min is also global min.

Example: Linear Regression

Suppose we have a function $y = mx + b$, and we want to fit a line to data. We need to minimize total distance between dots and the line.

• Each distance is $r_i = \hat{y}_i – y_i$, where $\hat{y}_i$ is the estimated (on the line) value and $y_i$ is the real value.
• So our cost function is:

J = \sum_{i=1}^{n} (\hat{y}_i - y_i)^2 = \sum_{i=1}^{n} r_i^2 = \sum_{i=1}^{n} (m \cdot x_i + b - y_i)^2

• So we need to minimize J with respect to m and b:

J = \frac{1}{2} \sum_{i=1}^{n} (\hat{y_i} - y_i)^2

\nabla J = \begin{bmatrix} \frac{\partial J}{\partial m} \\ \frac{\partial J}{\partial b} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}

\frac{\partial J}{\partial m} = \frac{1}{2} \sum \frac{\partial}{\partial m} (\hat{y_i} - y_i)^2 = 0

\sum (\hat{y_i} - y_i)(y_i)' = 0

• If we simplify further:

\sum_{i=1}^{n} (mx_i + b - y_i)x_i = 0

\sum_{i=1}^{n} (mx_i^2 + bx_i - x_i y_i) = 0

\sum_{i=1}^{n} mx_i^2 + \sum_{i=1}^{n} bx_i - \sum_{i=1}^{n} x_i y_i = 0

m \sum_{i=1}^{n} x_i^2 = \sum_{i=1}^{n} x_i y_i - b \sum_{i=1}^{n} x_i

m = \frac{\sum_{i=1}^{n} x_i y_i - b x_i}{\sum_{i=1}^{n} x_i^2}

• We can do this also for finding b, then we get the our solution.
• We can write a code for this:

Initialize $m = 1$ and $maxIter = 10$
For $iter = 1$ to $maxIter$:
   $b_{hat} = (1/n) * sum(y_i - m_{hat} * x_i)$
    $m_{hat} = sum((y_i - b_{hat}) * x_i) / sum(x_i^2)$
End For

• And we finally get the m and b, and also we find the best line as $mx + b$.

In some non-linear cases, we cannot get the $\nabla f(x) = 0$.