Lecture notes - Assignment PDF

Preview

Summary

Assignment...

Description

Math Tools Topics 1. Determinant of a matrix 2. Cramer’s Rule 3. Hessian Matrix & Hessian Rule 4. Hessian Rule with Constrained Optimization 5. Implicit Functions 1. Determinant of a matrix: A 1 1 Matrix A = [a11] A = a11 2 2 matrix   a12 11 Let A = aa21 a22 Then, the det of A is: A = a11a22 a21 a12 j

j



j

j



j

j





Example: Let A = 12 A =2 4 1 3=5

j

j





3



4



Matrix 3 2 a11 a12 a13 Let A = 4 a21 a22 a23 5 a31 a32 a33 Expand along column 1:

33

A

a a a a a a a a a a +a31 (a12 a23 a22 a13) Note: 1. Alternate signs, beginning with a11 being + 2. Expand along any column or any row j

j

= + 11 ( 22 33  32 23 )  21 ( 12 33  32 12 ) 

2 Example: Let A = 4

1

2

3

2

0

1

3

4

2

A =? 1. Expand along column 1. A = 1 (0 2 4 1) j

j

j

j



2



3 5

2. Expand along column 2. A = 2 (2 2 3 1)



j

(2  2  4  3)

j

+3 (2  1  0  3) =

4 









+ 0 ()



2 (8) + 3 (2) = 18

=

2

4 (1  1  2  3) (1)



4 (5) = 18

2. Cramer’s Rule: to solve a system of linear equations. 1

Example:

5x1 + 3x2 = 30 6x 1

(

2x 2 = 8



Solve for 1 , x

no

Ax



D

x1

2 2

2

x1 x2 )

x2

Matrix form:   =  5 3 6

or

2

x1 ;

2 1

x2



30

=

2 1

8

De…nition: 1 = 30 ( 2) 8 3 = 84 = replace the  column 1 in A with the D vector  jA j











A1 A1

=

A2

=

30

3

8

2

replace thecolumn 2 in A with the D vector 

30 8 jA2j = 5  8  6  30 =

A2

jAj

5 6

=

= 5  (2)



Cramer’s Rule: =

x1

jA1j

63=



2 =

x

jAj

140

28

jA2j jAj

 = 84 = 3  28 140 x = 2 28 = 5

x1

Need

jAj 6=

0

Solve by substitution 5x1 + 3x2 = 30 6x 1



303x2

 30=3x2 5

x1

2x 2 = 8

6



5

2x 2 = 8

=5 303x2  x1 = x2

5

15 = 5 =3

3. Hessian Matrix & Hessian Rule Defn: Leading Principal Minors 3 (PM) 2 Let

A

=

4

a11

a12

a13

a21

a22

a23

a31

a32

a33

5

First Leading Principal Minor 1 = [ 11] = 11 This consists of the …rst element of the submatrix on the main diagonal of jA j

A.

Second PM

 jA2 j

=

j

a11

a12

a21

a22

j a

j

a

 j

=

2

a11 a22  a21 a12

The submatrix containing the …rst and second element of the main diagonal of A 3rd PM

jA3 j

=

jAj

2 Example A = 4

3

5

8

2

1

0

0

4

1

3 5

jA1 j

=3

jA2 j

= 3  1  (2)  5 = 13 = jAj = 3 (1)  (2)  (5  32) =

jA3 j

51

Defn: Hessian Matrix Matrix of 2nd derivatives of a function. Denote Hessian Matrix by y

=

f1

f ( x1 ; x2 ) @y @f = @x = @x 1 1

f2

@2 f

@f

= @x 1 = @x @x 1 1 1 @f1 f21 = @x1 f11

 H

=

f11

f12

f21

f22

Example: f1

H

y



=

f12

f12

f21

f22

f

( x1 ; x2 ; x3 )

@f

= @x21

@f2 f22 = @x2

2 H = 4



f2

f11

=

= @x = @x2 2

= 2x12 + x1 x2 =

= 4x 1 + x 2

y

@f

@y

H:

  =

=

f

1

1

0

f12

f13

f21

f22

f23

f31

f32

f33

3 5

( x1 ; x2 )

x1

4

f11



Hessian Rule for Unconstrained Optimization Let

y

=

f

(x1 ; x2 ; :::; xn )

then

FONC (First Order Necessary Condition): @f for all i = 1; 2; :::; n fi = @x = 0 i

(note: for

n

x’s, you will have

(solve for

n

x’s such that

f

n

FONC)

is maximized or minimized)

(the same number of equations as the number of unknowns) SOSC (Second Order Su¢cient Condition): For Maximum: The Leading PM of

H

0 jH1 j <

0; jH2 j

>

0; jH3 j

<

0; etc:

3

alternate in signs, starting with

jH1 j <

For Minimum: All leading PM of H are positive jH1 j >

0; jH2 j

>

0; etc:

( x1 ; x2 ; x3 ) =

Ex: f

2 1

x

+ 6x22 + 3x32

2x 1 x 2





4x 2 x 3 + 4x 1

FONC f1

= 2x 1

f2

= 12x2

f3

= 6x 3



2x 2 + 4 = 0





2x 1



4x 3 = 0

4x 2 = 0

Linear equations. Cramer’s Rule Ax 2 =D 2 2 4 2 12

0

4

4

3 2 5 =4

x1 x2

6





32 54

0

3 5

4

0 0

x3



Goal: x1 ; x 2 ; x3 ?Also determine whether they give rise to a maximum or a minimum?

2 6 6 j6 4

Cramer’s Rule:

x



1

=

A1 A

j

j

j

j

2  jAj = 4  jA1j

x



2

x



3

=

=

=

=

4

A2 A

j

j

A3 A

j

j

j

j

j

j

4

2

0

0 0

12 4

6

A

j

2

2

2

12

4

0

4

6

=

=

2 6 6 6 4 

2 6 6 4 6 

2

4

0

2

0

4

0

0

6

88

2

2

2

12

0

0

4

0

224

88

;

48

SOSC

=

f11

f12

f13

f21

f22

f23

f31

f32

f33

88

3  7  7 7 5 

88

;

32

88

3 2 5 =4

224

=

=

(4)(12)

88

4(8)

88

=

; f (x1 ; x2 ; x3)

48

= 88

32

88



2

2

0

2

12

4

0

4

6

3 5

A if the equations from the FONC are LINEAR.

 jH2 j =  

jH1 j

4

3  7 7  7 5 

88



224

3 5 = 2 (12  6  16)  (2) (12) = 88 

0

2. Max or Min?

H

=

(12  6  (4)(4)) =

Critical Point:

2 H = 4

j

4

3 7 7 7 5j

=2

>

0

2

2

2

12

  = 2  12  4 = 44 > 0 4

jH3 j

=

jH j

=

jAj

= 88

  

0

>

  

(x1 ; x2 ; x3 ; f (x 1 ; x 2 ; x3 ))

At

is a minimum.

4. Hessian Rule with Constrained Optimization

Defn: Bordered Hessian, H Matrix of second partials of the Lagrangian Function.

max

Ex:

x1 ;x2 ;x3

f

( x1 ; x2 ; x3 )

s:t:

g

( x1 ; x2 ; x3 )

Lagrangian Function L

=



=The

f

(x1 ; x2 ; x3 ) + g (x1 ; x2 ; x3 ) Lagrange Multiplier

Note: if we have n x’s, the number of contraints should be smaller or equal to n 

1:

aside:

3

x’s, 3 constraints. 3 equations.

(x1 ) ;1

aside: f

2 6 H = 6 4 n m

L11

L12

L13

L1

L21

L22

L23

L2

L31

L32

L33

L3

L1

L2

L3

L

=number =number

=4

x, 1 constraint, x1

3 77 5 

(n+m) (n+m)

of x’s of contraints or number of Lagrange multipliers

Defn:Border-preserving principal minors PM obtained by not striking out the border, starting with size

3  3:

Example:

2 jH 2 j = 4

L11 L21

2 6 j = 6 jH 3 j = jH 4 L1

 jH 1 j

=

j

L12

3 5

L1

L22

L2

L2

0

L11

L12

L13

L1

L21

L22

L23

L2

L31

L32

L33

L3

L1

L2

L3

L

L11

L1

L1

0

3

3

 j

2

2

=

L11 

3 77 5 4

4

0  L1

 L1

Hessian Rule for Constrained Optimization

max

n

x1 ;:::;x

f

(x1 ; :::; xn )

s:t:

g1

(x1 ; :::; xn )

:::

5

= 0  L21 =



gm

=

L

f

(x1 ; :::; xn ) + 1

 g1

(x1 ; :::; xn )

(x1 ; :::; xn ) + ::: + m

 gm

(x1 ; :::; xn )

FONC (First Order Necessary Condition): @L =0 for all i = 1; :::; n Li = @x i

@L

=

Lj

@j

=0

for all

j

= 1; ::; m

(Aside: How many equations do I have in FONC? n

+m

How many unknowns do I have in FONC? n

of x’s; m of

’s, n

+ m)

SOSC: Maximum: border-preserving PM to alternate in sign, starting with 0: jH 2 j >

0; jH 3 j

<

0; jH 4 j

>

jH 2 j >

0; etc:

Minimum: all border-preserving PM are negative: jH 2 j <

0; jH 3 j

<

0; jH 4 j

<

0; etc

Example: Find all critical points and determine if they give us a max or a min. 2 (x1 ; x2 ) = x12 + x2 g ( x 1 ; x 2 ) = 2  x 1  4x 2 = 0 2 2 L = x +x 1 2 +  (2  x1  4x2 ) f

rearrange :

x1

FONC: L1

=

L2

=

L

@L @x1 @L

= 2x 1



=0

= 2x 2  4 = 0 @x2 = 2  x 1  4x 2 = 0

(1)

2x 1 =

(2) (3)

3 equations, 3 unknowns (x1 ; x2 ; ) Solve by subsitution (1) (2)

x1 x2

= =

2x1 2x2 1 4 1 x 4 2



= 4

= subsitute into (3) x1

1 2 4 4 x x2 = 1 2= + 4 x2 4 8 2  = 17 x2 = 4:25 2 1  x = x1 = 17 4 2  4  = 2x 1 = 17

2



2x 2 = 4

0

Solve by Cramer’s Rule

6

+ 4x 2 = 2

2 4

= 2

Ax

0

1

0

2

4

1

4

0

jAj

x



1



x2





D

A1 j

j

= jAj =

A2 j Aj =

j

=

j

=

A3 j = jAj

x1 x2

3 2 5 =4



0 + (1) (2) =

0

0

1

0

2

4

2

4

0

2

0

1

0

0

4

1

2

0

34

2

j

0

0

0

2

0

1

4

2

34

Critical point:



(x1; x2 ;  ) =

34

3 7 7 7 5j

j

2 6 6 j6 4

0 2

Aj

2 6 6 j6 4

3 5

0



= 2 (0  16)

2 6 6 j6 4

32 54

2(2)

3 7 7 7 5j

=

3 7 7 7 5j

=

34

=

4

34

(2)(80) 34

= 2

17

=

16

34

= 8

17

= 4

17

2

17

;

8 4 ; 17 17



Is it a max or min? SOSC L1 L2

@L = 2x 1 1 @L = @x = 2x2 2 = @x

2 H = 4

L

= 2  x1

 j jH 2

=



 

=0

4x 2 = 0

2

0

1

0

2

4

1

4

0

j jH

=

jAj

(1)

4 = 0

=

2x 1 =

(2)

3 (3) 5=A

34 <



2x 2 = 4

if the FONC are linear equations

0





at x1 ; x2 , we get a minimum. Example: f

( x1 ; x2 ; x3 )

s:t:

x1

sub ject to L

=

f

x2

+ x2 = 10

+ x3 = 15

(x1 ; x2 ; x3 ) + 1 (10  x1

 x2 )

+ 2 (15  x2

FONC take derivatives w.r.t.

2 66 H = 6 64

x1 ; x2 ; x3 ; 1 ; 2

SOSC

L11

L12

L13

L11

L12

L21

L22

L23

L21

L22

L31

L32

L33

L31

L32

L1 1

L1 2

L1 3

L1 1

L1 2

L2 1

L2 2

L2 3

L2 1

L2 2

7

3 77 77 5 5 5

 x3 )

5. Implicit Functions Consider

h

(x; a) = 0

This is an implict function (relationship) between

x

and

a:

a:parameter,exogenous x:

choice variable,endogenous

Example: 3px h(x; p; M )

2

M

=0

=0

This is an implict function betwen

x

and the parameters, which are

p, M :

Can we solve x as a function of only the parameters in this function? This is equivalent to asking can we write x as an explicit function of the paramters? 2 = k (M ; p) k () is just a name we give to this function. x = 3 x can be written as an explicit function, because it is a function of only the

Mp

parameters in the equation.

2

ax1 x3 x1

=

+ mx25 = 0

mx5 ax3 2



not an explicit function

1 equation, 3 unknowns. If the number of equation is less than the number of unknowns, then you cannot write the unknown as an explicit function of only the parameters in the equation.

2

ax x3 1

+ mx25 = 0

x2 + 5mx3 = 0 2ax1 + x2 + x3

 15 = 0

3 equations, 3 unknowns. Can we solve for x1 ; x2 ; x3 (unknowns) such that we can write them as explict functions of the parameters in the equations.

n

f (x1 ; :::; x ; a) FONC: f1 :::

n

n

(x1 ; :::; x ; a) = 0

n

f (x1 ; :::; x ; a) = 0 n of implicit functions between x0 s and a: Can we solve x1 :::x by writing x1 :::x as explicit functions of

n

n

6. Implicit Function Theorem

8

a?...