Constrained optimization and Lagrange multipliers

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

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

* 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

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

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

econd derivative test

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 inconclusiveIn the above example.

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

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

Constrained maximum and minimum

When finding the extreme values of f(x_1,x_2,cdots, x_n) subject to a constraint g(x_1,x_2,cdots, x_n)=k, the stationary points found above will not work. This new problem can be thought of as finding extreme values of f(x_1,x_2,dots, x_n) when the point (x_1,x_2,dots, x_n) is restricted to lie on the surface g(x_1,x_2,dots, x_n)=k . The value of f(x_1,x_2,dots, x_n) is maximized(minimized) when the surfaces touch each other,"i.e" , they have a common tangent line. This means that the surfaces gradient vectors at that point are parallel, hence,

: abla f(x_1,x_2,cdots, x_n) = lambda abla g(x_1,x_2,cdots, x_n) .

The number lambda in the equation is known as the Lagrange multiplier.

Lagrange multiplier method

The Lagrange multiplier methods solves the constrained optimization problem by transforming it into a non-constrained optimization problem of the form:
* L(x_1,x_2,ldots, x_n,lambda)= f(x_1,x_2,ldots, x_n)+lambda (k-g(x_1,x_2,ldots, x_n))Then finding the gradient and hessian as was done above will determine any optimum values of L(x_1,x_2,ldots, x_n,lambda).

Suppose we now want to find optimum values for f(x,y)=2x^2+y^2 subject to x+y=1 from [2] .

Then the Lagrangian method will result in a non-constrained function.
* L(x,y,lambda)= 2x^2+y^2+lambda (1-x-y)

The gradient for this new function is
* frac{partial L}{partial x}(x,y,lambda)= 4x+lambda (-1)=0
* frac{partial L}{partial y}(x,y,lambda)= 2y+lambda (-1)=0
* frac{partial L}{partial lambda}(x,y,lambda)=1-x-y=0

Finding the stationary points of the above equations can be obtained from their matrix from.

: egin{bmatrix}4 & 0 & -1 \0& 2 & -1 \1 & 1 & 0end{bmatrix} egin{bmatrix}x\y \lambda end{bmatrix}= egin{bmatrix}0\0\1end{bmatrix}

This results in x=1/3, y=2/3, lambda=4/3.

Next we can use the hessian as before to determine the type of this stationary point.

: H(L)= egin{bmatrix}4 & 0 & 0 \0& 2 & 0 \0&0&0end{bmatrix}

Since H(L) >0 then the solution (1/3,2/3,4/3) minimizes f(x,y)=2x^2+y^2 subject to x+y=1 with f(x,y)=2/3.

References

: [1] T.K. Moon and W.C. Stirling. "Mathematical Methods and Algorithms for Signal Processing". Prentice Hall. 2000.: [2] http://mat.gsia.cmu.edu/QUANT/NOTES/chap4/node1.html: [3] http://www.ece.tamu.edu/~chmbrlnd/Courses/ECEN601/ECEN601-Chap3.pdf


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Lagrange multipliers — In mathematical optimization problems, the method of Lagrange multipliers, named after Joseph Louis Lagrange, is a method for finding the extrema of a function of several variables subject to one or more constraints; it is the basic tool in… …   Wikipedia

  • Lagrange multipliers on Banach spaces — In the field of calculus of variations in mathematics, the method of Lagrange multipliers on Banach spaces can be used to solve certain infinite dimensional constrained optimization problems. The method is a generalization of the classical method …   Wikipedia

  • Lagrange multiplier — Figure 1: Find x and y to maximize f(x,y) subject to a constraint (shown in red) g(x,y) = c …   Wikipedia

  • Convex optimization — Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. Given a real vector space X together with a convex, real valued function defined on a convex subset of X, the problem is to find …   Wikipedia

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • Multidisciplinary design optimization — Multi disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. As defined by Prof. Carlo Poloni, MDO is the art of finding the best compromise …   Wikipedia

  • Constraint optimization — In constraint satisfaction, constrained optimization (also called constraint optimization) seeks for a solution maximizing or minimizing a cost function. Contents 1 Definition 2 Solution methods 2.1 Branch and bound …   Wikipedia

  • Newton's method in optimization — A comparison of gradient descent (green) and Newton s method (red) for minimizing a function (with small step sizes). Newton s method uses curvature information to take a more direct route. In mathematics, Newton s method is an iterative method… …   Wikipedia

  • Shape optimization — is part of the field of optimal control theory. The typical problem is to find the shape which is optimal in that it minimizes a certain cost functional while satisfying given constraints. In many cases, the functional being solved depends on the …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.