Relative Extrema and Convex Functions - Revision history

Khanh at 17:23, 24 October 2021

2021-10-24T17:23:25Z

Khanh at 17:21, 24 October 2021

2021-10-24T17:21:25Z

Show changes

Khanh at 23:33, 22 October 2021

2021-10-22T23:33:33Z

Khanh at 23:23, 22 October 2021

2021-10-22T23:23:33Z

Khanh at 23:22, 22 October 2021

2021-10-22T23:22:29Z

Lila at 19:09, 22 October 2021

2021-10-22T19:09:32Z

Lila: Created page with " http://mathonline.wikidot.com/convex-and-concave-functions"

2021-10-22T19:07:56Z

Created page with " http://mathonline.wikidot.com/convex-and-concave-functions"

New page

http://mathonline.wikidot.com/convex-and-concave-functions

@@ Line 42: / Line 42: @@
 | <nowiki> |</nowiki>''x''<nowiki>|</nowiki> ||Global minimum at ''x'' = 0 that cannot be found by taking derivatives, because the derivative does not exist at ''x'' = 0.
 |-
-| cos(''x'') ||Infinitely many global maxima at 0, ±2{{pi}}, ±4{{pi}}, ..., and infinitely many global minima at ±<math>\pi</math>, ±3<math>\pi</math>, ±5<math>\pi</math>, ....
+| cos(''x'') ||Infinitely many global maxima at 0, ±2<math>\pi</math>, ±4<math>\pi</math>, ..., and infinitely many global minima at ±<math>\pi</math>, ±3<math>\pi</math>, ±5<math>\pi</math>, ....
 |-
 | 2 cos(''x'') − ''x'' ||Infinitely many local maxima and minima, but no global maximum or minimum.

← Older revision		Revision as of 23:33, 22 October 2021
Line 1:		Line 1:
		+	[[File:Extrema example original.svg\|thumb\|Local and global maxima and minima for cos(3π''x'')/''x'', 0.1≤'' x ''≤1.1]]
		+	In mathematical analysis, the '''maxima''' and '''minima''' (the respective plurals of '''maximum''' and '''minimum''') of a function, known collectively as '''extrema''' (the plural of '''extremum'''), are the largest and smallest value of the function, either within a given range (the ''local'' or ''relative'' extrema), or on the entire domain (the ''global'' or ''absolute'' extrema). Pierre de Fermat was one of the first mathematicians to propose a general technique, adequality, for finding the maxima and minima of functions.
		+
		+	As defined in set theory, the maximum and minimum of a set are the greatest and least elements in the set, respectively. Unbounded infinite sets, such as the set of real numbers, have no minimum or maximum.
		+
		+	==Definition==
		+	A real-valued function ''f'' defined on a domain ''X'' has a '''global''' (or '''absolute''') '''maximum point''' at ''x''<sup>∗</sup>, if ''f''(''x''<sup>∗</sup>) ≥ ''f''(''x'') for all ''x'' in ''X''. Similarly, the function has a '''global''' (or '''absolute''') '''minimum point''' at ''x''<sup>∗</sup>, if ''f''(''x''<sup>∗</sup>) ≤ ''f''(''x'') for all ''x'' in ''X''. The value of the function at a maximum point is called the '''maximum value''' of the function, denoted <math>\max(f(x))</math>, and the value of the function at a minimum point is called the '''minimum value''' of the function. Symbolically, this can be written as follows:
		+	:<math>x_0 \in X</math> is a global maximum point of function <math>f:X \to \R,</math> if <math>(\forall x \in X)\, f(x_0) \geq f(x).</math>
		+	The definition of global minimum point also proceeds similarly.
		+
		+	If the domain ''X'' is a metric space, then ''f'' is said to have a '''local''' (or '''relative''') '''maximum point''' at the point ''x''<sup>∗</sup>, if there exists some ''ε'' > 0 such that ''f''(''x''<sup>∗</sup>) ≥ ''f''(''x'') for all ''x'' in ''X'' within distance ''ε'' of ''x''<sup>∗</sup>. Similarly, the function has a '''local minimum point''' at ''x''<sup>∗</sup>, if ''f''(''x''<sup>∗</sup>) ≤ ''f''(''x'') for all ''x'' in ''X'' within distance ''ε'' of ''x''<sup>∗</sup>. A similar definition can be used when ''X'' is a topological space, since the definition just given can be rephrased in terms of neighborhoods. Mathematically, the given definition is written as follows:
		+	:Let <math>(X, d_X)</math> be a metric space and function <math> f:X \to \R</math>. Then <math>x_0 \in X</math> is a local maximum point of function <math>f</math> if <math> (\exists \varepsilon > 0)</math> such that <math>(\forall x \in X)\, d_X(x, x_0)<\varepsilon \implies f(x_0)\geq f(x).</math>
		+
		+	The definition of local minimum point can also proceed similarly.
		+
		+	In both the global and local cases, the concept of a '''strict extremum''' can be defined. For example, ''x''<sup>∗</sup> is a '''strict global maximum point''' if for all ''x'' in ''X'' with ''x'' ≠ ''x''<sup>∗</sup>, we have ''f''(''x''<sup>∗</sup>) > ''f''(''x''), and ''x''<sup>∗</sup> is a '''strict local maximum point''' if there exists some ''ε'' > 0 such that, for all ''x'' in ''X'' within distance ''ε'' of ''x''<sup>∗</sup> with ''x'' ≠ ''x''<sup>∗</sup>, we have ''f''(''x''<sup>∗</sup>) > ''f''(''x''). Note that a point is a strict global maximum point if and only if it is the unique global maximum point, and similarly for minimum points.
		+
		+	A continuous real-valued function with a compact domain always has a maximum point and a minimum point. An important example is a function whose domain is a closed and bounded interval of real numbers (see the graph above).
		+
		+	==Search==
		+	Finding global maxima and minima is the goal of mathematical optimization. If a function is continuous on a closed interval, then by the [[extreme value theorem]], global maxima and minima exist. Furthermore, a global maximum (or minimum) either must be a local maximum (or minimum) in the interior of the domain, or must lie on the boundary of the domain. So a method of finding a global maximum (or minimum) is to look at all the local maxima (or minima) in the interior, and also look at the maxima (or minima) of the points on the boundary, and take the largest (or smallest) one.
		+
		+	Likely the most important, yet quite obvious, feature of [[Continuous function\|continuous]] [[Real-valued function\|real-valued]] functions of [[Function of a real variable\|a real variable]] is that they [[Decreasing function\|decrease]] before local minima and [[Increasing function\|increase]] afterwards, likewise for maxima. (Formally, if ''f'' is continuous real-valued function of a real variable ''x'', then ''x''<sub>0</sub> is a local minimum [[if and only if]] there exist {{nowrap\|''a'' < ''x''<sub>0</sub> < ''b''}} such that ''f'' decreases on (''a'', ''x''<sub>0</sub>) and increases on (''x''<sub>0</sub>, ''b'')). A direct consequence of this is the [[Fermat's theorem (stationary points)\|Fermat's theorem]], which states that local extrema must occur at [[critical point (mathematics)\|critical point]]s (or points where the function is non-[[Differentiable function\|differentiable]]). One can distinguish whether a critical point is a local maximum or local minimum by using the [[first derivative test]], [[derivative test#Second derivative test (single variable)\|second derivative test]], or [[higher-order derivative test]], given sufficient differentiability.
		+
		+	For any function that is defined [[piecewise]], one finds a maximum (or minimum) by finding the maximum (or minimum) of each piece separately, and then seeing which one is largest (or smallest).
		+
		+	==Examples==
		+	[[Image:xth root of x.svg\|thumb\|right\|The global maximum of {{math\|{{sqrt\|''x''\|''x''}}}} occurs at ''x'' = ''e''.]]
		+	{\|class="wikitable"
		+	!Function!!Maxima and minima
		+	\|-
		+	\| ''x''<sup>2</sup>\|\|Unique global minimum at ''x'' = 0.
		+	\|-
		+	\| ''x''<sup>3</sup> \|\|No global minima or maxima. Although the first derivative (3''x''<sup>2</sup>) is 0 at ''x'' = 0, this is an [[inflection point]]. (2nd derivative is 0 at that point.)
		+	\|-
		+	\| <big><math>\sqrt[x]{x}</math></big> \|\|Unique global maximum at ''x'' = ''[[e (mathematical constant)\|e]]''. (See figure at right)
		+	\|-
		+	\| ''x''<sup>−''x''</sup> \|\|Unique global maximum over the positive real numbers at ''x'' = 1/''e''.
		+	\|-
		+	\| ''x''<sup>3</sup>/3 − ''x'' \|\|First derivative ''x''<sup>2</sup> − 1 and [[second derivative]] 2''x''. Setting the first derivative to 0 and solving for ''x'' gives [[stationary point]]s at −1 and +1. From the sign of the second derivative, we can see that −1 is a local maximum and +1 is a local minimum. This function has no global maximum or minimum.
		+	\|-
		+	\| <nowiki> \|</nowiki>''x''<nowiki>\|</nowiki> \|\|Global minimum at ''x'' = 0 that cannot be found by taking derivatives, because the derivative does not exist at ''x'' = 0.
		+	\|-
		+	\| cos(''x'') \|\|Infinitely many global maxima at 0, ±2{{pi}}, ±4{{pi}}, ..., and infinitely many global minima at ±{{pi}}, ±3{{pi}}, ±5{{pi}}, ....
		+	\|-
		+	\| 2 cos(''x'') − ''x'' \|\|Infinitely many local maxima and minima, but no global maximum or minimum.
		+	\|-
		+	\| cos(3{{pi}}''x'')/''x'' with {{nowrap\|0.1 ≤ ''x'' ≤ 1.1}} \|\|Global maximum at ''x'' = 0.1 (a boundary), a global minimum near ''x'' = 0.3, a local maximum near ''x'' = 0.6, and a local minimum near ''x'' = 1.0. (See figure at top of page.)
		+	\|-
		+	\|''x''<sup>3</sup> + 3''x''<sup>2</sup> − 2''x'' + 1 defined over the closed interval (segment) [−4,2] \|\| Local maximum at ''x'' = −1−{{radic\|15}}/3, local minimum at ''x'' = −1+{{radic\|15}}/3, global maximum at ''x'' = 2 and global minimum at ''x'' = −4.
		+	\|}
		+
		+	For a practical example, assume a situation where someone has <math>200</math> feet of fencing and is trying to maximize the square footage of a rectangular enclosure, where <math>x</math> is the length, <math>y</math> is the width, and <math>xy</math> is the area:
		+
		+	:<math> 2x+2y = 200 </math>
		+	:<math> 2y = 200-2x </math>
		+	:<math> \frac{2y}{2} = \frac{200-2x}{2} </math>
		+	:<math> y = 100 - x</math>
		+	:<math> xy=x(100-x) </math>
		+
		+	The derivative with respect to <math>x</math> is:
		+	:<math>\begin{align}
		+	\frac{d}{dx}xy&=\frac{d}{dx}x(100-x) \\
		+	&=\frac{d}{dx} \left(100x-x^2 \right) \\
		+	&=100-2x
		+	\end{align}</math>
		+	Setting this equal to <math>0</math>
		+	:<math>0=100-2x</math>
		+	:<math>2x=100</math>
		+	:<math>x=50</math>
		+	reveals that <math>x=50</math> is our only [[Critical_point_(mathematics)\|critical point]].
		+	Now retrieve the [[Interval_(mathematics)\|endpoints]] by determining the interval to which <math>x</math> is restricted. Since width is positive, then <math>x>0</math>, and since <math>x=100-y</math>, that implies that <math>x < 100</math>.
		+	Plug in critical point <math>50</math>, as well as endpoints <math>0</math> and <math>100</math>, into <math>xy=x(100-x)</math>, and the results are <math>2500, 0,</math> and <math>0</math> respectively.
		+
		+	Therefore, the greatest area attainable with a rectangle of <math>200</math> feet of fencing is <math>50 \times 50 = 2500</math>.
		+
		+	==Functions of more than one variable==
		+
		+	[[File:Modell einer Peanoschen Fläche -Schilling XLIX, 1-.jpg\|thumb\|left\|Peano surface, a counterexample to some criteria of local maxima of the 19th century]][[File:MaximumParaboloid.png\|thumb\|right\|The global maximum is the point at the top]]
		+	[[File:MaximumCounterexample.png\|thumb\|right\|Counterexample: The red dot shows a local minimum that is not a global minimum]]
		+	For functions of more than one variable, similar conditions apply. For example, in the (enlargeable) figure on the right, the necessary conditions for a ''local'' maximum are similar to those of a function with only one variable. The first [[partial derivatives]] as to ''z'' (the variable to be maximized) are zero at the maximum (the glowing dot on top in the figure). The second partial derivatives are negative. These are only necessary, not sufficient, conditions for a local maximum, because of the possibility of a [[saddle point]]. For use of these conditions to solve for a maximum, the function ''z'' must also be [[Differentiable function\|differentiable]] throughout. The [[second partial derivative test]] can help classify the point as a relative maximum or relative minimum.
		+	In contrast, there are substantial differences between functions of one variable and functions of more than one variable in the identification of global extrema. For example, if a bounded differentiable function ''f'' defined on a closed interval in the real line has a single critical point, which is a local minimum, then it is also a global minimum (use the [[intermediate value theorem]] and [[Rolle's theorem]] to prove this by [[proof by contradiction\|reductio ad impossibile]]). In two and more dimensions, this argument fails. This is illustrated by the function
		+	:<math>f(x,y)= x^2+y^2(1-x)^3,\qquad x,y \in \R,</math>
		+	whose only critical point is at (0,0), which is a local minimum with ''f''(0,0) = 0. However, it cannot be a global one, because ''f''(2,3) = −5.
		+
		+	==Maxima or minima of a functional==
		+	If the domain of a function for which an extremum is to be found consists itself of functions (i.e. if an extremum is to be found of a [[Functional (mathematics)\|functional]]), then the extremum is found using the [[calculus of variations]].
		+
		+	==In relation to sets==
		+	Maxima and minima can also be defined for sets. In general, if an [[ordered set]] ''S'' has a [[greatest element]] ''m'', then ''m'' is a [[maximal element]] of the set, also denoted as <math>\max(S)</math>. Furthermore, if ''S'' is a subset of an ordered set ''T'' and ''m'' is the greatest element of ''S'' with (respect to order induced by ''T''), then ''m'' is a [[supremum\|least upper bound]] of ''S'' in ''T''. Similar results hold for [[least element]], [[minimal element]] and [[infimum\|greatest lower bound]]. The maximum and minimum function for sets are used in [[database]]s, and can be computed rapidly, since the maximum (or minimum) of a set can be computed from the maxima of a partition; formally, they are self-[[decomposable aggregation function]]s.
		+
		+	In the case of a general [[partial order]], the '''least element''' (i.e., one that is smaller than all others) should not be confused with a '''minimal element''' (nothing is smaller). Likewise, a '''[[greatest element]]''' of a [[partially ordered set]] (poset) is an [[upper bound]] of the set which is contained within the set, whereas a '''maximal element''' ''m'' of a poset ''A'' is an element of ''A'' such that if ''m'' ≤ ''b'' (for any ''b'' in ''A''), then ''m'' = ''b''. Any least element or greatest element of a poset is unique, but a poset can have several minimal or maximal elements. If a poset has more than one maximal element, then these elements will not be mutually comparable.
		+
		+	In a [[total order\|totally ordered]] set, or ''chain'', all elements are mutually comparable, so such a set can have at most one minimal element and at most one maximal element. Then, due to mutual comparability, the minimal element will also be the least element, and the maximal element will also be the greatest element. Thus in a totally ordered set, we can simply use the terms '''''minimum''''' and '''''maximum'''''.
		+
		+	If a chain is finite, then it will always have a maximum and a minimum. If a chain is infinite, then it need not have a maximum or a minimum. For example, the set of [[natural number]]s has no maximum, though it has a minimum. If an infinite chain ''S'' is bounded, then the [[topological closure\|closure]] ''Cl''(''S'') of the set occasionally has a minimum and a maximum, in which case they are called the '''greatest lower bound''' and the '''least upper bound''' of the set ''S'', respectively.
		+
	==Convex and Concave Functions==		==Convex and Concave Functions==
	<blockquote style="background: white; border: 1px solid black; padding: 1em;">		<blockquote style="background: white; border: 1px solid black; padding: 1em;">

@@ Line 50: / Line 50: @@
 ==Licensing==
 Content obtained and/or adapted from:
-* [https://en.wikipedia.org/wiki/Maxima_and_minima] under a CC BY-SA license
+* [https://en.wikipedia.org/wiki/Maxima_and_minima Maxima and minima, Wikipedia] under a CC BY-SA license
-* [http://mathonline.wikidot.com/convex-and-concave-functions] under a CC BY-SA license
+* [http://mathonline.wikidot.com/convex-and-concave-functions Convex and Concave Functions, Mathonline] under a CC BY-SA license

← Older revision		Revision as of 23:22, 22 October 2021
Line 1:		Line 1:
−	~~https~~://en.~~wikipedia~~.~~org~~/~~wiki~~/~~Maxima_and_minima~~	+	==Convex and Concave Functions==
		+	<blockquote style="background: white; border: 1px solid black; padding: 1em;">
		+	:'''Definition''': A function <math>f : I \to \mathbb{R}</math> is said to be '''Convex''' if for every <math>x, y \in I</math> and for every <math>t \in [0, 1]</math> we have that
		+	:<math>f(tx + (1 - t)y) \leq tf(x) + (1 - t)f(y)</math>.
		+	:A function <math>f : I \to \mathbb{R}</math> is said to be '''Concave''' if for every <math>x, y \in I</math> and for every <math>t \in [0, 1]</math> we have that
		+	:<math>f(tx + (1 - t)y) \geq tf(x) + (1 - t)f(y)</math>.</td>
		+	</blockquote>

−	http://mathonline.wikidot.com/convex-and-concave-functions	+	We now give equivalent definitions for convex and concave functions.
		+	<blockquote style="background: white; border: 1px solid black; padding: 1em;">
		+	:'''Theorem 1:''' Let <math>f : I \to \mathbb{R}</math>.<br />
		+	:'''a)''' <math>f</math> is convex on <math>I</math> if and only if for all <math>a, b, c \in I</math> with <math>a < b < c</math> we have that <math>\displaystyle{\frac{f(b) - f(a)}{b - a} \leq \frac{f(c) - f(a)}{c - a}}</math>.<br />
		+	:'''b)''' <math>f</math> is concave on <math>I</math> if and only if for all <math>a, b, c \in I</math> with <math>a < b < c</math> we have that <math>\displaystyle{\frac{f(b) - f(a)}{b - a} \geq \frac{f(c) - f(a)}{c - a}}</math>.</td>
		+	</blockquote>
		+
		+	We only prove (a) above. The proof of (b) is analogous.</em></p>
		+	*'''Proof of a):''' Let ><math>a, b, c \in I</math> be such that <math>a < b < c</math>.</li>
		+
		+	*<math>\Rightarrow</math> Suppose that <math>f</math> is convex on <math>I</math>. Then for all <math>t \in [0, 1]</math> we have that:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad f(tx + (1 - t)y) \leq tf(x) + (1 - t)f(y) \end{align}</math></div>
		+	*Set <math>a = x</math>, <math>b = tx + (1-t)y</math>, and <math>c = y</math>. Combining the first and third equations with the second equation gives us:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad b = ta + (1-t)c \end{align}</math></div>
		+	*Solving for <math>t</math> gives us:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad b = ta + c - tc \\ \quad b - c = t(a - c) \\ \end{align}</math></div>
		+	*Therefore:
		+	<div style="text-align: center;"><math>\begin{align} \quad t = \frac{b - c}{a - c} = \frac{c - b}{c - a} \end{align}</math></div>
		+	*Similarly, we compute <math>1 - t</math> to be:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad 1 - t = \frac{c - a}{c - a} - \frac{c - b}{c - a} = \frac{b - a}{c - a} \end{align}</math></div>
		+	*From the convexity of <math>f</math> we have <math>f(tx + (1-t)y) \leq tf(x) + (1-t)f(y)</math>, or equivalently:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad f(b) \leq \frac{c - b}{c - a}f(a) + \frac{b - a}{c - a}f(c) \\ \end{align}</math></div>
		+	*And hence:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad (c - a)f(b) \leq (c - b)f(a) + (b - a)f(c) = (c - a + a - b)f(a) + (b - a)f(c) = (c - a)f(a) - (b - a)f(a) + (b - a)f(c) \end{align}</math></div>
		+	*Therefore:</li>
		+	<div style="text-align: center;"><math>\begin{align} \quad (c - a)[f(b) - f(a)] \leq (b - a)[f(c) - f(a)] \quad \Leftrightarrow \quad \frac{f(b) - f(a)}{b - a} \leq \frac{f(c) - f(a)}{c - a} \end{align}</math></div>
		+	*<math>\Leftarrow</math> Obtained by working backwards from above. <math>\blacksquare</math></li>
		+
		+	We state yet another important definition for convex and concave functions.</p>
		+
		+	<blockquote style="background: white; border: 1px solid black; padding: 1em;">
		+	:'''Theorem 2:''' Let ><math>f : I \to \mathbb{R}</math>.<br />
		+	:'''a)''' <math>f</math> is convex on ><math>I</math> if and only if for all ><math>a, b, c \in I</math> with ><math>a <; b <; c</math> we have that ><math>\displaystyle{\frac{f(b) - f(a)}{b - a} \leq \frac{f(c) - f(b)}{c - b}}</math>.<br />
		+	:'''b)''' <math>f</math> is concave on ><math>I</math> if and only if for all ><math>a, b, c \in I</math> with ><math>a <; b <; c</math> we have that ><math>\displaystyle{\frac{f(b) - f(a)}{b - a} \geq \frac{f(c) - f(b)}{c - b}}</math>.</td>
		+	</blockquote>
		+
		+	Theorem 2 gives us a nice characterization of convex functions. It tells us that a function <math>f : I \to \mathbb{R}</math> is convex if and only if whenever we take three points <math>a, b, c \in I</math> with <math>a <; b <; c</math> we have that the slope of the line connecting <math>(a, f(a))</math> and <math>(b, f(b))</math> is less than or equal to the sope of the line connecting <math>(b, f(b))</math> and <math>(c, f(c))</math>. In other words, the slope of the line segments connecting consecutive pairs of points on the graph of <math>f</math> is increasing.</p>
		+
		+	We can combine theorems 1 and 2 to get a nice chain of inequalities. That is, <math>f : I \to \mathbb{R}</math> is convex if and only if for all <math>a, b, c \in I</math> with ><math>a < b < c</math> we have that:</p>
		+	<div style="text-align: center;"><math>\begin{align} \frac{f(b) - f(a)}{b - a} \leq \frac{f(c) - f(a)}{c - a} \leq \frac{f(c) - f(b)}{c - b} \end{align}</math></div>
		+
		+	==Licensing==
		+	Content obtained and/or adapted from:
		+	* [https://en.wikipedia.org/wiki/Maxima_and_minima] under a CC BY-SA license
		+	* [http://mathonline.wikidot.com/convex-and-concave-functions] under a CC BY-SA license

← Older revision		Revision as of 19:09, 22 October 2021
Line 1:		Line 1:
		+	https://en.wikipedia.org/wiki/Maxima_and_minima

	http://mathonline.wikidot.com/convex-and-concave-functions		http://mathonline.wikidot.com/convex-and-concave-functions