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\).

Excercise.: Prove the previous lemma.

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 the dual of \(C_{p}[a,b]\) is \(C_{q}[a,b]\).

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 \ell_{p}\), \(\int_{0}^{1}a(t)x(t)\) 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\).

Idea behind proof.: Draw circle and dot.

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.

Idea behind proof.: Draw picture of circle.

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 Gateaux differential is useful, but if we are willing to assume that the space \(X\) has a metric then we can use a more specific definition

Definition 1.10 Let \(X\) and \(Y\) be normed vector spaces and let \(D \subseteq X\) be an open subset of \(X\). If for some \(x \in D\) and every \(h \in X\) there exists

\[\lim_{||h|| \rightarrow 0} \frac{||f(x + h) - f(x) - \partial f(x;h)||}{||h||} = 0\]

then \(f\) is Frechet differentiable at \(x\) and \(\partial f(x;h)\) is the Frechet differential of \(f\) at \(x\) with increment \(h\).

Proposition 1.3 If the Frechet differential of \(f\) exists at \(x\) then the Gateaux differential exists at \(x\) and they are equal.

Proof. Luenberger, page 173.

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) = 0\]

The last of these terms must be zero [EXPLAIN]. 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 \(h\) is continuous, the integrand above must be zero everywhere [EXPLAIN WHY]. 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 a partial differential equation 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.4 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 constraints that \(c(0) = S\) and \(c(T) = 0\). 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\]

[INTERPRET]

Now, let’s plug in a utility function for this. Consider \(u(c) = \frac{1}{1-\gamma}c^{1-\gamma}\). Then the condition above becomes

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 Frechet differential in a particular direction. Specifically, consider a path \(\{s(t)\}\) and imagine increasing savings by one unit at time \(t\). Notice that this will decrease consumption slightly at time \(t\) and increase wealth at time \(t+1\). In this case, the Frechet derivative is

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

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)\]

rearranging this FOC yields the equation

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

\[\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}\). In this case, this first order equation becomes

\[\beta\frac{-e^{-\gamma c_{t+1}}}{-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} \begin{aligned} g_{1}(x) & = 0 \\ g_{2}(x) & = 0 \\ \vdots \\ g_{n}(x) & = 0 \end{aligned} \end{aligned}\]

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

Definition 1.11 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.12 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.13 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.4 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.14 A function is said to be quasiconcave if all of its upper contour sets are convex. Specifically, for all \(f(x) \ge c\) and \(f(x') \ge c\) it is the case that \(f(\alpha x + (1-\alpha x')) ge c\). The function is strictly quasiconcave is the last inequality is strict.

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 if \(\lambda > 0\) then whenever \(x > 10\) then this function is decreases when it move beyond 10. Therefore, the role of the Lagrangian is to great an alternative objective function for which the solution to the unconstrained maximization problem associated with the Lagrangian is equal 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.

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.5 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

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

We notice that this has rank 2 \(\ne 3\) and as such, the constraint qualification does not hold. That is, there is no \((x,y)\) that can satisfy these equations and as such, there can be no solution to the problem that satisfies these constraints.

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} \begin{aligned} D_{x}f(x) - \lambda' D_{x}G(x) - \gamma' D_{x}H(x) & = \mathbf{0} \\ G(x) & = \mathbf{0} \\ \gamma_{i} H_{i}(x) & = 0 \mbox{ for all } i \end{aligned} \end{aligned}\]

Proof. See Mas-Colell

Example.

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\).