Math Review. ECON 510 Chapter 2 Optimization See Sydsaeter(2005, Chapters 2, 3)and Chiang(1984, Chapters 9, 11, 12 and 21) Positive definite matrix Definite matrices are directly related to optimization. A symmetric matrix A is positive semi- definite(A≥0) if rAr≥0,Vx; positive definite(A>0) if 2 Ar>0,Vx≠0: negative semi- definite(A≤0)ifx'Ax≤0,vx; negative definite(A< O) if xar<0,x≠0 Example 2.1.A= Example 2.2. Consider A Example23. For a symmetric matrix A,ifA≥0, then a≥0 for all i;ifA≤0, then a<0 for all i.■
Chapter 2 Optimization Math Review, ECON 510 See Sydsæter (2005, Chapters 2, 3) and Chiang (1984, Chapters 9, 11, 12 and 21). 1. Positive Definite Matrix Definite matrices are directly related to optimization. A symmetric matrix A is positive semi-definite (A ≥ 0) if x0 Ax ≥ 0, ∀ x; positive definite (A > 0) if x0 Ax > 0, ∀ x 9= 0; negative semi-definite (A ≤ 0) if x0 Ax ≤ 0, ∀ x; negative definite (A < 0) if x0 Ax < 0, ∀ x 9= 0. Example 2.1. A = ⎛ ⎜⎝ 1 −1 −1 1 ⎞ ⎟⎠ ≥ 0. Example 2.2. Consider A = ⎛ ⎜⎝ a b b c ⎞ ⎟⎠ . Example 2.3. For a symmetric matrix A, if A ≥ 0, then aii ≥ 0 for all i; if A ≤ 0, then aii ≤ 0 for all i. 2—1
Given a matrix a=(a1)nxn,fori1,…,i∈{1,2,…,n} with i10←→k>0, for all k. (b)A0, for all k (c)A≥0÷→di}≥0, for all permutations{in,,ik} and all k=1, (d)A≤0←→(-1)dxa}≥0, for all permutations{iy…,ik} and all k=1,…,n Example 2. (a)Verify >0. b (b) Find conditions for A Proposition 2.1. a>0 iff all its eigenvalues are positive a>0 iff all its eigenvalues are strictly positive If A>0 then A-I>0 A>0今-A<0
Given a matrix A = (aij )n×n, for i1, ··· , ik ∈ {1, 2, ··· , n} with i1 0 ⇐⇒ dk > 0, for all k. (b) A 0, for all k. (c) A ≥ 0 ⇐⇒ d{i1,···ik} ≥ 0, for all permutations {i1,...,ik} and all k = 1, . . . , n. (d) A ≤ 0 ⇐⇒ (−1)kd{i1,···ik} ≥ 0, for all permutations {i1,...,ik} and all k = 1, . . . , n. Example 2.4. (a) Verify ⎛ ⎜⎝ 1 −1 −1 1 ⎞ ⎟⎠ ≥ 0. (b) Find conditions for A = ⎛ ⎜⎝ a b b c ⎞ ⎟⎠ ≥ 0. Proposition 2.1. • A ≥ 0 iff all its eigenvalues are positive. • A > 0 iff all its eigenvalues are strictly positive. • If A > 0, then A−1 > 0. • A ≥ 0 ⇔ −A ≤ 0. 2—2
●A>0今-A0 and AA>0 ·ⅡfA>0and|Bl≠0, then BAB>0.■ 2. Concavity Given points RE R, a convex combination is y=ArzI 入k≥0 Given any two points a, y, the intervals are ,列≡{2|2=Ax+(1-y,A∈p,1} (x,y)≡{=|2=Mx+(1-My,A∈(0,1)} a set SCRn is a convex set if ,y∈ x,引cS. Proposition 2.2.(Properties of Convex Sets 1. Any intersection of convex sets is also convex 2. The Cartesian product of convex sets is also convex. f: X-R is concave if XCRn is convex and fx+(1-)≥Af(x)+(1-入)f(y),A∈(0,1),x,y∈X If the inequality holds strictly, f is strictly concave f is(strictly) convex if -f is(strictly)concave Theorem 2.2.(Properties of Concave Functions). X CRn is convex 1.f:X→ R is concave iff{(x,t)∈X×R|f(x)≥t} Is convex 2. Concave functions are continuous in the interior of their domains 3. A function f: X-R is concave iff f(A1x2+…+Akx2)≥Af(x2)+…+Akf(x), for all k>1 and all convex combinations A1 +.+Ak.x
• A > 0 ⇔ −A 0 and AA0 ≥ 0. • If A > 0 and |B| 9= 0, then B0 AB > 0. 2. Concavity Given points xk ∈ Rn, a convex combination is y ≡ λ1x1 + ··· + λmxm, λk ≥ 0, [m k=1 λk = 1. Given any two points x, y, the intervals are [x, y] ≡ z | z = λx + (1 − λ)y, λ ∈ [0, 1] , (x, y) ≡ z | z = λx + (1 − λ)y, λ ∈ (0, 1) . A set S ⊂ Rn is a convex set if ∀ x, y ∈ S, [x, y] ⊂ S. Proposition 2.2. (Properties of Convex Sets). 1. Any intersection of convex sets is also convex. 2. The Cartesian product of convex sets is also convex. f : X → R is concave if X ⊂ Rn is convex and f[λx + (1 − λ)y] ≥ λf(x) + (1 − λ)f(y), ∀ λ ∈ (0, 1), x, y ∈ X. If the inequality holds strictly, f is strictly concave. f is (strictly) convex if −f is (strictly) concave. Theorem 2.2. (Properties of Concave Functions). X ⊂ Rn is convex. 1. f : X → R is concave iff {(x, t) ∈ X × R | f(x) ≥ t} is convex. 2. Concave functions are continuous in the interior of their domains. 3. A function f : X → R is concave iff f(λ1x1 + ··· + λkxk) ≥ λ1f(x1 ) + ··· + λkf(xk), for all k ≥ 1 and all convex combinations λ1x1 + ··· + λkxk. 2—3
Theorem 2.3. Given convex XCR, twice differentiable f: X-R, 1. f is convex D2f(x)≥0,x∈X 2. D f(a)>0,VIEX f is strictly convex 3. f is concave← (x)≤0,Vx∈X. 4. D f(a)0,VaEX, k.= f is strictly convex 4.(-1)dk(x)>0,Vx∈X, f is strictly concave. I 3 xample25.“ f is strictly convex”#“D2f>0.E.g.,f(x)=x4 Example 2.6. For f(a, y)=a+y, defined on R2 +, where a, B20, concave if0≤a,B≤1; f strictly concave, if 00, a+Bf(y)-f(x), for all x,y∈X,x≠y
Theorem 2.3. Given convex X ⊂ Rn, twice differentiable f : X → R, 1. f is convex ⇐⇒ D2f(x) ≥ 0, ∀ x ∈ X. 2. D2f(x) > 0, ∀ x ∈ X =⇒ f is strictly convex. 3. f is concave ⇐⇒ D2f(x) ≤ 0, ∀ x ∈ X. 4. D2f(x) 0, ∀ x ∈ X, ∀ k. =⇒ f is strictly convex. 4. (−1)kdk(x) > 0, ∀ x ∈ X, ∀ k. =⇒ f is strictly concave. Example 2.5. “ f is strictly convex” > “ D2f > 0”. E.g., f(x) = x4. Example 2.6. For f(x, y) = xα + yβ, defined on R2 ++, where α, β ≥ 0, f is ⎧ ⎪⎨ ⎪⎩ concave, if 0 ≤ α, β ≤ 1; strictly concave, if 0 0, α + β f(y) − f(x), for all x, y ∈ X, x 9= y. 2—4
3. Quasi-Concavity Given a convex set XCR,f:X→ R is quasi- concave if,wx,y∈X,z∈ f(y)≥f(x)→f(2)≥f(x) f is strictly quasi-concave if, V ,yEX, 2E(a, y) f(y)≥f(x)→f()>f(x) f is(strictly) quasi-convex if -f is(strictly) quasi-concave Theorem 2. 4. Given convex set X CR, 1.f:X→ R is quasi-concave iff the upper level set{x∈X|f(x)≥ t is convex, yt∈R 2.f:X→ R is quasi- convex iff the lower level set{r∈X|f(x)≤ t is convex, Vt∈R Set f-(t)=eXIf(=t is called a level set Theorem 2.5 (a)Concave functions are quasi-concave; convex functions are quasi-convex (b)Strictly concave functions are strictly quasi-concave. Strictly convex functions are trictly quasi-convex. (c)Monotonic functions defined on R are both quasi-concave and quasi-convex Quasi-concavity doesnt necessarily imply concavity. strict concavity concavity strict quasi-concavity quasI-concavity
3. Quasi-Concavity Given a convex set X ⊂ Rn, f : X → R is quasi-concave if, ∀ x, y ∈ X, z ∈ (x, y), f(y) ≥ f(x) ⇒ f(z) ≥ f(x). f is strictly quasi-concave if, ∀ x, y ∈ X, z ∈ (x, y), f(y) ≥ f(x) ⇒ f(z) > f(x). f is (strictly) quasi-convex if −f is (strictly) quasi-concave. Theorem 2.4. Given convex set X ⊂ Rn, 1. f : X → R is quasi-concave iff the upper level set {x ∈ X | f(x) ≥ t} is convex, ∀ t ∈ R. 2. f : X → R is quasi-convex iff the lower level set {x ∈ X | f(x) ≤ t} is convex, ∀ t ∈ R. Set f −1(t) = {x ∈ X | f(x) = t} is called a level set. Theorem 2.5. (a) Concave functions are quasi-concave; convex functions are quasi-convex. (b) Strictly concave functions are strictly quasi-concave. Strictly convex functions are strictly quasi-convex. (c) Monotonic functions defined on R are both quasi-concave and quasi-convex. Quasi-concavity doesn’t necessarily imply concavity. strict concavity =⇒ concavity ⇓ ⇓ strict quasi-concavity =⇒ quasi-concavity 2—5
Given f: X-R, define the bordered Hessian matrix B,(a) 0f1 fn f af(ar) af(a) f1 f1 B(a) fn f Theorem 2.6. Given convex X CR, twice differentiable f: X-R, and the principal b(a),., bn+1() of B(a), For XCR, f is quasi-convex=bk(x)≤0,yx∈X,k. 2. For X CR4, f is quasi-concave -(1)b()0, quasI-concave, if0≤a,B≤1; f is strictly quasi-concave,if00
Given f : X → R, define the bordered Hessian matrix Bf (x) : fi ≡ ∂f(x) ∂xi , fij ≡ ∂2f(x) ∂xi∂xj , Bf (x) ≡ ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ 0 f1 ··· fn f1 f11 ··· f1n . . . . . . . . . fn fn1 ··· fnn ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ . Theorem 2.6. Given convex X ⊂ Rn, twice differentiable f : X → R, and the principal minors b1(x),...,bn+1(x) of Bf (x), 1. For X ⊂ Rn +, f is quasi-convex =⇒ bk(x) ≤ 0, ∀ x ∈ X, ∀ k. 2. For X ⊂ Rn +, f is quasi-concave =⇒ (−1)kbk(x) ≤ 0, ∀ x ∈ X, ∀ k. 3. For X = Rn + or Rn, bk(x) 0. 2—6
4. Unconstrained Optimization See Sydsaeter(2005, Chapter 3) and Chiang(1984, Chapter 9) If there is a neighborhood N(x*)of a with radius r such that z* is the maximum point of f on Mr(a*), then a* is a local maximum point of f For f: R-R, if Df( )=0, call i or (i, f()) a stationary point, and f(e) the stationary value. Given a stationary point i, there are three possible situations at i: local maximum, local minimum point, and a reflection point Example 2.10. Compare y=r2 with y=x3 at =0 Theorem 2.7.(Extreme-Value Theorem). For continuous f: R-R and compact AC Rn max f(ar) has at least one solution Theorem 2.8. Let ACRn (a)If a'is an interior solution of max then(FOC) Df(a*)=0 and(SONC)D2f(a*)<0 (b) If Df(a*)=0 and(SOSC) D f(*<0, 3 Mr(*)st. is the maximum point of f on Nr(a* (c) If f is concave on A, any point a E A satisfying Df(a*)=0 is a maximum point (d)If f is strictly quasi-concave, a local maximum over a convex set A is the unique global maximum Note: the FOC and SONC are not necessary for corner solutions; they are also not sufficient for local maximization, even for interior points Example 2.11. Find a maximum point for f(1, I2)=T2-4.2+3.1.T2-I2
4. Unconstrained Optimization See Sydsæter (2005, Chapter 3) and Chiang (1984, Chapter 9). If there is a neighborhood Nr(x∗) of x∗ with radius r such that x∗ is the maximum point of f on Nr(x∗), then x∗ is a local maximum point of f. For f : Rn → R, if Df(ˆx)=0, call xˆ or (ˆx, f(ˆx)) a stationary point, and f(ˆx) the stationary value. Given a stationary point x, ˆ there are three possible situations at xˆ : local maximum, local minimum point, and a reflection point. Example 2.10. Compare y = x2 with y = x3 at x = 0. Theorem 2.7. (Extreme-Value Theorem). For continuous f : Rn → R and compact A ⊂ Rn, max x∈A f(x) has at least one solution. Theorem 2.8. Let A ⊂ Rn. (a) If x∗ is an interior solution of max x∈A f(x) then (FOC) Df(x∗)=0 and (SONC) D2f(x∗) ≤ 0. (b) If Df(x∗)=0 and (SOSC) D2f(x∗) < 0, ∃ Nr(x∗) s.t. x∗ is the maximum point of f on Nr(x∗). (c) If f is concave on A, any point x∗ ∈ A satisfying Df(x∗)=0 is a maximum point. (d) If f is strictly quasi-concave, a local maximum over a convex set A is the unique global maximum. Note: the FOC and SONC are not necessary for corner solutions; they are also not sufficient for local maximization, even for interior points. Example 2.11. Find a maximum point for f(x1, x2) = x2 − 4x2 1 + 3x1x2 − x2 2. 2—7
5. Constrained Optimization e Sydsaeter(2005, Chapter 3)and Chiang(1984, Chapters 12 and 21) Theorem 2.9.(Lagrange). For f: Rn-+R, G: Rn-R, consider problem 图x f(a) t.G(x)=0. Let L(A, a)=f()+A G()(Lagrange function) If a* is a solution and if DG(a*)has full rank, then 3 AERm(Lagrange multi- pler s FOC DxC(,x)=0, SONC h'D2f(a*)hs0, V h satisfying DG (a*)h=0, Vi If the FOC is satisfied, G(r)=0, G is quasi-concave, and SOSC: hDf(a)h0 and b>0, consider F(a,b)≡max x1+T2 Theorem 2.10. Let A E Rnxn be symmetric. C E Rmxn has full rank, m n, and 0 C 1,…,bm+ be the principal minors of B≡ Then 1.xAx>0fox≠0 satisfying Ca=0→(-1)mbk>0,Vk≥2m+1 2.xAx0,yk≥2m+1
5. Constrained Optimization See Sydsæter (2005, Chapter 3) and Chiang (1984, Chapters 12 and 21). Theorem 2.9. (Lagrange). For f : Rn → R, G : Rn → Rm, consider problem max x∈Rn f(x) s.t. G(x)=0. Let L(λ, x) ≡ f(x) + λ · G(x) (Lagrange function). • If x∗ is a solution and if DG(x∗) has full rank, then ∃ λ ∈ Rm (Lagrange multiplier) s.t. FOC : DxL(λ, x∗ )=0, SONC : h0 D2 xf(x∗ )h ≤ 0, ∀ h satisfying DGi(x∗ )h = 0, ∀ i. • If the FOC is satisfied, G(x∗)=0, G is quasi-concave, and SOSC: h0 D2 f(x∗ )h 0 and b > 0, consider F(a, b) ≡ max x1, x2 −ax2 1 − bx2 2 s.t. x1 + x2 = 1. Theorem 2.10. Let A ∈ Rn×n be symmetric, C ∈ Rm×n has full rank, m 0 for x 9= 0 satisfying Cx = 0 ⇐⇒ (−1)mbk > 0, ∀ k ≥ 2m + 1. 2. x0 Ax 0, ∀ k ≥ 2m + 1. 2—8
Discussions (1)What is the intuition for the FOC? (2) What is the intuition for the SOC? (3How to verify the SOC? (4) Is the SOC related to quasi-concavity? Example 2. 13. Verify the SoC for Example 2. 12. Example 2. 14. verify the SoC for Example 2. 12. Theorem 2.11.(Kuhn-Tucker). For differentiable f: R-R and G: Rn- Rm consider problem st.G(x)≥0. Let C(, A)=f(a)+AG(a). If a* is a solution and Dg; (a),i=l k corresponding to binding constraints are linearly independent, then there exists AER+ such that FOC:D2L(x*,)=0, Kuhn-Tucker condition: A G(r)=0. Theorem 2.12. Suppose f, gi, hi: Rn- R are C functions, i= l,..., m,j= 1,., k, and k< n. Let G=(91,., gm) and H =(h1, .. hk). If a* is a solution of the following problem V≡maxf(x) t.G(x)≥0, H(x)=0, and the vectors Dg;(a")and Dh; (a), i=l,., m, j=1, ...,k, corresponding to binding constraints are linearly independent, then there exists a unique A E Rn and ∈ RK such that (a)Df(x*)+入.G(x)+p·H(x2)=0; (b)入.G(x)=0.■
Discussions: (1) What is the intuition for the FOC? (2) What is the intuition for the SOC? (3) How to verify the SOC? (4) Is the SOC related to quasi-concavity? Example 2.13. Verify the SOC for Example 2.12. Example 2.14. Verify the SOC for Example 2.12. Theorem 2.11. (Kuhn-Tucker). For differentiable f : Rn → R and G : Rn → Rm, consider problem V ≡ max x∈Rn f(x) (2.1) s.t. G(x) ≥ 0. Let L(x, λ) ≡ f(x)+λ·G(x). If x∗ is a solution and Dgj (x∗), i = 1, . . . , m, j = 1,..., k, corresponding to binding constraints are linearly independent, then there exists λ ∈ Rm + such that FOC: DxL(x∗ , λ)=0, Kuhn-Tucker condition: λ · G(x∗ )=0. Theorem 2.12. Suppose f, gi, hj : Rn → R are C1 functions, i = 1, . . . , m, j = 1,..., k, and k < n. Let G ≡ (g1,...,gm)T and H ≡ (h1,...,hk)T . If x∗ is a solution of the following problem V ≡ max x∈Rn f(x) (2.2) s.t. G(x) ≥ 0, H(x)=0, and the vectors Dgi(x∗) and Dhj (x∗), i = 1, . . . , m, j = 1,..., k, corresponding to binding constraints are linearly independent, then there exists a unique λ ∈ Rm + and μ ∈ Rk such that (a) Df(x∗ ) + λ · G(x∗ ) + μ · H(x∗ ) = 0; (b) λ · G(x∗ )=0. 2—9
Theorem 2.13.(global maximum). Let f and gi, i=1,., m, be quasi-concave, where G=(g1, ...,9m). Let a' satisfy the Kuhn-Tucker condition and the FOC for (2. 1). Then, I'is a global maximum point if (1) Df(r")+0, and f is locally twice continuously differentiable, or (2)f is concave H: Rn-R is linear if H()=Az+B, where A is matrix and B is a vector Proposition24.Letf:Rn→ R and g:Rn→ rh be concave,,andH:R→Rm be linear. Also, 3 o s.t. G(o>>0. Then, I* is a solution of max f(a) st.G(x)≥0 (x)=0 iG(x)≥0,H(x*)=0, and there exist入∈ Rn and A∈ RR Such that入(x”)=0 and x* is a solution of maxL(x,),)≡f(x)+入.G(x)+p·H(x).■ Example 2.15. For a E(0, 1), consider U(p1,p2,m)≡max。Arin2-a t 6. Envelope Theorem Theorem 2. 14.(Envelope). For differentiable f: XXA+R, XCR, A CRK and x*(a) being an interior maximum point of F(a)≡maxf(x,a), we have dF(a af(a, a
Theorem 2.13. (global maximum). Let f and gi, i = 1, . . . , m, be quasi-concave, where G = (g1,...,gm)T . Let x∗ satisfy the Kuhn-Tucker condition and the FOC for (2.1). Then, x∗ is a global maximum point if (1) Df(x∗) 9= 0, and f is locally twice continuously differentiable, or (2) f is concave. H : Rn → Rk is linear if H(x) = Ax + B, where A is matrix and B is a vector. Proposition 2.4. Let f : Rn → R and G : Rn → Rk be concave, and H : Rn → Rm be linear. Also, ∃ x0 s.t. G(x0) >> 0. Then, x∗ is a solution of maxx f(x) s.t. G(x) ≥ 0 H(x)=0 iff G(x∗) ≥ 0, H(x∗)=0, and there exist λ ∈ Rm + and μ ∈ Rk such that λ ·G(x∗)=0 and x∗ is a solution of max x∈Rn L(x, λ, μ) ≡ f(x) + λ · G(x) + μ · H(x). Example 2.15. For a ∈ (0, 1), consider v(p1, p2, m) ≡ max x1, x2≥0 Axa 1x1−a 2 s.t. p1x1 + p2x2 ≤ m. 6. Envelope Theorem Theorem 2.14. (Envelope). For differentiable f : X × A → R, X ⊂ Rn, A ⊂ Rk, and x∗(a) being an interior maximum point of F(a) ≡ max x∈X f(x, a), we have dF(a) da = ∂f(x, a) ∂a x=x∗(a) . 2 — 10