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)

## One comment