Cuong Le Van
email: cuong.le-van@univ-paris1.fr

Ngoc-Sang Pham
email: npham@em-normandie.fr

Lecture Notes: Mathematics for Economics

We present some mathematical tools widely used in courses taught in (under)graduate programs in economics. We hope that readers can learn how to apply mathematical results in economics and how to prove them. We focus on two topics: finitedimensional convex optimization and discrete-time dynamical systems. 1 We also present several applications in economics.

1 Some basics of mathematical analysis An excellent introduction of mathematical analysis can be found in [START_REF] Rudin | Principles of Mathematical Analysis[END_REF]. In the following, we only cover essential notions and results that are extremely useful in economics and will be used for the next sections. 1.1 Bounds,inferior,superior Definition 1. A greatest element of a subset S of a partially ordered set (P, ≤)2 is an a ∈ S satisfying b ≤ a ∀b ∈ S.

A least element of a subset S of a partially ordered set (P, ≤) is an a ∈ S satisfying a ≤ b ∀b ∈ S.

Definition 2. A lower bound of a subset S of a partially ordered set (P, ≤) is an element a of P such that: a ≤ x for all x ∈ S.

A lower bound a of S is called an infimum (or greatest lower bound, or meet; abbreviated inf ) of S if, for all lower bounds y of S in P , y ≤ a (a is larger than or equal to any other lower bound).

Similarly, an upper bound of a subset S of a partially ordered set (P, ≤) is an element b of P such that b ≥ x∀x ∈ S.

An upper bound b of S is called a supremum (or least upper bound, or join; abbreviated sup) of S if, for all upper bounds z of S in P , z ≥ b (b is less than any other upper bound).

Exercise 1. Let S = (0, 1) in (R, ≤).

(i) Prove that inf S = 0 and sup S = 1.

(ii) Prove that there is neither any greatest element nor least element of S.

Proposition 1. Let A ⊂ R be a nonempty set. The sup(A) is the unique element (eventually +∞) such that : (i) If x > sup(A) then x / ∈ A (ii) if x < sup(A) then there exists a ∈ A such that x < a (iii) There exists a sequence in A which converges to sup(A).

Proof. (i) If

x ∈ A then x ≤ sup(A) since this one is an upper bound of A. The result is then obvious.

(ii) If not, for any a ∈ A, a ≤ x and x is an upper bound which is smaller than the smallest upper bound which is sup(A).

(iii) First suppose that sup(A) is finite. Then for any k ∈ N, there exists a k ∈ A which satisfies sup(A)-1 k < a k ≤ sup(A). The sequence {a k } k converges to sup(A). Now suppose sup(A) = +∞.The set A is then unbounded from above. Hence, for any k ∈ N, there exists a k ∈ A with a k ≥ k. Obviously, the sequence {a k } k converges to +∞ = sup(A).

Proposition 2. Let A ⊂ R be a nonempty set. The inf(A) is the unique element (eventually -∞) such that :

(i) If x < inf(A) then x / ∈ A (ii) if x > inf(A) then there exists a ∈ A such that x > a (iii) There exists a sequence in A which converges to inf(A).

Sequence and limit

A sequence is a function whose domain is the positive numbers. We write (x i ) i = (x 1 , x 2 , . . . , ). The value x i may be in R, R N or in other spaces.

A subsequence (x kn ) n of (x k ) k is an infinite sequence x k 1 , x k 2 , . . . where k 1 , k 2 , . . . is an infinite increasing sequence of integers.

We now focus on the case x ∈ R N ≡ {(a 1 , a 2 , . . . , a N ) : a i ∈ R, ∀i = 1, . . . , N }. We say that a sequence (x i ) i has the limit x if, for any > 0, there is a positive integer n such that

x i -x ≤ ∀i ≥ n, where a -b ≡ N i=1 (a i -b i ) 2
is the distance between vectors a and b. Definition 3. A sequence having the limit is said to be convergent (in this case, we write lim n→∞ x n = x). A sequence is divergent if it is not convergent. Definition 4. A sequence of real numbers {x k } k converges to +∞ (notation x k → +∞) if: for any A ∈ R, there exists K such that, if k ≥ K then x k ≥ A. Exercise 3. The above distance • between two vectors satisfies the Triangle Inequality:

x + y ≤ x + y and

x -z ≤ x -y + y -z Theorem 1. A sequence in R n has at most one limit.

Proof. Assume {x k } k in R n has two limits a, b. Then, given ε > 0, one can find N a , N b such that, for any n ≥ N a , one has x n -a ≤ ε and any n ≥ N b , one has x n -b ≤ ε.

In this case, if we take N ≥ max{N a , N b }, we have

a -b = a -x N + x N -b ≤ a -x N + x N -b ≤ 2ε ∀
It means that a -b ≤ 2 ∀ > 0. So, we have a -b = 0 and hence a = b.

Theorem 2. A sequence of points {x k } k in R n converges to x = (x 1 , x 2 , . . . , x n ), where x k = (x k 1 , x k 2 , . . . , x k n ), if, and only if, x k i → x i for any i = 1, . . . , n.

Proof. Exercise

Remark 1. Prove that If the real sequences (a n ) and (b n ) converge to x ∈ R, then any sequence (c n ) satisfying a n ≤ c n ≤ b n ∀n also converges to x.

Properties 1. Suppose that two real-value sequences x n and y n are convergent with limits x and y respectively. We have 1. lim n→∞ cx n = cx ∀c ∈ R.

2. lim n→∞ (x n + y n ) = x + y.

3. lim n→∞ x n y n = xy.

4. lim n→∞ (x n /y n ) = x/y if y = 0.

Exercise 4 (Theorem 3.20 [START_REF] Rudin | Principles of Mathematical Analysis[END_REF]). Prove that 1. If p > 0, then lim n→∞ 1/n p = 0.

2. If p > 0, then lim n→∞ p 1/n = 1.3

3. lim n→∞ n 1/n = 1. . By applying this theorem, we have

(1 + p) n = n k=0 n k 1 n-k p k = n k=0 n(n -1) • • • (n -k + 1) k! p k ≥ n(n -1) • • • (n -k + 1) k! p k ∀k ≤ n
Given p and α, choose k > α, k > 0. Choose n > 2k, we have

(1 + p) n ≥ n(n -1) • • • (n -k + 1) k! p k = n(n -1) • • • (n -k + 1) p k k! > n k 2 k p k k!
because n -k + 1 > n/2. Therefore,

n α (1 + p) n < 2 k k! p k n α-k
Since α -k < 0, the right hand side converges to zero when n goes to infinity. So, lim n→∞ n α (1+p) n = 0. Exercise 5. Find the limit (if it exists) of the following real-value sequences:

1. x n = (-1) n /n.

2.

x n = (-1) n . Definition 5. A real-value sequence is increasing (respectively, strictly increasing) if x n+1 ≥ x n ∀n (respectively, x n+1 > x n ∀n). It is decreasing (respectively, strictly decreasing) if x n+1 ≤ x n ∀n (respectively, x n+1 < x n ∀n).

A sequence is bounded if it has a lower bound and an upper bound.

Theorem 3 (monotone convergence theorem). A monotonic sequence (with real values) is convergent if and only if it is bounded.

Proof. Consider a monotonically increasing sequence (x n ). Suppose that (x n ) is convergent to x. It is easy to see that x n is bounded by x. Suppose now that (x n ) is bounded. In this case, we have sup n x n < ∞. We will prove that it is convergent and lim n→∞ x n = sup n x n . We do so by using the definition. Denote c ≡ sup n x n . Let be strictly positive. By definition of supremum, there exists an element x m such that c -x m < (indeed, otherwise c -≥ x m ∀m, which means that c -is an upper bound of (x n ) and smaller than c, a contradiction). We have |x n -c| = c -x n ∀n because x n ≤ c.

For n ≥ m, we have |x n -c| = c -x n ≤ c -x m ≤ . So, lim n→∞ x n = sup n .

Example 1. (Growth, Interest rates). At date 0 (initial date), the GDP per capita of countries a and b are y a and y b respectively with y a < y b . Denote y i,t the GDP per capita of country i at period t.

Assume that the rate of growth of country i is r i which is constant over time, for i = a, b.

Assume that r a > r b > 0.

Prove that 1. y a,t -y b,t converges to infinity 2. and there is a date t 0 such that y a,t -y b,t ≤ 0 ∀t ≤ t 0 and y a,t -y b,t > 0 ∀t > t 0 .

Example 2 (Compound interest).

(1) The value of P usd invested at an annual rate of interest r compounded n times per year is

V n = P 1 + r n n
When n → ∞, we define

V = lim n→∞ V n = lim n→∞ P 1 + r n n .
This is the value of P usd invested for one year at an interest rate of r with continuous compounding.

Prove that

V = P e r .
where e is the natural number. It approximately equals 2. 71828. Recall the definitions of e.

e = lim n→∞

P 1 + 1 n n e = ∞ n=0 1 n! = 1 + 1 1 + 1 1 • 2 + 1 1 • 2 • 3 + • • •
(2) The value of P usd invest for t years becomes

V n,t = P 1 + r n Note that the sequence a n ≡ inf m≥n x m is increasing while the sequence b n ≡ sup m≥n x m is decreasing.

Exercise 6. Prove that lim sup n→∞ (-1) n = 1 and lim inf n→∞ (-1) n = -1.

Exercise 7. Suppose that lim inf n→∞ x n > a. Prove that there exists a positive integer n 0 > 0 such that x n > a ∀n > n 0 .

Series

Definition 7. Let (a t ) be a sequence. s n ≡ n t= a t is called a series. Example: Present value of a stream of payments. Present value of incomes.

Remark 2.

1. If the series converges, then lim n→∞ a n = 0.

2. The converse may not hold.

We introduce "comparison test" which is very useful. n-1 k=0 a k = a n -1 a-1 if a = 1, and equals n if a = 1.

2.

n-1 k=1 a k = a n -a a-1 if a = 1, and equals n -1 if a = 1.

3.

n k=1 ka k = (a-1)(n+1)a n+1 -a n+2 +a (a-1) 2 if a = 1.

4.

∞ k=0 a k = 1 1-a if a ∈ (0, 1), and equals ∞ if a ≥ 1. 5. (Present Value of a Stream of Payments) Given that the interest rate is strictly positive (r > 0), prove that

∞ k=1 V (1 + r) k = V r .
Exercise 10. Prove that 1.

∞ n=1

1 n a < ∞ if a > 1. 2. ∞ n=1 1 n a = ∞ if a ≤ 1. In particular, ∞ n=1 1 n = ∞. Exercise 11. Prove that e ≡ ∞ n=0 1 n! = 1 + 1 1 + 1 1 • 2 + 1 1 • 2 • 3 + • • • < ∞ Exercise 12. Consider a positive sequence (a n ). Prove that lim n→∞ n i=1 (1 + a i ) < ∞ if and only if n i=1 a i < ∞.

Open, closed and compact sets

For x ∈ R n , the open ball B(x, r) with centre x and radius r is the set B(x, r) ≡ {y ∈ R n : y -x < r}.

• A set S ∈ R n is open if for all x ∈ S there exists r > 0 such that B(x, r) ⊆ S. In particular the ball B(x, r) is an open set.

• A point x is in the interior of a set S ⊆ R n if there exists r > 0 such that the open ball B(x, r) is contained in S.
The set of all interior points of S is denoted by intS.

• A set S ∈ R n is closed if its complement S c = {x ∈ R n : x / ∈ S} is open
S n = (1 -1/n, 2 + 1/n). Then ∩ n≥1 S n = [1, 2] is a closed set
+ S 2 = {x ∈ R n : x = x 1 + x 2 , x 1 ∈ S 1 , x 2 ∈ S 2 }
• The union of a finite collection of closed sets is closed

• The union of an arbitrary collection of closed sets is not always closed. Example:

S n = [0, 1 -1/n]. Then ∪ n≥1 S n = [0, 1) is not closed.
• The intersection of an arbitrary collection of closed sets is closed

• The sum of two closed sets is not always closed.

Example:

S 1 = {(x, y) ∈ R 2 : x > 0, y = 1 x }, S 2 = {(x, y) ∈ R 2 : x > 0, y = -1 x }. Note that (0, 0) ∈ S 1 + S 2 because, if (x, y) ∈ S 1 + S 2 , we must have x > 0.
Definition 8. Let S ⊂ R N . We say that S is bounded if there exists M such that S ⊆ B(0, M ). In other words, S is bounded if there exists M > 0 such that x ≤ M for all x ∈ S.

Theorem 4 (the Bolzano-Weierstrass theorem). If the sequence (x n ) in R N is bounded, then it has a convergent subsequence.

Proof. Let us firstly prove the result in the space R. Let (x n ) be a bounded sequence.

We will construct a subsequence of (x n ), which is monotonic. Then, by applying Theorem 3, this subsequence is convergent.

It remains to prove the following result.

Lemma 1. Every infinite sequence (x n ) in R has a monotone subsequence.

Proof. Define

A = {n ∈ N : ∀p ≥ n, x p ≤ x n } B = {n ∈ N : ∃p ≥ n, x p > x n }
There are two cases.

1. card(A) = ∞. Let (n k ) k be an increasing infinite sequence in A. Then the subse- quence (x n k ) of (x n ) is decreasing. 2. card(A) < ∞.
Let N a be the highest element of A. Hence, for any n > N a , we have n ∈ B. Take m 1 = N a + 1, then m 1 ∈ B and hence there exists m 2 > m 1 such that x m 2 > x m 1 . By induction argument, there exists an increasing infinite sequence

(m k ) k such that x m k+1 > x m k ∀k. So, the subsequence (x m k ) k of (x n ) is increasing. We now consider the case of R N . Let (x k ) ⊂ R N . x k = (x 1,k , . . . , x N,k ). Since (x k ) is bounded, the sequence (x i,k ) is bounded for any i = 1, . . . , N . So, there is a subsequence (x 1,k 1,m ) m which is convergent.
We consider the subsequence

x k 1,m = (x 1,k 1,m , x 2,k 1,m , . . . , x N,k 1,m ) of (x k ). Since (x 2,k 1,m ) is bounded, it has a convergent subsequence (x 2,k 2,m ) with (k 2,m ) ⊂ (k 1,m ). By induction argument, we con construct subsequences (k N,m ) ⊂ (k N -1,m ) ⊂ • • • ⊂ (k 1,m ) and the subsequence x k N,m = (x 1,k N,m , x 2,k N,m , . . . , x N,k N,m ) of (x k ) is convergent. Definition 9. Let S ⊂ R N .
We say that S is compact if it is bounded and closed Theorem 5. Let S ⊂ R N . The following statements are equivalent 1. S is compact.

2. S is bounded and closed. (The Heine-Borel theorem.)

3. For all sequences {x k } in S, there exists a subsequence {x km } m which converges to a point x ∈ S.5

Proof. We prove the equivalence between ( 2) and (3).

(3) implies (2): Assume S has the property that for all sequences {x k } in S, there exists a subsequence {x km } m which converges to a point x ∈ S. Let us prove it is compact. First, S is bounded. If not there exists a sequence {x k } k ⊂ S with lim k→+∞ x k = +∞. There exists a subsequence {x kn } n of {x k } k which converges to some x ∈ S, which is impossible since lim n x kn = +∞. We now prove S is closed. Suppose {x k } k ⊂ S converges to x. There exists a subsequence which converges in S. This limit must be x. Hence, x ∈ S.

(2) implies (3): Assume that S is compact. We will assume S ⊂ R 2 . One can easily see that the proof can be carried on when the dimension of the space is larger than 2. Let {x k } be a sequence of S. Write

x k = (x k 1 , x k 2 ), ∀k.
Since S is bounded, there exists a subsequence {x kn 1 } n which converges to some x 1 ∈ R. But there exists also a subsequence {x

kn l 2 } l of {x kn 2 } n which converges to some x 2 ∈ R. Since S is closed, (x 1 , x 2 ) ∈ S since it is the limit of {(x kn l 1 , x kn l
2 )} l . To summarize, we have found a subsequence of {x k } which converges to a point in S.

Properties 3.

• The union of a finite collection of compact sets is compact.

• The union of an arbitrary collection of compact sets is NOT ALWAYS compact.

• The intersection of an arbitrary collection of compact sets is compact.

• The sum of two compact sets is compact.

Continuous functions

Mappings Let f : S → T , where

S ⊆ R n , T ⊆ R m . Then S is called the domain of f , and T is the range of f . For R ⊆ S, the image of R under f is f (R) = {y ∈ T : y = f (x), for some x ∈ R} For U ⊆ T , the inverse image of U , f -1 (U ) is f -1 (U ) = {x ∈ S : f (x) = y, y ∈ U }
The set f -1 (U ) may be empty.

• A mapping f : S → R m , where S ⊆ R n is continuous at x ∈ S if for all sequences {x k } in S converging to x, we have that f (x k ) → f (x). Equivalently, f is continuous at x ∈ S, if for every ε > 0 there exists δ > 0 such that if y ∈ S and y -x < δ then f (y) -f (x) < ε.

• Let f (x) = (f 1 (x), . . . , f m (x))
where f i is a mapping from S to R. Then f is continuous at x ∈ S if, and only if, each f i is continuous at x.

• A mapping f is continuous on S if it is continuous at any x ∈ S.

• Let f : R n → R m , g : R n → R m . Assume f, g are continuous. Then f + g is continuous.
If λ is a real number, then λf is continuous.

• Let f : R n → R m , g : R m → R p . Assume f, g are continuous.
The mapping gof defined by gof (x) = g(f (x)) for any x is continuous.

• Let f : R n → R m . Then f is continuous if, and only if, for any open set A ⊆ R m , f -1 (A) is open in R n .
Equivalently, f is continuous if, and only if, for any closed set

A ⊆ R m , f -1 (A) is closed in R n . Proof. Assume f is continuous. Let A ∈ R m be open. We will show that f -1 (A) is open. For that, let x ∈ f -1 (A). Since A is open, there exists an open ball B(f (x), ε) ⊂ A. Since f is continuous, there exists δ > 0 such that if y ∈ B(x, δ) then f (y) ∈ B(f (x), ε) ⊂ A. This implies y ∈ f -1 (A). Equivalently, B(x, δ) ⊂ f -1 (A) and f -1 (A) is open. Conversely, assume that for any open set A ⊂ R m , the set f -1 (A) is open. We will prove that f is continuous. Let A = {z ∈ R m : z -f (x) < ε}. The set A is open. Observe that x ∈ f -1 (A). Since f -1 (A) is open, there exists an open ball B(x, δ) ⊂ f -1 (A). That means, if y -x < δ then f (y) ∈ A or equivalently f (y) -f (x) < ε.
We have proved that f is continuous.

To prove that f is continuous if, and onl! y if, for any closed set

A ⊆ R m , f -1 (A) is closed in R n , one can observe that f -1 (A c ) = (f -1 (A)) c .
Theorem 6 (Intermediate value theorem). Let f be a continuous function on the interval

[a, b]. If f (a) < f (b) and c ∈ (f (a), f (b)), then there exists a point x ∈ (a, b) such that f (x) = c. 6
Note that such a x is not necessarily unique.

Proof. Define S ≡ {d ∈ [a, b] : f (d) ≤ c}.
S is non-empty and bounded. So, there exists the supremum of S. Let x ≡ sup(S). We can prove that f (x) = c.

Example 3 (The demand, the supply and equilibrium price). Let D(p) and S(P ) be the demand and supply functions which depend on the price p ≥ 0. Assume that D and S are continuous.

A price p > 0 is said to be an equilibrium price if D(p) = S(P ).

According to Theorem 6, there is an equilibrium price p is D(0) -S(0) > 0 and lim x→∞ D(x) -S(x) < 0.

Proposition 5. Let f : S → R m , where S ⊆ R n . Assume S is compact and f is continuous on S. Then f (S) is compact.

Proof. First, f (S) is bounded. If not there exists a sequence {y n } n ⊂ f (S) with lim n→+∞ y n = +∞. We can write y n = f (x n ) with x n ∈ S for every n. Since S is compact, there exists a subsequence {x n k } k which converges to some x ∈ S and f (x n k ) converges to f (x). That is a contradiction since f (x n k ) converges to infinity too. We now show that f (S) is closed. For that, let {y n } n ⊂ f (S)→ y. We claim that y ∈ f (S). Write y n = f (x n ) with x n ∈ S for every n. Since S is compact, there exists a subsequence {x n k } k which converges to some x in S and f (x n k ) converges to f (x). We must have y = f (x). Hence, y ∈ f (S).

Theorem 7 (Weirstrass Theorem). Let f : S → R, where S ⊆ R n . Assume S is compact, nonempty and f is continuous on S. Then f has both a maximum and a minimum.

Proof. Let M = sup(f (S)). There exists a sequence {f (x n )} n converging to M . Since S is compact, there exists a subsequence {x n k } which converges to some x ∈ S and f (x n k ) converges to f (x) ∈ f (S). We have M = f (x) and hence, M = max(f (S)). The proof is similar for min(f (S)). This motivates us to study derivatives of functions.

Derivatives

Differentiability of real functions

• Let f : S → R, where S ⊆ R. We say that f is differentiable at x 0 ∈ S, where x 0 must be in the interior of S, if there exists the limit lim

x→x 0 f (x) -f (x 0 ) x -x 0
Denote this limit by f (x 0 ). This is called the derivative of function f at x 0 .

Note that we have

lim h→0 f (x) -f (x 0 ) -f (x 0 )(x -x 0 ) x -x 0 = 0 • Let f : S → R, where S ⊆ R n .
We say that f is differentiable at x 0 ∈ S, where x 0 must be in the interior of S, if there exists a vector a ∈ R n so that

f (x) -f (x 0 ) -a • (x -x 0 ) x -x 0 → 0, as x → x 0 where x -x 0 ≡ (x 1 -x 0,1 ) 2 + • • • + (x n -x 0,n ) 2 .
The vector a is called the derivative of f at x 0 and is denoted by Df (x 0 ). Moreover, we say that f is differentiable on S if it is differentiable at every point of S. We can regard Df as a mapping from S to R n . If Df is continuous, we say that f is continuously differentiable or f is C 1 .

• Let f : S → R, where S ⊆ R n . We study the derivative via partial derivatives.

Let (e 1 , . . . , e n ) be the canonical basis of R n . If e i is a vector of this basis, then the coordinates of e i equal zero excepted the i-th coordinate which equals 1. The i-th partial derivative of f at a point x is the number ∂f (x) ∂x i defined by

∂f (x) ∂x i = lim t→0 f (x + te i ) -f (x) t

Differentiability of mappings

• A mapping f : S → R m , where S ⊆ R n , is differentiable at x 0 ∈ S, where x 0 must be in the interior of S, if there exists a m × n matrix A so that

f (x) -f (x 0 ) -A(x -x 0 ) x -x 0 → 0, as x → x 0 where x -x 0 ≡ (x 1 -x 0,1 ) 2 + • • • + (x n -x 0,n ) 2
The matrix A is called the derivative of f at x 0 and is denoted by Df (x 0 ). Moreover, we say that f is differentiable on S if it is differentiable at every point of S.

Second derivatives

• Let f : S → R, where S ⊆ R n . Then the derivative Df (x) = ∂f (x) ∂x 1 , ∂f (x) ∂x 2 , . . . , ∂f (x) ∂xn is also a mapping from S to R n . If Df is differentiable then f is called twice differentiable with second derivative D 2 f (x). The partial derivatives of the partial derivatives of f are denoted by ∂ 2 f (x) ∂x i ∂x j if i = j, and by ∂ 2 f (x)

∂x 2 i if i = j.
In these cases we have

D 2 f (x) =        ∂ 2 f (x) ∂x 2 1 . . . ∂ 2 f (x) ∂x 1 ∂xn . . . . . . . . . . . . . . . ∂ 2 f (x) ∂xn∂x 1 . . . ∂ 2 f (x) ∂x 2 n       
This matrix is called the Hessian of f at x.

• When f is twice differentiable on S and each second partial derivative is a continuous function, then f is called twice continuously differentiable or C 2 .

Theorem 9. If f is C 2 on S ⊆ R n , then D 2 f (x) is a symmetric matrix, i.e. ∂ 2 f (x) ∂x i ∂x j = ∂ 2 f (x)
∂x j ∂x i for all i, j and all x ∈ S.

Notice that it can happen that ∂ 2 f (x) ∂x i ∂x j = ∂ 2 f (x) ∂x j ∂x i if our assumptions are not satisfied.

Exercise 13. [START_REF] Rudin | Principles of Mathematical Analysis[END_REF] Define

f (0, 0) = 0 f (x, y) = xy(x 2 -y 2 )
x 2 +y 2 if (x, y) = (0, 0)

Prove that 1. f , D 1 f , D 2 f are continuous in R 2 .
2. D 12 f and D 21 f exist at every point of R 2 , and are continuous except at (0, 0). By definition, we have lim h→0 φ(c) = f (c).

We will prove that f (c) = 0. By definition of c, we have

f (c + h) -f (h) ≥ 0, ∀h satisfying c + h ∈ [a, b].
Let h > 0 and tend to zero, we have f (c) ≥ 0. Let h < 0 and tend to zero, we have f (c) ≤ 0. Therefore, f (c) = 0.

Theorem 11 (Mean value theorem). Let f be a function from [a, b]

into R. Assume that f is continuous on [a, b], differentiable on (a, b). Then there exists c ∈ (a, b) such that f (c) = f (b)-f (a) b-a .
Proof. Without loss of generality, we assume that a < b.

Consider the function

g(x) ≡ f (x) - f (b) -f (a) b -a (x -a)
We have g(a) = g(b). Applying Rolle's theorem, we get the result.

The following theorem is very important for Optimization and Dynamical System. We state the result without proof.

Theorem 12 (Taylor expansion). Let f : S → R, where S ⊆ R n is an open set. Pick

x 0 ∈ S 1. If f is C 1 on S, then for any x ∈ S we can write f (x) = f (x 0 ) + Df (x 0 ) • (x -x 0 ) + R 1 (x, x 0 ) x -x 0 where R 1 (x 0 , x 0 ) = 0 and R 1 (x, x 0 ) → 0 as x → x 0 .
We explicitly write

f (x 1 , . . . , x n ) = f (x 0,1 , . . . , x 0,n ) + n i=1 ∂f (x 0 ) ∂x i (x i -x 0,i ) + R 1 (x, x 0 ) x -x 0 2.
If f is C 2 on S, then for any x ∈ S, one can write

f (x) = f (x 0 ) + Df (x 0 ) • (x -x 0 ) + 1 2 (x -x 0 ) D 2 f (x 0 )(x -x 0 ) + R 2 (x, x 0 ) x -x 0 2
where R 2 (x 0 , x 0 ) = 0 and R 2 (x, x 0 ) → 0 as x → x 0 .

We explicitly write

f (x 1 , . . . , x n ) =f (x 0,1 , . . . , x 0,n ) + n i=1 ∂f (x 0 ) ∂x i (x i -x 0,i ) + 1 2 i,j ∂ 2 f (x 0 ) ∂x i ∂x j (x i -x 0,i )(x j -x 0,j ) + R 2 (x, x 0 ) x -x 0 2 (Quasi)

Convexity and (quasi)concavity

The notion of convexity is very important in economics. Indeed, in economic models, the budget set of agents are usually assumed to be convex. In many setups, we assume that preferences of agents are convex or the utility functions are (quasi)concave. These observations motivate us to study the (quasi)convex and (quasi)concave functions.

Convexity and concavity

Definition 10

(Convex set). A set A in R n is convex if λa + (1 -λ)b ∈ A ∀a ∈ A, ∀b ∈ A, ∀λ ∈ [0, 1] (the line segment is a subset of A).
Definition 11 (Concavity). Let f : A → R be a function defined from A, a nonempty set of R n , into R. We require that A is convex.

1. f is convex on A if f (λa + (1 -λ)b) ≤ λf (a) + (1 -λ)f (b)∀a ∈ A, ∀b ∈ A, ∀λ ∈ [0, 1]. 2. f is strictly convex on A if f (λa + (1 -λ)b) < λf (a) + (1 -λ)f (b)∀a ∈ A, ∀b ∈ A, a = b, ∀λ ∈ (0, 1).

The function

f : A → R is concave on A if -f is convex. Explicitly, f is concave on A if ∀a 1 ∈ A, ∀a 2 ∈ A, ∀λ ∈ [0, 1] , f (λa 1 + (1 -λ)a 2 ) ≥ λf (a 1 ) + (1 -λ)f (a 2 ).
It is strictly concave on A if:

∀a 1 ∈ A, ∀a 2 ∈ A, a 1 = a 2 , ∀λ ∈ ]0, 1[ , f (λa 1 + (1 -λ)a 2 ) > λf (a 1 ) + (1 -λ)f (a 2 ).
The function f (x) = x 2 is strictly convex and f (x) = x 1/2 is strictly concave. The function f (x) = Ax is convex and concave but neither strictly convex nor strictly concave.

Proposition 6 (Jensen inequality). Let U be a nonempty convex set of R n and let f : U → R be a convex function on U . Then f is convex if, and only if, for any integer p ≥ 2, for any p elements of U , x 1 , . . . , x p , for any p positive numbers λ 1 , . . . , λ p , the sum of which equals 1, then

f (λ 1 x 1 + . . . + λ p x p ) ≤ λ 1 f (x 1 ) + . . . + λ p f (x p ). Proof. Let f : U → R where U is a convex, nonempty subset of R n . Assume f convex. Let x 1 , . . . , x p be p elements of U . If p = 2, then obviously f (λ 1 x 1 + . . . + λ p x p ) ≤ λ 1 f (x 1 ) + . . . + λ p f (x p ).
Assume that Jensen Inequality holds for p -1. We will show that it holds also for p. If λ p = 1, then the result is trivially true. So, we assume λ p = 1. Let s p-1 = λ 1 + . . . + λ p-1 . We have:

λ 1 x 1 + . . . + λ p x p = s p-1 λ 1 s p-1 x 1 + . . . + λ p-1 s p-1 x p-1 + (1 -s p-1 )x p .
The function f being convex, we have:

f (λ 1 x 1 + . . . + λ p x p ) ≤ s p-1 f λ 1 s p-1 x 1 + . . . + λ p-1 s p-1 x p-1 + (1 -s p-1 )f (x p ).
We have assumed that Jensen Inequality holds for p -1. Hence

f ( λ 1 s p-1 x 1 + . . . + λ p-1 s p-1 x p-1 ) ≤ λ 1 s p-1 f (x 1 ) + . . . + λ p-1 s p-1 f (x p-1 ).
Thus:

f (λ 1 x 1 + . . . + λ p x p ) ≤ λ 1 f (x 1 ) + . . . + λ p f (x p ).
The converse is true by taking p = 2.

The following theorem is very important and useful.

Theorem 13 (first-order convexity condition). Let f be a differentiable function from its domain (dom(f )) into R. Assume that dom(f ) is convex.

1. f is convex if and only if, for any x, y ∈ dom(f ), we have

f (y)-f (x) ≥ Df (x)•(y-x).
f is strictly convex if and only if, for any x, y ∈ dom(f

), x = y we have f (y)-f (x) > Df (x) • (y -x).
2. f is concave if and only if, for any x, y ∈ dom(f ), we have

f (y) -f (x) ≤ Df (x) • (y -x).
f is strictly concave if and only if, for any x, y ∈ dom(f

), x = y we have f (y)-f (x) < Df (x) • (y -x).
Proof. Notice that we cannot directly use Taylor's expansion. Let us prove the first point. Suppose that f is convex. We have to prove that f (y) -f (x) ≥ Df (x) • (y -x) for any x, y ∈ dom(f

). Let x, y ∈ dom(f ). Consider z(λ) ≡ (1 -λ)x + λy with λ ∈ [0, 1]. Since dom(f ) is convex, we have z(λ) ∈ dom(f ), ∀λ ∈ [0, 1]. By the convexity of f , we have f ((1 -λ)x + λy) ≤ (1 -λ)f (x) + λf (y) ⇔ f (x + λ(y -x)) ≤ f (x) + λ(f (y) -f (x)) or equivalently f (x + λ(y -x)) -f (x) λ ≤ f (y) -f (x).
Let λ go to zero, we get that Df (x)

• (y -x) ≤ f (y) -f (x). Suppose now that f (y) -f (x) ≥ Df (x) • (y -x), ∀x, y ∈ dom(f ) (1) Consider z(λ) ≡ (1 -λ)x + λy with λ ∈ [0, 1]. Applying (1), we have f (x) -f (z) ≥ Df (z) • (x -z) ⇒ (1 -λ) f (x) -f (z) ≥ (1 -λ)Df (z) • (x -z) (2) f (y) -f (z) ≥ Df (z) • (y -z) ⇒ λ f (y) -f (z) ≥ λDf (z) • (x -z) (3)
Taking the sum of both sides, we get that

(1 -λ) f (x) -f (z) + λ f (y) -f (z) ≥ (1 -λ)Df (z) • (x -z) + λDf (z) • (x -z) ⇔ (1 -λ)f (x) + λf (y) ≥ f (z) So, the function f is convex. Corollary 1. Consider f : dom(f ) → R. Assume that f is convex. If x ∈ dom(f ) such that Df (x) = 0, then f (x) = min a∈dom(f ) (f (a)).
The following properties are very useful. We can prove them by using definition.

Properties 5. We have the following properties.

1. If f, g are convex from a convex set U into R and if λ is a nonnegative real number, then f + g and (λf ) are convex.

2. Let f , g be two convex functions from a convex set U, into R. Then max(f, g) is convex. More generally, consider a collection of convex functions

{f i } i=1,...,I , from U into R. Then max{f i | i = 1, . . . , I} is convex from U into R. 3. If functions f : U → R, g : V → R, with f (U ) ⊂ V , are convex, if g is nondecreasing, then g • f is convex. 4. If (f i ) i∈N is a sequence of convex functions from R n into R which converges pointwise, i.e. ∀x ∈ R n , the sequence (f i (x)) i∈N converges in R, then the function defined for all x ∈ R n by f (x) = lim i→+∞ f i (x) is convex from R n into R. Proof. Let us prove point 2. Denote f = max i f i . Let a, b ∈ U and λ ∈ [0, 1].
We have

f i (λa + (1 -λ)b) ≤ λf i (a) + (1 -λ)f i (b) ≤ λf (a) + (1 -λ)f (b).
Taking the maximum over i, we have f

(λa + (1 -λ)b) ≤ λf (a) + (1 -λ)f (b). So, the function f is convex.
Example 4 (Simple composition results).

1. If g is convex then e g(x) is convex.

2. If g is concave and positive, then log g(x) is concave.

3. If g is concave and positive, then 1/g(x) is convex.

4. If g is convex and nonnegative and p ≥ 1, then (g(x)) p is convex.

If g is convex then -ln(-g(x)

) is convex on {x : g(x) < 0}.

Convexity and continuity

Theorem 14.

If f is convex from an open set U ⊂ R n into R, then it is continuous in U . 7
Proof. It is not easy to prove this result. We need an intermediate step.

Lemma 2. Let f be a convex function from an open set U of R n into R. Assume 0 ∈ U .
Then, there exists a closed ball B(0, r) ⊂ U such that f is bounded above on B(0, r).

Proof. Since 0 ∈ U, one can choose α > 0 sufficiently small such that the convex hull V = co{αe 1 , . . . , αe n , -αe 1 , . . . , -αe n }, 8 where the e i are the vectors of the canonical basis of R n , is contained in U .

V has a nonempty interior, 0 is in the interior of V . Thus, V contains a closed ball B(0, r). 9 Any x in V may be expressed as:

x = α n i=1 λ i e i -α n i=1 λ i e i with λ i ≥ 0, λ i ≥ 0, ∀i, n i=1 (λ i + λ i ) = 1. Since f is convex, f (x) ≤ n i=1 λ i f (αe i ) + λ i f (-αe i ) ≤ max f (αe 1 ), . . . , f (αe n ), f (-αe 1 ), . . . , f (-αe n ) .
Therefore f is bounded above on B(0, r).

We now prove Theorem 14. Let

x 0 ∈ U . Define V ≡ U -{x 0 }. Observe that V is convex, open and 0 ∈ V . Consider the function h : V → R defined by h(x) = f (x + x 0 ) -f (x 0 ).
Obviously h is convex and h(0) = 0. Moreover, f is continuous at x 0 if, and only if, h is continuous at 0.

We will prove that h is continuous at 0. Let {x n } n ⊂ V converge to 0. We have to prove that h(x n ) converges to h(0) = 0.

Since V is open and 0 ∈ V , there exists a closed ball B(0, r) ⊂ V . Since {x n } n converge to 0, there exists n 0 such that {x n } n≥n 0 ⊂ B(0, r). Let S denote the sphere of radius r:

S ≡ {x ∈ R n : x = r}. Define y n = rx n x n , z n = -rx n x n . Then y n ∈ S, z n ∈ S, ∀n. One can see that x n = x n y n r + 1 - x n r 0 0 = r r + x n x n + x n r + x n z n
Since h is convex, we then get

h(x n ) ≤ x n r h(y n ) + 1 - x n r h(0) = x n r h(y n ) ≤ x n r sup y∈S h(y) 0 = h(0) ≤ r r + x n h(x n ) + x n r + x n h(z n ) ⇒ 0 ≤ h(x n ) + x n r h(z n ) ≤ h(x n ) + x n r sup y∈S h(y).
Let n → +∞. Then x n → 0 and

lim sup n h(x n ) ≤ 0 = h(0) 0 ≤ lim inf n h(x n ). 8 Let T = {a 1 , a 2 , . . . , a m } ⊂ R n .
We define: the convex hull of T denoted by coT is the set [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].

coT = x : x = m i=1 λ i a i , λ i ≥ 0, ∀i, m i=1 λ i = 1 9 See Lemma 1.2.1 in

Mathematics for Economics

Summing up 0

= h(0) ≤ lim inf n h(x n ) ≤ lim sup n h(x n ) ≤ 0 = h(0) Hence 0 = h(0) = lim n h(x n ).

Testing concavity and convexity

Definition 12 (Definite and semidefinite matrices). Let A be an n × n matrix. Then A is said to be

• positive definite if x Ax > 0 for all x ∈ R n , x = 0 • positive semidefinite if x Ax ≥ 0 for all x ∈ R n • negative definite if x Ax < 0 for all x ∈ R n , x = 0 • negative semidefinite if x Ax ≤ 0 for all x ∈ R n Example 5. The matrix I = a 0 0 b , where a, b > 0, is positive-definite.
In particular, the identity matrix I = 1 0 0 1 is positive-definite.

The matrix I = a 0 0 b , where a, b < 0, is negative-definite.

Proposition 7 (second-order convexity condition). Let f : A → R be a function defined from A, a nonempty, convex set of R n , into R. Assume that f is twice continuously differentiable.

1. f is concave if and only if D 2 f (x) is negative semidefinite for every x ∈ A.

If D 2 f (x) is negative definite for every x ∈ A, then the function is strictly concave.10

2. f is convex if and only if D 2 f (x) is positive semidefinite for every x ∈ A.
If D 2 f (x) is positive definite for every x ∈ A, then the function is strictly convex.

Proof. To present a proof. Let us prove point 1.

Corollary 2. Let f : A → R be a function defined from A, a nonempty, convex set of R, into R. Assume that f is twice continuously differentiable. 1. f is concave if and only if f (x) ≤ 0 for every x ∈ A.
If f (x) < 0 for every x ∈ A, then the function is strictly concave.

2. f is convex if and only if f (x) ≥ 0 for every x ∈ A.

If f (x) > 0 for every x ∈ A, then the function is strictly convex.

Exercise 14 (Function of one variable). 1. Exponential. e ax is convex on R, for any a ∈ R.

Power.

x a is convex on R ++ when a ≥ 1 or a ≤ 0, and concave for a ∈ [0, 1].

Power of absolute value: |x|

p , for p ≥ 1, is convex on R. 4. Logarithm: log(x) is concave on R ++ .
5. Negative entropy: xlog(x) (either on R ++ , or on R + , defined as 0 for x = 0) is convex. is convex.

Proposition 7 leads to the following result.

Corollary 3. Let f : A → R be a function defined from A, a nonempty, convex set of R 2 , into R. Assume that f is twice continuously differentiable.
1. f is concave if and only if

f 11 (x 1 , x 2 ) ≤ 0 (4a) f 22 (x 1 , x 2 ) ≤ 0 (4b) f 11 (x 1 , x 2 )f 22 (x 1 , x 2 ) -f 12 (x 1 , x 2 ) 2 ≥ 0 (4c) 2.
f is strictly concave if and only if

f 11 (x 1 , x 2 ) < 0 (5a) f 11 (x 1 , x 2 )f 22 (x 1 , x 2 ) -f 12 (x 1 , x 2 ) 2 > 0. ( 5b
)
This result is very useful when we need to verify the concavity (convexity) of a function of 2 variables. When the function is of several variables, we need conditions to check whether the Hessian matrix D 2 f is negative or positive (semi)definite. Linear Algebra answers this question.

Positive (semi)definite matrix: a test

Matrices are commonly written in box brackets or parentheses:

A =      a 11 a 12 • • • a 1n a 21 a 22 • • • a 2n . . . . . . . . . . . . a m1 a m2 • • • a mn      =      a 11 a 12 • • • a 1n a 21 a 22 • • • a 2n . . . . . . . . . . . . a m1 a m2 • • • a mn      = (a ij ) ∈ R m×n .
Given a matrix A, we denote by A k the k × k submatrix of A formed by taking just the first k rows and columns of A. It means that

A k =      a 11 a 12 • • • a 1k a 21 a 22 • • • a 2k . . . . . . . . . . . . a k1 a k2 • • • a kk     
We give without proof the following tests in Linear Algebra.

Lemma 3 (Sylvester's criterion). Let A be a symmetric n × n matrix.

(i) A is positive definite if, and only if, detA k > 0 for all k = 1, . . . , n (ii) A is negative definite if, and only if, detA k > 0 for all even k ∈ {1, . . . , n} and detA k < 0 for all odd k ∈ {1, . . . , n}. (i.e., (-1)

i det(A i ) > 0 ∀i = 1, . . . , n).
There is NO equivalence of the above result for positive or negative SEMIDEFINITE matrices.

Lemma 4. Let A be a symmetric n × n matrix. A is negative semidefinite if and only if (-1) i det(A π i ) > 0 ∀i = 1, . . . , n and for every permutation π of the indices {1, . . . , n}. 11 These two lemmas and Proposition 7 allow us to verify whether a function f which is twice continuously differentiable is (strictly)concave or (strictly)convex via the Hessian of f .

Exercise 15 (Function of several variables).

1. Norms. f (x) = x is convex on R n . 2. Max function. f (x) = max i (x i ) is convex on R n .
3. Quadratic-over-linear function. The function f (x, y) = x 2 y defined on the domain

dom(f ) = R × R ++ is convex. 4. Log-sum-exp function. f (x) = ln(e x 1 + • • • + e xn ) is convex on R n . 5. Geometric mean: The function f (x) = x 1 x 2 • • • x n 1 n is convex on dom(f ) ≡ R n ++ . 6. Quadratic functions: f (x) = 1 2 x T Qx + c T x on R n , where Q ∈ R n×n is a positive definite matrix and c ∈ R n .

Quasiconvexity and quasiconcavity

Definition 13 (Quasi-concavity). Let f : A → R be a function defined from A, a nonempty set of R n , into R. We require that A is convex.

1. We say that f is quasi-concave if its upper contour sets {x ∈ A : f (x) ≥ t} are convex sets for any t, that is

f (λx + (1 -λ)x ) ≥ t if min(f (x), f (x )) ≥ t for any t ∈ R, x, x ∈ A, λ ∈ [0, 1].
2. We say that f is strictly quasi-concave if it satisfies:

f (λx + (1 -λ)x ) > t if min(f (x), f (x )) ≥ t for any t ∈ R, x, x ∈ A, x = x , λ ∈ (0, 1).
11 A permutation of the set S ≡ {1, . . . , n} is defined as a bijection from S to itself.

3. f is call (strictly) quasiconvex if -f is (strictly) quasiconcave. Precisely, f is call quasiconvex if {x ∈ A : f (x)
≤ t} are convex sets for any t.

4.

A function that is both quasiconvex and quasiconcave is quasilinear.

Example 6.

1. Prove that ln(x) on R ++ is quasiconvex and quasiconcave.

2. Prove that sin(x) on R is neither quasiconvex nor quasiconcave.

Consider the function

f : R 2 → R with domain(f ) ≡ R 2 + and f (x 1 , x 2 ) = x 1 x 2 .
(a) Prove that f is neither convex nor concave.

(b) Prove that f is quasiconcave on R 2 + but not quasiconcave on R 2 . Properties 6. (i) f is quasiconcave if and only if

f (λx + (1 -λ)x ) ≥ min(f (x), f (x )) for any x, x ∈ A, λ ∈ [0, 1].
f is strictly quasiconcave if and only if

f (λx + (1 -λ)x ) > min(f (x), f (x )) for any t ∈ R, x, x ∈ A, λ ∈ [0, 1].
(ii) Any increasing function of one variable is quasiconcave.

(iii) A concave function is quasiconcave. However, the converse is not true.

Properties 7.

1. If f i is quasiconvex and λ > 0, then λf i is quasiconvex.

If

f i is quasiconvex for all i ∈ I, then sup i (f i ) is quasiconvex. 3. If f is quasiconvex and g is non-decreasing from R into R, then g • f is quasiconvex.
Notice that the sum of two quasiconvex functions need not be quasiconvex.

Exercise 16. Suppose that f (x, y) is quasiconvex and C is a convex set. Prove that

g(x) ≡ inf y∈C f (x, y)
is quasiconvex

Testing quasiconcavity and quasiconvexity

Theorem 15 (first-order quasiconvexity condition). Let f be a differentiable function from its domain (dom(f )) into R. Assume that dom(f ) is convex.

1. f is quasiconvex if and only if, for any x, y ∈ dom(f ), we have that:

f (y) ≤ f (x) ⇒ Df (x) • (y -x) ≤ 0. (6)
2. f is quasiconcave if and only if, for any x, y ∈ dom(f ), we have that.

f (y) ≥ f (x) ⇒ Df (x) • (y -x) ≥ 0. ( 7
)
Proof. Let us prove point 2.

Necessary condition. Suppose that f is quasiconcave. Let x, y ∈ dom(f ). Assume that f (y) ≥ f (x). We have to prove that Df (x)•(y-x) ≥ 0. Since f is quasiconcave, we have

f ((1 -λ)x + λy) ≥ min(f (x), f (y)) = f (x) for any λ ∈ [0, 1]. Observe that (1 -λ)x + λy = x + λ(y -x).
Hence, we have

f (x + λ(y -x)) -f (x) λ ≥ 0 ∀λ ∈ (0, 1].
Let λ go to zero, we get that Df (x) • (y -x) ≥ 0. Sufficient condition. Suppose that f satisfies condition (7). We will prove that f is quasiconcave, i.e.,

f ((1 -λ)x + λy) ≥ min(f (x), f (y)) for any x, y ∈ A, λ ∈ [0, 1].
Suppose that this is not true. That is there exists

x, y ∈ A, λ ∈ [0, 1] such that f ((1 -λ)x + λy) < min(f (x), f (y)).
We have to find a contradiction.

Without loss of generality, we assume that f (y) ≥ f (x). So, we have

f ((1 -λ)x + λy) < f (x) ≤ f (y).
For each θ ∈ [0, 1], we define z θ ≡ (1-θ)x+θy = x+θ(y-x) and g(θ

) ≡ f ((1-θ)x+θy). Since dom(f ) is convex, we have z θ ∈ dom(f ).
We present two ways to get a contradiction 1. Proof 1. Since g(λ) < g(0), there exists λ 1 ∈ (0, λ) such that g (λ 1 ) = g(λ)-g(0) λ < 0.

Since g(λ) < g(1), there exists λ 2 ∈ (λ, 1) such that g (λ 2 ) = g(λ)-g(1)

λ-1 > 0. To sum up, we have 0 < λ 1 < λ < λ 2 < 1 and g (λ 2 ) > 0 > g (λ 1 ). This implies that g (λ 1 )(λ 2 -λ 1 ) < 0 and g (λ

2 )(λ 1 -λ 2 ) < 0. If g(λ 1 ) ≥ g(λ 2 ), i.e., f ((1 -λ 1 )x + λ 1 y) ≥ f ((1 -λ 2 )x + λ 2 y), we apply condition (7) to get get g (λ 2 )(λ 1 -λ 2 ) ≥ 0, a contradiction. If g(λ 1 ) ≤ g(λ 2 ), i.e., f ((1 -λ 1 )x + λ 1 y) ≤ f ((1 -λ 2 )x + λ 2 y), we apply condition (7) to get get g (λ 1 )(λ 2 -λ 1 ) ≥ 0, a contradiction. 2. Proof 2. Define m ≡ min θ∈[0,1] {g(θ)} and θ * ≡ inf{θ ∈ [0, 1] : g(θ) = m}. Notice that m < f (x).
By continuity of the function g and m < f (x), there exists > 0 such that g(θ

) < f (x) ∀θ ∈ (θ * -, θ * ).
By definition of θ * , we have g(θ) > m ∀θ < θ * .

So, we have g(θ) > m = g(θ * ) ∀θ ∈ (θ * -, θ * ). Take θ ∈ (θ * -, θ * ). Applying the mean value theorem, there exists τ ∈ (θ * -, θ * ) such that

g (τ ) = g(θ) -g(θ * ) θ -θ * < 0 This means that Df (z τ ) • (y -x) > 0. (8) Now, since τ ∈ (θ * -, θ * ), we have g(τ ) < f (x), i.e., f (x) > f ((1 -τ )x + τ y). Recall that f (y) ≥ f (x), we have f (y) > f ((1 -τ )x + τ y). Using condition (7), we get that Df ((1 -τ )x + τ y) • ((1 -τ )(y -x)) ≥ 0 which is equivalent to Df (z τ ) • (y -x) ≥ 0.
which is a contradiction with (8). We have finished our proof.

Theorem 16 (second-order quasiconvexity condition). Let f : A → R be a function defined from A, a nonempty, convex set of R n , into R. Assume that f is twice continuously differentiable.

1. If f is quasiconvex, we have that:

x ∈ dom(f ), y ∈ R n , y T Df (x) = 0 ⇒ y T D 2 f (x)y ≥ 0. 2. f is quasiconvex if f satisfies y T Df (x) = 0 ⇒ y T D 2 f (x)y > 0 for any x ∈ dom(f ) and y ∈ R n , y = 0.
Proof. See Florenzano and Le [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF] or [START_REF] Boyd | Convex Optimization[END_REF] among others.

For other second-order conditions for quasiconvexity, see Exercise 3.44 in [START_REF] Boyd | Convex Optimization[END_REF].

We present here a simple test for functions of 2 variables.

Proposition 8. Let f : A → R be a function defined from A, a nonempty, convex set of R 2 , into R. Suppose that (1) f is twice continuously differentiable, (2) f is strictly increasing in each component (f 1 ≡ ∂f ∂x 1 > 0, f 2 ≡ ∂f ∂x 2 on A). 1. If f is quasiconcave, then the determinant of the bordered Hessian is non-negative the bordered Hessian: B 2 ≡   0 f 1 f 2 f 1 f 11 f 12 f 2 f 21 f 22   that is 2f 1 (x 1 , x 2 )f 2 (x 1 , x 2 )f 12 (x 1 , x 2 ) -f 1 (x 1 , x 2 ) 2 f 22 (x 1 , x 2 ) -f 2 (x 1 , x 2 ) 2 f 11 (x 1 , x 2 ) ≥ 0 ∀(x 1 , x 2 ) ∈ A. 2. If 2f 1 (x 1 , x 2 )f 2 (x 1 , x 2 )f 12 (x 1 , x 2 ) -f 1 (x 1 , x 2 ) 2 f 22 (x 1 , x 2 ) -f 2 (x 1 , x 2 ) 2 f 11 (x 1 , x 2 ) > 0 ∀(x 1 , x 2 ) ∈ A, then f is strictly quasiconcave.
Proof. See [START_REF] Simon | Mathematics for Economists[END_REF], page 530, among others.

Other exercises

Exercise 17. For each of the following functions, determine if the function is convex, concave, quasiconvex, or quasiconcave.

1. f (x) = e x -1 on R. 2. f (x) = x 1-σ 1-σ -2 on R + . 3. f (x 1 , x 2 ) = x 1 x 2 on R 2 ++ . 4. f (x 1 , x 2 ) = 1 x 1 x 2 on R 2 ++ . 5. f (x 1 , x 2 ) = x 1 x 2 on R 2 ++ . 6. f (x 1 , x 2 ) = x 2 1 x 2 on R × R ++ .
More exercises can be found in Florenzano and Le [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF] and [START_REF] Boyd | Convex Optimization[END_REF].

The following exercises are important in Economics.

Exercise 18 (Probability and Statistics). Let X be a real-valued random variable defined by

P (X = a i ) = P robability(X = a i ) = p i where a 1 < a 2 < • • • < a n .
For each of the following functions of p on the simplex ∆ n (defined by

∆ n ≡ {p ∈ R n + : p 1 + • • • + p n = 1}), determine if the function is convex, concave, quasiconvex, or quasiconcave. 1. E(X) ≡ i p i a i . 2. P (X ≥ α) 3. P (α ≤ X ≤ β).

4.

i p i ln(p i ) (the negative entropy of the distribution).

V ar(

X) ≡ E(X -E(X)) 2 = E(X 2 ) -(E(X)) 2 . 6. Quartile(X) ≡ inf{β : P (X ≤ β) ≥ 0.25}
Exercise 19 (Functions in economics). For each of the following functions, determine if the function is convex, concave, quasiconvex, or quasiconcave.

1. Cobb-Douglas function: f (x 1 , x 2 ) = x α 1 x 1-α 2 on R 2 ++ , where α ∈ [0, 1]. 2. Cobb-Douglas function: f (x 1 , x 2 ) = x α 1 x β 2 on R 2 ++ , where α > 0, β > 0. 3. Leontief function: f (x 1 , x 2 ) = min( x 1 a , x 2 b ) on R 2 ++ , where a > 0, b > 0.
4. Constant elasticity of substitution (CES) function:

f (x 1 , x 2 ) = (ax r 1 + bx r 2 ) 1 r on R 2 ++
, where a > 0, b > 0. 12 12 Hint: Look at two cases r < 1 and r > 1.

5. The sum of squared residuals (in the multiple linear regression):

f (β 0 , β 1 , • • • , β k ) ≡ n i=1 y i -β 0 - k j=1 β j x i,j 2 on R k+1

Convex optimization in finite-dimensional spaces

This section uses Florenzano and Le [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].

Let f : S → R, where S ⊆ R n is a nonempty set.

• A point x ∈ S is a global maximum (respectively, global minimum) of f on S if f (y) ≤ f (x) (respectively, f (y) ≥ f (x)
) for all y ∈ S.

• A point x ∈ S is a local maximum (respectively, local minimum) of f on S if there exists r > 0 such that f (y) ≤ f (x) (respectively, f (y) ≥ f (x)) for all y ∈ S ∩ B(x, r).

• A point x ∈ S is a strict local maximum (respectively, strict local minimum) of f on S if there exists r > 0 such that f (y) < f (x) (respectively, f (y) > f (x)) for all y ∈ S ∩ B(x, r), y = x.

• A point x ∈ S is an unconstrained local maximum (respectively, unconstrained local minimum) of f on S if there exists r > 0 such that B(x, r) ⊆ S and f (y

) ≤ f (x) (respectively, f (y) ≥ f (x)) for all y ∈ B(x, r).
Remark 3. Assume that the set S is convex. Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.

Proof. Let x be a local minimum. It means that there exists r > 0 such that f (y) ≤ f (x) for all y ∈ S ∩ B(x, r).

We have to prove that f (y) ≥ f (x) for all y ∈ S. Suppose that there exists y ∈ S such that f (y) < f (x) Define z λ ≡ (1 -λ)x + λy. Since S is convex, we have that z λ ∈ S. Observe that

z λ = x + λ(y -x)
So, we can choose λ > 0 small enough so that z λ ∈ B(x, r).

We now look at f (z λ ). By the convexity of the function f , we have

f (z λ ) = f ((1 -λ)x + λy) ≤ (1 -λ)f (x) + λf (y) Since f (y) < f (x), we get that f (z λ ) < f (x)
. This is a contradiction to the fact that x is a local minimum. We have finished our proof.

We aim to give the necessary and sufficient conditions for a point to be an optimal solution to Problem (P ):

(P ) Minimize f 0 (x) under the constraints

   f i (x) ≤ 0, ∀i ∈ I g i (x) ≤ 0, ∀i ∈ J g i (x) = 0, ∀i ∈ K.
where f 0 : R n → R is a convex function, I, J and K are finite and possibly empty sets, for all i ∈ I, f i is convex, non-affine function from R n into R, for all i ∈ J ∪ K, g i is a non-null affine function.

The function f 0 is called the objective function. A feasible point is a point x ∈ R n that satisfies all the constraints. An optimal solution to (P ) or simply a solution to (P ) is a feasible point x, such that for all feasible point x, f 0 (x) ≥ f 0 (x).

Let I be a finite set, card(I) denotes the number of elements of I. Proof. See Florenzano and Le [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].

Separation theorems

H is a hyperplane in R n if there exists p ∈ R n , p = 0 and α ∈ R such that H = {x ∈ R n : p • x = α}.
Notice that the compactness in Proposition 10 is an important assumption.

Exercise 20.

Let A = {(x, y) : xy ≥ 1, x ≥ 0} and B = {(x, y) : x ≤ 0}.
Prove that A and B are non-empty, convex, closed and disjoint. Prove that X and Y cannot be strictly separated, i.e., there do not exist α, β, α < β and p ∈ R n , p = 0, such that

p • a ≤ α < β ≤ p • b, for all a ∈ A, all b ∈ B.
Note that A and B are not bounded in this example. Therefore, they are not compact.

The following result is very important.

Proposition 11. Let C be nonempty convex sets in R n and P

= (R m -× {0 R r }) where, m ≥ 0, r ≥ 0, m + r = n. Suppose that C ∩ (R m -× {0 R r }) = ∅. Then there exists p ∈ R n , p = 0 such that p • x ≤ 0 ≤ p • y, ∀x ∈ P, ∀y ∈ C
and there exists z ∈ C such that p • z > 0.

Proof. Applying Proposition 3.2.6 in Florenzano and Le [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].

Let us illustrate this result by considering a particular case: n = 2, m = 2, r = 0. In this case, P = {(x, y) : x ≤ 0, y ≤ 0}. A line p = (p 1 , p 2 ) is represented by an equation Figure 1: Monotonic convergence versus oscillatory convergence p 1 x + p 2 y = 0. Our result says that there is a line that separates P and C and there is a point z = (z 1 , z 2 ) ∈ C such that z is above the line p, i.e., p 1 z 1 + p 2 z 2 > 0.

When the set C is C 1 in the graphic, it is easy to geometrically check our result.

When the set C is C 2 ≡ {(x, y) : x > 0, y ≤ 0}, we can choose the line "x = 0", i.e., p = (p 1 , p 2 ) = (1, 0). It is easy to see that this line separates P and C 2 . Moreover, for any z ∈ C 2 , we have p 1 z 1 + p 2 z 2 = z 1 > 0.

Necessary and sufficient condition for optimality

Lemma 5. (i) Let f be a linear function on R n (in the sense that f

(x) = Ax = A 1 x 1 + • • • + A n x n ). If f (x) ≥ 0 for any x then f = 0.
(ii) Hence, if g is an affine function (i.e., g(x) = Ax + B) which satisfies g(x) ≥ 0 for any x, then g equals a nonnegative constant.

Proof. (i) Suppose f = 0. There exists x such that f (x) > 0. But we have a contradiction 0 > -f (x) = f (-x) ≥ 0. Hence f = 0.

(ii) We can write ∀x, g(x) = f (x) + b where f is linear and b is a real constant. Let x ∈ R n . We have f (x)+b ≥ 0. Let λ > 0. We also have λf (x)+b = f (λx)+b ≥ 0, ∀λ > 0. This is equivalent to f (x) + b λ ≥ 0 for all λ > 0. Let λ → +∞. We get f (x) ≥ 0. But x has been arbitrarily chosen. That means f (x) ≥ 0, ∀x. Thus, f = 0 and g(x) = b, ∀x. And b ≥ 0. Lemma 6. Let I, J and K be finite possibly empty sets in N, and for all i ∈ I, f i is a convex, non-affine function from R n into R, and for all i ∈ J ∪ K, g i is non-null affine function. Assume there exists x 0 such that

g i (x 0 ) ≤ 0, ∀i ∈ J g i (x 0 ) = 0, ∀i ∈ K. If the system:    f i (x) < 0, ∀i ∈ I g i (x) ≤ 0, ∀i ∈ J g i (x) = 0, ∀i ∈ K.
has no solution, then there exist nonnegative real scalars (λ i ) i∈I , (µ i ) i∈J , and real numbers (µ i ) i∈K , at least one of the (λ i ) i∈I is not zero, which verify:

i∈I λ i f i (x) + i∈J µ i g i (x) + i∈K µ i g i (x) ≥ 0, ∀x.
Proof. Let p = card(I), q = card(J), r = card(K), and

Z = (z i ) i∈I∪J∪K ∈ R p+q+r ∃x, ∀i ∈ I, f i (x) < z i ∀i ∈ J ∪ K, g i (x) = z i
The set Z is convex, nonempty and

Z ∩ (R p+q -× {0 R r }) = ∅.
From Proposition 11 there exist real scalars (λ i ) i∈I , (µ i ) i∈J∪K , all of them not being equal to zero, which verify:

i∈I λ i z i + i∈J∪K µ i z i ≥ i∈I λ i ζ i + i∈J µ i ζ i , ∀z ∈ Z, ∀ζ ∈ R p+q - and there exists z ∈ Z such that i∈I λ i z i + i∈J∪K µ i z i > 0.
If for some i, λ i < 0, then letting z i tend to +∞, we get a contradiction. Thus

λ i ≥ 0, ∀i ∈ I.
If for some i ∈ J, one has µ i < 0, then letting ζ i tend to -∞, we have another contradiction. Hence, µ i ≥ 0, ∀i ∈ J.

Let ε > 0 and x ∈ R n . Define z ∈ Z by

z i = f i (x) + ε, ∀i ∈ I, z i = g i (x), ∀i ∈ J ∪ K.
We have

i∈I λ i f i (x) + i∈J∪K µ i g i (x) + ε i∈I λ i ≥ 0. Let ε tend to zero. We obtain that i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≥ 0, ∀x ∈ R n . ZZ
To end the proof, it remains to show that at least one of the (λ i ) i∈I is strictly positive. Assume the contrary. We then have i∈J∪K µ i g i (x) ≥ 0, ∀x ∈ R n and hence i∈J∪K µ i g i (x 0 ) = 0. The affine function i∈J∪K µ i g i has a minimum in R n . From Lemma 5, it must be equal to zero. But since i∈I λ i z i + i∈J∪K µ i z i > 0 for some z ∈ Z, and since all the (λ i ) i∈I are equal to zero, there exists x such that i∈J∪K µ i g i (x) > 0. That contradicts that i∈J∪K µ i g i is equal to zero. Definition 14. The Problem (P ) satisfies Slater Condition (S) if there exists x 0 such that:

f i (x 0 ) < 0, ∀i ∈ I, g i (x 0 ) ≤ 0, ∀i ∈ J, g i (x 0 ) = 0, ∀i ∈ K.
Proposition 12. Consider Problem (P ). Assume that (P ) satisfies Slater Condition (S). If (P ) has an optimal solution x, then there exists scalars (λ i ) i∈I , (µ i ) i∈J∪K such that:

(i) ∀i ∈ I, λ i ≥ 0, λ i f i (x) = 0, ∀i ∈ J, µ i ≥ 0, µ i g i (x) = 0. (ii) f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≤ f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x)
for any x.

(iii) If f 0 , (f i ) i∈I , (g i ) i∈J∪K are differentiable, then 0 = Df 0 (x) + i∈I λ i Df i (x) + i∈J∪K µ i Dg i (x)
Proof. Let α = f 0 (x). Then the following system has no solution (why? Readers should explain this point).

       f 0 (x) < α, f i (x) < 0, ∀i ∈ I, g i (x) ≤ 0, ∀i ∈ J, g i (x) = 0, ∀i ∈ K.
The Slater condition allows us to apply Lemma 6. According to Lemma 6, there exist λ 0 , (λ i ) i∈I , (µ i ) i∈J∪K such that λ 0 ≥ 0, λ i ≥ 0, ∀i ∈ I, µ i ≥ 0, ∀i ∈ J, at least one of the λ 0 , (λ i ) i∈I is strictly positive, and

λ 0 (f 0 (x) -α) + i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≥ 0, ∀x. (10)
We claim that λ 0 > 0. Indeed, if λ 0 = 0, then ∀x, i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≥ 0. Moreover, since there exists at least one i ∈ I such that λ i > 0, we deduce i∈I λ i f i (x 0 ) + i∈J∪K µ i g i (x 0 ) < 0, a contradiction. Thus λ 0 > 0 and one can, without loss of generality, suppose λ 0 = 1. Define the convex function h by

h(x) = f 0 (x) + i∈I (λ i f i )(x) + i∈J∪K µ i g i (x), ∀x ∈ R n .
The inequality (10) can be equivalently rewritten as

h(x) ≥ α ∀x. But h(x) -α = i∈I λ i f i (x)+ i∈J∪K µ i g i (x) ≤ 0. Hence, α = h(x). Thus i∈I λ i f i (x)+ i∈J∪K µ i g i (x) = 0 and since x is feasible, one has ∀i ∈ I, λ i f i (x) = 0 and ∀i ∈ J, µ i g i (x) = 0. We have proved Assertion (i). Now, h(x) ≥ α ∀x is equivalent to f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≤ f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x)
for any x. We have proved assertion (ii). Statement (iii) is obvious when f 0 , (f i ) i∈I , (g i ) i∈J∪K are differentiable. The proof is now complete.

Definition 15. The real numbers (λ i ) i∈I , (µ i ) i∈J∪K are called Lagrange parameters, Lagrange multipliers or Kuhn-Tucker coefficients or more simply multipliers of Problem (P ).

Definition 16. We say that x, (λ i ) i∈I , (µ i ) i∈J∪K satisfy Kuhn-Tucker Conditions of Problem (P ) if they satisfy Conditions (i), (ii) and (iii).

(i) ∀i ∈ I, λ i ≥ 0, f i (x) ≤ 0, λ i f i (x) = 0, ∀i ∈ J, µ i ≥ 0, g i (x) ≤ 0, µ i g i (x) = 0. (ii) ∀i ∈ K, g i (x) = 0. (iii) f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x) ≤ f 0 (x) + i∈I λ i f i (x) + i∈J∪K µ i g i (x) for any x.
Conditions (i), (ii) and (iii) are called Kuhn-Tucker Conditions for Problem (P ).

Definition 17. The Lagrangian of Problem (P ) is the function L : R p + ×R q + ×R r-q ×R n → R defined by: for all (λ, µ, x) = ((

λ i ) i∈I , (µ i ) i∈J , (µ i ) i∈K , x), L(λ, µ, x) = f 0 (x) + i∈I λ i f i (x) + i∈J µ i g i (x) + i∈K µ i g i (x).
where p = card(I), q = card(J) and r = card(J ∪ K).

Proposition 13. Let x, (λ i ) i∈I , (µ i ) i∈J∪K verify Kuhn-Tucker Conditions for Problem (P ). Then x is a solution to (P ).

Proof. Let ∀x ∈ R n , h(x) = f 0 (x) + i∈I (λ i f i )(x) + i∈J∪K µ i g i (x). Condition (iii) is equivalent to h(x) ≥ h(x), ∀x.
Combining conditions (i) and (ii), we get h(x) ≥ f (x), ∀x. Let x satisfy the contraints of Problem (P ). We obtain f 0 (x) ≥ f 0 (x), ∀x.

Theorem 17 (Kuhn-Tucker (minimization problem)). Assume that Slater Condition is satisfied for Problem (P ). Then x is a solution to (P ) if, and only if, there exists coefficients (λ i ) i∈I , (µ i ) i∈J∪K which, together with x, satisfy Kuhn-Tucker Conditions for Problem (P ).

Proof. The statement follows from Proposition 12 and Proposition 13.

As particular case of Proposition 12, we get the following result when the problem is without convex constraints.

Corollary 4. Consider Problem (P ) without convex constraints, i.e. min f 0 (x) under the constraints

g i (x) ≤ 0, ∀i ∈ J g i (x) = 0, ∀i ∈ K.
where f 0 : R n → R is convex, and for all i ∈ J ∪ K, g i is affine.

For this problem, Slater Condition is: ∃x 0 such that g i (x 0 ) ≤ 0, ∀i ∈ J, and g i (x 0 ) = 0, ∀i ∈ K.

The problem (P ) has an optimal solution x if and only if there exist scalars

(µ i ) i∈J∪K verifying: (i) ∀i ∈ J, µ i ≥ 0, µ i g i (x) = 0, (ii) f 0 (x) + i∈J∪K µ i g i (x) ≤ f 0 (x) + i∈J∪K µ i g i (x) for any x Proof. Obvious Remark 4. (i)
The Slater condition is very important even in the one-dimensional case. Consider the following example:

min{f (x) = x | x 2 ≤ 0}.
The problem has a unique solution x = 0. The Slater condition is not satisfied. There exists no λ ≥ 0 such that 0 = x + λx 2 ≤ x + λx for any x ∈ R.

(ii) It is important to notice that Slater Condition is not necessary to obtain Kuhn-Tucker Conditions. In the previous example, Slater Condition is not satisfied and there is no Kuhn-Tucker coefficient. Now replace this problem by an equivalent problem which is min{f (x) = x | g(x) = |x| ≤ 0}. As before, Slater Condition does not hold. The unique solution is always x = 0. Let λ = 1, we have successively g(0) = 0, λg(0) = 0 and 0 = f (0) + λg(0) ≤ f (x) + λg(x) = x + |x|, for any x ∈ R. In other words, Kuhn-Tucker Conditions hold. (iii) In the previous example, one can check that Kuhn-Tucker Conditions are sufficient for 0 to be a solution. This result is quite general as it will be proved in the next proposition.

Maximization problem

In many economic models, we need to maximize a function subject to several constraints (physical constraint, financial constraint, legal constraint, ...). We present here the result concerning the following maximization problem (P ):

(P ) Maximize f 0 (x) under the constraints    f i (x) ≤ 0, ∀i ∈ I g i (x) ≤ 0, ∀i ∈ J g i (x) = 0, ∀i ∈ K.
where f 0 : R n → R is a concave function, I, J and K are finite and possibly empty sets, for all i ∈ I, f i is convex, non-affine function from R n into R, for all i ∈ J ∪ K, g i is a non-null affine function.

Definition 18. The Lagrangian of Problem (P ) is the function L : R p + ×R q + ×R r-q ×R n → R defined by: for all (λ, µ, x) = ((

λ i ) i∈I , (µ i ) i∈J , (µ i ) i∈K , x), L(λ, µ, x) = f 0 (x) - i∈I λ i f i (x) - i∈J µ i g i (x) - i∈K µ i g i (x).
where p = card(I), q = card(J) and r = card(J ∪ K).

Theorem 18 (Kuhn-Tucker (maximization problem)). Assume that functions f i , g i are differentiable.

Assume that Slater Condition is satisfied for Problem (P ). Then x is a solution to (P ) if, and only if, there exists coefficients (λ i ) i∈I , (µ i ) i∈J∪K which, together with x, satisfy Kuhn-Tucker Conditions for Problem (P ), i.e.,

∀i ∈ I, λ

i ≥ 0, λ i f i (x) = 0, ∀i ∈ J, µ i ≥ 0, µ i g i (x) = 0.
2.

f 0 (x) - i∈I λ i f i (x) - i∈J∪K µ i g i (x) ≥ f 0 (x) - i∈I λ i f i (x) - i∈J∪K µ i g i (x) (11)
for any x.

If f 0 , (f i ) i∈I , (g i ) i∈J∪K are differentiable, then condition ( 11) is replaced by

Df 0 (x) = i∈I λ i Df i (x) + i∈J∪K µ i Dg i (x) (12)
Proof. This is a direct consequence of Theorem 17.

Applications

Theorems 17 and 18 have many applications in economics, econometrics and finance. In the following, we present some applications.

Consumer maximization problem

The consumer maximizes her utility by choosing allocation (x 1 , . . . , x n ) of commodity max

(x 1 ,...,xn) U (x 1 , . . . , x n ) subject to: p 1 x 1 + • • • p n x n ≤ w x 1 ≥ 0, . . . , x n ≥ 0
where p i is price of commodity i and w is the consumer's income. (p i ) and w are endogenously given.

Assume that the function U : R n + → R is continuously differentiable. Assume that p i > 0 ∀i, w > 0. Assume that U is concave. Assume that ∂U ∂x i (x) > 0 ∀i, ∀x. We consider a simple example Example 7. Consider n = 2 and u(x) = x α 1 1 x α 2 2 where α i > 0. We want to solve the following problem max

(x 1 ,x 2 ) x α 1 1 x α 2 2 subject to: p 1 x 1 + p 2 x 2 ≤ w x 1 ≥ 0, x 2 ≥ 0
where p i > 0 is price of commodity i and w > 0 is the consumer's income. Notice that our objective function is quasiconcave but not concave. We cannot directly apply Theorem 18. We proceed as follows.

If (a 1 , a 2 ) is a solution to the above problem, then a 1 > 0, a 2 > 0 (why?). This implies that (a 1 , a 2 ) is a solution of the following problem

(P e ) max (x 1 ,x 2 ) f (x 1 , x 2 ) = ln(x α 1 1 x α 2 2 ) = α 1 ln(x 1 ) + α 2 ln(x 2 ) subject to: p 1 x 1 + p 2 x 2 ≤ w x 1 ≥ 0, x 2 ≥ 0
The objective function is concave now. It is differentiable on R 2 ++ . Applying Theorem 18, there exist non-negative multipliers λ 1 , λ 2 , λ such that

∂f ∂x 1 (a 1 , a 2 ) = -λ 1 + p 1 λ ∂f ∂x 2 (a 1 , a 2 ) = -λ 2 + p 2 λ λ 1 x 1 = 0, λ 2 x 2 = 0, λ(p 1 x 1 + p 2 x 2 -w) = 0
Since a 1 > 0, a 2 > 0, we have λ 1 = λ 2 = 0. From this, we find that p 1 a 1 α 1 = p 2 a 2 α 2 . Observe that ∂f ∂x 1 (a 1 , a 2 ) = p 1 λ which implies that λ > 0. Thus, we have p 1 a 1 + p 2 a 2 = w.13 Therefore, we get that

p 1 a 1 = α 1 α 1 + α 2 w, p 2 a 2 = α 2 α 1 + α 2 w.
We have proved that if (a 1 , a 2 ) is a solution, then p 1 a 1 = α 1 α 1 +α 2 w, p 2 a 2 = α 2 α 1 +α 2 w. Lastly, we see that such a pair (a 1 , a 2 ) with the above multipliers satisfy the Kuhn-Tucker conditions for the problem (P e ). We conclude that (

α 1 α 1 +α 2 w p 1 , α 2 α 1 +α 2 w p 2 )
+ → R + defined by u(c 1 , c 2 ) = a 1 c α 1 α + a 2 c α 2 α where a 1 > 0, a 2 > 0, α ∈ (0, 1).
Let w > 0, p 1 > 0, p 2 > 0.

We want to solve the following problem:

(P ) : Maximize u(c 1 , c 2 ) under the constraints:

p 1 c 1 + p 2 c 2 ≤ w c 1 ≥ 0, c 2 ≥ 0 1. Prove that the set B ≡ {(c 1 , c 2 ) : p 1 c 1 + p 2 c 2 ≤ w, c 1 ≥ 0, c 2 ≥ 0} is convex, compact.
2. Prove that the problem (P) has a solution.

3. Prove that the function u is strictly concave on R 2 + .

Prove that: if

(c 1 , c 2 ) is a solution, then p 1 c 1 + p 2 c 2 = w. 5. Assume that (c 1 , c 2 ) is a solution and c 1 > 0, c 2 > 0.
(a) Is the Slater condition satisfied and why? If this is the case, write the Kuhn-Tucker conditions.

(b) Find this solution (c 1 , c 2 ).

(c) When p 1 increases, how does the solution (c 1 , c 2 ) change? Provide an economic interpretation.

6. We want to prove that the solution found in Question 5 is the unique solution of the problem (P). )-u 0

x > 0 for x > 0 small enough.

(d) Prove that c 1 cannot be zero.

(e) Prove that c 1 > 0, c2 > 0 at optimum and hence the solution (c 1 , c 2 ) in Question 5 is the unique solution of the problem (P).

7. We now use another method to prove that the solution found in Question 5 is the unique solution of the problem (P).

(a) Assume that (c 1 , c 2 ) is a solution of the problem (P) and that (c 1 , c 2 ) = (c 1 , c 2 ).

Prove that u( Compactness: we see that

c 1 +c 1 2 , c 2 +c 2 2 ) > u(c 1 , c 2 ). (
p i c i ≤ w ∀i = 1, 2. Since p i > 0, we have c i ∈ [0, w/p i ].
So, B is bounded. It is easy to see that B is closed. Therefore, B is compact.

2. The function u is continuous and B is compact. So, the problem (P ) has a solution.

The function a i c α i

α is strictly concave for any i = 1, 2. So, the function u is strictly concave.

Remark: We can also compute the Hessian matrix and then prove that u is strictly concave.

4.

It is easy to see that, if (c 1 , c 2 ) is a solution, then p 1 c 1 + p 2 c 2 = w. Otherwise, we can improved a little bit c 1 or c 2 to get a strictly higher utility.

Assume that (c 1 , c

2 ) is a solution and c 1 > 0, c 2 > 0.

(a) The Problem (P ) satisfies Slater Condition (S) if there exists (c 1 , c 2 ) such that:

p 1 c 1 + p 2 c 2 ≤ w -c 1 ≤ 0 -c 2 ≤ 0.
It is easy to see that Slater condition is satisfied. So, we can write the first-order conditions

a 1 c α-1 1 = λp 1 a 2 c α-1 2 = λp 2 (b)
From the first-order condition, we can compute c 1 and c 2 as functions of λ.

Then, we use p 1 c 1 + p 2 c 2 = w to get an equation of λ. Solving this equation, we find λ and then compute c 1 , c 2 :

c 1 = ( a 1 p 1 ) 1 1-α a 1 1-α 1 p α 1-α 1 + a 1 1-α 2 p α 1-α 2 , c 2 = ( a 2 p 2 ) 1 1-α a 1 1-α 1 p α 1-α 1 + a 1 1-α 2 p α 1-α 2
(c) When p 1 increases, we see that the optimal value c 1 decreases (this is a version of "Law of demand"). We also observe that c 2 increases (this is a substitution effect).

6. If c 1 = 0, we have p 2 c 2 = w and hence c 2 = w/p 2 . We have u 0 = u(0, w/p 2 ) = a 2 α ( w p 2 ) α It is easy to see that (x, w-p 1 x p 2 ) is in the set B for any x satisfying ∈ [0, w/p 1 ]. We have

u(x, w-p 1 x p 2 ) -u 0 x = a 1 x α α + a 2 ( w-p 1 x p 2 ) α α -a 2 α ( w p 2 ) α x = a 1 x α-1 α + a 2 ( w-p 1 x p 2 ) α α -a 2 α ( w p 2 ) α x
The first terms converges to infinity while the second converges to a 2 p 1 p 2 ( w p 2 ) α-1 when x goes to zero (because α -1 < 0). )-u 0

x > 0 for x > 0 small enough.

We have seen that u(x, w-p 1 x p 2 ) > u 0 for x > 0 small enough. So, the allocation (0, w/p 2 ) cannot be optimal. It means that c 1 cannot be zero. By using the same argument, c 2 cannot be zero. So, we have c 1 > 0 and c 2 > 0 at optimal. 7. We now use another method to prove that the solution found in Question 5 is the unique solution of the problem (P).

Assume that (c 1 , c 2 ) is a solution of the problem (P) and that (c 1 , c 2 ) = (c 1 , c 2 ). Since u is strictly concave, we have

u( c 1 + c 1 2 , c 2 + c 2 2 ) > 1 2 u(c 1 , c 2 ) + 1 2 u(c 1 , c 2 ) ≥ 1 2 u(c 1 , c 2 ) + 1 2 u(c 1 , c 2 ) = u(c 1 , c 2 ).
So, (

c 1 +c 1 2 , c 2 +c 2
2 ) is in the set B and u(

c 1 +c 1 2 , c 2 +c 2
2 ) is strictly higher that the maximum value u(c 1 , c 2 ). This is a contradiction. So, we have proved the uniqueness.

Exercise 22. (1) For the following utility functions, check whether there are continuous, monotomic, strictly monotonic, concave, quasi-concave.

Leontief preference: u

(x) = min{α 1 x 1 , α 2 x 2 }, α h > 0, h = 1, 2 u(x) = c 1 x 1 + c 2 x 2 , c h > 0 u(x) = x α 1 1 x α 2 2 . . . x αn n , α h > 0 u(x) = (x α 1 + x α 2 ) 1 α , α ∈ (0, 1) u(x) = x 1 (1 + √ x 2 ) u(x) = x 1 + √ x 2 ) u(x) = -e -α 1 x 1 -e -α 2 x 2 , α h > 0.
(2) For each of above functions, find the solution of the following maximization problem

max (x 1 ,x 2 ) U (x 1 , x 2 ) subject to: p 1 x 1 + p 2 x 2 ≤ w x 1 ≥ 0, x 2 ≥ 0
where p i > 0 is price of commodity i and w > 0 is the consumer's income.

Proof. Let consider the Leontief utility function.

u(x) = min{α 1 x 1 , α 2 x 2 }, α h > 0, h = 1, 2.
This function is continuous. It is increasing in each component but it may not be strictly increasing. Indeed, if min{α 1 x 1 , α 2 x 2 } = α 1 x 1 , then we have u(x 1 , x 2 ) = u(x 1 , x 2 ) for all x 2 > x 2 .

Notice that this function is not differentiable at the point (x 1 , x 2 ) satisfying α 1 x 1 = α 2 x 2 . So, we cannot use our tests based on derivatives to verify the (quasi)concavity of u. We can prove the concavity of this function by using definition. See also Proposition 5.

Exercise 23. In a two-good economy. The consumption set of a consumer is

X = {x ∈ R 2 + : x 1 + x 2 ≥ 1}. Let u(x 1 , x 2 ) = x 1 + 4x 2 . Let the price (p 1 , p 2 ) = (1, 2).
1. Find the solution of the following maximization problem

max (x 1 ,...,xn) U (x 1 , x 2 ) subject to: x ∈ X p 1 x 1 + p 2 x 2 ≤ w
where w > 0 is the consumer's income.

2. The solution (x 1 , x 2 ) depends on w. Does the demand of the commodity 1 (i.e., x(1)) increase with the income w?

A two-period optimal growth model

An agent living for two periods (present and future, represented by 0 and 1) wants to choose consumption allocation (c 0 , c 1 ) and physical capital k 1 to maximize her(his) utility U (c 0 , c 1 ) max

(c 0 ,c 1 ,k 1 ) U (c 0 , c 1 ) (13) subject to: c 1 ≥ 0, c 1 ≥ 0, k 1 ≥ 0 (14) c 0 + k 1 ≤ w 0 (15) c 1 ≤ w 1 + F (k 1 ) ( 16
)
where w 0 , w 1 are given and strictly positive. The function F is assumed to be strictly increasing, concave, continuously differentiable and F (0) = 0.

We would like to solve this problem to understand the optimal value of (c 0 , c 1 , k 1 ). Notice that in this setup, k t can be also interpreted as investment.

First, it is easy to see that the Slater condition is satisfied. So, we can write the Lagrangian

L = U (c 0 , c 1 ) + µ 0 c 0 + µ 1 c 1 + µ k k 1 + λ 0 (w 0 -c 0 -k 1 ) + λ 1 (w 1 + F (k 1 ) -c 1 ) (17) Assume that U (c 0 , c 1 ) = u(c 0 ) + βu(c 1 )
where the function u is strictly concave, increasing, continuously differentiable, u (0) = ∞. Parameter β represents the rate of time preference. Since u (0) = ∞, we have c 0 > 0, c 1 > 0 at optimum (@reader: why?), which implies that µ 0 = µ 1 = 0. Therefore, the first-order conditions become

∂U (c 0 , c 1 ) ∂c 0 -λ 0 ⇔ u (c 0 ) = λ 0 ∂U (c 0 , c 1 ) ∂c 1 -λ 1 ⇔ βu (c 1 ) = λ 1 µ k -λ 0 + λ 1 F (k 1 ) = 0 ⇔ λ 0 = λ 1 F (k 1 ) + µ k µ k k 1 = 0, µ k ≥ 0
So, we obtain that u (c 0 ) = βF (k 1 )u (c 1 ) + µ k . At optimum, we must have c 0 + k 1 = w 0 and c 1 = w 1 + F (k 1 ). Thus, we get that

u (w 0 -k 1 ) = βF (k 1 )u (w 1 + F (k 1 )) + µ k (18)
Notice that at this stage, we do not require that F (0) = ∞.

There are two cases.

1. k 1 > 0. In this case, we have µ k = 0 and hence k 1 is determined by

H(k 1 ) ≡ u (w 0 -k 1 ) -βF (k 1 )u (w 1 + F (k 1 )) = 0 (19)
The function H is strictly increasing in k 1 .

H(0) = u (w 0 ) -βF (0)u (w 1 ) while H(w 0 ) = ∞ because u (0) = ∞.
So, the existence of a strictly positive solution k 1 requires that u (w 0 ) -βF (0)u (w 1 ) < 0.

It means that the productivity F (0), the rate of time preference β, the endowment at initial date w 0 are high and the endowment at date 1 is low.

2. k 1 = 0. Condition (18) becomes u (w 0 ) -βF (0)u (w 1 ) ≤ 0.

To sum up, we obtain the following result:

Proposition 14. Assume that above conditions hold. Assume also that u (0) = ∞. The optimal choice k 1 is strictly positive if and only if

u (w 0 ) -βF (0)u (w 1 ) < 0
In such a case, k 1 is the unique solution to the equation H(k 1 ) = 0.

It is useful to consider some particular cases.

1. Assume that u(c) = ln(c), F (k) = Ak α where α ∈ (0, 1), and w 1 = 0. In this case,

F (0) = ∞.
We have

1 w 0 -k 1 = βαAk α-1 1 1 w 1 + Ak α 1 = βαAk α-1 1 1 Ak α 1 (20) ⇔ k 1 = αβ 1 + αβ w 0 (21)
The investment k 1 is increasing in the initial endowment w 0 and the rate of time preference.

2. Assume that u(c) = ln(c), F (k) = Ak, w 1 > 0. We have that (a) If w 1 < βAw 0 , then k 1 is strictly positive and we can compute that k 1 = βAw 0 -w 1 A(1+β) . The investment is increasing in the productivity A, the rate of time preference β, the initial endowment but decreasing in the endowment in the future.

(b) If w 1 ≥ βAw 0 , then k 1 = 0. The intuition: when the productivity, the initial endowment, the rate of time preference are low, but the endowment in the future is high, we do not need to save/invest.

Cost minimization problem

Let prices be strictly positive p 1 > 0, . . . , p n > 0. The firm minimizes its cost by choosing allocation (x 1 , . . . , x n ) of inputs such that the production F (x 1 , . . . , x n ) is not less than a given level y.

min

(x 1 ,...,xn)

p 1 x 1 + • • • + p n x n (22) subject to: x 1 ≥ 0, x n ≥ 0 (23) F (x 1 , . . . , x n ) ≥ y (24) Example 8. Assume that n = 2, F (x 1 , x 2 ) = Ax a 1 1 x a 2
2 with a 1 , a 2 > 0 and a 1 + a 2 ≤ 1. Find the solution of the cost minimization problem.

Solution. This is a minimization problem. The objective function is linear and hence convex.

We rewrite F (x 1 , x 2 ) ≥ y as y -F (x 1 , x 2 ) ≤ 0. Since the function F is concave, the function -F is convex. We can easily check that the Slater condition is satisfied. So, we can apply Theorem 17. The Lagrangian is

L = p 1 x 1 + p 2 x 2 + λ y -Ax a 1 1 x a 2 2 + µ 1 (-x 1 ) + µ 2 (-x 2 )
The first order conditions are

∂L ∂x 1 = p 1 -λa 1 Ax a 1 -1 1 x a 2 2 -µ 1 = 0 ∂L ∂x 2 = p 2 -λa 2 Ax a 1 1 x b 1 -1 2 -µ 2 = 0 µ 1 x 1 = 0, µ 2 x 2 = 0 Since F (x 1 , x 2 ) = Ax a 1 1 x a 2 2 ≥ y > 0, we have x 1 > 0, x 2 > 0. Thus, µ 1 = µ 2 = 0.
According to the FOCs, we have

p 1 p 2 = λa 1 Ax a 1 -1 1 x a 2 2 λa 2 Ax a 1 1 x a 2 -1 2 = a 1 x 2 a 2 x 1 ⇒ x 1 = a 1 a 2 p 2 p 1 x 2
At optimum, we must have y = F (x 1 , x 2 ), and hence,

y = Ax a 1 1 x a 2 2 = A a 1 a 2 p 2 p 1 x 2 a 1 x a 2 2 = A a 1 a 2 p 2 p 1 a 1 x a 1 +a 2 2
Therefore, we find that

x 2 = A -1 a 1 +a 2 a 2 a 1 p 1 p 2 a 1 a 1 +a 2 y 1 a 1 +a 2 x 1 = A -1 a 1 +a 2 a 1 a 2 p 2 p 1 a 1 a 1 +a 2 y 1 a 1 +a 2
The optimal quantity of input 1 is increasing in the output y and the price of input 2 but decreasing in the price of input 1 and the productivity A.

We can also compute the cost function

Cost = p 1 x 1 + p 2 x 2 = a 1 a 2 p 2 x 2 + p 2 x 2 = a 1 + a 2 a 1 p 2 x 2 = a 1 + a 2 a 2 p 2 A -1 a 1 +a 2 a 2 a 1 p 1 p 2 a 1 a 1 +a 2 y 1 a 1 +a 2 = a 1 + a 2 a a 2 a 1 +a 2 2 a a 1 a 1 +a 2 1 A -1 a 1 +a 2 p a 1 a 1 +a 2 1 p a 2 a 1 +a 2 2 y 1 a 1 +a 2
The cost is increasing in input prices p 1 , p 2 , the output y, but decreasing in the productivity A.

Proposition 15 (Shephard's lemma). Consider the cost minimization problem. Assume that F is in C 2 (i.e., twice continuously differentiable). Assume that F is strictly increasing in each component and concave. Let x * (y, p) denote the solution of the problem and C(y, p) the optimal value (cost function). Suppose that p i > 0 and x * i > 0 ∀i. Prove that

x * i (y, p) = ∂C(y, p) ∂p i ∀i (25) ∂x * i ∂p j = ∂x * j ∂p i ∀i, j. ( 26
)
Proof. The Lagrangian is

L = i p i x i + λ y -F (x 1 , . . . , x n ) + i µ i (-x i )
The first order conditions imply that, for any i,

∂L ∂x i = p i -λ ∂F ∂x i (x * 1 , . . . , x * n ) -µ i = 0 x * i µ i = 0
Under assumption x * i > 0, we have µ i = 0. So, we get that

p i = λ ∂F ∂x i (x * 1 , . . . , x * n ), ∀i
The cost function is C(y, p) = i p i x * i . Thus, we can compute

∂C(y, p) ∂p i = x * i + n t=1 p t ∂x * t ∂p i (27)
By taking the derivative with respect to p i of both sides of the equation

F (x * 1 , . . . , x * n ) = y, we have n t=1 ∂F ∂x t (x * 1 , . . . , x * n ) ∂x * t ∂p i = 0 Since ∂F ∂xt (x * 1 , . . . , x * n ) = p t /λ, we get that n t=1 p t ∂x * t ∂p i = 0.
So, by combining with ( 27), we obtain ∂C(y,p)

∂p i = x * i .
From this, we compute

∂x * i ∂p j = ∂ 2 C(y, p) ∂p j ∂p i ∂x * j ∂p i = ∂ 2 C(y, p) ∂p i ∂p j
Since ∂ 2 C(y,p) ∂p j ∂p i = ∂ 2 C(y,p) ∂p i ∂p j , we obtain (26).

Profit maximization problem

Let prices of inputs be strictly positive p 1 > 0, . . . , p n > 0. Denote p be the price of output.

The firm maximizes its profit by choosing allocation (x 1 , . . . , x n ) of inputs:

max (x 1 ,...,xn) pF (x 1 , . . . , x n ) -(p 1 x 1 + • • • + p n x n ) (28) subject to: x 1 ≥ 0, x n ≥ 0 (29)
Assume that the function

F : R n + → R is continuously differentiable. Assume that F is concave. Assume that F is increasing in each component. ∂F ∂x i (x) > 0 ∀i, ∀x.
In the case of two inputs, the problem becomes max

(x 1 ,x 2 ) pF (x 1 , x 2 ) -(p 1 x 1 + p 2 x 2 ) ( 30
)
subject to:

x 1 ≥ 0, x 2 ≥ 0 (31)
Exercise 24. Find the solution and compute the maximum profit of the profit maximization problem for the following cases:

1. n = 1, F (x) = ax where a > 0. 2. n = 1, f (x) = Ax α where A > 0, α ∈ (0, 1). 3. n = 2, F (x 1 , x 2 ) = Ax α 1 1 x α 2 2 where A > 0, α 1 > 0, α 2 > 0, α 1 + α 2 ≤ 1. 4. n = 2, f (x 1 , x 2 ) = ax 1 + bx 2
, where a, b > 0.

5. n = 2, f (x 1 , x 2 ) = min(ax 1 , bx 2 ) where a, b > 0.

6. f (x 1 , x 2 ) = Ax r 1 + Bx r 2 )
1 r , where r < 1, r = 0.

7. n = 3, F (x 1 , x 2 , x 3 ) = Ax α 1 1 x α 2 2 x α 3 3 where A > 0, α 1 > 0, α 2 > 0, α 3 > 0, α 1 +α 2 +α 3 ≤ 1. When α 1 + α 2 + α 3 = 1, compute the cost share p i x i i p i x i . Linear production functions. Let us consider the case f (x 1 , x 2 ) = ax 1 + bx 2 , where a, b > 0. Then pf (x 1 , x 2 )-p 1 x 1 -p 2 x 2 = p(ax 1 +bx 2 )-p 1 x 1 -p 2 x 2 The profit maximization problem becomes max (x 1 , xn) (pa -p 1 )x 1 + (pb -p 2 )x 2 subject to: x 1 ≥ 0, x 2 ≥ 0 Suppose that (x 1 , x 2 ) is a solution. It is easy to see that • If pa = p 1 , then x 1 takes any value. • If pa > p 1 , then x 1 = ∞. • If pa < p 1 , then x 1 = 0.
Leontief production functions. We now consider f (x 1 , x 2 ) = min(ax 1 , bx 2 ) where a, b > 0. The profit maximization problem becomes max

(x 1 , xn) pmin(ax 1 , bx 2 ) -p 1 x 1 -p 2 x 2 subject to: x 1 ≥ 0, x 2 ≥ 0
The objective function is not differentiable. So, we cannot apply the Kuhn-Tucker theorem. We will prove that: if (x 1 , x 2 ) is a solution, then ax 1 = bx 2 . Indeed, if, ax 1 > bx 2 , then min(ax 1 , bx 2 ) = bx 2 . We can introduce x 1 = x 1 -where ax 1 > bx 2 . Then, the new profit π(x 1 , x 2 ) is strictly higher than π(x 1 , x 2 ), a contradiction. Hence, we cannot have ax 1 > bx 2 . Similarly, we cannot have ax 1 < bx 2 . So, ax 1 = bx 2 . The remaining is simple.

Cobb-Douglas production function (the case of one variable). The problem becomes max

x≥0 pAx α -p 1 x
where α ∈ (0, 1) while p, p 1 are the prices of output, input respectively.

First, a solution x must be strictly positive x > 0 (why?). 14 The FOC implies that we have αpA(x) α-1 = p 1 at optimal. So, the solution is

x = ( αpA p 1 ) 1 1-α .
So, the optimal choice of input of the firm is increasing in the productivity A and the output price p while decreasing in the input price p 1 .

Cobb-Douglas production function (the case of two variables). The problem becomes max

x 1 ≥0,x 2 ≥0 pAx α 1 1 x α 2 2 -p 1 x 1 -p 2 x 2 where α 1 + α 2 ≤ 1. Denote Π ≡ max x 1 ≥0,x 2 ≥0 pAx α 1 1 x α 2 2 -p 1 x 1 -p 2 x 2 . Observe that Π ≥ 0. Moreover, at optimum, if x 1 = 0 or x 2 = 0, then x 1 = x 2 = 0. 1. Assume that α 1 + α 2 = 1. Let (x 1 , x 2 ) be a solution. If x 1 = 0 or x 2 = 0, then Π = 0. If x 1 > 0, x 2 > 0.
We have the FOCs

α 1 pAx α 1 -1 1 x α 2 2 -p 1 = 0 α 2 pAx α 1 1 x α 2 -1 2 -p 2 = 0.
14 Indeed, by definition of x, we have pA(x) α -p 1 x ≥ pAx α -p 1 x, ∀x. If x = 0, we have 0 ≥ pAx α -p 1 x = x(pAx α-1 -p 1 ), ∀x. Hence, 0 ≥ x(pAx α-1 -p 1 ), ∀x. Let x be closed to zero but still strictly positive so that pAx α-1 -p 1 > 0, we have a contradiction. Therefore, we have x > 0.

Hence,

p 1 p 2 = α 1 pAx α 1 -1 1 x α 2 2 α 2 pAx α 1 1 x α 2 -1 2 = α 1 x 2 α 2 x 1 ⇔ x 2 = p 1 p 2 α 2 α 1 x 1 .
From this and the FOCs, we have

p 1 = α 1 pAx α 1 -1 1 p 1 p 2 α 2 α 1 x 1 α 2 ⇔ pA = p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2
To sum up, we have the following result:

(a) If pA < p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2
, then the unique solution is

x 1 = x 2 = 0. In this case, the profit Π = 0. (b) If pA = p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2 , then any coupe (x 1 , x 2 ) satisfying x 2 = p 1 p 2 α 2 α 1 x 1 ≥ 0 is a solution. In this case, the profit Π = 0. (c) If pA > p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2
, there is no solution. Indeed, let us consider an allocation

x 2 = p 1 p 2 α 2 α 1 x 1 , we have that pAx α 1 1 x α 2 2 -p 1 x 1 -p 2 x 2 = pAx α 1 1 ( p 1 p 2 α 2 α 1 x 1 ) α 2 -p 1 x 1 -p 2 p 1 p 2 α 2 α 1 x 1 (32) = pAx α 1 +α 2 1 p α 2 1 p α 2 2 α α 2 2 α α 2 1 -p 1 x 1 (1 + α 2 α 1 ) = pAx 1 p α 2 1 p α 2 2 α α 2 2 α α 2 1 - p 1 x 1 α 1 (33) = x 1 p 1 α 1 pA α α 2 2 α 1-α 2 1 p 1-α 2 1 p α 2 2 -1 (34) Since pA α α 2 2 α 1-α 2 1 p 1-α 2 1 p α 2 2
-1 > 0, when we let x 1 tend to infinity, the profit of this allocation (x 1 , x 2 ) tends to infinity.

Assume that

α 1 + α 2 -1 < 1. A solution (x 1 , x 2 ) must satisfy x 1 > 0, x 2 > 0 (why?).
We have the FOCs

α 1 pAx α 1 -1 1 x α 2 2 -p 1 = 0 α 2 pAx α 1 1 x α 2 -1 2 -p 2 = 0.
Hence, we get

p 1 p 2 = α 1 pAx α 1 -1 1 x α 2 2 α 2 pAx α 1 1 x α 2 -1 2 = α 1 x 2 α 2 x 1 ⇔ x 2 = p 1 p 2 α 2 α 1 x 1 .
From this and the FOCs, we have

p 1 = α 1 pAx α 1 -1 1 p 1 p 2 α 2 α 1 x 1 α 2 ⇔ pAx α 1 +α 2 -1 1 = p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2
Since α 1 + α 2 -1 < 1, we can easily find that

x 1 = pA p 1-α 2 1 p α 2 2 α 1-α 2 1 α α 2 2 1 1-α 1 -α 2
This is increasing in the productivity A, the output price p but decreasing in the input prices p 1 , p 2 .

Least squares regression

The sum of squared residuals (in the multiple linear regression):

f (β 0 , β 1 , • • • , β k ) ≡ n i=1 y i -β 0 - k j=1 β j x i,j 2 on R k+1 .

Let us start by considering the case

k = 1. f (β 0 , β 1 ) ≡ n i=1 y i -β 0 -β 1 x i 2
We want to solve the following problem

Minimize (β 0 ,β 1 ) f (β 0 , β 1 ) ≡ n i=1 y i -β 0 -β 1 x i 2 subject to β 0 ∈ R, β 1 ∈ R This is an unconstrained convex minimization problem.
The objective function is convex (why?).

The first-order conditions (or Kuhn-Tucker conditions) give us

β 1 n i=1 x i (x i -x) = n i=1 x i (y i -ȳ) β 0 = ȳ -β 1 x where x ≡ n i=1 x i n , ȳ ≡ n i=1 y i n
are the sample averages.

Notice that

n i=1 x i (x i -x) = n i=1 (x i -x) 2 and n i=1 x i (y i -ȳ) = n i=1 (x i -x)(y i -ȳ). 2.
We now consider the general case. We want to solve the following problem

Minimize (β 0 ,...,β k ) n i=1 y i -β 0 - k j=1 β j x i,j 2 subject to β 0 ∈ R, • • • , β k ∈ R
This is an unconstrained convex minimization problem.

Non-convex optimization (optional)

We follow the exposition of [START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].

Unconstrained Optimization

First-order conditions for an unconstrained optimum Theorem 19. Suppose x * ∈ S is either an unconstrained local minimum or an unconstrained local maximum. Then Df (x * ) = 0.

Proof. Suppose that x * is an unconstrained local maximum. There exists r > 0 such that B(x * , r) ⊆ S and f (y) ≤ f (x * ) for all y ∈ B(x * , r). Assume a = Df (x * ) = 0. From the Taylor expansion, we have

f (x) = f (x * ) + Df (x * ) • (x -x * ) + R 1 (x, x * ) x -x *
For any real number t, define x t = x * + ta. For t close enough to zero, we have that

x t ∈ B(x * , r) ∩ S. Then f (x t ) = f (x * ) + a • (x t -x * ) + R 1 (x t , x * ) x t -x * = f (x * ) + t a 2 + R 1 (x * + ta, x * )|t| a = f (x * ) + t a ( a + R 1 (x * + ta, x * )) , when t ≥ 0 > f (x * )
when t is small enough. We get a contradiction. Hence Df (x * ) = 0. The proof is similar when x * is an unconstrained local minimum.

A point x is an optimum for f if it is either a maximum or a minimum of f . If it is an unconstrained local optimum, we have proved that Df (x) = 0.

Second order conditions for an unconstrained local optimum Lemma 7. (i) Let M be a positive definite n×n matrix. Let S(0, 1) denote the unit-sphere of R n . Then min x∈S(0,1) x M x > 0.

(ii) Let M be a negative definite n × n matrix. Let S(0, 1) denote the unit-sphere of R n . Then max x∈S(0,1) x M x < 0.

Proof. (i) The function ψ : S(0, 1) → R + defined by ψ(x) = x M x for x ∈ S(0, 1) is continuous and positive for any x ∈ S(0, 1). Since S(0, 1) is compact, ψ has a minimum on S(0, 1) which is positive, i.e. there exists x ∈ S(0, 1) which satisfies 0 < ψ(x) = x M x = min x∈S(0,1) x M x.

(ii) The proof is similar.

Theorem 20. Let f : S → R, where S ⊆ R n . Assume x 0 is an unconstrained local optimum of f . If D 2 f (x 0 ) is negative definite then x 0 is an unconstrained local maximum. If D 2 f (x 0 ) is positive definite, then x 0 is an unconstrained local mimimum.
Proof. We must have Df (x 0 ) = 0. Consider the Taylor expansion

f (x) = f (x 0 ) + Df (x 0 ) • (x -x 0 ) + 1 2 (x -x 0 ) D 2 f (x 0 )(x -x 0 ) + R 2 (x, x 0 ) x -x 0 2 = f (x 0 ) + 1 2 (x -x 0 ) D 2 f (x 0 )(x -x 0 ) + R 2 (x, x 0 ) x -x 0 2
Assume D 2 f (x 0 ) positive definite. When x = x 0 , let u = x-x 0 x-x 0 ∈ S(0, 1). We know that min x∈S(0,1) x D 2 f (x 0 )x = α > 0. Therefore,

f (x) = f (x 0 ) + 1 2 (x -x 0 ) D 2 f (x 0 )(x -x 0 ) + R 2 (x, x 0 ) x -x 0 2 = f (x 0 ) + 1 2 x -x 0 2 u D 2 f (x 0 )u + R 2 (x, x 0 ) x -x 0 2 , when x = x 0 ≥ f (x 0 ) + 1 2 x -x 0 2 [α + 2R 2 (x, x 0 )] , when x = x 0
When x is close to x 0 but different from x 0 , we have α + 2R 2 (x, x 0 ) > 0 and thus f (x) ≥ f (x 0 ). We have that x 0 is an unconstrained local minimum.

Similarly, when D 2 f (x 0 ) is negative definite then x 0 is an unconstrained local maximum. where the row-vector Df i (a) is the derivative of f i at point a.

Let f be a function from an open, convex, nonempty set U of R n into R. We say that f is locally minimal at x under the constraints x ∈ Γ, if x ∈ Γ and if there exists a neighborhood

V of x such that ∀x ∈ V ∩ Γ, f (x) ≥ f (x).
Consider the following problem (P ):

( P ) min f 0 (x) under the constraints

   x ∈ U f i (x) ≤ 0, ∀i = 1, . . . , I g i (x) = 0, ∀i = 1, . . . , K
where f 0 and f i , for i = 1, . . . , I, g i , for ii = 1, .

⊂ R m × R p × R q into R.
We suppose 0 ∈ U . Suppose that the function f : (x, y, z) → f (x, y, z) is locally minimal at 0 under the constraints x ≥ 0, y = 0. Then:

f x (0, 0, 0) ≥ 0, f z (0, 0, 0) = 0. Proof. Let C = {(x, y, z) ∈ R m × R p × R q | x ≥ 0, y = 0}. Let (r, s, t) ∈ C.
Then there exists λ 1 > 0 such that ∀λ ∈ [0, λ 1 [, one has (λr, λs, λt) ∈ C ∩ U . The function F defined by ∀λ ≥ 0, F (λ) = f (λr, λs, λt) is locally minimal at 0. Hence, F (0) ≥ 0, i.e.

f (0, 0, 0) • (r, s, t) ≥ 0, ∀(r, s, t) ∈ C.

In particular, f x (0, 0, 0) • r ≥ 0, ∀r ∈ R m such that r ≥ 0, f z (0, 0, 0) • t ≥ 0, ∀t ∈ R q . Hence: f x (0, 0, 0) ≥ 0 and f z (0, 0, 0) = 0.

Let x be a feasible point, i.e. f i (x) ≤ 0, ∀i = 1, . . . , I, and g i (x) = 0, ∀i = 1, . . . , K. Let I(x) = {i | f i (x) = 0}. We say that the constraints of Problem (P ) are regular at x if the gradients (Df i (x)) i∈I(x) , (Dg i (x)) i=1,...,K are linearly independent.

Theorem 21. Suppose that f 0 is locally minimal at x under the constraints of Problem (P ). Suppose also that the constraints are regular at x. Then there exist non-negative scalars (λ i ) i∈I , and scalars (µ i ) i∈K such that: (i) Df 0 (x) = -i=1,...,I λ i Df i (x) + i=1,...,K µ j Dg j (x), (ii) λ i f i (x) = 0, ∀i = 1, . . . , I.

Proof.

Observe that f 0 is also locally minimal at x under the constraints

f i (x) ≤ 0, ∀i ∈ I(x), g i (x) = 0, ∀i = 1, . . . , K where I(x) = {i ∈ I | f i (x) = 0}.
Suppose that I(x) has cardinal J. Since, by assumption, the constraints are regular at x, there exists θ 1 , . . . , θ q , vectors of R n , with q = n -J -K, such that the matrix ((Df i (x)) i=1,...,I ; (Dg i (x)) i=1,...,K , θ 1 , . . . , θ q ) is invertible. Define θi (x) = θ i • (x -x), ∀i = 1, . . . , q, ∀x ∈ R n , and the map ϕ from R n into R n by ϕ(x) = ((-f i (x)) i∈I(x) , (g j (x)) i=1,...,K , ( θi (x)) i=1,...,q ). One has ϕ(x) = 0, and J ϕ (x) is invertible, where J ϕ (x) is the Jacobian matrix of ϕ at x. From the Local inversion theorem (Theorem 22), ϕ has, in a neighborhood V of x, an inverse ϕ -1 which is continuously differentiable. Define, on ϕ(V ), the map F = f 0 • ϕ -1 . One has: F (u, v, w) = f 0 (x) if ϕ(x) = (u, v, w). In particular, F (0, 0, 0) = f 0 (x). Hence F (u, v, w) ≥ F (0, 0, 0) for u ≥ 0, v = 0. From Lemma 8, F u (0, 0, 0) ≥ 0 and F w (0, 0, 0) = 0, that means: F (0, 0, 0) = (λ, µ, 0) with λ ∈ R J + and µ ∈ R K . But Df 0 (x) = F (0, 0, 0)(J ϕ (x)). Since

J ϕ (x) = ((-Df i (x)) i∈I(x) , (Dg i (x)) i∈K , (θ i ) i=1,...,q ), one gets: Df 0 (x) = - i∈I(x) λ i Df i (x) + i=1,...,K µ i Dg i (x)
with λ i ≥ 0, ∀i ∈ I(x). Define λ i = 0, ∀i / ∈ I(x). Relation (i) is thus proved. We have λ i f i (x) = 0, ∀i = 1, . . . , I, that is Condition (ii). under the constraints

(x, y) ∈ R 2 : x 2 + y 2 2 = 1}

Comparative Statics

We are interested in a fundamental question: What is the effect of a change in an exogenous variable on the solution value of the endogenous variable? The issue is referred to "comparative statics".

Mathematical tools

We present fundamental tools that help us to do comparative statics. Assume that the Jacobian matrix J f (a) (derivatives of f )

J = ∂f ∂x 1 • • • ∂f ∂x n =    ∇ T f 1 . . . ∇ T f n    =       ∂f 1 ∂x 1 • • • ∂f 1 ∂x n . . . . . . . . . ∂f n ∂x 1 • • • ∂f n ∂x n      
is invertible. ∇ T f i is the transpose (row vector) of the gradient of the i component. Then

1.

there exists an open set U and V in R n such that a ∈ U and b ∈ V , f is one-to-one on U , and f (U ) = V .

2. the inverse function of f (denoted by f -1 ) is continuously differentiable on V .

Recall: The inverse function f -1 is defined by: for y ∈ V , take x ∈ U such that f (x) = y (this value x is uniquely determined because f is one-to-one on U ). Then we defined f -1 (y) = x, i.e., f -1 (f (x)) = x.

Proof. See [START_REF] Rudin | Principles of Mathematical Analysis[END_REF]

E = U × V of R n+m (U ⊂ R n , V ∈ R m ) into R n . Suppose that f (a, b) = 0 for some point (a, b) ∈ U × V . Assume that that Df a (
=       ∂f 1 ∂a 1 (a, b) • • • ∂f 1 ∂a n (a, b) . . . . . . . . . ∂f n ∂a 1 (a, b) • • • ∂f n ∂a n (a, b)       1. Then there exists an open set U 1 ⊂ U containing a, an open set V 1 ∈ V containing b, an open set W containing 0 and a function g : V 1 × W → U 1 such that f (x, y) = z ⇔ x = g(y, z) ∀x ∈ U 1 , ∀y ∈ V 1 , ∀z ∈ W Moreover, g is continuously differentiable on V 1 × W .
2. In particular, we have that:

f (x, y) = 0 ⇔ x = φ(y) ∀x ∈ U 1 , ∀y ∈ V 1 (35)
where φ is differentiable on V 1 . Moreover, we can compute the derivative of φ by using f (φ(y), y) = 0 Df x (φ(y), y)Dφ(y) + Df y ((φ(y), y)) = 0

Note that Df x (φ(y), y) is an n × n matrix while Df y ((φ(y), y)) is an n × m matrix.

Df x =       ∂f 1 ∂x 1 • • • ∂f 1 ∂x n . . . . . . . . . ∂f n ∂x 1 • • • ∂f n ∂x n       , Dφ =       ∂φ 1 ∂y 1 • • • ∂φ 1 ∂y m . . . . . . . . . ∂φ n ∂y 1 • • • ∂φ n ∂y m       Df y =       ∂f 1 ∂y 1 • • • ∂f 1 ∂y m . . . . . . . . . ∂f n ∂y 1 • • • ∂f n ∂y m      
The function φ is implicitly defined by (35).

Applications in Economics

Let us explicitly write f (a, b) = 0 as follows

f 1 (a 1 , . . . , a n , b 1 , . . . , b m ) = 0 • • • f n (a 1 , . . . a n , b 1 , . . . , b m ) = 0.
In economics, a 1 , . . . , a n are viewed as endogenous variables while b 1 , . . . , b m exogenous. To study the effect of exogenous variables (b j ) on endogenous variables (a i ) or to understand how (a i ) changes when (b i ) changes, we can apply the implicit function theorem and compute the derivatives of (a i ) as functions of (b j ).

Let us consider a two-period optimal growth model introduced in Section 3.3.2. Let conditions in Proposition 14 be satisfied. Then, the optimal physical capital k 1 is determined by

u (w 0 -k 1 ) -βF (k 1 )u (w 1 + F (k 1 )) = 0 (36)
Notice that w 0 , w 1 , β are exogenous parameters while k 1 is endogenous and depends on w 0 , w 1 , β.

Denote f (k 1 , w 0 , w 1 , β) ≡ u (w 0 -k 1 )-βF (k 1 )u (w 1 +F (k 1 )). Observe that the function f is striclty increasing in k 1 and w 1 , but strictly decreasing in w 0 and β Assume that u and F are continuously differentiable. Applying the implicit functions theorem, the optimal value k 1 determined by f (k 1 , w 0 , w 1 , β) = 0 can be expressed as a differentiable function of w 0 , w 1 , β. We write k 1 = k 1 (w 0 , w 1 , β).

We now look at the role of the initial endowment w 0 . Taking the derivative with respect to w 0 of both sides of the equation f (k 1 , w 0 , w 1 , β) = 0, we have

∂f ∂k 1 (k 1 , w 0 , w 1 , β) ∂k 1 ∂w 0 (w 0 , w 1 , β) + ∂f ∂w 0 (k 1 , w 0 , w 1 , β) = 0
Since ∂f ∂k 1 > 0 and ∂f ∂w 0 < 0, we get that ∂k 1 ∂w 0 (w 0 , w 1 , β) > 0. It means that the optimal value k 1 is increasing in the initial endowment.

5 Discrete dynamical systems (difference equations)

Motivating examples

The basic idea is that, in some cases the (economic) outcomes at a period depend on the variables in the pass. For instance,

x 1,t+1 = f 1 (x 1,t , • • • , x n,t ) • • • x n,t+1 = f n (x 1,t , • • • , x n,t ).
So, investigating the evolution of the sequence (x 1,t , . . . , x n,t ) requires us to deal with this dynamical system.15

One-dimensional, first-order systems

Consider the one-dimentional autonomous, first-order difference equation:

y t+1 = f (y t )∀t ≥ 0 ( 37
)
y 0 is given and f : R → R is a real function. If we consider the system

y t+1 = f t (y t )∀t ≥ 0 (38)
where the function f t depends on time, then it is called "non-autonomous" Definition 20. A solution of this difference equation is a trajectory (x t ) t≥0 that satisfies (37) and initial condition x 0 = y 0 .

Definition 21. Let f be a function and x ∈ R (or in general, in the domain of f ).

We define f n (x) the nth iterate of f under f by the following relationship:

f n (x) = f (f n-1 (x))∀n ≥ 1, f 0 (x) ≡ x.
Definition 22.

1. A steady-state equilibrium (or equilibrium point, or fixed point) is a value x * satisfying f (x * ) = x * .

2.

x is an eventually equilibrium (fixed) point if there exists a positive integer r and an equilibrium point x * such that f r (x) = x * , f r-1 (x) = x * , where f n (x) is the nth iterate of f under f .

Linear cases

Consider a linear, first-order, autonomous difference equation

x t+1 = ax t + b
where a, b are constants. We can proved that

x t = a t x 0 + b 1-a t 1-a ∀t ≥ 0, if a = 1 x 0 + bt if a = 1.
Consequently, if a ∈ (-1, 1), we have lim t→∞ x t = b/(1 -a) ∀y 0 .

Notice that x * ≡ b/(1 -a) is the unique steady state when a = 1. We also observe that

x t = a t (y 0 -y * ) + y * ∀t ≥ 0, if a = 1 y 0 + bt if a = 1.
Graphics here. Prove that

y t = t-1 i=1 a i y 0 + t-1 k=0 b k t-1 i=k a i a k
Exercise 27. Study the following system

x t+1 = Ax α t where x 0 > 0 is given, A > 0 and α > 0.

Find the fixed points.

Find conditions (based on x 0 , A, α) under which x t converges (diverges). Hint: Consider α = 1, α > 1, α < 1.

Exercise 28. Study the following system

x t+1 = A max(x t -b, 0)
where x 0 > 0 is given, A > 0 and b > 0.

Find the fixed points.

Find conditions (based on x 0 , A, b) under which x t converges (diverges). Hint: Draw the graph of the function f (x) = Amax(x -b, 0). Consider A = 1, A > 1, A < 1.

Proof. Let x > 0 be a fixed point. We have x = Amax(x -b, 0). Since x > 0, we have max(x -b, 0) > 0. This implies that x -b > 0. Hence, max(x -b, 0) = x -b. From this, we can find x by x = A(x -b), i.e., x(A -1) = Ab.

Exercise 29. Suppose that aggregate consumption in period t is given by

C t = A + BY t-1
where Y t represents the income in period t and B ∈ (0, 1) is the marginal propensity to consume out of the previous year's income.

Assume that

Y t = C t + I t I t = (1 + g) t
where g > 0 is the exogenous growth rate in investment spending.

Prove that

Y t = B t Y 0 + t-1 k=0 A + (1 + g) k B t-1-k = B t Y 0 + A 1 -B t 1 -B + A (1 + g) t -B t 2. Moreover, we have lim t→∞ C t Y t-1 = B lim t→∞ Y t I t = A 3.
When happens if g < 0?

Nonlinear, first-order, autonomous difference equation

When the function f is not linear, it is not easy to explicitly compute f t (x 0 ) or investigate the evolution of f t (x 0 ). There may exist multiple steady-state equilibria. Indeed, let consider the system k t+1 = f (k t ) where f (x) = Ax 0.5 (1 + x), A > 0, and k 0 > 0. We can check that if A < 0.5, then there are two steady states (see Example 9).

Convergence and global stability

In economics, we are particularly interested in the convergence and stability of the sequence x t = f t (x 0 ). We would like to find conditions under which the sequence x t converges.

Proposition 16. Let f : S → S where S is a closed set of R. Suppose that f is increasing.

Suppose that there exists a unique x * such that f (x * ) = x * . Moreover, f (x) < x ∀x > x * , and f (x) > x ∀x < x * . Then the system (x t ) defined by x t+1 = f (x t ) converges to x * for any x 0 ∈ S.

Proof. If x 0 = x * , then x t = x * , ∀t. If x 0 < x * , then f (x 0 ) > x 0 , or, equivalently, x 1 > x 0 . By induction, we can easily prove that the sequence x t is increasing: x t+1 ≥ x t , ∀t. Indeed, this holds for t = 0. Assume that it holds until date t. Since x t ) ≥ x t-1 , we have f (x t ) ≤ f (x t-1 ), which is equivalent to x t+1 ≤ x t . So, x t is increasing. Notice that x t+1 ≥ x t means that f (x t ) ≥ x t . According to our assumption, this implies that x t ≤ x * . To sum up, x t is increasing and bounded from above. Thus, it converges to some value x. We will prove that x = x * . Since x t+1 = f (x t ), by letting t tend to infinity, we have x = f (x). Since the fixed point is unique, we obtain that x = x * .

For the case x 0 > x * , we can use a similar argument to prove that x t decreasingly converges to x * .

Definition 23 (contraction mapping). A function f : R → R is a contraction mapping (or function) if there exists θ ∈ (0, 1) such that |f (x) -f (y)| ≤ θ|x -y| ∀x, y.

If f is differentiable and sup x |f (x)| < 1, then f is a contraction mapping (why?). Notice that the condition |f (x) -f (y)| ≤ θ|x -y| ∀x, y is quite restrictive. It is not satisfied for the function f

(x) = x 2 . Indeed, we have |f (x)-f (y)| = |(x+y)(x-y)| ≥ |x-y| if |(x + y)| ≥ 1.
We present the following result which is a simple case of Banach Fixed Point Theorem that shows the existence and uniqueness of the fixed point of a contraction mapping in a complete metric space. 1. If f is a contraction mapping, then the system has a unique steady-state x * and lim t→∞ x t = x * for any x 0 .

2. Assume that f is differentiable and sup x |f (x)| < 1, then the system has a unique steady-state x * and lim t→∞ x t = x * for any x 0 .

We also state the results in the space R n .

Proposition 18. Let f : R n → R n be contraction mapping, i.e., there exists θ ∈ (0, 1) such that f (x) -f (y) ≤ θ x -y ∀x, y.

1. f has a unique fixed point x * (i.e., there is a unique x * such that f (x * ) = x * ).

2. For every x 0 ∈ R, the sequence (x t ), determined by x t+1 = f (x t ) ∀t, converges to x * .

Proof. Although we consider the space R n , the proof in a complete metric space is similar. Uniqueness of x * . Suppose that there is x = x * such that f (x) = x. Since f is a contraction mapping, we have

f (x) -f (x * ) ≤ θ x - * . However, f (x) -f (x * ) = x -x * . Hence, x - * ≤ θ x - * < x - * , a contradiction.
Therefore, we have proved the uniqueness of x * .

Existence of x * . Let x 0 ∈ R n . Consider the sequence (x t ) defined by x t+1 = f (x t ), ∀t, i.e, x t = f t (x 0 ). We will prove that x t converges to x * .

First, we prove that (x t ) is a Cauchy sequence in the sense that: ∀ > 0, there exists n 0 such that x n -x m < , ∀n > n 0 , m > n 0 . Indeed, we have

x 2 -x 1 = f (x 1 ) -f (x 0 ) ≤ θ x 1 -x 0 x n+1 -x n = f (x n ) -f (x n-1 ) ≤ θ x n -x n-1 ≤ • • • ≤ θ n x 1 -x 0
and hence, for n > m, we have

x n -x m = x n -x n-1 + • • • + x m+1 -x m ≤ x n -x n-1 + • • • + x m+1 -x m ≤ θ n-1 x 1 -x 0 + • • • ≤ θ m x 1 -x 0 = x 1 -x 0 θ m (1 + θ + • • • + θ n-1-m ) ≤ x 1 -x 0 θ m 1 1 -θ
For any > 0, since θ ∈ (0, 1), we can choose n 0 such that x 1 -x 0 θ n 0 1 1-θ < . Then, for any n > n 0 , m > n 0 , we have

x n -x m ≤ x 1 -x 0 θ m 1 1 -θ ≤ x 1 -x 0 θ n 0 1 1 -θ < .
Second, since (x t ) is a Cauchy sequence, it converges to some value x ∈ R n (see [START_REF] Rudin | Principles of Mathematical Analysis[END_REF]). By definition, we have x t+1 = f (x t ). Let t tend to infinity, we get that x = f (x). However, since the fixed point is unique, we obtain that x = x * . It means that x t converges to x * .

Local stability

Definition 24.

1. The equilibrium point x * is stable (or Lyapunov stable) if, for any > 0, there exists δ > 0 such that:

|x 0 -x * | < δ implies that |f n (x 0 ) -x * | < ∀n > 0.
If x * is not stable, then it is called unstable.

2.

x * is said to be attracting if there exists η > 0 such that:

|x 0 -x * | < η implies lim t→∞ x t = x * x * is called global attracting if η = ∞.

3.

x * is said to be asymptotically stable equilibrium point if it is stable and attracting.

If η = ∞, then x * is said to be globally asymptotically stable.

Definition 25. The equilibrium point x * is said to be hyperbolic if |f (x * )| = 1.

Theorem 24. Let x * be an equilibrium point of the difference equation x t+1 = f (x t ). Assume that f is continuously differentiable at x * . We have that: Let x 0 ∈ J. We have

x 1 -x * = f (x 0 ) -x * = f (x 0 ) -f (x * ) = f (ξ)(x 0 -x * )
where ξ is between x 0 and x * . (Recall that x 0 may be lower or higher than x * .) By consequence, we have

|x 1 -x * | = |f (ξ)||x 0 -x * | ≤ M |x 0 -x * | ≤ |x 0 -x * | < γ
This implies that x 1 ∈ J. By induction we get that x n ∈ J ∀n and

|x n -x * | ≤ M n |x 0 -x * |∀n.
Let > 0, choose δ < min(γ, ), then we have

|x n -x * | ≤ M n |x 0 -x * | ≤ |x 0 -x * | < δ < ∀n.
So, x * is stable. x * is attracting because: |x 0 -x * | < δ implies that lim t→∞ x t = x * . Therefore, x * is stable.

(2) We now suppose that |f (

x * )| > 1. Since f (x) is continuous and |f (x * )| > 1, there exist γ > 0 and M > 1 such that |f (x)| > M > 1 ∀x ∈ J ≡ (x * -γ, x * + γ).
Suppose that x * is stable. Let be in the interval (0, γ). So, there exist δ > 0 such that:

|x 0 -x * | < δ implies that |f n (x 0 ) -x * | < ∀n > 0.
Take 0 < α < min( , δ). We have:

|x 0 -x * | < α implies that |f n (x 0 ) -x * | < ∀n > 0. Take x 0 be such that 0 < |x 0 -x * | < α. We have |x n -x * | < < γ ∀n > 0. Hence, x n ∈ J ∀n. So, we get that |x n -x * | = |f (ξ n )||x n-1 -x * | ≥ • • • ≥ M n |x 0 -x * |
where ξ n is between x 0 and x * and hence belongs the interval J.

Since M > 1, |x n -x * | must tend to infinity, a contradiction (because |x n -x * | < ). Therefore, x * is not stable.

Example 9 (increasing return to scale and middle-income trap). Consider the system k t+1 = f (k t ) where f (x) = Ax 0.5 (1 + x), A > 0, and k 0 > 0 is given. k t can be interpreted as the physical capital stock of the economy at date t (see Section 5.2.6).

Solving the problem. The equation determining the steady states is x = Ax 0.5 (1 + x), or equivalently Ax -x 0.5 + A = 0.

Denote ∆ = 1 -4A 2 . There is no positive steady state if and only if ∆ < 0 or equivalently A > 1/2. In this case, we can check that Ax 0.5 (1 + x) > x, ∀x > 0. By consequence, k t is strictly increasing in t. Since there is no positive steady state, k t converges to infinity.

Economically, we can say that when the productivity A is high (in the sense that A > 1/2), the economy grows without bound (k t converges to infinity).

There are 2 positive steady states if and only if ∆ > 0 or equivalently, 0 < A < 1/2. We can easily compute these two steady state:16

x L = 1 - √ 1 -4A 2 2A 2 , x H = 1 + √ 1 -4A 2 2A 2 .
We can see in the graph that f (x) > x, ∀x ∈ (0, x L ) or x ∈ (x H , ∞), and f (x) < x, ∀x ∈ (x L , x H ).

1. We can see that x L is asymptotically stable because |f (x L )| < 1. (Actually, f (x L ) ∈ (0, 1).)

2. We now prove k t increasingly converges to ∞ if k 0 > x H . Then, x H is not stable.

For k 0 > x H , we can show that k t is strictly increasing in t (use the fact that f (x) > x, ∀x ∈ (x H , ∞)). By consequence, k t converges. It cannot converge to a steady state because k t+1 > k t > x H , ∀t. So, it must converge to infinity.

The point x H is not stable because k t converges to infinity for any k 0 > x H .

3. We now want to prove that: lim t→∞ k t = x L ∀k 0 ∈ (0, x H ).

First, observe that f (x) ≥ x if x ∈ (0, x L ) and f (x) < x if x ∈ (x L , x H ).

(a) We prove that k t increasingly converges to x L if k 0 ∈ (0, x L ). Proof: Let k 0 ∈ (0, x L ). By applying the above remark, we have f (k 0 ) ≤ k 0 , and hence, k 1 ≤ k 0 .

Nonhyperbolic fixed points

Proposition 19. Let x * be a fixed point and f (x * ) = 1. Assume that f is in C 3 . We have 1. If f (x * ) = 0, then x * is unstable.

2. If f (x * ) = 0 and f (x * ) > 0 then x * is unstable.

3. If f (x * ) = 0, and f (x * ) < 0 then x * is asymptotically stable.

Proof. By using the Taylor theorem and f (x * ) = 1, we have

f (x) =f (x * ) + f (x * )(x -x * ) + 1 2 f (x * )(x -x * ) 2 + R 2 (x, x * ) x -x * 2 (39) =f (x * ) + (x -x * ) + 1 2 f (x * )(x -x * ) 2 + R 2 (x, x * ) x -x * 2 (40) f (x) =f (x * ) + f (x * )(x -x * ) + 1 2 f (x * )(x -x * ) 2 + 1 6 f (x * )(x -x * ) 3 + R 3 (x, x * ) x -x * 3 =f (x * ) + (x -x * ) + 1 2 f (x * )(x -x * ) 2 + 1 6 f (x * )(x -x * ) 3 + R 3 (x, x * ) x -x * 3 (41)
1. If f (x * ) = 0, then we consider two cases.

(a) f (x * ) > 0. In this case, f (x) is increasing in a neighborhood (x * -δ, x * + δ) of x * . Since f (x * ) = 1, we have f (x) > 1 = f (x * ) ∀x ∈ (x * , x * + δ). By adopting the argument in the proof of part 2 of Theorem 24, we can prove that x * is unstable.

(b) f (x * ) < 0. Using the same argument, we have that x * is unstable.

2. If f (x * ) = 0 and f (x * ) > 0, then we have

f (x) -f (x * ) = (x -x * ) 1 + 1 6 f (x * )(x -x * ) 2 + R 3 (x, x * ) x -x * 3 .
By adopting the argument in the proof of part 2 of Theorem 24, we can prove that x * is unstable.

3. If f (x * ) = 0, and f (x * ) < 0, then (41) implies that

f (x) -f (x * ) = (x -x * ) 1 + 1 6 f (x * )(x -x * ) 2 + R 3 (x, x * ) x -x * 3
By adopting the argument in the proof of part 1 of Theorem 24, we can prove that x * is asymptotically stable.

Application: Solow growth models

We consider a model à la Solow. The long-term rate of growth g of the output depends strongly on the rate of growth of the TFP A. The higher A, the higher the rate of growth g.

Proof.

Left to the readers.

We now consider a more general model à la Solow.

Solow Model:

c t + S t = Y t I t = S t k t+1 = k t (1 -δ) + I t S t = sY t Y t = A t k α t L 1-α t , α ∈ (0, 1) A t = a(1 + γ) t L t = L 0 (1 + n) t
Here γ > -1 is the rate of growth of the TFP A t , n > -1 is the rate of growth of the labor force. Both of them are assumed to be exogenous.

Y t = a(1 + γ) t k α t L 1-α t Y t+1 Y t = (1 + γ)(1 + n) 1-α k t+1 k t α k t+1 = k t (1 -δ) + sa(1 + γ) t k α t L 1-α t 2.
Prove that ∆Yt Yt → g where ∆Y t ≡ Y t+1 -Y t and g satisfies

1 + g = (1 + n)(1 + γ) 1 1-α
The long-term rate of growth g of the output depends strongly on the rate of growth of the TFP A t . The higher γ, the higher the rate of growth g.

Proof.

Left to the readers.

Application: a Malthusian growth model

In 1798, Thomas Malthus wrote: "Through the animal and vegetable kingdoms, nature has scattered the seeds of life abroad with the most profuse and liberal hand. ... The germs of existence contained in this spot of earth, with ample food, and ample room to expand in, would fill millions of worlds in the course of a few thousand years. Necessity, that imperious all pervading law of nature, restrains them within the prescribed bounds. The race of plants, and the race of animals shrink under this great restrictive law. And the race of man cannot, by any efforts of reason, escape from it. Among plants and animals its effects are waste of seed, sickness, and premature death. Among mankind, misery and vice." 18 Thomas Malthus hypothesized that population growth is an inverse function of income per capita. Inspired by this idea, we assume that

N t+1 -N t N t = n - b w t
where w t is income per capita, N t is population in period t while a, b are positive constants.

Assume that w t is given by

w t = Y t N t
where Y t is aggregate output in the economy. Assume that

Y t = N α t
where α ∈ (0, 1).

18 See Thomas Malthus, 1798. An Essay on the Principle of Population. Chapter I.

From this, we get that

w t = N α-1 t .
Hence, the income is a decreasing function of the population. Rearranging equations, we obtain a nonlinear, first-order difference equation:

N t+1 = N t (1 + n -bN 1-α t )
Exercise 32.

1. Find the positive steady states of this dynamical system.

2. Are they asymptotically stable or unstable? Why?

Multiple-dimensional, first-order systems

We now consider a multiple-dimensional, first-order system: x t+1 = f (x t ) where f : R n → R n . Explicitly, we write that

x 1,t+1 = f 1 (x 1,t , • • • , x n,t ) • • • x n,t+1 = f n (x 1,t , • • • , x n,t ).
In general, it is difficult to deal with this system.

Let us look at a steady states x * determined by f (x * ) = x * . Notice that it is not easy to compute x * .

Assume that, for any i, the function f i is in C 1 (continuously differentiable). Applying the Taylor's theorem, in a neighborhood of x * , we can approximate f i by an affine function f i (x 1,t , . . . , x n,t ) =f i (x * 1 , . where R i (x * , x * ) = 0 and R 1 (x t , x * ) → 0 as x t → x * . This can be rewritten in a matrix form   

x 1,t+1 . . .

x n,t+1

   =       ∂f 1 ∂x 1 (x * ) • • • ∂f 1 ∂x n (x * ) . . . . . . . . . ∂f n ∂x 1 (x * ) • • • ∂f n ∂x n (x * )         
x 1,t . . . when b = 0, the system is said to be homogeneous. Let x * be a fixed point x * = Ax * + b. x * exists and equals (I -A) -1 b if the determinant det(I -A) = 0 where I is the n × n identity matrix. We have that x t+1 -x * = A(x t -x * ) hence x t -x * = A t (x 0 -x * )∀t ≥ 0 It remains to compute A t . This task is not easy. Linear Algebra helps us to deal with this problem. Assume that we can diagonalize the matrix A in the sense that

A = V DV -1
where the matrix V is convertible and D is a diagonal matrix

D =    λ 1 • • • 0 . . . . . . . . . 0 • • • λ n   
and λ i ∈ R, λ i = λ j ∀i, j. This happens if the characteristic polynomial det(A -λI) has n different real roots. So, under this condition, we obtain A t = V D t V -1 ∀t and hence

x t -x * = V D t V -1 (x 0 -x * )∀t ≥ 0 D t =    λ t 1 • • • 0 . . . . . . . . . 0 • • • λ t n   
To sump up, x t converges to the steady state x * if the polynomial det(A -λI) has n different real roots (λ i ) n i=1 and |λ i | < 1 ∀i. 19

Exercise 2 .

 2 Prove that a • b ≤ a b where a • b ≡ (a 1 b 1 , . . . , a N b N ).

4.

  If p > 0, and α ∈ R, then lim n→∞ n α (1+p) n = 0. 4 5. If |x| < 1, then lim n→∞ x n = 0. Proof. Point 4. Recall the binomial theorem: (x+y) n -k)!

  Prove that V t ≡ lim n→∞ V n,t = P e rt Definition 6. The limit inferior of a sequence (x n ) is defined by

  4 = n(6n 4 +15n 3 +10n 2 -1) 30 .Exercise 9. Prove that 1.

•

  The union of an arbitrary collection of open sets is again open • The intersection of an arbitrary collection of open sets is not always open. Example:

A

  motivation: The Total-and Marginal-Cost Functions. Suppose that the total cost function of a firm is C = C(y) where y is its output. Let us look at ∆C ∆y = C(y + ∆y) -C(y) ∆y This represents the (average) rate of change in cost per added unit of output produced. If we know ∆C ∆y , then we can compute the change in cost C(y + ∆y) -C(y) as a function of ∆y by using the formula C(y + ∆y) -C(y) = ∆C ∆y × ∆y. The instantaneous rate of change (the marginal-cost of production) + ∆y) -C(y) ∆y

3 . D

 . 12 f (0, 0) = 1 and D 21 f (0, 0) = -1.Theorem 10 (Rolle's theorem). Let f be a function from[a, b] into R. Assume that f is continuous on [a, b], differentiable on (a, b), and f (a) = f (b). Then there exists c ∈ (a, b) such that f (c) = 0. Proof. Since f is continuous, there exist m ≡ min{f (x) : x ∈ [a, b]} and M ≡ max{f (x) : x ∈ [a, b]}.If m = M , then f is constant which implies that its derivative equals zero.If m < M , we have either f (a) > m or f (a) < M . Without loss of generality, we can assume that f (a) > m. Then there exists c such that f (c) = m. We observe that c = a, c = b. Define φ(h) ≡ f (c+h)-f (h) h with h 0 and h is small enough so that c+h ∈ [a, b].

  . (Readers may like to consider the case k = 1 to simplify the calculation.)3 Finite-dimensional optimization 3.1 Motivating examples 1. Utility maximization problem 2. Profit maximization problem 3. Cost minimization problem

Proposition 9 .

 9 [First separation theorem] Let A and B be two nonempty disjoint convex subsets of R n . There there exist α, β, α ≤ β and p ∈ R n , p = 0, such that p • a ≤ α ≤ β ≤ p • b, for all a ∈ A, all b ∈ B (i.e., we can separate A and B by a hyperplane).Proof. See Florenzano and Le[START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF].Proposition 10. [Second separation theorem] Let A and B be two nonempty disjoint closed convex subsets of R n . If one of them is compact, then there there exist α, β, α < β and p ∈ R n , p = 0, such that p • a ≤ α < β ≤ p • b, for all a ∈ A, all b ∈ B (i.e., we can strictly separate A and B by a hyperplane).

  is the unique solution of the original problem. Exercise 21. Consider the function u : R 2

  (a) Assume that c 1 = 0 at optimum. Find c 2 and compute u 0 ≡ u(c 1 , c 2 ) (b) Prove that (x, w-p 1 x p 2 ) is in the set B for any x satisfying ∈ [0, w/p 1 ].

  b) How can we get a contradiction? Proof. 1. Convexity: let c = (c 1 , c 2 ) and c = (c 1 , c 2 ) be in B. We have to check that λc + (1 -λ)c ∈ B for any λ ∈ [0, 1]. This is easy.

  Let f be a continuously differentiable mapping from an open, nonempty convex set U of R n into R n . Let a ∈ U . Then f (a) = (f 1 (a), . . . , f n (a)).The Jacobian matrix J f (a) is J f

Theorem 22 .

 22 [The Inverse Function Theorem] Let f be a continuously differentiable mapping from an open, nonempty set E of R n into R n . Consider a point a ∈ E. Denote b = f (a).

  a, b) is invertible, where Df a (a, b) is the partial derivative of f with respect to the variable (a) at point (a, b) defined by Df a (a, b)

1

  Figure 2: Monotonic convergence versus oscillatory convergence

Figure 3 :

 3 Figure 3: lim t→∞ x t = x * , ∀x 0 > 0. See Proposition 16.

  2. |fn (x 0 ) -x * | ≤ θ n |x 0 -x * | ∀n ≥ 1.Corollary 5. Consider the difference equation x t+1 = f (x t ) where f : R → R.

Figure 4 :

 4 Figure 4: Monotonic convergence versus oscillatory convergence

  2. If |f (x * )| > 1, then x * is unstable. Proof. (1) Suppose that |f (x * )| < 1. We can choose M such that |f (x * )| < M < 1. Since f (x) is continuous, there exists an interval J = (x * -γ, x * + γ), where γ > 0, such that |f (x)| < M < 1 ∀x ∈ J.

Proposition 21 .

 21 Consider the above Solow model. 1. Prove that, for any t ≥ 0,

  x t , x * ) x t -x * . . . R n (x t , x * ) x t -x * the following we focus on a linear dynamical system given by x t+1 = Ax t + b,

  Proposition 3. 1. If there exists N 0 such that |a n | ≤ c n ∀n ≥ N 0 , and if c n converges, then n a n converges 2. If there exists N 0 such that a n ≥ d n ∀n ≥ N 0 , and if d n diverges, then n a n diverges Proposition 4. 1. The series converges if lim sup n→∞ | a n+1 an | < 1. 2. The series diverges if there exists n 0 such that | a n+1 an | ≥ 1 ∀n ≥ n 0 . 3. The series diverges if lim inf n→∞ | a n+1 an | > 1.

	Exercise 8. Prove that
	1.

  The sum of two open sets is open, where we define the sum of two sets S 1 , S 2 of R n by S 1

• The intersection of a finite collection of open sets is open

•

•

  If f is differentiable on a set S, its derivative Df can be seen as a mapping Df : S → R m×n . If this mapping is continuous, we say that f is continuously differentiable orf is C 1 . Let f : S → R, where S ⊆ R n is an open set. If f is differentiable on S,then it is continuous on s.

	Properties 4. Proof. Using definition.
	Theorem 8. Let f : S → R, where S ⊆ R n is an open set. The function f is C 1 on S if,
	and only if, all partial derivatives of f exist and are continuous on S. In that case we also
	have	Df (x) =	∂f (x) ∂x 1	,	∂f (x) ∂x 2	, . . . ,	∂f (x) ∂x n

  . . , K are continuously differentiable functions from an open, convex, nonempty set U of R n into R. Lemma 8. Let f be a differentiable function from an open, convex set U

  , page 221.

	Theorem 23. [The implicit Functions Theorem] Let f be a continuously differentiable
	function from an open, nonempty set

  Solow Model:c t + S t = Y t I t = S t k t+1 = k t (1 -δ) + I t S t = sY t Y t = A t k α t L 1-α t , α ∈ (0, 1) A t = A L t = 1where c t , S t , I t are consumption, saving, investment at date t (t = 0, 1, . . . , +∞), s ∈ (0, 1) is the exogenous saving rate, k t is the physical capital stock at date t (k 0 > 0 is given), δ ∈ [0, 1] is the capital depreciation rate, Y t is the output.Proposition 20. Consider the above Solow model. 1. Prove that, for any t ≥ 0,

	Y t = Ak α t
	Y t+1 Y t	=	k t+1 k t

α k t+1 = k t (1 -δ) + sAk α t 2.

Prove that k t and Y t converge. Find k * ≡ lim t→∞ k t and Y * ≡ lim t→∞ Y t . How k * and Y * depend on A, s? 3. Is k * asymptotically stable? Why? Illustrate your arguments by diagrams.

The set P and the binary relation ≤ constitute a partially ordered set if the binary ≤ is reflexive (x ≤ x), transitive (x ≤ y and y ≤ z imply that x ≤ z) and anti-symmetric (x ≤ y and y ≤ x imply that x = y).

Hint: Define x ≡ p 1/n -1. Observe that (1 + x) n > 1 + nx ∀x > 0 and n is integer.

Hint: Let k be an integer and higher than α. Prove that (1 + p) n > n k p k 2 k k! ∀n > 2k.

We can also prove that S is compact if and only if every open covering of S has a finite sub-covering.Here, we define that: An open covering of a set S is a collection of open sets {U α } α such that S ⊆ ∪ α U α . This definition is in general used when R N is replaced by a topological space.

A generalization of this theorem can be found in Theorem4.22 in Rudin (1976).

See Theorem 5.2.1 in Florenzano and Le[START_REF] Florenzano | Finite dimensional convexity and optimization[END_REF] for a stronger result.

We do not have "if and only if" for the strictly concave function. Indeed, the function f (x) = -x 4 is strictly concave, but its second derivative equals 0 at x = 0.

In general, if the function f is strictly increasing in one component, then p 1 a 1 + p 2 a 2 = w. Indeed, if p 1 a 1 + p 2 a 2 < w, then we can increase a 1 and/or a 2 by with is low enough such that p 1 (a 1 + ) + p 2 (a 2 + ) < w to get a strictly higher value of the objective function).

See Bosi and Ragot (2011) for an excellent introduction of discrete dynamical systems.

However, we can eventually provide analysis without computing x L , x H .

Readers may like to use https://www.desmos.com/calculator?lang=en to draw the graph of the function f .

See Simon and Blume (1994) among others for more details.