en>Bgwhite: /* Reading */WP:CHECKWIKI error fix #34. Do general fixes and cleanup if needed. - using AWB

2013-02-22T01:21:53Z

Reading: WP:CHECKWIKI error fix #34. Do general fixes and cleanup if needed. - using AWB

New page

The '''maximum theorem''' provides conditions for the [[continuous function|continuity]] of an [[Optimization (mathematics)|optimized]] function and the set of its maximizers as a parameter changes. The statement was first proven by [[Claude Berge]] in 1959.<ref>Ok, p. 306</ref> The theorem is primarily used in [[mathematical economics]].

==Statement of theorem==
Let <math>X</math> and <math>\Theta</math> be metric spaces, <math>f:X\times\Theta\to\mathbb{R}</math> be a function jointly continuous in its two arguments, and <math>C:\Theta\twoheadrightarrow X</math> be a compact-valued [[Multivalued function|correspondence]].

For <math>x</math> in <math>X</math> and <math>\theta</math> in <math>\Theta</math>, let
: <math>f^*(\theta)=\max\{f(x,\theta)|x\in C(\theta)\}</math> and

: <math>C^*(\theta)=\mathrm{arg}\max\{f(x,\theta)|x\in C(\theta)\}=\{x\in C(\theta)\,|\,f(x,\theta)=f^*(\theta)\}</math>.

If <math>C</math> is continuous (i.e. both upper and lower [[hemicontinuity|hemicontinuous]]) at some <math>\theta</math>, then <math>f^*</math> is continuous at <math>\theta</math> and <math>C^*</math> is non-empty, compact-valued, and upper hemicontinuous at <math>\theta</math>.

==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, <math>\Theta</math> is the parameter space, <math>f(x,\theta)</math> is the function to be maximized, and <math>C(\theta)</math> gives the constraint set that <math>f</math> is maximized over. Then, <math>f^*(\theta)</math> is the maximized value of the function and <math>C^*</math> is the set of points that maximize <math>f</math>.

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==
The proof relies primarily on the sequential definitions of upper and lower [[hemicontinuity]].

Because <math>C</math> is compact-valued and <math>f</math> is continuous, the [[extreme value theorem]] guarantees the constrained maximum of <math>f</math> is well-defined and <math>C^*(\theta)</math> is non-empty for all <math>\theta</math> in <math>\Theta</math>. Then, let <math>\theta_n</math> be a sequence converging to <math>\theta</math> and <math>x_n \in C^*(\theta_n)</math> be a sequence in <math>X</math>. Since <math>C</math> is upper hemicontinuous, there exists a convergent subsequence <math>x_{n_k}\to x \in C(\theta)</math>.

If it is shown that <math>x \in C^*(\theta)</math>, then
: <math>\lim_{k \to \infty} f^*(\theta_{n_k}) = \lim_{k \to \infty} f(x_{n_k},\theta_{n_k}) = f(x,\theta) = f^*(\theta)</math>
which would simultaneously prove the continuity of <math>f^*</math> and the upper hemicontinuity of <math>C^*</math>.

Suppose to the contrary that <math>x \not\in C^*(\theta)</math>, i.e. there exists an <math>\hat{x}\in C(\theta)</math> such that <math>f(\hat{x},\theta) > f(x,\theta)</math>. Because <math>C</math> is lower hemicontinuous, there is a further subsequence of <math>n_k</math> such that <math>\hat{x}_{n_j} \in C(\theta_{n_j})</math> and <math>\hat{x}_{n_j} \to \hat{x}</math>. By the continuity of <math>f</math> and the contradiction hypothesis,
: <math>\lim_{j \to \infty} f(\hat{x}_{n_j},\theta_{n_j}) = f(\hat{x},\theta) > f(x,\theta) = \lim_{j \to \infty} f(x_{n_j},\theta_{n_j})</math>.
But this implies that for sufficiently large <math>j</math>,
: <math>f(\hat{x}_{n_j},\theta_{n_j}) > f(x_{n_j},\theta_{n_j})</math>
which would mean <math>x_{n_j}</math> is not a maximizer, a contradiction of <math>x_n \in C^*(\theta_n)</math>. This establishes the continuity of <math>f^*</math> and the upper hemicontinuity of <math>C^*</math>.

Because <math>C^*(\theta) \subset C(\theta)</math> and <math>C(\theta)</math> is compact, it is sufficient to show <math>C^*</math> is closed-valued for it to be compact-valued. This can be done by contradiction using sequences similar to above.

==Variants==
If in addition to the conditions above, <math>f</math> is [[quasiconcave]] in <math>x</math> for each <math>\theta</math> and <math>C</math> is convex-valued, then <math>C^*</math> is also convex-valued. If <math>f</math> is strictly quasiconcave in <math>x</math> for each <math>\theta</math> and <math>C</math> is convex-valued, then <math>C^*</math> is single-valued, and thus is a continuous function rather than a correspondence.

If <math>f</math> is [[Concave function|concave]] and <math>C</math> has a [[Convex set|convex]] graph, then <math>f^*</math> is concave and <math>C^*</math> is convex-valued. Similarly to above, if <math>f</math> is strictly concave, then <math>C^*</math> is a continuous function.<ref>Sundaram, p. 239</ref>

==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,
* <math>X=\mathbb{R}_+^l</math> is the space of all bundles of <math>l</math> commodities,
* <math>\Theta=\mathbb{R}_{++}^l \times \mathbb{R}_{++}</math> represents the price vector of the commodities <math>p</math> and the consumer's wealth <math>w</math>,
* <math>f(x,\theta)=u(x)</math> is the consumer's [[utility function]], and
* <math>C(\theta)=B(p,w)=\{x \,|\, px \leq w\}</math> is the consumer's [[budget set]].

Then,
* <math>f^*(\theta)=v(p,w)</math> is the [[indirect utility function]] and
* <math>C^*(\theta)=x(p,w)</math> is the [[Marshallian demand]].

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

==See also==
* [[Envelope theorem]]

==Notes==
{{reflist}}

==References==
{{refbegin}}
* {{cite book
| author = Claude Berge
| title = Topological Spaces
| year = 1963
| publisher = Oliver and Boyd
}}
* {{cite book
| author = Efe Ok
| title = Real analysis with economics applications
| year = 2007
| publisher = Princeton University Press
| isbn = 0-691-11768-3
}}
* {{cite book
| author = Rangarajan K. Sundaram
| title = A first course in optimization theory
| year = 1996
| publisher = Cambridge University Press
| isbn = 978-0-521-49770-1
}}
{{refend}}

[[Category:Mathematical optimization]]
[[Category:Continuous mappings]]
[[Category:Mathematical economics]]
[[Category:Mathematical theorems]]

Sinc numerical methods - Revision history

en>Bgwhite: /* Reading */WP:CHECKWIKI error fix #34. Do general fixes and cleanup if needed. - using AWB