Calculus Optimization Methods

From Wikibooks, open books for an open world
Jump to: navigation, search


A key application of calculus is in optimization: finding maximum and minimum values of a function, and which points realize these extrema.

Context[edit]

Formally, the field of mathematical optimization is called mathematical programming, and calculus methods of optimization are basic forms of nonlinear programming. We will primarily discuss finite-dimensional optimization, illustrating with functions in 1 or 2 variables, and algebraically discussing n variables. We will also indicate some extensions to infinite-dimensional optimization, such as calculus of variations, which is a primary application of these methods in physics.

Techniques[edit]

Basic techniques include the first and second derivative test, and their higher-dimensional generalizations.

A more advanced technique is Lagrange multipliers, and generalizations as Karush–Kuhn–Tucker conditions and Lagrange multipliers on Banach spaces.

Applications[edit]

Optimization, particularly via Lagrange multipliers, is particularly used in the following fields:

Further, several areas of mathematics can be understood as generalizations of these methods, notably Morse theory and calculus of variations.

Terminology[edit]

  • Input points, output values
  • Maxima, minima, extrema, optima
  • Stationary point, critical point; stationary value, critical value
  • Objective function
  • Constraints – equality and inequality
    • Especially sublevel sets
    • Feasible region, whose points are candidate solutions

Statement[edit]

This tutorial presents an introduction to optimization problems that involve finding a maximum or a minimum value of an objective function f(x_1,x_2,\ldots, x_n) subject to a constraint of the form g(x_1,x_2,\ldots, x_n)=k.

Maximum and minimum[edit]

Finding optimum values of the function  f(x_1,x_2,\ldots, x_n) without a constraint is a well known problem dealt with in calculus courses. One would normally use the gradient to find stationary points. Then check all stationary and boundary points to find optimum values.

Example[edit]

  •  f(x,y)=2x^2+y^2
  •  f_x(x,y)=4x=0
  •  f_y(x,y)=2y=0

f(x,y) has one stationary point at (0,0).

The Hessian[edit]

A common method of determining whether or not a function has an extreme value at a stationary point is to evaluate the hessian of the function at that point. where the hessian is defined as

H(f)= \begin{bmatrix}
\frac{{\partial}^2 f}{\partial x_1^2} & \frac{{\partial}^2 f}{\partial x_1 \partial x_2} & \dots & \frac{{\partial}^2 f}{\partial x_1 \partial x_n} \\
\frac{{\partial}^2 f}{\partial x_2 \partial x_1} & \frac{{\partial}^2f}{\partial x_2^2}& \dots & \frac{{\partial}^2f}{\partial x_2 \partial x_n}\\
\vdots & \vdots & \ddots & \vdots \\
\frac{{\partial}^2f}{\partial x_n \partial x_1} & \frac{{\partial}^2f}{\partial x_n \partial x_2}& \dots & \frac{{\partial}^2f}{\partial x_n^2}\\
\end{bmatrix}.

Second derivative test[edit]

The Second derivative test determines the optimality of stationary point x according to the following rules [2]:

  • If H(f)>0 at point x then f has a local minimum at x
  • If  H(f) < 0 at point x then f has a local maximum at x
  • If  H(f) has negative and positive eigenvalues then x is a saddle point
  • Otherwise the test is inconclusive

In the above example.

 H(f)=\begin{bmatrix}
4 & 0\\
0& 2
\end{bmatrix}.

Therefore f(x,y) has a minimum at (0,0).

Sections[edit]

References[edit]

[1] T.K. Moon and W.C. Stirling. Mathematical Methods and Algorithms for Signal Processing. Prentice Hall. 2000.
[2]http://www.ece.tamu.edu/~chmbrlnd/Courses/ECEN601/ECEN601-Chap3.pdf