maximum theorem

{{short description|Provides conditions for a parametric optimization problem to have continuous solutions}}

The maximum theorem provides conditions for the continuity of an optimized function and the set of its maximizers with respect to its parameters. The statement was first proven by Claude Berge in 1959.{{cite book

| first = Efe |last=Ok

| title = Real Analysis with Economics Applications

| url = https://archive.org/details/realanalysiswith00okef | url-access = limited | year = 2007

| publisher = Princeton University Press

| isbn = 978-0-691-11768-3

| page = [https://archive.org/details/realanalysiswith00okef/page/n323 306]

}} The theorem is primarily used in mathematical economics and optimal control.

Statement of theorem

Maximum Theorem. The original reference is the Maximum Theorem in Chapter 6, Section 3 {{cite book |author = Claude Berge |title = Topological Spaces |year = 1963 |publisher = Oliver and Boyd |pages = 116}} Famously, or perhaps infamously, Berge only considers Hausdorff topological spaces and only allows those compact sets which are themselves Hausdorff spaces. He also requires that upper hemicontinuous correspondences be compact-valued. These properties have been clarified and disaggregated in later literature.Compare with Theorem 17.31 in {{cite book |author1 = Charalambos D. Aliprantis |author2 = Kim C. Border |title=Infinite Dimensional Analysis: A Hitchhiker's Guide |url = https://archive.org/details/infinitedimensio00alip_016 |url-access = limited |publisher=Springer |year=2006 |pages=[https://archive.org/details/infinitedimensio00alip_016/page/n582 570]|isbn = 9783540295860 }} This is given for arbitrary topological spaces. They also consider the possibility that $f$ may only be defined on the graph of $C$ .Compare with Theorem 3.5 in {{cite book| author1 = Shouchuan Hu| author2 = Nikolas S. Papageorgiou| title = Handbook of Multivalued Analysis| volume = 1: Theory| year = 1997| publisher = Springer-Science + Business Media, B. V| pages = 84}} They consider the case that $\Theta$ and $X$ are Hausdorff spaces.Theorem 3.6 in {{cite book |first1=Brian |last1=Beavis |first2=Ian |last2=Dobbs |title=Optimization and Stability Theory for Economic Analysis |location=New York |publisher=Cambridge University Press |year=1990 |isbn=0-521-33605-8 |pages=83–84 }}

Let $X$ and $\Theta$ be topological spaces, $f:X\times\Theta\to\mathbb{R}$ be a continuous function on the product $X \times \Theta$ , and $C:\Theta\rightrightarrows X$ be a compact-valued correspondence such that $C(\theta) \ne \emptyset$ for all $\theta \in \Theta$ . Define the marginal function (or value function) $f^* : \Theta \to \mathbb{R}$ by

: $f^*(\theta)=\sup\{f(x, \theta) : x\in C(\theta)\}$

and the set of maximizers $C^* : \Theta \rightrightarrows X$ by

: $C^*(\theta)=
\mathrm{arg}\max\{f(x,\theta) : x \in C(\theta)\}
= \{x \in C(\theta) : f(x, \theta) = f^*(\theta)\}$ .

If $C$ is continuous (i.e. both upper and lower hemicontinuous) at $\theta$ , then the value function $f^*$ is continuous, and the set of maximizers $C^*$ is upper-hemicontinuous with nonempty and compact values. As a consequence, the $\sup$ may be replaced by $\max$ .

Variants

The maximum theorem can be used for minimization by considering the function $-f$ instead.

Interpretation

The theorem is typically interpreted as providing conditions for a parametric optimization problem to have continuous solutions with regard to the parameter. In this case, $\Theta$ is the parameter space, $f(x,\theta)$ is the function to be maximized, and $C(\theta)$ gives the constraint set that $f$ is maximized over. Then, $f^*(\theta)$ is the maximized value of the function and $C^*$ is the set of points that maximize $f$ .

The result is that if the elements of an optimization problem are sufficiently continuous, then some, but not all, of that continuity is preserved in the solutions.

Proof

Throughout this proof we will use the term neighborhood to refer to an open set containing a particular point. We preface with a preliminary lemma, which is a general fact in the calculus of correspondences. Recall that a correspondence is closed if its graph is closed.

Lemma. Compare with Theorem 7 in Chapter 6, Section 1 of {{cite book

| author = Claude Berge

| title = Topological Spaces

| year = 1963

| publisher = Oliver and Boyd

| pages = 112

}} Berge assumes that the underlying spaces are Hausdorff and employs this property for $X$ (but not for $C$ ) in his proof.Compare with Proposition 2.46 in {{cite book

| author1 = Shouchuan Hu

| author2 = Nikolas S. Papageorgiou

| title = Handbook of Multivalued Analysis

| volume = 1: Theory

| year = 1997

| publisher = Springer-Science + Business Media, B. V

| pages = 53

}} They assume implicitly that $\Theta$ and $X$ are Hausdorff spaces, but their proof is general.Compare with Corollary 17.18 in {{cite book

|author1 = Charalambos D. Aliprantis

|author2 = Kim C. Border

|title=Infinite Dimensional Analysis: A Hitchhiker's Guide

|url = https://archive.org/details/infinitedimensio00alip_667

|url-access = limited

|publisher=Springer

|year=2006

|pages=[https://archive.org/details/infinitedimensio00alip_667/page/n576 564]

|isbn = 9783540295860

}} This is given for arbitrary topological spaces, but the proof relies on the machinery of topological nets.

If $A, B : \Theta \rightrightarrows X$ are correspondences, $A$ is upper hemicontinuous and compact-valued, and $B$ is closed, then $A \cap B : \Theta \rightrightarrows X$ defined by $(A \cap B) (\theta) = A(\theta) \cap B(\theta)$ is upper hemicontinuous.

Let $\theta \in \Theta$ , and suppose $G$ is an open set containing $(A\cap B)(\theta)$ . If $A(\theta) \subseteq G$ , then the result follows immediately. Otherwise, observe that for each $x \in A(\theta) \setminus G$ we have $x \notin B(\theta)$ , and since $B$ is closed there is a neighborhood $U_x \times V_x$ of $(\theta, x)$ in which $x' \notin B(\theta')$ whenever $(\theta', x') \in U_x \times V_x$ . The collection of sets $\{G\} \cup \{V_x : x \in A(\theta) \setminus G\}$ forms an open cover of the compact set $A(\theta)$ , which allows us to extract a finite subcover $G, V_{x_1}, \dots, V_{x_n}$ . By upper hemicontinuity, there is a neighborhood $U_\theta$ of $\theta$ such that $A(U_\theta)\subseteq G \cup V_{x_1} \cup \dots \cup V_{x_n}$ . Then whenever $\theta' \in U_\theta\cap U_{x_1} \cap \dots \cap U_{x_n}$ , we have $A(\theta') \subseteq G \cup V_{x_1} \cup \dots \cup V_{x_n}$ , and so $(A \cap B)(\theta') \subseteq G$ . This completes the proof. $\square$

The continuity of $f^*$ in the maximum theorem is the result of combining two independent theorems together.

Theorem 1. Compare with Theorem 2 in Chapter 6, Section 3 of {{cite book

| author = Claude Berge

| title = Topological Spaces

| year = 1963

| publisher = Oliver and Boyd

| pages = 116

}} Berge's argument is essentially the one presented here, but he again uses auxiliary results proven with the assumptions that the underlying spaces are Hausdorff.Compare with Proposition 3.1 in {{cite book

| author1 = Shouchuan Hu

| author2 = Nikolas S. Papageorgiou

| title = Handbook of Multivalued Analysis

| volume = 1: Theory

| year = 1997

| publisher = Springer-Science + Business Media, B. V

| pages = 82

}} They work exclusively with Hausdorff spaces, and their proof again relies on topological nets. Their result also allows for $f$ to take on the values $\pm \infty$ .Compare with Lemma 17.30 in {{cite book

|author1 = Charalambos D. Aliprantis

|author2 = Kim C. Border

|title=Infinite Dimensional Analysis: A Hitchhiker's Guide

|url = https://archive.org/details/infinitedimensio00alip_667

|url-access = limited

|publisher=Springer

|year=2006

|pages=[https://archive.org/details/infinitedimensio00alip_667/page/n581 569]

|isbn = 9783540295860

}} They consider arbitrary topological spaces, and use an argument based on topological nets.

If $f$ is upper semicontinuous and $C$ is upper hemicontinuous, nonempty and compact-valued, then $f^*$ is upper semicontinuous.

Fix $\theta \in \Theta$ , and let $\varepsilon > 0$ be arbitrary. For each $x \in C(\theta)$ , there exists a neighborhood $U_x \times V_x$ of $(\theta, x)$ such that whenever $(\theta', x') \in U_x \times V_x$ , we have $f(x', \theta') < f(x, \theta) + \varepsilon$ . The set of neighborhoods $\{V_x : x \in C(\theta)\}$ covers $C(\theta)$ , which is compact, so $V_{x_1}, \dots, V_{x_n}$ suffice. Furthermore, since $C$ is upper hemicontinuous, there exists a neighborhood $U'$ of $\theta$ such that whenever $\theta' \in U'$ it follows that $C(\theta') \subseteq \bigcup_{k=1}^{n} V_{x_k}$ . Let $U = U' \cap U_{x_1} \cap \dots \cap U_{x_n}$ . Then for all $\theta' \in U$ , we have $f(x', \theta') < f(x_k, \theta) + \varepsilon$ for each $x' \in C(\theta')$ , as $x' \in V_{x_k}$ for some $k$ . It follows that

: $f^*(\theta') = \sup_{x' \in C(\theta')} f(x', \theta') < \max_{k=1, \dots, n} f(x_k, \theta) + \varepsilon \leq f^*(\theta) + \varepsilon,$

which was desired. $\square$

Theorem 2. Compare with Theorem 1 in Chapter 6, Section 3 of {{cite book

| author = Claude Berge

| title = Topological Spaces

| year = 1963

| publisher = Oliver and Boyd

| pages = 115

}} The argument presented here is essentially his.Compare with Proposition 3.3 in {{cite book

| author1 = Shouchuan Hu

| author2 = Nikolas S. Papageorgiou

| title = Handbook of Multivalued Analysis

| volume = 1: Theory

| year = 1997

| publisher = Springer-Science + Business Media, B. V

| pages = 83

|author1 = Charalambos D. Aliprantis

|author2 = Kim C. Border

|title=Infinite Dimensional Analysis: A Hitchhiker's Guide

|url = https://archive.org/details/infinitedimensio00alip_667

|url-access = limited

|publisher=Springer

|year=2006

|pages=[https://archive.org/details/infinitedimensio00alip_667/page/n581 569]

|isbn = 9783540295860

}} They consider arbitrary topological spaces and use an argument involving topological nets.

If $f$ is lower semicontinuous and $C$ is lower hemicontinuous, then $f^*$ is lower semicontinuous.

Fix $\theta \in \Theta$ , and let $\varepsilon > 0$ be arbitrary.

By definition of $f^*$ , there exists $x \in C(\theta)$ such that $f^*(\theta) < f(x,\theta) + \frac{\varepsilon}{2}$ .

Now, since $f$ is lower semicontinuous, there exists a neighborhood $U_1 \times V$ of $(\theta, x)$ such that whenever $(\theta', x') \in U_1 \times V$ we have $f(x, \theta) < f(x', \theta') + \frac{\varepsilon}{2}$ . Observe that $C(\theta) \cap V \ne \emptyset$ (in particular, $x \in C(\theta) \cap V$ ). Therefore, since $C$ is lower hemicontinuous, there exists a neighborhood $U_2$ such that whenever $\theta' \in U_2$ there exists $x' \in C(\theta') \cap V$ .

Let $U = U_1 \cap U_2$ .

Then whenever $\theta' \in U$ there exists $x' \in C(\theta') \cap V$ , which implies

: $f^*(\theta) < f(x, \theta) + \frac{\varepsilon}{2} < f(x', \theta') + \varepsilon \leq f^*(\theta') + \varepsilon$

which was desired. $\square$

Under the hypotheses of the Maximum theorem, $f^*$ is continuous. It remains to verify that $C^*$ is an upper hemicontinuous correspondence with compact values. Let $\theta \in \Theta$ . To see that $C^*(\theta)$ is nonempty, observe that the function $f_\theta : C(\theta) \to \mathbb{R}$ by $f_\theta(x) = f(x, \theta)$ is continuous on the compact set $C(\theta)$ . The Extreme Value theorem implies that $C^*(\theta)$ is nonempty. In addition, since $f_\theta$ is continuous, it follows that $C^*(\theta)$ a closed subset of the compact set $C(\theta)$ , which implies $C^*(\theta)$ is compact. Finally, let $D : \Theta \rightrightarrows X$ be defined by $D(\theta) = \{x \in X : f(x, \theta) = f^*(\theta)\}$ . Since $f$ is a continuous function, $D$ is a closed correspondence. Moreover, since $C^*(\theta) = C(\theta) \cap D(\theta)$ , the preliminary Lemma implies that $C^*$ is upper hemicontinuous. $\square$

Variants and generalizations

A natural generalization from the above results gives sufficient local conditions for $f^*$ to be continuous and $C^*$ to be nonempty, compact-valued, and upper semi-continuous.

If in addition to the conditions above, $f$ is quasiconcave in $x$ for each $\theta$ and $C$ is convex-valued, then $C^*$ is also convex-valued. If $f$ is strictly quasiconcave in $x$ for each $\theta$ and $C$ is convex-valued, then $C^*$ is single-valued, and thus is a continuous function rather than a correspondence.

If $f$ is concave in $X \times \Theta$ and $C$ has a convex graph, then $f^*$ is concave and $C^*$ is convex-valued. Similarly to above, if $f$ is strictly concave, then $C^*$ is a continuous function.{{cite book |last=Sundaram |first=Rangarajan K. |url=https://archive.org/details/firstcourseinopt0000sund/ |title=A First Course in Optimization Theory |publisher=Cambridge University Press |year=1996 |isbn=0-521-49770-1 |page=[https://archive.org/details/firstcourseinopt0000sund/page/237 237] |url-access=limited}}

It is also possible to generalize Berge's theorem to non-compact correspondences if the objective function is K-inf-compact.Theorem 1.2 in {{cite journal |last1=Feinberg |first1=Eugene A. |author-link=Eugene A. Feinberg |last2=Kasyanov |first2=Pavlo O. |last3=Zadoianchuk |first3=Nina V. |date=January 2013 |title=Berge's theorem for noncompact image sets |journal=Journal of Mathematical Analysis and Applications |volume=397 |issue=1 |pages=255–259 |arxiv=1203.1340 |doi=10.1016/j.jmaa.2012.07.051 |s2cid=8603060}}

Examples

Consider a utility maximization problem where a consumer makes a choice from their budget set. Translating from the notation above to the standard consumer theory notation,

$X=\mathbb{R}_+^l$ is the space of all bundles of $l$ commodities,
$\Theta=\mathbb{R}_{++}^l \times \mathbb{R}_{++}$ represents the price vector of the commodities $p$ and the consumer's wealth $w$ ,
$f(x,\theta)=u(x)$ is the consumer's utility function, and
$C(\theta)=B(p,w)=\{x \,|\, px \leq w\}$ is the consumer's budget set.

Then,

$f^*(\theta)=v(p,w)$ is the indirect utility function and
$C^*(\theta)=x(p,w)$ is the Marshallian demand.

Proofs in general equilibrium theory often apply the Brouwer or Kakutani fixed-point theorems to the consumer's demand, which require compactness and continuity, and the maximum theorem provides the sufficient conditions to do so.

Notes

References

{{cite book

| author = Claude Berge

| title = Topological Spaces

| year = 1963

| publisher = Oliver and Boyd

| pages = 115–117

}}

{{cite book

| author1 = Charalambos D. Aliprantis

| author2 = Kim C. Border

| title = Infinite Dimensional Analysis: A Hitchhiker's Guide

| url = https://archive.org/details/infinitedimensio00alip_667

| url-access = limited

| year = 2006

| publisher = Springer

| pages = [https://archive.org/details/infinitedimensio00alip_667/page/n581 569]-571

| isbn = 9783540295860

}}

{{cite book

| author1 = Shouchuan Hu

| author2 = Nikolas S. Papageorgiou

| title = Handbook of Multivalued Analysis

| volume = 1: Theory

| year = 1997

| publisher = Springer-Science + Business Media, B. V

| pages = 82–89

}}

Category:Theory of continuous functions

Category:Convex optimization

Category:Mathematical economics

Category:Mathematical optimization

Category:Mathematical theorems

Category:Theorems in mathematical analysis

maximum theorem

Statement of theorem

Variants

Interpretation

Proof

Variants and generalizations

Examples

See also

Notes

References