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 i1<i2< define a kx k minor as In particular, denote the principal minors as di≡d(},d≡d(12},……,dn=d(12,,n Theorem 2.1. For a symmetric matrix A, (a)A>0←→k>0, for all k. (b)A<0←→(-1)dk>0, 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 < i2 < ··· < ik, define a k × k minor as d{i1,···ik} ≡ ai1i1 ai1i2 ··· ai1ik ai2i1 ai2i2 ai2ik . . . . . . . . . aiki1 aiki1 ··· aikik . In particular, denote the principal minors as d1 ≡ d{1}, d2 ≡ d{1,2}, ..., dn ≡ d{1,2,...,n}. Theorem 2.1. For a symmetric matrix A, (a) A > 0 ⇐⇒ dk > 0, for all k. (b) A < 0 ⇐⇒ (−1)kdk > 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今-A<0. e If A is a tall full-rank matrix. then A'A>0 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. • If A is a tall full-rank matrix, then A0 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 f is strictly concave Corollary 2.1. Given convex X C R, twice differentiable f: X -R, and let d(r,, ik,(a) be a k x k principal minors of D f(ar) 1. f is convex+dta…4}(x)≥0,Vx∈X,k,V{t1,…,i} 2. f is concave(-1)d1…xh(x)≥0,x∈X,Vk,V{i,…,i} 3. dk()>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 0<a, B<l. Example 2.7. For Cobb-Douglas function f(a, y)=y, defined on R2+,where Concave, ifa,B≥0,a+B≤1; strictly concave, if a,B>0, a+B<1. Proposition 2.3. Let f: X-R be differentiable. Then, (1) f is concave→Df(x)·(y-x)≥f(y)-f(x), for all a,y∈X (2) f is strictly concave←→Df(x)·(y-x)>f(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 =⇒ f is strictly concave. Corollary 2.1. Given convex X ⊂ Rn, twice differentiable f : X → R, and let d{i1,··· ,ik}(x) be a k × k principal minors of D2f(x), 1. f is convex ⇐⇒ d{i1,··· ,ik}(x) ≥ 0, ∀ x ∈ X, ∀ k, ∀{i1, ··· , ik}. 2. f is concave ⇐⇒ (−1)kd{i1,··· ,ik}(x) ≥ 0, ∀ x ∈ X, ∀ k, ∀{i1, ··· , ik}. 3. dk(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 < α, β < 1. Example 2.7. For Cobb-Douglas function f(x, y) = xαyβ, defined on R2 ++, where α, β ≥ 0, f is ⎧ ⎪⎨ ⎪⎩ concave, if α, β ≥ 0, α + β ≤ 1; strictly concave, if α, β > 0, α + β < 1. Proposition 2.3. Let f : X → R be differentiable. Then, (1) f is concave ⇐⇒ Df(x) · (y − x) ≥ f(y) − f(x), for all x, y ∈ X. (2) f is strictly concave ⇐⇒ Df(x) · (y − x) > 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