1 Optimization

1.1 Introduction

This section introduces the mathematical tools necessary to conduct optimization in vector spaces.

1.1.1 Module Meta Information

Reading material: MWG M.J and M.K, Luenberger

1.2 Properties of a vector space

One of the principle spaces on which we develop optimization problems is a vector space. The next definition defines the properties of a vector space.

Definition 1.1 A set \(X\) over which addition and scalar multiplication are defined in such a way that \(x + y \in X\) for \(x,y \in X\) and \(\alpha \cdot x \in X\) for \(\alpha \in \mathbb{R}\) is a vector space if for any \(x\), \(y\) and \(z \in X\) and \(\alpha, \beta \in \mathbb{R}\),

\(x + (y + z) = (x + y) + z\)

\(x + y = y + x\)

There exists an element \(0 \in X\) such that \(x + 0 = x\) for all \(x \in X\)

For all \(x \in X\), there exists an element \(-x \in X\) for which \(x + (-x) = 0\)

\(\alpha(\beta x) = (\alpha \beta) x\)

\(1x = x\)

\(\alpha(x + y) = \alpha x + \alpha y\)

\((\alpha + \beta) x = \alpha x + \beta x\)

Example 1.1 Consider the set of all infinite sequences of real numbers. Prove that there exist definitions of addition and scalar multiplication for which this set is a vector space. What is the 0 element?

Example 1.2 Consider the set of all functions from \([0,1]\) into \(\mathbb{R}\). Prove that there exist definitions of addition and scalar multiplication for which this set is a vector space. What is the zero element? Does this hold true for the set of all continuous functions from \([0,1]\) into \(\mathbb{R}\)? The set of all differentiable functions? The set of all differentiable functions with derivatives bounded above by 2?

The leading example of a vector space used in economic analysis is \(\mathbb{R}^n\), sometimes called "n-dimensional Euclidean space." For many of the problems used in economics this space has been found to be a reasonable approximation to reality. For examples like household consumption choice, some savings and investment problems this set and firm behavior this set is often used.

Exercise 1.1 Let \(X\) be a vector space. Prove that:

\(X\) is convex.

the number of elements in \(X\) is at least countably infinite.

Defining a general concept of distance is helpful in many optimization problems. A norm does this.

Definition 1.2 A norm on a vector space \(X\) is a function \(||\cdot||:X \rightarrow \mathbb{R}\) having the following properties:

\(||x|| > 0\) if \(x \ne 0\)

\(||\alpha x|| = |\alpha| ||x||\) for any \(\alpha \in \mathbb{R}\)

\(||x + y|| \le ||x|| + ||y||\) for any \(x,y \in X\)

Example 1.3 Consider the following functions. Determine whether these are norms or not.

The Euclidean distance over \(\mathbb{R}^2\).

The maximum over an element of \(\mathbb{C}_{[0,1]}\) where \(\mathbb{C}_{[a,b]}\) is the set of continuous functions on the real interval \([a,b]\).

The function \(||\cdot|| = \max_{a \le t \le b}|x(t)| + \max_{a \le t \le b} |\dot{x}(t)|\) over the set \(D[a,b]\) of continous function over the interval \([a,b]\) that have continuous first derivatives.

The function \(\epsilon(x,y) = \sum_{i=1}^{n}x_{i}\log \frac{y_{i}}{x_{i}}\)

The function \(||x|| = \int_{a}^{b}|x(t)|dt\) over the space of continuous functions over the interval \([a,b]\). Notice that this is a different normed space than \(\mathbb{C}[a,b]\) since it has a different norm.

Definition 1.3 A normed vector space is a pair \((X,||\cdot||)\) where \(X\) is a vector space and \(||\cdot||\) is a norm.

Exercise 1.2 Prove that if \(||\cdot||\) is a norm on a vector space \(X\) then \(||x|| - ||y|| \le ||x - y||\) for any two vectors \(x,y \in X\).

Definition 1.4 An inner product over a space \(X\) is a function \(\langle \cdot,\cdot \rangle : X \times X \rightarrow \mathbb{R}\) that satisfies the following properties:

\(\langle x, y \rangle = \langle y, x \rangle\)

\(\langle \alpha x, y \rangle = \alpha \langle x , y \rangle\)

\(\langle x + y, z \rangle = \langle x, z\rangle + \langle y,z \rangle\)

\(\langle x, x \rangle \ge 0\)

\(\langle x,x \rangle = 0\) only if \(x = 0\)

For any space over which an inner product is defined, there is a natural (i.e. often convenient) norm that can be defined.

Lemma 1.1 Let \(X\) be a space and \(\langle \cdot, \cdot \rangle\) be an inner product defined on \(X\). Then \(\sqrt{\langle \cdot, \cdot \rangle}\) is a norm on the space \(X\).

Proof. Write \(\|x\| = \sqrt{\langle x, x\rangle}\). Positivity and homogeneity are immediate from the inner-product axioms (Definition 1.4): \(\|x\| \ge 0\) with \(\|x\| = 0\) only if \(x = 0\), and \(\|\alpha x\| = \sqrt{\langle \alpha x, \alpha x\rangle} = \sqrt{\alpha^{2}\langle x,x\rangle} = |\alpha|\,\|x\|\). Only the triangle inequality requires work, and it rests on the Cauchy–Schwarz inequality \[|\langle x, y\rangle| \le \|x\|\,\|y\|.\] To prove Cauchy–Schwarz, assume \(y \ne 0\) (the case \(y = 0\) is trivial). For every \(t \in \mathbb{R}\), \[0 \le \langle x - ty,\, x - ty\rangle = \|x\|^{2} - 2t\langle x, y\rangle + t^{2}\|y\|^{2}.\] This quadratic in \(t\) is nonnegative for all \(t\), so its discriminant is nonpositive: \(4\langle x,y\rangle^{2} - 4\|x\|^{2}\|y\|^{2} \le 0\), which is exactly \(|\langle x,y\rangle| \le \|x\|\,\|y\|\). Now \[\|x + y\|^{2} = \|x\|^{2} + 2\langle x, y\rangle + \|y\|^{2} \le \|x\|^{2} + 2\|x\|\,\|y\| + \|y\|^{2} = \big(\|x\| + \|y\|\big)^{2},\] and taking square roots gives \(\|x + y\| \le \|x\| + \|y\|\). Hence \(\sqrt{\langle\cdot,\cdot\rangle}\) satisfies all three norm axioms.

However, not all norms need be generated by an inner product.

1.3 Linear functionals, hyperplanes and convex sets

Definition 1.5 Let \(X\) be a vector space. A function \(f:X \rightarrow \mathbb{R}\) is linear if for any two \(\alpha, \beta \in \mathbb{R}\), \(f(\alpha x + \beta y) = \alpha f(x) + \beta f(y)\). We call such a function a linear functional.

Definition 1.6 The set of all bounded linear functionals over the normed vector space \(X\) is called the dual space of \(X\) and is denoted \(X^{*}\).

Examples.

Consider the following dual spaces:

The dual of \(\mathbb{R}^n\) is the set of all functions of the form \(f(x) = a\cdot x\) for \(a \in \mathbb{R}^n\).

Let \(\ell_p\) be the space of infinite sequences of real numbers for which \(\sum_{i=0}^{\infty}|x_{i}|^{p} < \infty\). The typical norm defined over this space is \(||x||_{p} = \left ( \sum_{i=0}^{\infty}|x_{i}|^{p} \right )^{1/p}\). If \(q\) is such that \(1/p + 1/q = 1\), then the dual of \(\ell_{p}\) is \(\ell_{q}\).

Let \(C_p[a,b]\) be the space of continuous functions over the interval \([a,b]\) for which \(\int_{a}^{b}|x(t)|^{p}dt < \infty\). The typical norm defined over this space is \(||x||_{p} = \left ( \int_{t=a}^{b}|x(t)|^{p}dt \right )^{1/p}\). If \(q\) is such that \(1/p + 1/q = 1\), then every \(a \in C_{q}[a,b]\) defines a bounded linear functional on \(C_{p}[a,b]\) via \(f(x) = \int_{a}^{b}a(t)x(t)dt\). (Strictly speaking, the full dual of this space is the larger space \(L^{q}[a,b]\); the continuous functions give a natural family of examples.)

Exercises.

Check that for a vector \(a \in \mathbb{R}^n\), the functional \(f(x) = a'\cdot x\) is a linear functional.
Let \(a = (a_{0},a_{1},a_{2},\ldots) \in \ell_{q}\). Check that for any \(x \in \ell_{p}\), \(\sum_{t=0}^{\infty}a(t)x(t)\) is a linear functional. Why must \(p\) and \(q\) satisfy the equation in example 2 above?
Let \(a:[0,1] \rightarrow \mathbb{R}\) be in \(C_{q}[0,1]\). Show that for any \(x \in C_{p}[0,1]\), \(\int_{0}^{1}a(t)x(t)dt\) is a linear functional. Why must \(p\) and \(q\) satisfy the equation in example 3 above?

A linear functional can also be used to describe particular subsets of a vector space \(X\) called hyperplanes.

Definition 1.7 Let \(f \in X^{*}\) be a linear functional over the set \(X\). Consider the set \(\{x: f(x) = c \}\) for some \(c \in \mathbb{R}\). We call this set the hyperplane in \(X\) defined by the pair \((f,c)\).

Examples.

Let \(a = (a_{1},a_{2})\). Consider the set of vectors \(H = \{x \in \mathbb{R}^{2}:a \cdot x = c\}\). Geometrically, this set looks like a (1-dimensional) line running through \(\mathbb{R}^{2}\). For \(b = (b_{1},b_{2},b_{3}) \in \mathbb{R}^{3}\), the set \(H = \{x \in \mathbb{R}^{3}: b\cdot x = c\}\) is a two-dimensional plane in three dimensional space (this is where the phrase hyperplane comes from). In general, for \(x \in \mathbb{R}^{n}\), if \(d \in (\mathbb{R}^{n})^{*}\) then \(H = \{x \in \mathbb{R}^{n}: d \cdot x = c \}\) is a \((n-1)\)-dimensional hyperplane in \(\mathbb{R}^{n}\).
Let \(X = \ell_{p}\). For any linear functional \(f \in \ell_{q}\), the set \(H = \{x \in X: f(x) = c\}\) can be thought of as hyperplane in \(\ell_{p}\).

Linear functionals are especially useful as a means for describing convex sets. To see this, define the set \(H_{-} = \{x:f(x) \le c \}\) and \(H_{+} = \{x:f(x) \ge c \}\) as the two closed half-spaces defined by the hyperplane \(H = \{x:f(x) = c \}\).

First, think about a closed convex and compact set \(K \subseteq X\) (where \(X\) is a metric space), a linear functional \(f \in X^{*}\) and the function \(h(f,K): X^{*} \rightarrow \mathbb{R}\) defined by

\[h(f,K) = \min_{x \in K} f(x)\]

Since \(K\) is compact, the minimum always exists and this function is well defined. Furthermore, the following theorem shows that every half-space defined by \(H(f) = \{x: f(x) = h(f,K)\}\) either contains all of \(K\) or only things on the boundary of \(K\).

Proposition 1.1 If \(K\) is a closed convex set and \(x \notin K\), there is a closed half-space that contains \(K\) but does not contain \(x\).

Proof. Work in \(\mathbb{R}^{n}\) (or any inner-product space) and let \(x \notin K\). Because \(K\) is closed and convex, it has a unique point \(p \in K\) nearest to \(x\) in the norm \(\|\cdot\| = \sqrt{\langle\cdot,\cdot\rangle}\). (Existence: minimizing the continuous function \(z \mapsto \|x - z\|\) over the intersection of \(K\) with a large closed ball around \(x\) — a compact set — yields a minimizer. Uniqueness: if \(p_{1}, p_{2} \in K\) were both nearest, their midpoint lies in \(K\) by convexity and, by the parallelogram law, is strictly closer to \(x\) unless \(p_{1} = p_{2}\).)

Let \(a = x - p \ne 0\). We first establish the variational inequality \(\langle a, z - p\rangle \le 0\) for every \(z \in K\). Fix \(z \in K\); by convexity \(p + t(z - p) \in K\) for \(t \in [0,1]\), so \(\phi(t) = \|x - p - t(z - p)\|^{2}\) is minimized over \([0,1]\) at \(t = 0\). Since \(\phi'(0) = -2\langle a, z - p\rangle \ge 0\), we obtain \(\langle a, z - p\rangle \le 0\).

Thus \(\langle a, z\rangle \le \langle a, p\rangle\) for all \(z \in K\). Put \(f(z) = \langle a, z\rangle\) and \(c = \langle a, p\rangle + \tfrac{1}{2}\|a\|^{2}\). Every \(z \in K\) then satisfies \(f(z) \le \langle a, p\rangle < c\), so \(K \subset \{z : f(z) \le c\}\), while \(f(x) = \langle a, p + a\rangle = \langle a, p\rangle + \|a\|^{2} > c\). The closed half-space \(\{z : f(z) \le c\}\) therefore contains \(K\) but not \(x\).

Thus, the linear functional \(f\) defines a hyperplane that separates or supports the space \(K\) from the rest of the space \(X\). So we call this a separating hyperplane. A slightly more surprising result is that for a convex set, the intersection of all half-spaces defined by separating hyperplanes uniquely defines any convex set \(K\).

Proposition 1.2 (Dual characterization) If \(K\) is a closed convex set in a normed space, then \(K\) is equal to the intersection of all of the closed half-spaces that contain it.

Proof. Let \(K'\) be the intersection of all closed half-spaces that contain \(K\). Every such half-space contains \(K\), so \(K \subseteq K'\). For the reverse inclusion, take any \(x \notin K\). By Proposition 1.1 there is a closed half-space \(H\) with \(K \subseteq H\) and \(x \notin H\). Since \(H\) is one of the half-spaces defining \(K'\), we have \(K' \subseteq H\), and therefore \(x \notin K'\). Thus every point outside \(K\) is outside \(K'\), i.e. \(K' \subseteq K\). Combining the inclusions, \(K = K'\).

This idea of defining convex sets through separating hyperplanes has found significant use in economic theory. You used it when you first defined budget constraints. We will see it several times this year.

Definition 1.8 A closed hyperplane \(H\) in a normed space \(X\) is said to be a support (or supporting hyperplane) for the convex set \(K\) if \(K\) is contained in one of the closed half-spaces determined by \(H\) and \(H\) contains a point of \(\overline{K}\).

1.4 Differentials (or derivatives) in general vector spaces

For the next two definitions, let \(X\) be a vector space and \(Y\) a normed vector space.

Definition 1.9 Let \(x \in D \subset X\), \(h \in X\) and \(f:X \rightarrow Y\). If the limit

\[\delta f(x,h) = \lim_{\alpha \rightarrow 0}\frac{1}{\alpha}\left [ f(x + \alpha h) - f(x)\right]\]

exists, it is called the Gateaux differential of \(f\) in the direction \(h\). If this differential exists for all \(h \in X\) then \(f\) is said to be Gateaux differentiable at \(x\).

Exercise 1.3 Let \(X = \mathbb{R}^2\) and let \(f(x) = Ax_{1}^{\alpha}x_{2}^{1-\alpha}\). What is \(\delta f(x,(a,b))\)?

The definition asks us to do only one-dimensional calculus: perturb \(x\) in a fixed direction \(h\), differentiate with respect to the scalar \(\alpha\), and evaluate at \(\alpha = 0\). The following examples work this recipe out in detail, moving from Euclidean space to spaces of functions.

Example 1.4 (A quadratic form on \(\mathbb{R}^{n}\)) Let \(X = \mathbb{R}^{n}\) and \(f(x) = x^{\top}Qx\) where \(Q\) is a symmetric \(n \times n\) matrix. Fix a direction \(h \in \mathbb{R}^{n}\). Expanding,

\[f(x + \alpha h) = (x + \alpha h)^{\top}Q(x + \alpha h) = x^{\top}Qx + 2\alpha\, x^{\top}Qh + \alpha^{2}\, h^{\top}Qh,\]

where we used the symmetry of \(Q\) to combine the cross terms (\(h^{\top}Qx = x^{\top}Qh\)). Therefore

\[\frac{1}{\alpha}\left[ f(x + \alpha h) - f(x) \right] = 2 x^{\top}Qh + \alpha\, h^{\top}Qh \xrightarrow{\alpha \to 0} 2x^{\top}Qh.\]

So \(\delta f(x,h) = 2x^{\top}Qh\). Notice that this is exactly \(\nabla f(x) \cdot h\): in Euclidean space the Gateaux differential is the familiar directional derivative, and it is linear in the direction \(h\).

Example 1.5 (An integral functional on a space of continuous functions) Now let \(X = C[a,b]\), the space of continuous functions on \([a,b]\), and consider \(F: X \rightarrow \mathbb{R}\) given by

\[F(x) = \int_{a}^{b} x(t)^{2}\, dt.\]

Here a “point” \(x\) is an entire function and a “direction” \(h\) is also a function. For \(h \in C[a,b]\),

\[F(x + \alpha h) = \int_{a}^{b} \left( x(t) + \alpha h(t) \right)^{2} dt = \int_{a}^{b} x(t)^{2}\, dt + 2\alpha \int_{a}^{b} x(t)h(t)\, dt + \alpha^{2}\int_{a}^{b} h(t)^{2}\, dt.\]

Then

\[\frac{1}{\alpha}\left[ F(x + \alpha h) - F(x) \right] = 2\int_{a}^{b} x(t)h(t)\, dt + \alpha \int_{a}^{b} h(t)^{2}\, dt \xrightarrow{\alpha \to 0} 2\int_{a}^{b} x(t)h(t)\, dt.\]

So \(\delta F(x,h) = 2\int_{a}^{b} x(t)h(t)\, dt\). Compare with the previous example: the sum \(2x^{\top}Qh = 2\sum_{i,j} x_{i}Q_{ij}h_{j}\) has become an integral, but the structure — a linear functional pairing the “gradient” \(2x(t)\) with the direction \(h(t)\) — is identical.

Example 1.6 (A discounted utility functional) Let \(X = C[0,T]\) and consider the lifetime utility functional

\[U(c) = \int_{0}^{T} e^{-\beta t}\, u(c(t))\, dt,\]

where \(u\) is continuously differentiable. Here the direction \(h\) is a perturbation of the entire consumption path. Define \(g(\alpha) = U(c + \alpha h)\) and differentiate under the integral sign:

\[g'(\alpha) = \frac{d}{d\alpha}\int_{0}^{T} e^{-\beta t}\, u\left(c(t) + \alpha h(t)\right) dt = \int_{0}^{T} e^{-\beta t}\, u'\left(c(t) + \alpha h(t)\right) h(t)\, dt.\]

Evaluating at \(\alpha = 0\) gives

\[\delta U(c,h) = \int_{0}^{T} e^{-\beta t}\, u'(c(t))\, h(t)\, dt.\]

The economic content: \(e^{-\beta t}u'(c(t))\) is the discounted marginal utility of consumption at time \(t\), and the Gateaux differential aggregates the utility consequences of the perturbation \(h\) across the whole horizon. Setting \(\delta U(c,h) = 0\) for all admissible \(h\) is precisely the first-order condition we will exploit in the calculus of variations below.

Now, how can we use these generalized derivatives? As with traditional derivatives defined over Euclidean space, we have the following result.

Theorem 1.1 Let \(f: X \rightarrow \mathbb{R}\) have a Gateaux differential on a vector space \(X\). Then if \(f\) has an extremum at \(x_{0} \in X\) then \(\delta f(x_{0};h) = 0\) for all \(h \in X\).

Proof. For all \(h \in X\), define \(\hat{f}(\alpha; h) = f(x_{0} + \alpha h)\). If \(f(x_{0})\) has an extremum at \(x_{0}\) then \(\hat{f}(\alpha;h)\) must be maximized at \(\alpha = 0\). But since \(\alpha\) is a real number, we can use ordinary calculus and discover that this must imply that

\[\left. \frac{d}{d\alpha}f(x_{0} + \alpha h)\right \vert_{\alpha = 0} = 0.\]

This then implies that the Gateaux differential is zero in the direction \(h\). Since this must hold for all \(h\), the result is proved.

1.4.1 Calculus of variations and an intertemporal savings and consumption problem

Recall that \(D_{[a,b]}\) is the set of all differentiable functions with continuous derivatives. Consider the function \(U:D_{[a,b]} \rightarrow \mathbb{R}\) given by

\[U(x) = \int_{a}^{b} u(x(t),\dot{x}(t),t)dt\]

This function takes as an argument a continuous differentiable function \(x\) and returns a real number. What if we wanted to maximize the function \(U\) with respect to the choice of \(x \in D_{[a,b]}\). This class of problem is known as the calculus of variations. From our previous work, we know that to maximize this function, we are likely going to need to know how to calculate the (Gateaux) differential of \(U\) in the direction \(h\). Let’s think about that.

By definition, the differential is

\[\partial U(x;h) = \left. \frac{d}{d\alpha}\int_{a}^{b} u(x + \alpha h, \dot{x} + \alpha \dot{h}, t)dt\right \vert_{\alpha = 0}\]

Application of the chain rule shows that this implies the necessary condition

\[\partial U(x;h) = \int_{a}^{b} u_{x}(x, \dot{x}, t)h(t)dt + \int_{a}^{b} u_{\dot{x}}(x, \dot{x}, t)\dot{h}(t)dt = 0\]

Remember that integration by parts says that \(\int_{a}^{b} u dv = \left . uv \right \vert_{a}^{b} - \int_{a}^{b} v du\). Applying this to the second of the two terms above gives

\[\int_{a}^{b} u_{x}(x, \dot{x}, t)h(t)dt +\left . u_{\dot{x}}(x,\dot{x},t)h(t) \right \vert_{a}^{b} - \int_{a}^{b} \frac{d}{dt}u_{\dot{x}}(x,\dot{x},t)h(t)dt = 0\]

The boundary term \(\left. u_{\dot{x}}(x,\dot{x},t)h(t) \right\vert_{a}^{b}\) must be zero: admissible variations hold the endpoints fixed, so \(h(a) = h(b) = 0\) — a competing path \(x + \alpha h\) must still hit the prescribed boundary values \(x(a)\) and \(x(b)\) — and hence \(u_{\dot{x}}h\) vanishes at both \(a\) and \(b\). Combining terms gives

\[\int_{a}^{b} \left ( u_{x}(x, \dot{x}, t) - \frac{d}{dt}u_{\dot{x}}(x,\dot{x},t) \right) h(t)dt = 0\]

Since this holds for every admissible variation \(h\), the term in parentheses must be zero everywhere — this is the fundamental lemma of the calculus of variations. (If the continuous factor \(u_{x} - \frac{d}{dt}u_{\dot{x}}\) were nonzero, say positive, at some interior \(t_{0}\), then by continuity it would stay positive on an interval around \(t_{0}\); choosing a continuous \(h\) that is positive on that interval and zero outside it — and zero at the endpoints — would make the integral strictly positive, contradicting that it vanishes for all \(h\).) Therefore, a solution \(x(t)\) is optimal only if

\[u_{x}(x, \dot{x}, t) - \frac{d}{dt}u_{\dot{x}}(x,\dot{x},t) = 0\]

This is an ordinary differential equation (in general of second order, since \(\frac{d}{dt}u_{\dot{x}}\) involves \(\ddot{x}\)) that must be solved. We are looking for a function \(x\) that solves this equation. The best method of solving this equation will vary based on \(u\). Let’s consider a particular example from economics.

Example 1.7 Suppose that at every instant in time \(t\) you must choose your \(c(t)\). Savings receives a rate of return of \(r\). Then wealth \(x(t)\) evolves according to \(\dot{x}(t) = rx(t) - c(t)\). Given the vN-M utility function \(u(c)\) (which satisfies \(u'(c)> 0\) and \(u''(c) < 0\)) the individual has preferences

\[U(c) = \int_{0}^{T}e^{-\beta t}u(c(t))dt\]

subject to the boundary conditions on wealth \(x(0) = S\) and \(x(T) = 0\) (the individual starts with wealth \(S\) and exhausts it by time \(T\)). From the equation above we have that

\[re^{-\beta t}u'(c(t)) + \frac{d}{dt}e^{-\beta t}u'(c(t)) = 0\]

which implies that

\[\frac{d}{dt} u'(c(t)) = (\beta - r)u'(c(t))\]

Solving this o.d.e. gives

\[u'(c(t)) = u'(c(0))e^{(\beta - r)t}\]

This is a Keynes–Ramsey condition. Because \(u'' < 0\), marginal utility \(u'(c(t))\) and consumption \(c(t)\) move in opposite directions, so the sign of \(\beta - r\) determines the tilt of the optimal consumption path: if the individual is impatient relative to the market (\(\beta > r\)), marginal utility rises over time and consumption falls; if \(\beta < r\) consumption rises; and if \(\beta = r\) consumption is constant. Impatience and the return on saving pull consumption in opposite directions.

Now, let’s plug in a utility function for this. Consider \(u(c) = \frac{1}{1-\gamma}c^{1-\gamma}\), so that \(u'(c) = c^{-\gamma}\). Then the condition above becomes \[c(t)^{-\gamma} = c(0)^{-\gamma}e^{(\beta - r)t}.\] Solving for \(c(t)\) gives the optimal consumption path \[c(t) = c(0)\,e^{\frac{r - \beta}{\gamma}t},\] so consumption grows (or shrinks) at the constant rate \(\frac{r - \beta}{\gamma}\). The parameter \(1/\gamma\) — the elasticity of intertemporal substitution — scales how strongly the consumer responds to the gap between the return \(r\) and the discount rate \(\beta\): a lower \(\gamma\) (greater willingness to substitute across time) produces a steeper path. The level \(c(0)\) is pinned down by the budget and boundary conditions of the problem (integrating \(\dot{x} = rx - c\) against the prescribed initial and terminal wealth).

1.4.2 Euler equations and another intertemporal savings and consumption problem

Consider the discrete time analog of the above problem. The consumption set is \(\ell_{\infty}\). Given wealth \(w_{t}\) and consumption \(c_{t}\) at time \(t\), let savings have return \(r\). Therefore, the budget constraint at time \(t\) is \(c(t) + s(t) = w(t)\) (total wealth must be split between consumption and savings). Since the return on savings is \((1+r)\), wealth at time \(t+1\) will be \(w(t+1) = s(t)(1+r)\). A consumption path is an infinite sequence of consumption elements and preferences over these consumption streams are given by

\[U(c) = \sum_{t = 0}^{\infty}\beta^{t}u(c(t))\]

where \(c(t)\) is the consumption at time \(t\). Plugging in the budget constraint above, we have the unconstrained optimization problem

\[U(c) = \sum_{t = 0}^{\infty}\beta^{t}u\left( w(t) - s(t) \right)\]

In this case, one will choose an infinite sequence of savings amounts \(s(t)\) to maximize this function. Now, consider the Gateaux differential in a particular direction. Specifically, consider a path \(\{s(t)\}\) and the direction \(h = e_{t}\), the sequence that is one at time \(t\) and zero elsewhere — that is, imagine increasing savings by \(\alpha\) at time \(t\) only. Notice that this decreases consumption at time \(t\) and increases wealth (and hence consumption) at time \(t+1\), leaving all other periods unchanged. In this case, the perturbed objective is

\[U(s + \alpha h) = u(c(0)) + \cdots + \beta^{t}u\left(w(t) - s(t) - \alpha\right) + \beta^{t+1}u\left((s(t) + \alpha)(1+r) - s(t+1)\right) + \cdots\]

Taking the derivative of this with respect to \(\alpha\) yields the first order condition

\[0 = -\beta^{t}u'(c_{t}) + \beta^{t+1}u'(c_{t+1})(1+r)\]

Dividing through by \(\beta^{t}\) and rearranging this FOC yields the equation

\[u'(c_{t}) = \beta (1+r) u'(c_{t+1})\]

\[\frac{\beta u'(c_{t+1})}{u'(c_{t})} = \frac{1}{1+r}\]

which has the familiar interpretation of the LHS being the the individual’s internal tradeoff between consumption today and consumption tomorrow and the RHS is the market tradeoff between consumption today and consumption tomorrow.

Now, suppose that \(u(c) = -e^{-\gamma c}\), so that \(u'(c) = \gamma e^{-\gamma c}\). In this case, this first order equation becomes

\[\beta\frac{\gamma e^{-\gamma c_{t+1}}}{\gamma e^{-\gamma c_{t}}} = \beta e^{-\gamma(c_{t+1}-c_{t})} = \frac{1}{1+r}\]

which implies that \(c_{t+1} = c_{t} + \frac{1}{\gamma}\log \beta(1+r)\) at an interior optimum.

Excercise.: Solve the problem above for CRRA utility function \(u(c) = \frac{c^{1-\gamma}}{1-\gamma}\) (Hint, use consumption fractions instead of consumption amounts)

1.5 Constrained optimization

Consider now a set of constraints written implicitly in the vector space \(X\) of the form

\[\begin{aligned} g_{1}(x) & = 0 \\ g_{2}(x) & = 0 \\ \vdots \\ g_{n}(x) & = 0 \end{aligned}\]

For now, let us consider strictly concave/convex objective functions (so as to ignore second order conditions for now).

Definition 1.10 A function \(f\) is convex if \(f(\alpha x_{1} + (1-\alpha)x_{2}) \le \alpha f(x_{1}) + (1-\alpha) f(x_{2})\)

Definition 1.11 A function \(f\) is concave if \(f(\alpha x_{1} + (1-\alpha)x_{2}) \ge \alpha f(x_{1}) + (1-\alpha) f(x_{2})\)

What is the relationship between a convex function and convex sets? Here is one.

Definition 1.12 The upper contour set of the function \(f\) at \(c\) is the set \(\{x \in X: f(x) \ge c\}\). The lower contour set if the set \(\{x \in X: f(x) \le c\}\).

Proposition 1.3 Let \(f\) be a convex function. Then the set \(\{x: f(x) \le c\}\) is convex. Likewise, if \(f\) is concave then the set \(\{x:f(x) \ge c\}\) is convex.

This implication, that concave functions have convex upper contour sets has led to the question of whether only concave functions have convex upper contour sets. The answer is no. Since convex upper contour sets are an important part of both the theory of demand and general equilibrium theory, the following generalization of concavity is often used in economics.

Definition 1.13 A function is said to be quasiconcave if all of its upper contour sets are convex. Specifically, for all \(x, x'\) with \(f(x) \ge c\) and \(f(x') \ge c\) and all \(\alpha \in [0,1]\), it is the case that \(f(\alpha x + (1-\alpha)x') \ge c\). The function is strictly quasiconcave if the last inequality is strict whenever \(x \ne x'\) and \(\alpha \in (0,1)\).

Lemma 1.2 A function \(f\) is quasiconcave if and only if \(f(\alpha x + (1-\alpha)x') \ge \mbox{min }\{f(x),f(x')\}\).

One nice property of quasiconcavity is that it is always preserved under increasing transformations. On the other hand, concavity is not necessarily preserved under increasing transformations. Properties that are not preserved under increasing transformations are called cardinal properties.

1.5.1 Lagrangians

From 380, we have all become intimately familiar with Lagrangians. To get intuition for the role of a Lagrangian, consider maximizing the function \(f(x) = \ln x\) subject to the constraint \(x \le 10\). The answer to this problem is obviously \(x = 10\) but it is useful to analyze it anyway.

Consider this problem’s Lagrangian:

\[L(x,\lambda) = \ln x + \lambda ( 10 - x)\]

Notice that \(\frac{\partial L}{\partial x} = \frac{1}{x} - \lambda\), so if \(\lambda\) is large enough (here \(\lambda \ge 1/10\)), the Lagrangian is decreasing in \(x\) everywhere beyond \(x = 10\) — moving past the constraint is penalized more than it helps the objective. Therefore, the role of the Lagrangian is to create an alternative objective function for which, given the right choice of \(\lambda\), the solution to the unconstrained maximization problem associated with the Lagrangian coincides with the solution to the constrained maximization problem of the original objective.

In general spaces like that described above, we note that we can describe the problem to be solved as

\[\mbox{maximize } f(x) \mbox{ subject to } H(x) = \mathbf{0}\]

where \(H(x) = [g_{1}(x),g_{2}(x),\ldots,g_{n}(x)]\) and \(\mathbf{0}\) is the \(n\)-dimensional zero vector. In this situation, we can write the Lagrangian as

\[L(x,\mathbf{\lambda}) = f(x) - \langle H(x), \mathbf{\lambda} \rangle\]

where \(\langle \cdot,\cdot \rangle\) is the usual inner product on \(\mathbb{R}^{n}\) and \(\mathbf{\lambda}\) is a vector of Lagrange multipliers. (The sign in front of the multiplier term is a convention; we adopt the minus sign here so that it matches the example above, where \(\lambda(10 - x) = -\lambda(x - 10)\), and the Kuhn-Tucker conditions below.)

As can be seen, the Lagrange multiplier \(\lambda\) is a linear functional. As such, it maps the extent to which a particular \(x\) satisfies (or violates) the constraints \(H(x)\) into values that are comparable to the objective function \(f\).

1.5.2 Kuhn-Tucker Conditions

In the case of \(\mathbb{R}^{n}\), the Lagrangian takes a particularly useful form.

First, we define the constraint qualification. Let \(G(x) = [g_{1}(x),g_{2}(x),\ldots,g_{M}(x)] = \mathbf{0}'\) be a set of constraints. We say that the constraint qualification holds for this set at a point \(x_{0}\) if the partial derivative matrix \(D_{x}G(x)\) has rank \(M\). Recall that \(D_{x}G(x)\) is the \(M \times N\) matrix of partial derivatives of \(G(x)\).

Example 1.8 Let \(f(x,y) = -(x-2)^2 - (y-2)^2\). Consider the problem \(\max_{x,y}f(x,y)\) subject to the constraints \(x - 3y = 0, 3x - 2y = 0, 4x + y = 0\). In this case, the derivative matrix is

\[D_{x}G(x) = \begin{pmatrix} 1 & -3 \\ 3 & -2 \\ 4 & 1 \end{pmatrix}\]

We notice that this has rank 2 \(\ne 3\) and as such, the constraint qualification does not hold. (With two variables the rank can never reach 3, so it fails at every point.) Note that the problem is still feasible: the three lines all pass through the origin, so the feasible set is \(\{(0,0)\}\) and the solution is trivially \((x,y) = (0,0)\). The lesson is that because the constraint qualification fails there, the Lagrange/Kuhn-Tucker conditions need not hold at this solution — the failure is of the first-order characterization, not of feasibility.

Before stating the theorem we record its key tool. Farkas’ lemma is a theorem of the alternative: it converts the geometric statement “no direction simultaneously improves the objective and respects the constraints” into the algebraic statement “the objective gradient is a nonnegative combination of the constraint gradients.”

Lemma 1.3 (Farkas’ lemma) Let \(A\) be an \(m \times n\) matrix and \(b \in \mathbb{R}^{n}\). Exactly one of the following holds:

there exists \(y \in \mathbb{R}^{m}\) with \(y \ge \mathbf{0}\) and \(A'y = b\); or

there exists \(v \in \mathbb{R}^{n}\) with \(Av \le \mathbf{0}\) and \(\langle b, v\rangle > 0\).

Proof. The two alternatives cannot hold at once: if \(y \ge \mathbf{0}\) solves \(A'y = b\) and \(Av \le \mathbf{0}\), then \(\langle b, v\rangle = \langle A'y, v\rangle = \langle y, Av\rangle = \sum_{i} y_{i}(Av)_{i} \le 0\), contradicting \(\langle b, v\rangle > 0\).

It remains to show at least one holds. Let \(C = \{A'y : y \ge \mathbf{0}\}\) be the cone generated by the rows of \(A\). As the conical hull of finitely many vectors it is a closed convex cone, and \(\mathbf{0} \in C\). If \(b \in C\), alternative 1 holds. If \(b \notin C\), then by the separating-hyperplane theorem (Proposition 1.1) there are a vector \(v\) and a scalar \(c\) with \[\langle v, z\rangle \le c \ \text{ for all } z \in C, \qquad \langle v, b\rangle > c.\] Since \(\mathbf{0} \in C\), taking \(z = \mathbf{0}\) gives \(c \ge 0\). Since \(C\) is a cone, for any \(z \in C\) and \(t > 0\) we have \(tz \in C\), so \(t\langle v, z\rangle \le c\) for all \(t > 0\); letting \(t \to \infty\) forces \(\langle v, z\rangle \le 0\) for every \(z \in C\). Applying this to the generators \(z = A'e_{i}\) (the \(i\)-th row of \(A\)) gives \((Av)_{i} = \langle v, A'e_{i}\rangle \le 0\) for each \(i\), i.e. \(Av \le \mathbf{0}\); and \(\langle b, v\rangle > c \ge 0\). So \(v\) satisfies alternative 2.

An equality constraint \(a'v = 0\) is the pair of inequalities \(a'v \le 0\) and \(-a'v \le 0\). Applying the lemma to such a stacked system therefore produces a free-sign multiplier for each equality (the difference of the two associated nonnegative multipliers) and a nonnegative multiplier for each genuine inequality — exactly the multiplier structure of the Kuhn–Tucker conditions below.

Theorem 1.2 Consider the problem \(\max f(x)\) subject to the constraints \(G(x) = \mathbf{0}\) and \(H(x) \le \mathbf{0}\). Then, let \(\lambda\) be the Lagrange multipliers for \(G(x)\) and \(\gamma\) be those for \(H(x)\). If the solution \(x_{0}\) of this problem satisfies the constraint qualification then it also satisfies

\[\begin{aligned} D_{x}f(x) - \lambda' D_{x}G(x) - \gamma' D_{x}H(x) & = \mathbf{0} \\ G(x) & = \mathbf{0} \\ H(x) & \le \mathbf{0} \\ \gamma & \ge \mathbf{0} \\ \gamma_{i} H_{i}(x) & = 0 \mbox{ for all } i \end{aligned}\]

Proof. We give the argument; the constraint qualification is exactly what makes it work.

Equality constraints only. Suppose first there are no inequality constraints, so the problem is \(\max f(x)\) subject to \(G(x) = \mathbf{0}\). Because \(D_{x}G(x_{0})\) has full rank \(M\) (the constraint qualification), the implicit function theorem implies that near \(x_{0}\) the constraint set \(\{x : G(x) = \mathbf{0}\}\) is a smooth \((N - M)\)-dimensional surface whose tangent space at \(x_{0}\) is exactly \(\ker D_{x}G(x_{0}) = \{v : D_{x}G(x_{0})v = \mathbf{0}\}\). If \(x_{0}\) maximizes \(f\) on this surface, then along any curve in the surface through \(x_{0}\) the derivative of \(f\) vanishes, so \(D_{x}f(x_{0})v = 0\) for every \(v \in \ker D_{x}G(x_{0})\). A linear functional that vanishes on \(\ker D_{x}G(x_{0})\) lies in the row space of \(D_{x}G(x_{0})\); that is, there is a vector \(\lambda\) with \(D_{x}f(x_{0}) = \lambda' D_{x}G(x_{0})\).

Adding inequality constraints. Now include \(H(x) \le \mathbf{0}\). Call constraint \(i\) active at \(x_{0}\) if \(H_{i}(x_{0}) = 0\) and inactive if \(H_{i}(x_{0}) < 0\). An inactive constraint holds with strict slack throughout a neighborhood of \(x_{0}\), so it imposes no first-order restriction; we set \(\gamma_{i} = 0\) for such \(i\), which is precisely complementary slackness \(\gamma_{i}H_{i}(x_{0}) = 0\). A first-order feasible variation \(v\) must satisfy \(D_{x}G(x_{0})v = \mathbf{0}\) and \(D_{x}H_{i}(x_{0})v \le 0\) for each active \(i\). Optimality of \(x_{0}\) means no feasible variation increases \(f\): there is no \(v\) with \[D_{x}G(x_{0})v = \mathbf{0}, \quad D_{x}H_{i}(x_{0})v \le 0 \ (\text{active } i), \quad D_{x}f(x_{0})v > 0.\] By Farkas’ lemma (Lemma 1.3) — writing each equality \(D_{x}G(x_{0})v = \mathbf{0}\) as the pair \(D_{x}G(x_{0})v \le \mathbf{0}\) and \(-D_{x}G(x_{0})v \le \mathbf{0}\) — the unsolvability of this system is equivalent to the existence of multipliers \(\lambda\) (unrestricted, for the equalities) and \(\gamma_{i} \ge 0\) (for the active inequalities) with \[D_{x}f(x_{0}) = \lambda' D_{x}G(x_{0}) + \sum_{i \text{ active}} \gamma_{i}\, D_{x}H_{i}(x_{0}).\] Extending the sum over all \(i\) by setting \(\gamma_{i} = 0\) for the inactive constraints gives \[D_{x}f(x_{0}) - \lambda' D_{x}G(x_{0}) - \gamma' D_{x}H(x_{0}) = \mathbf{0},\] together with \(G(x_{0}) = \mathbf{0}\) and \(\gamma_{i}H_{i}(x_{0}) = 0\) (with \(\gamma_{i} \ge 0\)) for all \(i\). These are the stated Kuhn–Tucker conditions.

Example.

Maximize \(f(x) = -(x-2)^{2}\) subject to \(H(x) = x - 1 \le 0\). The Kuhn–Tucker conditions are \(f'(x) - \gamma H'(x) = 0\) with \(\gamma \ge 0\) and complementary slackness \(\gamma H(x) = 0\); here \(-2(x - 2) - \gamma = 0\). If the constraint is slack (\(\gamma = 0\)) then \(x = 2\), which violates \(x \le 1\), so this case is infeasible. Hence the constraint binds: \(x = 1\), giving \(\gamma = -2(1 - 2) = 2 \ge 0\). The optimum is \(x = 1\) with multiplier \(\gamma = 2\); the unconstrained maximizer \(x = 2\) is cut off by the constraint, and the positive multiplier measures the rate at which the objective would improve if the constraint were relaxed.

Excercises.

Write down the Kuhn-Tucker conditions for the following problems. Solve if possible.

\(\max -(x-2)^{2}\) s.t. \(x \ge 0, x \le 4\)

\(\max -(x-2)^{2} - (y-2)^{2}\) s.t. \(x \ge 0, y \ge 0, xy = 4\)

\(\max \sum_{t=0}^{\infty} \beta^{t}ln x(t)\) s.t. \(x(0) \le w(0)\), \(w(t+1) = w(t) - x(t)\) (Think carefully about what \(x\) is and what \(G(x)\) and \(H(x)\) are).

\(\max x + \ln y\) s.t. \(ax + by \le w\), \(x \ge 0, y \ge 0\).