Constrained Optimization Review
() Optimization 1 / 47
Optimization with equality constraints
Copyright By PowCoder代写 加微信 powcoder
The set of constraints
Lagrange multipliers
Collinearity interpretation of the optimal point Vector notations and scalar product Orthogonality of vectors
() Optimization 2 / 47
Constraint choice problem
Solving the producer problem
max π(K,L) wearefreetochooseanyK 0;L0.
However, there may be all sorts of constraints placed on the producer. Capacity constraint: K K ̄
Budget constraint: K pK +LpL M
() Optimization
Constraint choice problem
Similarly, the consumer seeks for maxu(x1,x2)
subject to
Budget constraint:
Resource constraint:
x1 p1 +x2 p2 = ()M. x1 0,×2 0
Optimization 4 / 47
Constraint choice problem
Same in vector notations
subject to
Budget constraint:
max u (x) x
x1p1+x2p2 = Mifn=2 Resource constraint:
∑xipi =M i
() Optimization 5 / 47
Digression: vectors
The last slide uses vector notation, say x.
A vector is a proÖle of numbers x =(x1,x2,,…,xn) Vectors can be added (componentwise)
Subtracted
Multiplied, scalar product,
x+y =(x1 +y1,x2 +y2,…,xn +yn) x y =(x1 y1,x2 y2,…,xn yn)
xy = (x1y1 +x2y2 +…+xnyn) xyz = (x1y1z1 +x2y2z2 +…+xnynzn)
The result of scalar multiplication of vectors is a scalar!
() Optimization
Digression: vectors
Vectors can be plotted (when n = 2 or 3). Take x =(1,0) and y = (0,1) x2 6
z = x + y = (1, 1) y6
Figure: sum of vectors, orthogonal vectors
Note that x y = 0. This is always true for orthogonal vectors () Optimization
Digression: vectors
Take u =(1,1), v =(1, 1), w = ( 1,1) and z = 32, 32. Notethatuv=0,uw=0,z=23 uandv=( 1)w Hence:
u and v are orthogonal, u and w are orthogonal, z and u are collinear
v and w are anticollinear
We can plot all these vectors, but the computation of the scalar product is enough to conclude all the above and it works even in high dimensions.
() Optimization 8 / 47
Budget constraint in vector form
Take two points x and y both on the BC
px = p1x1+p2x2=M py = p1y1+p2y2=M
subtract p1 (y1 x1)+p2 (y2 x2) = 0
Take vector p = (p1 , p2 ), and vector dx = y x = (y1 x1 , y2 x2 ) . They are orthogonal since
pdx = p1 (y1 x1)+p2 (y2 x2) = 0
Vector dx is a tangent vector, it lies on the budget line. Vector p is then
orthogonal to the budget line.
() Optimization 9 / 47
Budget constraint in vector form
x HjHH H Ha
y HHHHHHHHH –
Figure: Vector p is orthogonal to the budget line
Optimization
Gradient vector
Take function u (x) = u (x1 , x2 ) and Öx u (x1 , x2 ) = u ̄ . This deÖnes a curve in (x1 , x2 ) space where u (x1 , x2 ) = u ̄ .
Take a total di§erential on both sides of u (x1 , x2 ) = u ̄ .
ux1 (x)dx1 +ux2 (x)dx2 = 0
recall tangent vector dx = (dx1,dx2) form a new vector ru (x) = (ux1 (x) , ux2 (x))
ru (x) is the gradient vector of function u at point x, it consists of the partial derivatives ux1 (x) , ux2 (x) , etc. evaluated at x.
ux1 (x)dx1 +ux2 (x)dx2 = ru(x)dx = 0
Hence the gradient vector ru (x) is orthogonal to the curve itself at point x
() Optimization 11 / 47
Gradient vector
a ru(x)
x1 Figure: Gradient vector ru (x) is orthogonal to the curve u (x) = u ̄
() Optimization
Lagrange method with equality constraints
Take n = 2
The consumer choice problem is
subject to and
maxu(x1,x2) x1,x2
x1 p1 + x2 p2 = M. x1 0,×2 0
Optimization 13 / 47
Equality constraints
Ignore the x 0 constraint for now.
Thebudgetconstraintwithn=2isaline. Whenn>2,xp=M is a plane (as long as p = Const). In general BC is a surface di§erent from u (x) = Const.
Take n = 2 and consider some level of utility u ̄.
u(x) = u ̄ is an iso-utility line (or surface when n > 2) Suppose x is a maximiser that delivers u ̄, so that
u ( x ) = u ̄ . The slope of the iso-utility (at x) is
dx2 = ux1(x). dx1 ux2 (x)
() Optimization 14 / 47
Equality constraints
The slope of the constraint set
x1 p1 +x2 p2 =M
at any point is
dx2 = p1. dx1 p2
At x 0 the iso-utility curve must be tangent to the constraint set,
ux1(x) = p1. ux2(x) p2
() Optimization 15 / 47
More general equality constraints
Suppose the problem is subject to
max u (x) x
At any point x the slope of the constraint is
gx1(x). gx2 (x)
If x 0 is the optimum, the iso-utility curve must be tangent to the
constraint, hence
ux1 (x) = gx1 (x). ux2 (x) gx2 (x)
() Optimization 16 / 47
Lagrange multipliers
Alternatively rewrite
Here λ is the unknown Lagrange multiplier.
ux1 (x) = λgx1 (x), ux2 (x) = λgx2 (x).
() Optimization 17 / 47
Lagrange multipliers
With n = 2 we have two equations in three unknowns. However, g (x;p) = M.
This completes the system and we have to Önd a solution to
ux1 (x) ux2 (x) g (x)
= λgx1 (x), = λgx2 (x), = M.
This is in essence Lagrangeís theorem.
The real number λ is the one that makes the system work; it is the Lagrange multiplier.
() Optimization 18 / 47
Lagrangeís Theorem Theorem
Suppose x is an optimal solution to the problem max u (x)
subject to
g (x) = M.
There exists a real number λ such that (x, λ) is an optimum of the
Lagrangean function
L(x,λ) = u(x) λ[g (x) M]. Thatis,at(x,λ):Lx1 =0;Lx2 =0;andLλ =0.
() Optimization
subject to
Form the Lagrangean
max u (x1 , x2 ) = x1 x2 x1,x2
g(x1,x2)=x12+x2 =12. L(x1,x2,λ) = x1x2 λx12 +x2 12.
() Optimization 20 / 47
Lx1 = x2 2λx1=0 Lx2 = x1 λ=0
Lλ = x12+x2 12=0. We can express x1 and x2 in terms of λ.
x1 = λ x2 = 2λ2
λ2+2λ2 = 12
λ = 2orλ= 2.
Optimization 21 / 47
We have to follow both leads. With λ = 2.
With λ = 2.
x1 = λ=2 x2 =2λ2=8
The value of the objective u(x1,x2) tells what point is the actual maximizer.
For λ = 2,
For λ = 2,
u (x1 , x2 ) = 16 u (x1 , x2 ) = 16
Hence (x1, x2, λ) = (2, 8, 2) is the maximum. () Optimization
Collinearity of gradients
Lxi =uxi (x) λgxi (x)=0, foranyi=1,…,n. ru (x) = λrg (x) .
The optimality conditions of constrained problems display some interesting properties. Recall
So the gradient of the objective function ru = (ux1 , ux2 , …, uxn ) at a maximum is collinear to the gradient of the constraint
rg =(gx1,gx2,…,gxn).
In the consumer utility maximisation problem, the vector of marginal utilities at a maximum is collinear to the vector of prices
ru (x) = λp.
Go back to n = 2 and u = x1x2 and draw the gradients. Recall scalar product
() Optimization 23 / 47
Collinearity of gradients
() Optimization 24 / 47
The constraint as a penalty
Look at the constraint again, this time in the FOC:
Lxi =uxi λgxi =0, foranyi=1,…,n.
If the problem were unconstrained, the FOC would have been uxi = 0, for any i = 1,…,n.
measures the loss of marginal utility that is due to the constraint.
() Optimization
The constraint as a penalty
Alternatively, from:
M will have a direct (it enters L as is) and indirect e§ects (through x).
L(x, λ) = u(x) λ[g (x) M]
du(x) = dL(x, λ) dM dM
() Optimization 26 / 47
Lagrange multiplier interpretation
Since M enters in every xi one chooses at the optimum,
dL(x,λ) n dxi n dxi
= ∑uxi (x)dM ∑λgxi (x)dM+λ i=1 i=1
∑ [uxi (x ) λgxi (x )]dM +λ
[ru(x) λrg (x)] dx +λ = λ
This is the essence of the Envelope Theorem
That is, relaxing the constraint by dM increases the value of the
objective by λdM.
Giving extra income to the consumer translates into higher utility at
the rate of λ.
() Optimization 27 / 47
More than one equality constraint
Things extend nicely with more constraints. Suppose we have x and m constraints to deal with.
That is, we want to solve
subject to
max u (x) x
gj(x)=Mj forj=1,…,m.
() Optimization 28 / 47
More than one (two) equality constraints
Introduce the Jacobian for the constraints
∂g1 (x) ∂x1 ∂g2 (x) ∂x1
∂g1 (x) ! ∂x2
Assume that Dg (x) has full rank m. The m constaints are linearly
independent.
∂g2 (x) ∂x2
() Optimization
More than one equality constraint Theorem
Suppose x is an optimum of the problem max u (x)
subject to
and that Dg(x) has full rank. There exists a vector λ 2 Rm such that
gj(x)=Mj forj=1,…,m. (x, λ) is an optimum of the Lagrangean function
L(x, λ) = u(x) λ [g (x) M]. notice a scalar product notation
() Optimization
More than one equality constraint
In other words x is such that
ru(x) = λDg (x).
∂L(x,λ) = 0 for j = 1,…,m. ∂λj
What is ru (x) actually collinear with?
() Optimization 31 / 47
maxu(x1,x2) = x1x2
subjecttog1(x1,x2) = x1 =1andg2(x1,x2)=x2 =1
The only choice available is x = (1, 1) . Note that ru(x) = (1,1) and Dg (x) = 1 0
Set up the Lagrangean
L(x1,x2,λ1,λ2) = x1x2 λ1 (x1 1) λ2 (x2 1)
Lx2 Indeed, with λ = (1, 1)
= x2 λ1 =0henceλ1 =1 = x1 λ2 =0henceλ2 =1
ru(x) = λDg (x) Optimization
Another example
maxu(x1,x2) = x1x2
subject to g1 (x1,x2) = x12 +x2 = 1 and g2 (x1,x2) = x1 = 45
The only choice available is x = 54 , 35 . Note that ru(x) = 35, 45 and Dg (x) = 58 65
Set up the Lagrangean
L(x1,x2,λ1,λ2) = x1x2 λ1 x12 +x2 1 λ2 x1 45 Lx2 = x1 2λ1×2=0henceλ1=23
Lx1 = x2 2λ1×1 λ2 =0henceλ2 = 7 Andstillwithλ= 2, 7 15
ru(x) = λDg (x)
() Optimization 33 / 47
Optimization with inequality constraints
A more general optimization problem is max u (x)
subject to
where the constraint need not bind (it may be ” < ").
p x M.
() Optimization 34 / 47
Lagrange multipliers again
Thankfully Lagrange multipliers come to the rescue once more.
This time however in the form of the Karush-Kuhn-Tucker (KKT) Theorem.
Example: subject to
max f (x1, x2) = x1x2 x
x1 + 4x2 16.
Optimization
Lagrangean
L(x1,x2,λ) = x1x2 λ[x1 +4x2 16] Partial derivatives as with equalities
Lx1 = x2 λ=0 Lx2 = x1 4λ=0
and Complementary Slackness condition λ[x1 +4x2 16] = 0
() Optimization 36 / 47
What does Complementary Slackness mean?
With equality constraints, the only way the constraint is satisÖed is by
Lλ = x1 + 4x2 16 = 0
With inequality constraints there two ways to satisfy the constraint:
x1 + 4x2 16 = 0 x1 + 4x2 16 < 0
() Optimization 37 / 47
The complementary slackness condition
λ[x1 +4x2 16] = 0
covers either options. When
x1 + 4x2 16 = 0 nothing changed from the equality constraints.
the condition
simply tells is that λ = 0.
x1 + 4x2 16 < 0 λ[x1 +4x2 16] = 0
That is, the constraint is irrelevant; we say it is inactive, or not binding, or slack.
() Optimization
If the solution (x1,x2) is such that
x1 + 4x2 16 < 0
x1 + 4x2 16 0 is really not constraining our choice.
So it is as if the constraint were not there. λ[x1 +4x2 16] = 0
does cover all the contingencies. The trick is to know whether λ = 0.
() Optimization 39 / 47
Example: solution
In our example it is easy to see that λ 6= 0. From the Örst-order conditions
Lx1 = x2 λ=0 Lx2 = x1 4λ=0
if λ = 0, then x1 = x2 = 0. This satisÖes the constraint x1 + 4x2 16 0
but minimize x1x2.
So λ 6= 0, and we must also have
x1 + 4x2 16 = 0 for complementary slackness to hold.
() Optimization 40 / 47
Example: solution
From the Örst two equations:
x1 = 4x2 Substitute this in the constraint:
or Therefore
4x2 + 4x2 = 16 x2 = 2.
x1 =8andx2 =2.
Optimization 41 / 47
maxu(x1,x2) = x1x2 subjecttog1(x1,x2) = x12+x21
Set up the Lagrangean
L(x1,x2,λ) = x1x2 λ x12 +x2 1 Lx2 =x1 2λx2=0
Lx1 =x2 2λx1=0
and λ x12 +x2 1 = 0
() Optimization 42 / 47
x 12 = x 2 2
x 12 = x 2 2 = 21
From the Örst two equations, if λ = 0, x1 =x2 =0
but this is a minimum again.
If λ > 0 then the constraint binds
x 12 + x 2 2 = 1 and from the Örst two equations
() Optimization 43 / 47
This gives us four candidate solutions as follows 111
x1 = +p2,x2=+p2,λ=2 111
x1 = p2,x2= p2,λ=2 111
x1 = +p2,x2 = p2,λ= 2 111
x1 = p2,x2 =+p2,λ= 2
we can discard the last two as λ > 0. The others are maxima.
() Optimization
KKT Theorem
Let u and g be C1 functions. Suppose x is a solution to the problem max u (x)
subject to
Let L(x, λ) be the Lagrangean function
g (x) M.
L(x,λ) = u(x) λ[g (x) M].
() Optimization 45 / 47
KKT Theorem
There exists a multiplier λ such that at (x,λ), Lxi(x,λ) = 0,fori=1,…,n
λ[g(x) M] = 0,
Remember that a Örst-order condition of the form Lxi (x, λ) = 0
so that the gradients of u and g are collinear at x.
ru (x) = λrg (x) , () Optimization
The constraint as a penalty
As before,
measures the loss of marginal utility that is due to the constraint. When it
binds, λ > 0 and
du(x) dL(x,λ) n dxi n dxi
dM = dM = ∑ uxi (x ) dM ∑ λgxi (x ) dM + λ
i=1 i=1 n dxi
∑ [uxi (x ) λgxi (x )]dM +λ i=1
[ru(x) λrg (x)] dx +λ = λ dM
That is, relaxing the constraint by dM increases the objective by λdM.
() Optimization 47 / 47
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com