 ) by the symbol H (g (x0)). It is matrix of second order partial derivatives @@xgi(@x j called the Hessian matrix of g(x) at x0. Let g1(x); : : :; gm(x) be m real valued convex functions de ned on the convex subset  Rn. For each x 2, de ne s(x) = Maximum f g1(x); : : :; gm(x) g. The function s(x) is known as the pointwise supremum or maximum of fg1(x); : : :; gm(x)g. It is also convex on. See Figure 2.4 where we illustrate the pointwise supremum of several ane functions de ned on the real line.
Figure 2.4 l1(x) to l5 (x) are ve ane functions de ned on R1. Function values are plotted on the vertical axis. Their pointwise maximum is the function marked with thick lines here.
where g(x0) is nite. The vector d = (d1; : : :; dn )T is said to be a subgradient of g(x) at x0 if n 0 T 0 g(x) > (2:39) = g(x ) + d (x x ); for all x 2 R : Notice that the right hand side of (2.39) is l(x) = (g(x0) dt x0 ) + dT x, is an ane function in x; and we have g(x0) = l(x0). One can verify that l(x) is the rst order Taylor expansion for g(x) around x0, constructed using the vector d in place of the gradient vector of g(x) at x0. So d is a subgradient of g(x) at x0, ithis modi ed Taylor approximation is always an underestimate for g(x) at every x.
veri ed that the inequality (2.39) holds in this case. So d = (2) is a subgradient for g(x) at x0 = 1 in this case. The ane function l(x) on the right hand side of (2.39) in this case is 1 + 2(x 1) = 2x 1. See Figures 2.5, 2.6 where the inequality (2.39) is illustrated.
Figure 2.5 A Convex Function, and the Ane Function Below it Constructed Using a Subgradient for it at the Point x0.
lines in the cone marked by the angle sign. The set of all subgradients of g(x) at x0 is denoted by the symbol @g(x0), and called the subdierential set of g(x) at x0. It can be proved that if g(x) is dierentiable at x0, then its gradient rg(x0) is the unique subgradient of g(x) at x0. Conversely if @g(x0) contains a single vector, then g(x) is dierentiable at x0 and @g(x0) = frg(x0)g. See references [2.92{2.94] for these and other related results.
Subgradients of Concave Functions Let h(x) be a concave function de ned on a convex subset  Rn. In de ning a subgradient vector for h(x) at a point x0 2, the inequality in (2.39) is just reversed; 0 in other words, d is a subgradient for the concave function h(x) at x0 if h(x) < = h(x )+ T 0 d (x x ) for all x. With this de nition, all the results stated above also hold for concave functions.
@(x) = convex hull of f rgi(x) : i 2 J(x) g : See references [2.92{2.94].
which is a system of n equations in n unknowns, has a solution x 2. See references [2.48, 2.50, 2.68, 2.69, 2.72] for proofs of this theorem. We now provide an illustration of this theorem.
Figure 2.7 The curve of f (x) : [0; 1]! [0; 1]. Points of intersection of the curve with the dashed diagonal line are the Brouwer xed points of f (x).
Example 2.19 This example illustrates the need for convexity in Theorem 2.13. Let n = 2. Let K denote the dotted ring in Figure 2.8 between two concentric circles. Let f (x) denote the continuous mapping K! K obtained by rotating the ring through a speci ed angle  in the anti-clockwise direction. Clearly this f (x) has no xed points in K.
theorem. The need for the boundedness of the set for the validity of Theorem 2.13 follows from the fact that the mapping f (x) = x + a for each x 2 Rn, where a 6= 0 is a speci ed point in Rn, has no xed points. The need for the closedness of the set for the validity of Theorem 2.13 follows from the fact that the mapping f (x) = 12 (x + 1) from the set fx : 0 < = x < 1g into itself has no xed point in the set. The system (2.40) is a system of n equality constraints in n unknowns. An eort can be made to solve (2.40) using methods for solving nonlinear equations.
A Monk’s Story The following story of a monk provides a nice intuitive justi cation for the concept and the existence of a xed point. A monk is going on a pilgrimage to worship in a temple at the top of a mountain. He begins his journey on Saturday morning at 6:00 AM promptly. The path to the temple is steep and arduous and so narrow that trekkers on it have to go in a single le. Our monk makes slow progress, he takes several breaks on the way to rest, and at last reaches the temple by evening. He spends the night worshipping at the temple. Next morning, he begins his return trip from the temple exactly at 6:00 AM, by the same path. On the return trip, since the path is downhill, he makes fast progress and reaches the point from where he started his hjourney on Saturday morning, well before the evening.
Suppose we call a point (or spot or location) on the path, a xed point, if the monk was exactly at that spot at precisely the same time of the day on both the forward and return trips. The existence of a xed point on the path can be proved using Brouwer's xed point theorem, but there is a much simpler and intuitive proof for its existence (see A. Koestler, The Act of Creation, Hutchinson, 1976, London). Imagine that on Saturday morning exactly at 6:00 AM, a duplicate monk starts from the temple, down the mountain, proceeding at every point of time at exactly the same rate that the original monk would on Sunday. So, at any point of time of the day on Saturday, the duplicate monk will be at the same location on the path as the original monk will be at the time on Sunday. Since the path is so narrow that both cannot pass without being in each other's way, the two monks must meet at some time during the day, and the spot on the path where they meet is a xed point.
If the map f (x) satis es the contraction proprety, this successsive substituitions method is a very convenient method for computing a Brouwer's xed point of f (x). Unfortunately, the contraction property is a strong property and does not usually hold in many practical applications.
x22 1 = 0. The parabola is the set of all points satisfying x21 x2 = 0. The two intersect in two points (solutions of the system) one of which is x. Beginning with x0, the Newton-Raphson method obtains the sequence x1 ; x2 ; : : : converging to x. In order to solve (2.40) by Newton-Raphson method or some modi ed versions of it, the map f (x) must satisfy strong properties like being dierentiable etc., which do not hold in may many practical applications. Thus, to use Brouwer's xed point theorem in practical applications we should devise methods for solving (2.40) without requiring the map f (x) to satisfy any conditions besides continuity. In 1967 H. Scarf in a pioneering paper [2.68] developed a method for nding an approximate solution of (2.40) using a triangulation of the space, that walks through the simplices of the triangulation along a path satisfying properties similar to the one traced by the complementary pivot algorithm for the LCP. This method has the advantage that it works without requiring any conditions on the map f (x) other than those required by Brouwer's theorem for the existence of the xed point (i. e., continuity). Subsequently vastly improved versions of these methods have been developed by many researches. We will discuss one of these methods in detail.
jjx yjj < " : In general, a Type 1 approximate Brouwer xed point x may not be a Type 2 approximate Brouwer xed point, that