Unconstrained Optimization
Question:
Explain an unconstrained optimization problem. Explain how you would solve an unconstrained optimization problem?
Solution:
Unconstrained Optimization:
Consider the optimization problem
\[ min_{x_{1},...,x_{n}}f(x_{1},...x_{n}) \]
with objective function \( f \) and decision variables \( x_{1},..,x_{n} \)
This optimization means that we need to pick a vector
\[ X = \begin{pmatrix}x_{1} \\\\ \vdots \\\\ x_{n} \end{pmatrix} \]
such that the function
\[ f(x_{1},...,x_{n}) \]
is minimized.
\( \)
Solving an Unconstrained Optimization:
Just like finding local maxima/minima for a function of single variable, we follow a two step process for finding the maxima/minima of a multi-variable function. We look at the first and the second derivatives to find the maxima/minima of functions of multiple variables.
Step 1: First Derivative/Gradient vector
For an optimization point \( x* \), the gradient vector (vector of derivatives) \( \nabla f \) at \( x* \) must be zero. This gradient vector will be zero for all local maxima/minima/inflection points. This step will give us a sample of optimization points. We do not know at this step whether each of these points is a maxima/minima/inflection point.
\[ \nabla f = \begin{pmatrix}\frac{\partial f}{\partial x_{1}} \\\\ \vdots \\\\ \frac{\partial f}{\partial x_{n}}\end{pmatrix} = \begin{pmatrix}f_{x_{1}} \\\\ \vdots \\\\ f_{x_{n}}\end{pmatrix} = 0 \]
\( \)
Step 2: Second Derivative/Hessian matrix
Once we have the optimization points, we need to identify whether each of them is a maxima/minima/inflection point using a hessian (a matrix of second derivatives) \( \nabla^2f \) at x*. This hessian must be a positive definite matrix for minimization and a negative definite matrix for maximization.
\[ \nabla^2f = \begin{pmatrix}\frac{\partial^2f}{\partial x_{1}^2} & \cdots & \frac{\partial^2f}{\partial x_{1}\partial x_{n}} \\\\ \vdots & \ddots & \vdots \\\\ \frac{\partial^2f}{\partial x_{n}\partial x_{1}} & \cdots & \frac{\partial^2f}{\partial x_{n}^2}\end{pmatrix}= \begin{pmatrix}f_{x_{1}x_{1}} & \cdots & f_{x_{1}x_{n}} \\\\ \vdots & \ddots & \vdots \\\\ f_{x_{n}x_{1}} & \cdots & f_{x_{n}x_{n}}\end{pmatrix} \]
Once we understand the nature of hessian, we can identify the maxima/minima/inflection points for the multi-variable function. I will write in another post about positive definite, negative definite matrices.