Optimization#

Extrema - Definitions#

Consider a function \(f\) defined on a region \(R\).

  • \(f\) has an local maximum at the point \(P_{0}\) if \(f\left(P_{0}\right) \geq f(P)\) for all points \(P\) near \(P_{0}\).

  • \(f\) has an local minimum at the point \(P_{0}\) if \(f\left(P_{0}\right) \leq f(P)\) for all points \(P\) near \(P_{0}\).

  • \(f\) has an absolute maximum on \(R\) at the point \(P_{0}\) if \(f\left(P_{0}\right) \geq f(P)\) for all points \(P\) in \(R\).

  • \(f\) has an absolute minimum on \(R\) at the point \(P_{0}\) if \(f\left(P_{0}\right) \leq f(P)\) for all points \(P\) in \(R\).

Critical Points#

Points where the gradient is either \(\overrightarrow{0}\) or undefined are called critical points of the function.

  • To find the CPs of a function \(f(x, y)\) we therefore need to find \(f_{x}\) and \(f_{y}\) and identify any values of \(x, y\) for which one of the partial derivatives does not exist or for which both partial derivatives are simultaneously zero, that is the solution of the system of equations

\[\begin{split} \begin{aligned} &f_{x}(x, y)=0 \\ &f_{y}(x, y)=0 \end{aligned} \end{split}\]

  • Similarly for a function \(f(x, y, z)\) we look for points where one of the partial derivatives does not exist or \(f_{x}(x, y, z)=f_{y}(x, y, z)=f_{z}(x, y, z)=0\).

Second Derivative Test#

The second-derivative test for local extrema: Suppose \(\left(x_{0}, y_{0}\right)\) is a point where \(\operatorname{grad} f\left(x_{0}, y_{0}\right)=\overrightarrow{0}\). Let

\[ D=f_{x x}\left(x_{0}, y_{0}\right) f_{y y}\left(x_{0}, y_{0}\right)-\left(f_{x y}\left(x_{0}, y_{0}\right)\right)^{2} . \]

  • If \(D>0\) and \(f_{x x}\left(x_{\mathrm{o}}, y_{\mathrm{o}}\right)>0\), then \(f\) has a local minimum at \(\left(x_{\mathrm{o}}, y_{\mathrm{o}}\right)\).

  • If \(D>0\) and \(f_{x x}\left(x_{0}, y_{0}\right)<0\), then \(f\) has a local maximum at \(\left(x_{0}, y_{\mathrm{o}}\right)\).

  • If \(D<0\), then \(f\) has a saddle point at \(\left(x_{0}, y_{\mathrm{o}}\right)\).

  • If \(D=0\), anything can happen: \(f\) can have a local maximum, or a local minimum, or a saddle point, or none of these, at \(\left(x_{\mathrm{o}}, y_{\mathrm{o}}\right)\).

The Extreme Value Theorem for Multivariable Functions#

If a function \(z=f(x, y)\) is continuous on a closed, bounded region \(R\) then it has an absolute maximum and an absolute minimum in \(R\).

  • These absolute extrema occur either at critical points inside \(R\) or on the boundary of \(R\).

  • A closed region is a region which contains all its boundary points.

  • A bounded region is a region which does not stretch to infinity in any direction. (In \(R^{2}\) it is a region contained within some disk.)

The Method of Lagrange Multipliers#

Suppose \(f(x, y, z)\) and \(g(x, y, z)\) are differentiable and \(\vec{\nabla} g \neq \overrightarrow{\mathbf{0}}\) when \(g(x, y, z)=k\). To find the local maximum and minimum values of \(f\) subject to the constraint \(g(x, y, z)=k\) (if these exist), find the values of \(x, y, z\), and \(\lambda\) that simultaneously satisfy the equations

\[ \vec{\nabla} f=\lambda \vec{\nabla} g \quad \text { and } \quad g(x, y, z)=k . \]

  • For functions of two variables the method is similar but without \(z\).

  • To find the local maximum and minimum values of \(f\) subject to two constraints \(g(x, y, z)=k_{1}\) and \(g(x, y, z)=k_{2}\), find the values of \(x, y, z, \lambda, \mu\) that simultaneously satisfy the equations

\[ \vec{\nabla} f=\lambda \vec{\nabla} g_{1}+\mu \vec{\nabla} g_{2}, \quad g_{1}(x, y, z)=k_{1} \text { and } g_{2}(x, y, z)=k_{2} . \]

Alternative presentation#

As above, suppose that we want to find the local maximum and minimum values of \(f(x, y, z)\) subject to the constraint \(g(x, y, z)=k\). An alternative but equivalent approach is to construct a Lagrangian function \(\mathcal{L}(x, y, z, \lambda)=f(x, y, z)-\lambda(g(x, y, z)-k)\) and find the values of \(x, y, z\) for which all the partial derivatives of \(\mathcal{L}\left(\mathcal{L}_{x}, \mathcal{L}_{y}, \mathcal{L}_{z}\right.\) and \(\left.\mathcal{L}_{\lambda}\right)\) are zero. (This converts the constrained optimization problem into an unconstrained problem.)

Other Notes#

  • There is not one set way of solving systems of equations - use any method that works.

  • \(\vec{\nabla} f=\lambda \vec{\nabla} g\) is a necessary but not a sufficient condition for a solution to exist. In some cases an extreme value may not actually exist.

  • In the Lagrange multiplier method, there is no simple way of establishing whether an extremum is a maximum or a minimum, and the step is often omitted. In many practical applications, the nature of the extremum is obvious from the context. If needed, it may be determined by considering a plot of level curves or simply by comparing values.