Lagrange Multipler

The idea of Lagrange multiplier is to convert constrained optimization into solving system of equations of higher dimension.

Notation

1. D[f(x),y](v)  = differentiate f(x) with respect to y and substitute v into x
2. sum[i=1..N]( f(i) ) = f(1)+f(2)+…+f(N)
3. min[x in X]( f(x) ) = minimum value of f(x) over all element in set X.
4. s.t. is short form of such that

Lagrangian

A constrained optimisation usually in form of
min[x in X]( f(x) ) s.t. g[i](x) = 0 for i=1..M
where x is N-dimensional, M is number of constraint.

The Lagrangian L(x,a) of the above optimisation is
L(x,m) = f(x) + sum[i=1..M]( m[i]*g[i](x) )
where m is M-dimensional
m are called Lagrange multipliers

The theorem of Lagrange Multiplier state that the minimum/maximum of f(x) are also minimum/maximum of L(x,m). Therefore min/max of f(x) is one of the roots of the following N+M equations
D[L(x,m), x[i]](x,m) = 0 for i=1..N
g[i](x) = 0 for i=1..M

Proof of Lagrange Multiplier

Let L(x,m) = f(x) + sum[i=1..M]( m[i]*g[i](x) )

Lemma

1. For all x satisfy g[i](x) = 0 for i=1..M, we have L(x,m) = f(x) for all m
2. All extrema of L, say x’, satisfy g[i](x’) = 0 for i=1..M

Proof

min[x] f(x) s.t. g[i](x) = 0 for i=1..M
= min[x,m] f(x) s.t. g[i](x) = 0 for i=1..M (f(x) is independent of m)
= min[x,m] L(x,m) s.t. g[i](x) = 0 for i=1..M (by lemma 1)
= min[x,m] L(x,m) (by lemma 2, the constraint is always satisfied, so could be omitted)

Also see

Portfolio Theory

Advertisements

One comment

  1. Pingback: Portfolio Theory | i :: Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s