First-Order Approximation
A first-order approximation of a function $f(\mathbf({\text{x}}))$ at a point $\mathbf{x_0}$ uses the tangent line of the function at $\mathbf{x_0}$. This is essentially the linear approximation of the function, given by the first derivative (gradient in multivariable functions).
For a scalar function $f: \mathbb{R}^n \to \mathbb{R}$, the first-order approximation around a point $\mathbf{x_0}$ is:
$$f(\mathbf({\text{x}})) \approx f(\mathbf{x_0}) + \nabla f(\mathbf{x_0})^T (\mathbf({\text{x}}) – \mathbf{x_0})$$
Where:
- $f(\mathbf{x_0})$ is the value of the function at $\mathbf{x_0}$.
- $\nabla f(\mathbf{x_0})$ is the gradient (first derivative) of the function at $\mathbf{x_0}$.
- $(\mathbf({\text{x}}) – \mathbf{x_0})$ is the displacement vector from $\mathbf{x_0}$ to $\mathbf({\text{x}})$.
Example:
Consider the simple polynomial function $f(x) = x^2 + 2x + 1$.
To find the first-order approximation around $\mathbf{x_0} = 1$:
1. Compute $f(\mathbf{x_0})$:
$$f(1) = 1^2 + 2(1) + 1 = 4$$
2. Compute the gradient (first derivative):
$$\nabla f(x) = 2x + 2 \quad \text{so} \quad \nabla f(1) = 2(1) + 2 = 4$$
3. The first-order approximation of $f(x)$ around $\mathbf{x_0} = 1$ is:
$$f(x) \approx 4 + 4(x – 1)$$
Thus, the first-order approximation is a linear function: $f(x) \approx 4 + 4x – 4 = 4x$.
Second-Order Approximation
The second-order approximation (or Newton’s method) provides a better approximation by using both the first and second derivatives of the function. It involves the Hessian matrix (second-order partial derivatives in multivariable functions).
For a scalar function $f: \mathbb{R}^n \to \mathbb{R}$, the second-order approximation around a point $\mathbf{x_0}$ is:
$$f(\mathbf({\text{x}})) \approx f(\mathbf{x_0}) + \nabla f(\mathbf{x_0})^T (\mathbf({\text{x}}) – \mathbf{x_0}) + \frac{1}{2} (\mathbf({\text{x}}) – \mathbf{x_0})^T H(\mathbf{x_0}) (\mathbf({\text{x}}) – \mathbf{x_0})$$
Where:
- $H(\mathbf{x_0})$ is the Hessian matrix (matrix of second derivatives) evaluated at $\mathbf{x_0}$.
Example:
Consider the same polynomial function $f(x) = x^2 + 2x + 1$.
To find the second-order approximation around $\mathbf{x_0} = 1$:
1. Compute $f(\mathbf{x_0})$ (as before):
$$f(1) = 4$$
2. Compute the gradient (first derivative) $\nabla f(x)$ and evaluate at $x_0 = 1$:
$$\nabla f(x) = 2x + 2 \quad \text{so} \quad \nabla f(1) = 4$$
3. Compute the second derivative (Hessian) and evaluate at $x_0 = 1$:
$$H(x) = 2 \quad \text{so} \quad H(1) = 2$$
4. The second-order approximation of $f(x)$ around $\mathbf{x_0} = 1$ is:
$$f(x) \approx 4 + 4(x – 1) + \frac{1}{2} (x – 1)^2 \cdot 2$$
Simplifying:
$$f(x) \approx 4 + 4(x – 1) + (x – 1)^2$$
This is the second-order approximation of the function.
SECOND ORDER NEWTON’S:
In 2-D we have
$$f(X) \simeq f(X_0) + (X-X_0)(\nabla f)_{X_0} + \dfrac{1}{2}(X-X_0)^T H_{X_0}(X-X_0)$$
Similar to 1-D,
$$f'(X) = f'(X_0) + (\nabla f)_{X_0} + H_{X_0}(X-X_0) \quad$$
3rd term is from derivation of $A^TXA=AX$
$$\therefore \quad f'(X) = 0$$
$$ (\nabla f)_{X_0} = -H_{X_0}(X-X_0).$$
$$ -H_{X_0}X = -H_{X_0}X_0 + (\nabla f)_{X_0}$$
$$ X = X_0 – H_{X_0}^{-1}(\nabla f)_{X_0}$$
Generalization: to $n$-D,
Same expression with
$$X = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} \qquad X_0 = \begin{bmatrix} x_1^0 \\ \vdots \\ x_n^0 \end{bmatrix} \qquad \text{and} \qquad H = \left[\dfrac{\partial^2 f}{\partial x_i \partial x_j}\right]_{n \times n}.$$
$H$ is real and symmetric in most of the optimization problem.
Properties that affect the Process (Due to $H$)
Based on the learning of the property related to a square matrix, the above steps can have impact.
- Newton’s method is strongly influenced by the eigen structure of $H$.
- When $H$ is real and symmetric, its eigen values determine both the direction and scaling of parameter updates.
- When Condition Number of $H$ $\left(\dfrac{\lambda_{max}}{\lambda_{min}}\right)$is large, $H$ is ill conditioned. Newton’s updates can be poorly scaled across directions, impairing stable progress in parameter space.
(-Large $\lambda_{max}$: steep curvature $\to$ small steps.
Small $\lambda_{min}$: flat curvature: large steps.
Large ratio: distorted movement) - If $H$ is singular it will affect algorithm’s ability to move reliably through parameter space.
Example 1: Curvature and Condition Number $d^THd$.
$$f(x,y) = 5x^2 + y^2 \qquad \dfrac{\partial f}{\partial x} = 10x \qquad \dfrac{\partial f}{\partial y} = 2y \qquad \dfrac{\partial^2 f}{\partial x \partial y} = 0$$
$$\therefore \quad H = \begin{bmatrix} 10 & 0 \\ 0 & 2 \end{bmatrix} \qquad \text{Eigen values: } \{10, 2\} \qquad \text{vectors } \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \end{bmatrix} \text{ in fact } \begin{bmatrix} k_1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ k_2 \end{bmatrix}$$
Direction 1 (along $x$-axis)
$$d_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}; d^THd = 10$$
Direction 2 (along $y$-axis)
$$d_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix} d^THd = 2$$
Direction 3:
$$d = \dfrac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix} \quad (\text{Angle} 45°) $$
$$d^THd = 6$$
Curvature lies between eigen values.
$d^THd$ demonstrates that curvature along any arbitrary direction is a mixture of principal curvatures.
Collectively
Gradient $\to$ Direction
Curvature $\to$ Rapidity/stiffness
$d^THd$ or Eigen $\to$ Sensitivity to movement in that direction
Recall: max $\lambda$ to min $\lambda$ of $d^THd$ or Eigen
Example 2: Newton’s Method
$$f(x) = x^4 – 3x^2 + 2$$
$$f'(x) = 4x^3 – 6x$$
$$f”(x) = 12x^2 – 6 = 6(2x^2 – 1)$$
$$x_{k+1} = x_k – \dfrac{f'(x_k)}{f”(x_k)}$$
Step (1)
Let $x_0 = 1 \quad f'(1) = -2$;
$f”(1) = 6$.
$f(1) = 1 – 3 + 2 = 0$
$$\therefore \quad x_1 = 1 – \dfrac{-2}{6} = 1.3333$$
Step (2)
$f'(1.3333) = 1.4815$.
$f”(1.3333) = 15.3333$
$f(1.3333) = -0.1729 $
$$x_2 = 1.3333 – \dfrac{1.4815}{15.3333} = 1.2366$$
Step (3)
$f'(1.2366) = 0.1443$
$f”(1.2366) = 12.3501$
$f(1.2366)=-0.2491$
$$x_3 = 1.2366 – \dfrac{0.1091}{12.352} = 1.2249$$
Step (4)
Verify: $f'(1.2249) = 0.0019$
$f”(1.2249)=12.0046$
$f(1.2249)=-0.25$
$$x_4= 1.2249 – \dfrac{0.0019}{12.0046} = 1.2247$$
Example 3: Second-Order Approximation for a Two-Variable Function
Consider the function:
$$f(x_1, x_2) = x_1^2 + x_2^2 + 2x_1x_2 + 3x_1 + 4x_2$$
We will compute the second-order approximation around the point $\mathbf{x_0} = (1, 1)$.
Step 1: Compute the Gradient
The gradient of $f(x_1, x_2)$ is the vector of partial derivatives with respect to $x_1$ and $x_2$:
$$\nabla f(x_1, x_2) = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \end{pmatrix}$$
Compute each partial derivative:
$$\frac{\partial f}{\partial x_1} = 2x_1 + 2x_2 + 3, \quad \frac{\partial f}{\partial x_2} = 2x_2 + 2x_1 + 4$$
Thus, the gradient is:
$$\nabla f(x_1, x_2) = \begin{pmatrix} 2x_1 + 2x_2 + 3 \\ 2x_2 + 2x_1 + 4 \end{pmatrix}$$
Evaluate the gradient at $\mathbf{x_0} = (1, 1)$:
$$\nabla f(1, 1) = \begin{pmatrix} 2(1) + 2(1) + 3 \\ 2(1) + 2(1) + 4 \end{pmatrix} = \begin{pmatrix} 7 \\ 8 \end{pmatrix}$$
Step 2: Compute the Hessian Matrix
The Hessian matrix $H(x_1, x_2)$ is the matrix of second-order partial derivatives:
$$H(x_1, x_2) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} \end{pmatrix}$$
Compute each second-order partial derivative:
$$\frac{\partial^2 f}{\partial x_1^2} = 2, \quad \frac{\partial^2 f}{\partial x_1 \partial x_2} = 2, \quad \frac{\partial^2 f}{\partial x_2^2} = 2$$
Thus, the Hessian matrix is:
$$H(x_1, x_2) = \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}$$
Evaluate the Hessian matrix at $\mathbf{x_0} = (1, 1)$ (it is constant, so the value remains the same):
$$H(1, 1) = \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}$$
Step 3: Second-Order Approximation
The second-order approximation of the function $f(x_1, x_2)$ around $\mathbf{x_0} = (1, 1)$ is given by:
$$f(x_1, x_2) \approx f(1, 1) + \nabla f(1, 1)^T \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \end{pmatrix} + \frac{1}{2} \begin{pmatrix} x_1 – 1 & x_2 – 1 \end{pmatrix} H(1, 1) \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \end{pmatrix}$$
First, compute $f(1, 1)$:
$$f(1, 1) = 1^2 + 1^2 + 2(1)(1) + 3(1) + 4(1) = 11$$
The second-order approximation becomes:
$$f(x_1, x_2) \approx 11 + \begin{pmatrix} 7 & 8 \end{pmatrix} \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \end{pmatrix} + \frac{1}{2} \begin{pmatrix} x_1 – 1 & x_2 – 1 \end{pmatrix} \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix} \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \end{pmatrix}$$
Simplifying:
$$f(x_1, x_2) \approx 11 + 7(x_1 – 1) + 8(x_2 – 1) + (x_1 – 1)^2 + 2(x_1 – 1)(x_2 – 1) + (x_2 – 1)^2$$
Example 4: Second-Order Approximation for a Three-Variable Function
Consider the function:
$$f(x_1, x_2, x_3) = x_1^2 + x_2^2 + x_3^2 + 2x_1x_2 + 3x_2x_3 + 4x_1 + 5x_2 + 6x_3$$
We will compute the second-order approximation around the point $\mathbf{x_0} = (1, 1, 1)$.
Step 1: Compute the Gradient
The gradient of $f(x_1, x_2, x_3)$ is the vector of partial derivatives with respect to $x_1$, $x_2$, and $x_3$:
$$\nabla f(x_1, x_2, x_3) = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \frac{\partial f}{\partial x_3} \end{pmatrix}$$
Compute each partial derivative:
$$\frac{\partial f}{\partial x_1} = 2x_1 + 2x_2 + 4, \quad \frac{\partial f}{\partial x_2} = 2x_2 + 2x_1 + 3x_3 + 5, \quad \frac{\partial f}{\partial x_3} = 2x_3 + 3x_2 + 6$$
Thus, the gradient is:
$$\nabla f(x_1, x_2, x_3) = \begin{pmatrix} 2x_1 + 2x_2 + 4 \\ 2x_2 + 2x_1 + 3x_3 + 5 \\ 2x_3 + 3x_2 + 6 \end{pmatrix}$$
Evaluate the gradient at $\mathbf{x_0} = (1, 1, 1)$:
$$\nabla f(1, 1, 1) = \begin{pmatrix} 2(1) + 2(1) + 4 \\ 2(1) + 2(1) + 3(1) + 5 \\ 2(1) + 3(1) + 6 \end{pmatrix} = \begin{pmatrix} 8 \\ 12 \\ 11 \end{pmatrix}$$
Step 2: Compute the Hessian Matrix
The Hessian matrix $H(x_1, x_2, x_3)$ is the matrix of second-order partial derivatives:
$$H(x_1, x_2, x_3) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \frac{\partial^2 f}{\partial x_1 \partial x_3} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \frac{\partial^2 f}{\partial x_2 \partial x_3} \\ \frac{\partial^2 f}{\partial x_3 \partial x_1} & \frac{\partial^2 f}{\partial x_3 \partial x_2} & \frac{\partial^2 f}{\partial x_3^2} \end{pmatrix}$$
Compute each second-order partial derivative:
$$\frac{\partial^2 f}{\partial x_1^2} = 2, \quad \frac{\partial^2 f}{\partial x_1 \partial x_2} = 2, \quad \frac{\partial^2 f}{\partial x_1 \partial x_3} = 0$$
$$\frac{\partial^2 f}{\partial x_2^2} = 2, \quad \frac{\partial^2 f}{\partial x_2 \partial x_3} = 3, \quad \frac{\partial^2 f}{\partial x_3^2} = 2$$
Thus, the Hessian matrix is:
$$H(x_1, x_2, x_3) = \begin{pmatrix} 2 & 2 & 0 \\ 2 & 2 & 3 \\ 0 & 3 & 2 \end{pmatrix}$$
Evaluate the Hessian matrix at $\mathbf{x_0} = (1, 1, 1)$ (it is constant, so the value remains the same):
$$H(1, 1, 1) = \begin{pmatrix} 2 & 2 & 0 \\ 2 & 2 & 3 \\ 0 & 3 & 2 \end{pmatrix}$$
Step 3: Second-Order Approximation
The second-order approximation of the function $f(x_1, x_2, x_3)$ around $\mathbf{x_0} = (1, 1, 1)$ is given by:
$$f(x_1, x_2, x_3) \approx f(1, 1, 1) + \nabla f(1, 1, 1)^T \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \\ x_3 – 1 \end{pmatrix} + \frac{1}{2} \begin{pmatrix} x_1 – 1 & x_2 – 1 & x_3 – 1 \end{pmatrix} H(1, 1, 1) \begin{pmatrix} x_1 – 1 \\ x_2 – 1 \\ x_3 – 1 \end{pmatrix}$$
Simplifying as in the previous example leads to the second-order approximation expression.