L1 Compactness of Bounded BV Sets

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS:Vol.109,No.3,pp.475–494,JUNE2001 Convergence of a Block Coordinate DescentMethod for Nondifferentiable Minimization1P.T SENG2Communicated by O.L.MangasarianAbstract.We study the convergence properties of a(block)coordinatedescent method applied to minimize a nondifferentiable(nonconvex)function f(x1,...,x N)with certain separability and regularity proper-ties.Assuming that f is continuous on a compact level set,the sub-sequence convergence of the iterates to a stationary point is shown wheneither f is pseudoconvex in every pair of coordinate blocks from amongN A1coordinate blocks or f has at most one minimum in each of N A2coordinate blocks.If f is quasiconvex and hemivariate in every coordi-nate block,then the assumptions of continuity of f and compactness ofthe level set may be relaxed further.These results are applied to derivenew(and old)convergence results for the proximal minimization algo-rithm,an algorithm of Arimoto and Blahut,and an algorithm of Han.They are applied also to a problem of blind source separation.Key Words.Block coordinate descent,nondifferentiable minimization,stationary point,Gauss–Seidel method,convergence,quasiconvex func-tions,pseudoconvex functions.1.IntroductionA popular method for minimizing a real-valued continuously differen-tiable function f of n real variables,subject to bound constraints,is the (block)coordinate descent method.In this method,the coordinates are par-titioned into N blocks and,at each iteration,f is minimized with respect to one of the coordinate blocks while the other coordinates are heldfixed.This method,which is related closely to the Gauss–Seidel and SOR methods for equation solving(Ref.1),was studied early by Hildreth(Ref.2)and Warga (Ref.3),and is described in various books on optimization(Refs.1and4–1This work was partially supported by the National Science Foundation Grant CCR-9731273. 2Professor,Department of Mathematics,University of Washington,Seattle,Washington.4750022-3239͞01͞0600-0475$19.50͞0 2001Plenum Publishing Corporation476JOTA:VOL.109,NO.3,JUNE200110).Its applications include channel capacity computation(Refs.11–12), image reconstruction(Ref.7),dynamic programming(Refs.13–15),and flow routing(Ref.16).It may be applied also to the dual of a linearly constrained,strictly convex program to obtain various decomposition methods(see Refs.6–7,17–22,and references therein)and parallel SOR methods(Ref.23).Convergence of the(block)coordinate descent method requires typi-cally that f be strictly convex(or quasiconvex or hemivariate)differentiable and,taking into account the bound constraints,has bounded level sets(e.g., Refs.3–4and24–25).Zadeh(Ref.26;also see Ref.27)relaxed the strict convexity assumption to pseudoconvexity,which allows f to have a non-unique minimum along coordinate directions.For certain classes of convex functions,the level sets need not be bounded(see Refs.2,6–7,17,19–22, and references therein).If f is not(pseudo)convex,then an example of Powell(Ref.28)shows that the method may cycle without approaching any stationary point of f.Nonetheless,convergence can be shown for special cases of non(pseudo)convex f,as when f is quadratic(Ref.29),or f is strictly pseudoconvex in each of N A2coordinate blocks(Ref.27),or f has unique minimum in each coordinate block(Ref.8,p.159).If f is not differentiable, the coordinate descent method may get stuck at a nonstationary point even when f is convex(e.g.,Ref.4,p.94).For this reason,it is perceived generally that the method is unsuitable when f is nondifferentiable.However,an exception occurs when the nondifferentiable part of f is separable.Such a structure for f was consideredfirst by Auslender(Ref.4,p.94)in the case where f is strongly convex.This structure is implicit in a decomposition method and projection method of Han(Refs.18,30),for which f is the convex dual functional associated with a certain linearly constrained convex program(see Ref.22for detailed discussions).This structure arises also in least-square problems where an l1-penalty is placed on a subset of the para-meters in order to minimize the support(see Refs.31–33and references therein).Motivated by the preceding works,we consider in this paper the non-differentiable(nonconvex)case where the nondifferentiable part of f is sep-arable.Specifically,we assume that f has the following special form:Nf k(x k),(1)f(x1,...,x N)G f0(x1,...,x N)C∑k G1for some f0:ℜn1C···C n N>ℜ∪{S}and some f k:ℜn k>ℜ∪{S},k G 1,...,N.Here,N,n1,...,n N are positive integers.We assume that f is pro-per,i.e.,f͞≡S.We will refer to each x k,k G1,...,N,as a coordinate block of x G(x1,...,x N).We will show that each cluster point of the iterates generated by the(block)coordinate descent method is a stationary point ofJOTA:VOL.109,NO.3,JUNE2001477 f,provided that f0has a certain smoothness property(see Lemma3.1),f is continuous on a compact level set,and either f is pseudoconvex in every pair of coordinate blocks from among N A1coordinate blocks,or f has at most one minimum in each of N A2coordinate blocks(see Theorem4.1). If f is quasiconvex and hemivariate in every coordinate block,then the assumptions of continuity of f and compactness of the level set may be relaxed further(see Proposition5.1).These results unify and extend some previous results in Refs.4,6,8,26–27.For example,previous results assumed that f is pseudoconvex and that f1,...,f N are indicator functions for closed convex sets,whereas we assume only that f is pseudoconvex in every pair of coordinate blocks from among N A1coordinate blocks,with no additional assumption made on f1,...,f N.Previous results also did not consider the case where f is not continuous on its effective stly, we apply our results to derive new(and old)convergence results for the proximal minimization algorithm,an algorithm of Arimoto and Blahut (Refs.11–12),and an algorithm of Han(Ref.30);see Examples6.1–6.3. We also apply them to a problem of blind source separation described in Refs.31,33;see Example6.4.In our notation,ℜm denotes the space of m-dimensional real column vector.For any x,y∈ℜm,we denote by〈x,y〉the Euclidean inner product of x,y and by͉͉x͉͉the Euclidean norm of x,i.e.,͉͉x͉͉G1.For any set S⊆ℜm,we denote by int(S)the interior of S and denote bdry(S)G S\int(S).For any h:ℜm>ℜ∪{S},we denote by dom h the effective domain of h, i.e.,dom h G{x∈ℜm͉h(x)FS}.For any x∈dom h and any d∈ℜm,we denote the(lower)directional deriva-tive of h at x in the direction d byh′(x;d)G lim inf[h(x Cλd)A h(x)]͞λ.λ↓0We say that h is quasiconvex ifh(x Cλd)⁄max{h(x),h(x C d)},for all x,d andλ∈[0,1];h is pseudoconvex ifh(x C d)¤h(x),whenever x∈dom h and h′(x;d)¤0;see Ref.34,p.146;and h is hemivariate if h is not constant on any line segment belonging to dom h(Ref.1).For any nonempty I⊆{1,...,m},weJOTA:VOL.109,NO.3,JUNE 2001478say that h (x 1,...,x m )is pseudoconvex [respectively,has at most one mini-mum point].2.Block Coordinate Descent MethodWe describe formally the block coordinate descent (BCD)method below.BCD Method.Initialization.Choose any x 0G (x 01,...,x 0N )∈dom f .Iteration r C 1,r ¤0.Given x r G (x r 1,...,x r N )∈dom f ,choose an indexs ∈{1,...,N }and compute a new iteratex r C 1G (x r C 11,...,x r C 1N )∈dom fsatisfyingx r C 1s ∈arg min x s f (x r 1,...,x r s A 1,x s ,x r s C 1,...,x r N ),(2)x r C 1j G x r j ,∀j ≠s .(3)We note that the minimization in (2)is attained ifX 0G {x :f (x )⁄f (x 0)}is bounded and f is lower semicontinuous (lsc)on X 0,so X 0is compact (Ref.35).Alternatively,this minimization is attained if f is convex,has a minimum point,and is hemivariate in each coordinate block (but the level sets of f need not be bounded).To ensure convergence,we need further that each coordinate block is chosen suf ficiently often in the method.In particu-lar,we will choose the coordinate blocks according to the following rule (see,e.g.,Refs.7–8,21,25).Essentially Cyclic Rule.There exists a constant T ¤N such that every index s ∈{1,...,N }is chosen at least once between the r th iteration and the (r C T A 1)th iteration,for all r .A well-known special case of this rule,for which T G N ,is given below.Cyclic Rule.Choose s G k at iterations k ,k C N ,k C 2N ,...,for k G 1,...,N .JOTA:VOL.109,NO.3,JUNE2001479 3.Stationary Points of fWe say that z is a stationary point of f if z∈dom f andf′(z;d)¤0,∀d.We say that z is a coordinatewise minimum point of f if z∈dom f and f(z C(0,...,d k,...,0))¤f(z),∀d k∈ℜn k,(4) for all k G1,...,N.Here and throughout,we denote by(0,...,d k, 0the vector inℜn1C···C n N whose k th coordinate block is d k and whose other coordinates are zero.We say that f is regular at z∈dom f iff′(z;d)¤0,∀d G(d1,...,d N),such that f′(z;(0,...,d k,...,0))¤0,k G1,...,N.(5) This notion of regularity is weaker than that used by Auslender(Ref.4, p.93),which entailsNf′(z;(0,...,d k,...,0)),for all d G(d1,...,d N).f′(z;d)G∑k G1For example,the functionf(x1,x2)Gφ(x1,x2)Cφ(−x1,x2)Cφ(x1,−x2)Cφ(−x1,−x2),whereφ(a,b)G max{0,a C b A1a2C b2},is regular at z G(0,0)in the sense of(5),but is not regular in the sense of Ref.4,p.93.Since(4)impliesf′(z;(0,...,d k,...,0))¤0,for all d k,it follows that a coordinatewise minimum point z of f is a stationary point of f whenever f is regular at z.To ensure regularity of f at z,we consider one of the following smoothness assumptions on f0:(A1)dom f0is open and f0is Gaˆteaux-differentiable on dom f0.(A2)f0is Gaˆteaux-differentiable on int(dom f0)and,for every z∈dom f∩bdry(dom f0),there exist k∈{1,...,N}and d k∈ℜn ksuch that f(z C(0,...,d k,...,0))F f(z).JOTA:VOL.109,NO.3,JUNE2001480Assumption A1was considered essentially by Auslender(Ref.4, Example2on p.94).In contrast to Assumption A1,Assumption A2allows dom f0to include boundary points.We will see an application(Example 6.2)where A2holds but not A1.Lemma3.1.Under A1,f is regular at each z∈dom f.Under A2,f is regular at each coordinatewise minimum point z of f.Proof.Under A1,if z G(z1,...,z N)∈dom f,then z∈dom f0.Under A2,if z G(z1,...,z N)is a coordinatewise minimum point of f,then z∉bdry(dom f0),so z∈int(dom f0).Thus,under either A1or A2,f0is Gaˆteaux-differentiable at z.Fix any d G(d1,...,d N)such thatf′(z;(0,...,d k,...,0))¤0,k G1,...,N.Then,f′(z;d)G〈∇f0(z),d〉C lim infλ↓0∑Nk G1[f k(x k Cλd k)A f k(x k)]͞λ¤〈∇f(z),d〉C∑Nk G1lim infλ↓0[f k(x k Cλd k)A f k(x k)]͞λG〈∇f(z),d〉C∑Nk G1f′k(z k;d k)G∑Nk G1f′(z;(0,...,d k,...,0))¤0.ᮀ4.Convergence Analysis:IOurfirst convergence result unifies and extends a result of Auslender (Ref.4,p.95)for the nondifferentiable convex case and some results of Grippo and Sciandrone(Ref.27),Luenberger(Ref.8,p.159),and Zadeh (Ref.26)for the differentiable case.In what follows,r≡(N A1)mod N means r G N A1,2N A1,3N A1,....Theorem 4.1.Assume that the level set X0G{x:f(x)⁄f(x0)}is compact and that f is continuous on X0.Then,the sequence {x r G(x r1,...,x r N)}r G0,1,...generated by the BCD method using the essen-tially cyclic rule is defined and bounded.Moreover,the following statementsJOTA:VOL.109,NO.3,JUNE2001481 hold:(a)If f(x1,...,x N)is pseudoconvex in(x k,x i)for every i,k∈{1,...,N},and if f is regular at every x∈X0,then every clusterpoint of{x r}is a stationary point of f.(b)If f(x1,...,x N)is pseudoconvex in(x k,x i)for every i,k∈{1,...,N A1},if f is regular at every x∈X0,and if the cyclic ruleis used,then every cluster point of{x r}r≡(N A1)mod N is a stationarypoint of f.(c)If f(x1,...,x N)has at most one minimum in x k for k G2,...,N A1,and if the cyclic rule is used,then every cluster pointz of{x r}r≡(N A1)mod N is a coordinatewise minimum point of f.Inaddition,if f is regular at z,then z is a stationary point of f.Proof.Since X0is compact,an induction argument on r shows thatx r C1is defined,f(x r C1)⁄f(x r),and x r C1∈X0for all r G0,1,....Thus,{x r} is bounded.Consider any subsequence{x r}r∈R,with R⊆{0,1,...},con-verging to some z.For each j∈{1,...,T},{x r A T C1C j}r∈R is bounded,so bypassing to a subsequence,if necessary,we can assume that{x r A T C1C j}r∈R converges to some z j G(z j1,...,z j N),j G1,...,T. Thus,z T A1G z.Since{f(x r)}converges monotonically and f is continuous on X0,weobtain thatf(x0)¤limr→Sf(x r)G f(z1)G···G f(z T).(6)By further passing to a subsequence,if necessary,we can assume that the index s chosen at iteration r A T C1C j,j∈{1,...,T},is the same for all r∈R,which we denote by s j.For each j∈{1,...,T},since s j is chosen at iteration r A T C1C j for r∈R,then(2)and(3)yieldf(x r A T C1C j)⁄f(x r A T C1C j C(0,...,d s j,...,0)),∀d s j,j G1,...,T,x r A T C1C j k G x r A T C jk,∀k≠s j,j G2,...,T.Then,the continuity of f on X0yields in the limit thatf(z j)⁄f(z j C(0,...,d s j,...,0)),∀d s j,j G1,...,T,z j k G z j A1k ,∀k≠s j,j G2,...,T.(7)482JOTA:VOL.109,NO.3,JUNE2001Then,(6)and(7)yieldf(z j A1)⁄f(z j A1C(0,...,d s j,...,0)),∀d s j,j G2,...,T.(8)(a),(b)Suppose that f is regular at every x∈X0and that f(x1,...,x N) is pseudoconvex in(x k,x i)for every i,k∈{s1}∪···∪{s T A1}.This holds under the assumption(a)or under the assumption(b),with{x r}r∈R being any convergent subsequence of{x r}r≡(N A1)mod N.We claim that,for j G 1,...,T A1,f(z j)⁄f(z j C(0,...,d k,...,0)),∀d k,∀k G s1,...,s j.(9) By(7),(9)holds for j G1.Suppose that(9)holds for j G1,...,l A1for some l∈{2,...,T A1}.We show that(9)holds for j G l.From(8),we have that f(z l A1)⁄f(z l A1C(0,...,d s l,...,0)),∀d s l,implying,...,0))¤0.f′(z l A1;(0,...,z l s l A z l A1s lAlso,since(9)holds for j G l A1,we have that,for each k G s1,...,s l A1, f′(z l A1;(0,...,d k,...,0))¤0,∀d k.Since by(6)z l A1∈X0,so f is regular at z l A1,the above two relations imply f′(z l A1;(0,...,d k,...,0)C(0,...,z l s l A z l A1,...,0))¤0,∀d k.s lSince f is pseudoconvex in(x k,x s l),this yields[also using z l G z l A1C ,...,0)]for k G s1,...,s l A1that(0,...,z l s l A z l A1s lf(z l C(0,...,d k,...,0))¤f(z l A1)G f(z l),∀d k.Since we have also that(7)holds with j G l,we see that(9)holds for j G l. By induction,(9)holds for all j G1,...,T A1.Since z T A1G z and(9)holds for j G T A1,then(4)holds for k G s1,...,s T A1.Since z T A1G z and(8)holds(in particular,for j G T),then(4) holds for k G s T also.Since{1,...,N}G{s1}∪···∪{s T},this implies that z is a coordinatewise minimum point of f.Since f is regular at z,then z is in fact a stationary point of f.(c)Suppose that f(x1,...,x N)has at most one minimum in x k for k G s2,...,s T A1.This holds under the assumption(c),with{x r}r∈R being any convergent subsequence of{x r}r≡(N A1)mod N.For each j G2,...,T A1,sinceJOTA:VOL.109,NO.3,JUNE 2001483(7)and (8)hold,then the functiond s j >f (z j C (0,...,d s j ,...,0))attains its minimum at both d s j G 0and d s j G z j A 1s j A z j s j .By assumption,the minimum point is unique,implying 0G z j A 1s j A z j s j ,or equivalently,z j A 1Gz j .Thus,z 1G z 2G ···G z T A 1G z and (7)yields that (4)holds for k G s 1,...,s T A 1.Since z T A 1G z and (8)holds (in particular,for j G T ),then (4)holds for k G s T also.Since{1,...,N }G {s 1}∪···∪{s T },this implies that z is a coordinatewise minimum point of f .If f is regular at z ,then z is also a stationary point of f .ᮀNotice that,if f is pseudoconvex,then f is pseudoconvex in (x k ,x i )for every i ,k ∈{1,...,N };if f is quasiconvex and hemivariate in x k ,then f has at most one minimum in x k .The converses do not hold.For example,the 2-variable Rosenbrock function has a unique minimum point but is not quasiconvex.The following 3-variable quadratic functionf (x 1,x 2,x 3)G (1͞2)x 21C (1͞2)x 22C (1͞2)x 23C x 1x 3C x 2x 3A x 1x 2is convex in every pair of variables,but is not pseudoconvex.In particular,for x G (0,0,1͞2)and d G (1,1,−1),we have f ′(x ;d )G 1͞2¤0,while f (x C d )G −7͞8F f (x )G 1͞8.This example generalizes to any quadratic functionf (x )G 〈x ,Qx 〉.where Q ∈R N B N is symmetric,not positive semide finite,but whose 2B 2principal submatrices are positie semide finite.Then,for any d satisfying 〈d ,Qd 〉F 0and any x satisfying0⁄〈x ,Qd 〉F −(1͞2)〈d ,Qd 〉,we have thatf ′(x ;d )¤0,while f (x C d )F f (x ).Thus,parts (a)and (c)of Theorem 4.1may be viewed as extensions of two results of Grippo and Sciandrone (Ref.27,Propositions 5.2,5.3)for the case of f 0being continuously differentiable and each f k being the indicator function of some closed convex set.In turn,the first of these results extended a result of Zadeh (Ref.26)for which f k ≡0for all k .Part (b)makes a less restrictive assumption on f than part (a),though its assumption on the BCD method is more restrictive.Part (b)is sharp in the sense that it is false if instead we assume that f is convex in every coordinate block.This484JOTA:VOL.109,NO.3,JUNE2001is because the Powell3-variable example(Ref.28)is convex in each variable; see Ref.27,Section6for further discussions of the example.We will see an application(Example6.4)in which part(b)applies but not part(a)nor(c).5.Convergence Analysis:IIThe convergence analysis of the previous section assumes f to be con-tinuous on a bounded level set and makes no use of the special structure(1) of f.In this section,we show that this assumption can be relaxed by exploiting the special structure(1),provided that f is quasiconvex and hemi-variate in each coordinate block.More precisely,we will make the following assumptions on f,f0,f1,...,f N:(B1)f0is continuous on dom f0.(B2)For each k∈{1,...,N}and(x j)j≠k,the function x k> f(x1,...,x N)is quasiconvex and hemivariate.(B3)f0,f1,...,f N are lsc.We will see some applications(Ref.6,Section3.4.3and Examples6.1–6.3)for which f satisfies this weaker assumption although it is not strictly convex.In addition,we will make one of the following technical assump-tions on f0:(C1)dom f0is open and f0tends to S at every boundary point of dom f0.(C2)dom f0G Y1B···B Y N,for some Y k⊆R n k,k G1,...,N.In contrast to Assumption C1,Assumption C2allows f0to have afinite value on bdry(dom f).We will see in Example6.2a nonseparable function f0that satisfies Assumptions B1–B3and C2,but not C1.We show below that Assumptions B1–B3,together with either Assumption C1or C2,ensure that every cluster point of the iterates generated by the BCD method is a coordinate minimum point of f.The proof of this result is patterned after an argument given by Bertsekas and Tsitsiklis(Ref.6,pp.220–221;also see Ref.27),but is complicated by the fact that f is not necessarily differentiable (or even continuous)on its effective domain.Proposition5.1.Suppose that f,f0,f1,...,f N satisfy Assumptions B1–B3and that f0satisfies either Assumption C1or C2.Also,assume that the sequence{x r G(x r1,...,x r N)}r G0,1,...generated by the BCD method using the essentially cyclic rule is defined.Then,either{f(x r)}↓−S,or else every cluster point z G(z1,...,z N)is a coordinatewise minimum point of f.Proof.Since f(x0)FS and f(x r C1)⁄f(x r)for all r,then either {f(x r)}↓−S,or else{f(x r)}converges to some limit and{f(x r C1)A f(x r)}→0.Consider the latter case and let z be any cluster point of{x r}. Since f is lsc by Assumption B3,we havef(z)⁄limr→Sf(x r)FS,so z∈dom f.We show below that z satisfies(4)for k G1,...,N.First,we claim that,for any infinite subsequence{x r}r∈R→z,(10) with R⊆{0,1,...},there holds that(x r C1}r∈R→z.(11) We prove this by contradiction.Suppose that this were not true.Then,there exists an infinite subsequence R′of R and a scalar(H0such that ͉͉x r C1A x r͉͉¤(,for all r∈R′.By further passing to a subsequence,if necessary,we can assume that there is some nonzero vector d for which{(x r C1A x r)͉͉͞x r C1A x r͉͉}r∈R′→d,(12) and that the same coordinate block,say x s,is chosen t the(r C1)st iteration for all r∈R′.Moreover,(10)implies that{f0(x r)}r∈R and{f k(x r k)}r∈R,k G 1,...,N,are bounded from below,which together with the convergence of{f(x r)}G{f0(x r)C∑Nk G1f k(x r k)}implies that{f0(x r)}r∈R and{f k(x r k)}r∈R,k G1,...,N,are bounded.Hence,by further passing to a subsequence,if necessary,we can assume that there is some scalarθfor which{f0(x r)C f s(x r s)}r∈R′→θ.(13) Fix anyλ∈[0,(].LetzˆG z Cλd,(14) and for each r∈R′,letxˆr G x r Cλ(x r C1A x r)͉͉͞x r C1A x r͉͉.(15) Then,by(10),(12),and(14),{xˆr}r∈R′→zˆ.(16) For each r∈R′,we see from(2)that x r C1is obtained from x r by minimizing f with respect to x s,while the other coordinates are heldfixed.Sinceλ͉͉͞x r C1A x r͉͉⁄λ͞(⁄1,so xˆr lies on the line segment joining x r with x r C1,this together with f(x r C1)⁄f(x r)and the quasiconvexity of x s>f(x r1,...,x r s A1,x s, x r s C1,...,x r N)impliesf(xˆr)⁄f(x r),∀r∈R′.Since f is lsc,this and(16)imply zˆ∈dom f.Also,this and(1)and the obser-vation that x r and xˆr differ only in their s th coordinate block imply f0(xˆr)C f s(xˆr s)⁄f0(x r)C f s(x r s),∀r∈R′.This combined with(13)yieldslimr→S,r∈R′sup{f0(xˆr)C f s(xˆr s)}⁄θ.(17) Also,since{f(x r C1)A f(x r)}r∈R′→0,we have equivalently that{f0(x r C1)C f s(x r C1s)A f0(x r)A f s(x r s)}r∈R′→0,so(13)implies{f0(x r C1)C f s(x r C1s)}r∈R′→θ.(18) LetδG f0(zˆ)C f s(zˆs)Aθ.Since f0and f s are lsc,we have from(16),(17)thatδ⁄0.We claim that in factδG0.Suppose that this were not true,so thatδH0.By(16)and the observation that,for all r∈R′,xˆr and x r differ in only their s th coordinate block,we have{(x r1,...,x r s A1,zˆs,x r s C1,...,x r N)}r∈R′→zˆ.(19) Moreover,the vector on the left-hand side of(19)is in dom f0for all r∈R′sufficiently large.Since zˆ∈dom f0,this is certainly true under Assumption C1;under Assumption C2,this is also true because x r∈dom f0for all r and dom f0has a product structure corresponding to the coordinate blocks. Then,(18)together with(19)and the continuity of f0on dom f0implies that,for all r∈R′sufficiently large,there holds thatf0(x r1,...,x r s A1,zˆs,x r s C1,...,x r N)C f s(zˆs)⁄f0(x r C1)C f s(x r C1s)Cδ͞2,or equivalently[via(1)and the observation that x r and x r C1differ in only their s th coordinate block],f(x r1,...,x r s A1,zˆs,x r s C1,...,x r N)⁄f(x r C1)Cδ͞2,a contradiction to the fact that x r C1is obtained from x r by minimizing f with respect to the s th coordinate block,while the other coordinates are heldfixed.Hence,δG0and thereforef0(zˆ)C f s(zˆs)Gθ.Since the choice ofλwas arbitrary,we obtain[also using(14)]f0(z Cλd)C f s(z s Cλd s)Gθ,∀λ∈[0,(],where d s denotes the s th coordinate block of d.Since x r and x r C1differ in only their s th coordinate block for all r∈R′,then all coordinate blocks of d,except d s,are zero[see(12)],and the above relation,together with(1), shows that f(z Cλd)is constant(andfinite)for allλ∈[0,(],a contradiction to Assumption B2,namely,that f is hemivariate in the s th coordinate block. Hence,(11)holds.Since(11)holds for any subsequence{x r}r∈R of{x r}converging to z, we can apply(11)to the subsequence{x r C1}r∈R to conclude that {x r C2}r∈R→z and so on,yielding{x r C j}r∈R→z,∀j G0,1,...,T,(20) where T is the bound specified in the essentially cyclic rule.We claim that(20),together with Assumption C1or C2,implies f0(z)C f k(z k)⁄f0(z1,...,z k A1,x k,z k C1,...,z N)C f k(x k),(21) for all x k and all k∈{1,...,N}.To see this,fix any k∈{1,...,N}.Since the coordinate blocks are chosen according to the essentially cyclic rule, there exists some j∈{1,...,T}and an infinite subsequence R′⊆R such that the coordinate block x k is chosen at the(r C j)th iteration for all r∈R′.Then,for each r∈R′,x r C j k minimizes f0(x r C j1,...,x r C j k A1,x k, x r C j k C1,...,x r C j N)C f k(x k)over all x k[see(1),(2),(3)],so thatf0(x r C j)C f k(x r C j k)(x r C j1,...,x r C j k A1,x k,x r C j k C1,...,x r C j N)C f k(x k),∀x k.(22)⁄fFix any x k∈dom f k such that(z1,...,z k A1,x k,z k C1,...,z N)∈dom f0. Suppose that Assumption C1holds,so dom f0is open.Since z∈dom f0,then(20)implies that(x r C j1,...,x r C j k A1,x k,x r C j k C1,...,x r C j N)∈dom f0,for all r∈R′sufficiently large. Passing to the limit as r→S,r∈R′,and using the lsc property of f k and the continuity of f0on the open set dom f0,we obtain from(20) and(22)that(21)holds.Suppose instead that Assumption C2holds,sodom f0G Y1B···B Y N,for some Y1⊆ℜn1,...,Y N⊆ℜn N.Then,thefirst quantity on the right-hand side of(22)isfinite for all r∈ℜ′.Passing to the limit as r→S,r∈ℜ′,and using the lsc property of f k and the continuity of f0on dom f0,we obtain from(20)and(22)that (21)holds.If x k∉dom f k or(z1,...,z k A1,x k,z k C1,...,z N)∉dom f0,then the right-hand side of(21)has the extended value S,so(21)holds trivially.Since the above choice of k was arbitrary,this shows that(21) holds for all x k and all k∈{1,...,N}.Then,it follows from(1)that(4) holds for all k G1,...,N.ᮀProposition5.1extends a result of Grippo and Sciandrone(Ref.27, Proposition5.1)for the special case where each f k is the indicator func-tion for some closed convex set and f0is continuously differentiable and (block)coordinatewise strictly pseudoconvex.In turn,the latter result is an extension of a result of Bertsekas and Tsitsiklis(Ref.6,Proposition 3.9in Section3.3.5),which assumes further f0to be convex.As a cor-ollary of Proposition5.1,we obtain the following convergence result for the BCD method.Theorem5.1.Suppose that f,f0,f1,...,f N satisfy Assumptions B1–B3and that f0satisfies either Assumption C1or C2.Also,assume that {x:f(x)⁄f(x0)}is bounded.Then,the sequence{x r}generated by the BCD method using the essentially cyclic rule is defined,bounded,and every cluster point is a coordinatewise minimum point of f.Theorem5.1extends a result of Auslender[see Theorem1.2(a)in Ref. 4,p.95]for the special case where f k is convex for all k,dom f0G Y1B···B Y N for some closed convex sets Y k⊆ℜn k,k G1,...,N,and f0is strongly convex and continuous on dom f0.6.ApplicationsWe describe four interesting applications of the BCD method below. In all applications,the objective function f is not necessarily strictly convex nor differentiable everywhere on its effective domain.Example6.1.Proximal Minimization Algorithm.Letψ:ℜn>ℜ∪{S}be a proper(i.e.,ψ͞≡S)lsc function.Fix any scalar c H0,and consider the proper lsc function f defined byf(x,y)G c͉͉x A y͉͉2Cψ(x).Clearly,this function has the form(1)withf0(x,y)G c͉͉x A y͉͉2,f1Gψ,f2≡0.Applying the BCD method to f yields a method whereby f(x,y)is alter-nately minimized with respect to x and y.This method has the form x r C1G arg minc͉͉x A x r͉͉2Cψ(x),r G0,1,...,xwhich is the proximal minimization algorithm withfixed parameter c for minimizingψ;see Ref.6,Section3.4.3and Refs.36–37and references therein.It is easily seen that f,f0,f1,f2satisfy Assumptions B1–B3and that f0 satisfies Assumptions A1and C1.Moreover,f is regular everywhere on dom f.Then,by Proposition5.1,ifψis bounded below(so,f is bounded below),then every cluster point z of the iterates generated by the above proximal minimization algorithm is a stationary point ofψ,i.e.,ψ′(z;d)¤0,for all d.Notice that Theorem4.1is not applicable here,since f need not be continu-ous on its level sets.Example6.2.Arimoto–Blahut Algorithm.Let P ij,i G1,...,n,j G 1,...,m,be given nonnegative scalars satisfyingP ij G1,for all i.∑jThe P ij may be viewed as probabilities.Consider the proper lsc function f defined byf(x,y)G f0(x,y)C f1(x)C f2(y),。

用柯西收敛原理证明有限覆盖定理柯西收敛原理是实分析中的一个重要定理，它给出了一种数列或函数收敛的判别方法。

该原理表述为：一个实数列是收敛的，当且仅当它是柯西数列。

换句话说，对于任意给定的正数ϵ，存在一个正整数N，使得对所有的n,m>N，不等式|an - am| < ϵ都成立。

这个原理是由奥古斯丁·路易·柯西在19世纪提出的。

The Cauchy convergence principle is an important theorem in real analysis, providing a criterion for the convergence of a sequence or function. The principle states that a real sequence converges if and only if it is a Cauchy sequence. In other words, for any given positive number ϵ, there exists a positive integer N such that for all n, m>N, the inequality |an - am| < ϵ holds. This principle was formulated by Augustin-Louis Cauchy in the 19th century.有限覆盖定理是实数上的一个重要性质，它指出了实数集合的紧性质。

该定理表述为：如果实数集合有一个有限覆盖，那么这个集合就是有界的。

换句话说，如果存在有限个开区间，它们的并集包含了整个实数集合，那么这个实数集合是有界的。

The finite cover theorem is an important property of the real numbers, indicating the compactness of a set of real numbers. The theorem states that if a set of real numbers has a finite cover, then the set is bounded. In other words, if there exist a finite number of open intervals whose union contains the entire set of real numbers, then the set of real numbers is bounded.有限覆盖定理的证明可以利用柯西收敛原理。

本科毕业设计（论文）外文文献资料翻译院（系部）数学与信息科学学院专业名称数学与应用数学专业年级班级学生姓名学生学号2013年6月1日Compact SpacesThe notion of component is not nearly so natural as that of connectedness.From the beginnings of topology,it was clear that the closed interval []b a , of the real line had a certain proerty that was crucial for proving such thorrems as the maximum value theorem and the uniform continuity theorem .But for a long time,it was not clear how this property should be formulated for an arbitrary topological space.It used to be though that the crucial property of []b a , was the fact that every infinte subset of []b a , has a limit point,and this property was the one dignified with the name of ter ,mathematicians realized that this formulation does not lie at the heart of the matter,but rather that a stronger formulation,in terms of open coverings of the space,is morecentral.The latter formulation is what we now call compactness.It is not as natural or intuitive as the former,some familiarity with it is needed before its usefulness becomes apparent.Definition. A collection A of subsets of a space X is said to cover X ,or to be a covering of X ,if the union of the elements of A is equal to X .It is called an open covering of X if its elements are open subsets of X .Definition. A space X is said to be compact if every open covering A of X contains a finite subcollection that also covers X .EXAMPLE1. The real line R is not compact,for the covering of R by open intervals(){}+∈+=A Z n n n 2. contains no finite subcollection that covers R .EXAMPLE2. The following subspace of R is compact:{}{}+∈⋃=Z n nX 10. Given an open covering A of X ,there is an element U of A containing 0.The set U contains all but finitely many of the points n1;choose,for each points of X not in U ,an element of A containing it.The collection consisting of these elements of A ,along with the element U ,is a finite subcollection of A that covers X .EXAMPLE3. Any space X containing only finitely many points is necessarily compacts,because in this case every open covering of X is finite.EXAMPLE4 The interal (]1,0 is not compact;the open covering(]{}+∈=A Z n n1,1contains no finite subcollection covering (]1,0.Nor is the interal ()1,0 compact;the same argument applies.On the other hand,interal []1,0 is copact;you are probably already familiar with this fact from analysis.In any case,we shall prove it shortly.In general,it takes some effort to decide whether a given space is compact or not.First we shall prove some general theorems that show us how to construct new compact spaces out of existing ones. Then in the next section we shall show certain specific spaces are compact.The spaces include all closed interals in the real line,and all closed and bounded subsets of n R Let us first prove some facts about subspaces.If Y is a subspace of X ,a collection A of subsets of X is said to cover Y if the union of its elements contaons Y .Lemma 1. Let Y be a subspace of X .Then Y is compact if and only if every covering of Y by sets open in X contains a finite subcollection covering Y .Proof . Suppose that Y is compact and J }{A ∈=A αα is a covering of Y by sets open in X .Then the collection}{J Y A ∈ααis a covering of Y by sets of Y ;hence a finite subcollectionY}Y,{A 1 n A ααcovers Y .Then },{1n A A αα is a subcollection of A that covers Y .Coversely,suppose the given condition holds:we wish to prove Y compact.Let }{A 'α=A ‘ be a covering of Y by sets open in Y .For each α,choose a set αA open In X such thatY A A αα='The collection }{A α=A is a covering of Y by sets open in X .By hypothesis,some finitesubcollection },{1n A A αα covers Y .Then {''1nA A αα } is a subcollection of 'A that covers Y .◊Theorem1 Every closed subpace of a compate space is compact.Proof. Let Y be a closed subspace of the compact space X .Given a covering A of Y by sets open in X ,let us form an open covering B of X by adjoining to A the single open set Y X -,that is,Y}-{X A =B .Some finite subcollection of B covers X .If this subcollection contains the set Y X -,discard Y X -;otherwise,leave the subcollection alone.The resulting collection is a finite subcollection of A that covers Y .◊Theorem2 Every compact subspace of a Hausdorff space is closed.Proof Let Y be a compact subspace of the Hausdorff space X .Ww shall prove that Y X - is open,so that Y is closed.Let 0x be a point of Y X -.We show there is a neihborhood of 0x that is disjoint from Y .For each point y of Y ,let us choose disjoint neighborhoods y U and y V of the points 0x and y ,respectively (using the Hausdorff condition).The collection }Y y {V y ∈ is a covering of Y by sets open in X ;therefore,finitely many of them n 1,,ννV V cover Y .Theopen setn y y V V V 1=contains Y ,and it is disjoints from the open setn y y U U U 1=formed by taking the intersection of the corresponding neighborhoods of 0x .For if z is a point of V ,then i y V z ∈ for some i ,hence i y U z ∉ and so U z ∉.Then U is a neighborhood of 0x disjoint from Y ,as desired.◊The statement we proved in the course of the preceding proof will be useful to us later,so we repeat it here for reference purpose:Lemma2 If Y is a compact subspace of the Hausdorff space X and 0x is not in Y ,then there exist disjoint open sets U and V of X containing 0x and Y ,respectively.EXAMPLE5. Once we prove that the interval []b a , in R is compact,it follows from theorem1 that any closed subspace of []b a , is compact .On the other hand,it follows from theorem2 that the intervals (]b a , and ()b a , in R cannot be compact (which knew already) because they are not closed in the Huasdorff space R .EXAMPLE6 One needs the Hausdorff condition in hypothesis of Theorem2. Consider,for eample,the finite complement topology on the real line.The only proper subsets of R that are closed in this topology are the finite sets.But every subset of R compact in this topology,as you can check.T heorem3 The image of a compact space under a continuous map is compact.Proof. Let Y X f →: be continuous:let X be compact. Let A be a covering of the set ()X f by sets open in Y . The collection)}({A ∈-A A fis a collection of sets covering X ; these sets are open in X because f is continuous. Hence finitely many of them ,say()()n A f A f ,,1 -,cover X . Then the sets n A A ,1 cover ()A f .◊One important use of the preceding theorem is as a tool for verify that a map is a homeomorphism:Theorem 4. Let Y X f →: be a bijective continuous function. If X is compact and Y is hausdorff, then f is a homeomorphism.Proof. We shall prove that images of closed sets of X under f are closed in Y ;this will prove continuity of the map -f .If A is closed in X , then A is compact, by theorem1. Therefore, by the theorem3 just proved, ()A f is compact. Since Y is Hausdorff, ()A f is closed in Y , by Theorem 2.◊Theorem5. The product of finitely many compact spaces is compact.Proof. We shall prove that the product of two compact spaces is compact;the theorem follows by induction for any finite product.Step 1. Suppose that we are given spaces X and Y , with Y compact. Suppose that 0xis a point of X , and N is an open set of Y X ⨯ containing the ―slice‖ Y x ⨯0 of Y X ⨯. We prove the following:There is a neighborhood W of 0x in X such that N contains the entire set Y W ⨯ .The set Y W ⨯ is often called a tube about Y x ⨯0.First let us cover Y x ⨯0 by basis elements V U ⨯ (for the topology of Y X ⨯) lying in N . The space Y x ⨯0 is compact, being homeomorphic to Y . Therefor, we can cover Y x ⨯0 by finitely many such basis elementsn n V U V U ⨯⨯,,11 .(We assume that each of the basis elements i i V U ⨯ actually intersects Y x ⨯0, since otherwise that basis element would be superfluous ; we could discard it from the finite collection and still have a covering of Y x ⨯0.) Definen U U W 1=.The set W is open, and it contains 0x because each set i i V U ⨯ intersects Y x ⨯0.We assert that the sets i i V U ⨯, which were chosen to cover the slice Y x ⨯0,actually cover the tube Y W ⨯. Let y x ⨯ be a point of Y W ⨯. Consider the point y x ⨯0 of the slice Y x ⨯0 having the same coordinate y - as this point. Now y x ⨯0 belongs to i i V U ⨯ for some i , so that i V y ∈. But j U x ∈ for every j (because W x ∈). Therefore we have i j V U y x ⨯∈⨯, as desired.Since all the sets i i V U ⨯ lie in N ,and since they cover Y W ⨯, tube Y W ⨯ lies in N also.Step 2. Now we prove the theorem. Let X and Y be compact spaces. Let A be an open covering of Y X ⨯. Given X x ∈0, the slice Y x ⨯0 is compact and may therefore be covered by finitely many elements m A A ,,1 of A . Their union m A A N 1= is an open set containing Y x ⨯0; by step 1, the open set N contains a tube Y W ⨯ about Y x ⨯0,where W is open in X . Then Y W ⨯ is covered by finitely many elements m A A ,,1 of A .Thus, for each x in X ,we can choose a neighborhood x W of x such that the tube Y W x ⨯ can be covered by finitely many elements of A . The collection of all the neighborhoods x W is an open covering of X ; therefore by compactness of X , there exsits a finite subcollection},,{1n W Wcovering X . The union of the tubesY W Y W n ⨯⨯,,1is all of Y X ⨯ ;since each may be covered by finitely many elements of A ,so many Y X ⨯ be covered. ◊The statement proved in Step 1 of the preceding proof will be useful to us later, so we repeat it here as a lemma, for reference purposes:Lemma 3 (The tube lemma). Consider the product space Y X ⨯, where Y is compact. If N is an open set of Y X ⨯ containing the slice Y x ⨯0of Y X ⨯, then N contains some tube Y W ⨯ about Y x ⨯0, where W is a neighborhood of 0x inX .EXAMPLE 7 The tube lemma is certainly not true if Y is not compact. For eample, let Y be the axis y - in 2R , and let ()}x y x {112+<⨯=y NThen N is an open set containing the set R ⨯0, but it contains no tube about R ⨯0.There is an obvious question to ask at this point. Is the product of infinitely many compact spaces spaces compact? One would hope that the answer is ―yes‖, and in fact it is. The result is important(and different) enough to be called by the name of the man who proved it; it is called the Tychonoff theorem.In proving the fact that a cartesian product of connected spaces is connected, one proves it first for finite products and derives the general case from that. In proving that cartesian products of compact spaces are compact, however, there is no way to go directly from finite products to infinite ones. The finite case demands a new approach, and the proof is a difficult one. Because of its its difficulty, and also to avoid losing the main thread of our discussion inthis chapter, we have decided to postpone it until later. However , you can study it now if you wish; the section in which it is proved can be studied immediately after this section without causing any disruption in continuity.There is one final criterion for a space to be compact, a criterion that is formulated in terms of closed sets rather than open sets. It does not look very natural nor very useful at first glance, but it in fact proves to be useful on a number of occasion. First we make a definition.Definition . A collection of subsets of X is said to be have the finite intersection property if for every subcollection},,{1n C Cof ,the intersection n C C 1 is nonempty.Theorem6. Let X be a topological space. Then X is compact if and only if for every collection of closed sets in X having the finite intersection property, the intersection C C ∈ of all the elements of is nonempty.Proof. Given a collection A of subsets of X , let}{A ∈-=A A Xbe the collection of their complements. Then the following statements hold:(1) A is a collection of open sets if and only if is a collection of closed sets.(2) The collection A covers X if and only if the intersectionC C ∈ of all the elementsof is empty.(3) The finite subcollection },{1n A A of A covers X if and only if the intersection of the corresponding element i i A X C -= of is empty.The first statement is trivial, while the second and third follow from DeMorgan’slaw.The proof of the theorem now proceeds in two easy steps: taking the contrapositive(of the theorem), and then the complement (of the sets)!The satement that X is compact is equivalent to saying : ―Given any collection A of open subsets of X , if A covers X , then some finite subcollection of A covers X ‖. Letting be , as earlier, the collection }{A ∈-A A X and applying (1)---(3), we see that this atatement is in turn equivalent to the following : ―Given any collection of closed sets , if every finite intersection of elements of is nonempty , then the intersection of all the element of is nonempty.‖ This is just the condition of our theorem.A special case of this theorem occurs when we have a nested sequence n C C C 21⊃ of closed sets in a compact space X . If each of the sets n C is nonempty, then the collection+∈=Z n n C }{ automatically has the finite intersection property. Then the intersection+∈Z n n Cis nonempty.Local ConnectednessConnectedness is a useful property for a space to possess .But for some purproses,it is more important that the space satify a connectedness condition locally .Roughly speaking ,local connectedness means that each point has ―arbitrarily small‖neighborhoods that are connected.More precisely,one the following definition:Definition: A space X is said to be locally connected at x if for every neighborhood U of x ,there is a connected neighborhood V of x contained in UIf X is locally connected at each of its ponts ,it is said simply to be locally connected .Similarly,a space X is said to be locally path connected at x if for every neghborhood U of x ,there is a path-conneted neighborhood V of x contained in U .If X is locally path connected at each of its points,then it is said to be locally path connected. EXAMPLE 1 Each interval and each ray in the real line is both connected and locally connected.The subspace [)(]1,00,1⋃- of R is not connected.But it is locally connected.The rationals Q are neither connected nor locally connected.Theorem 1 A space X is locally connected if and only if for every open set U of X ,each component of U is open in X .Proof . Suppose that X is locally connected ;let U be an open set in X ;let C be a component of U .If x is a point of C ,we can choose a connected neighborhood V of x such that U V ⊂.Since V is connected ,it must lie entirely in the component C of U .Therefor ,C is open in X .Conversely,suppose that componnents of open sets in X are open .Given a piont x of X and a neighborhood U of x ,let C be the coponent of U containing x .Now C is connected;since it is open in X by hypothesis,X is locally connected at x . ◊A similar proof holds for the following theorem:Theorem 2 A space X is locally path connected if and only if for every open set U of X ,each path component of U is open in X .The relation between path components and components is given in the following theorenm:Theorem 3 If X is a topological space ,each path component of X lies in a component of X .If X is locally path connected ,then the components and the path components of X are the same.Proof Let C be a component of X;let x be a point of C;let P be the path component of X containing x.Since P is connected, CP⊆.We wish to show that if X is locally path connected, CP=.Suppose that CP⊂.Let Q denote the union of all the components of X that are different from P and intersect C;each of them necessarily lies in C,so that=.C⋃QPBcause X is locally path connected,each path component of X is open in X.therefore, P(which is a path component) and Q(which is a union of path components ) are open in X,so they constitute a separation of C.This contradicts the that C is connected.◊Compact Subspaces of the Real LineThe theorem of the preceding section enable us to constuct new compact spaces from existing ones, but in order to get very far we have to find some compact spaces to start with. The natural place to beigin is the real line; we shall prove that every closed interval in R is compact. Applications include the extreme value theorem and the uniform continuity theorem of calculus, suitably generalized. We aslo give a characterization of all compact subspaces of nR, and a proof of the uncountability of the set of real number.It turns out that in order to prove every closed interval in R is compact, we need only one of the order properties of the real line –the least upper bound property. We shall prove the theorem using only this hypothesis; then it will apply not only to the real line, but to well-ordered sets and other ordered sets as well.Theorem1. Let X be a simply order set having the least upper bound property. In the order topology, each closed interval in X is compact.Proof. Step 1. Given ba<, let A a covering of []b a,by sets open in []b a,in the subspace topology (which is the same as the order topology). We wish to prove the existence of a finite subcollection of A covering []b a,. First we prove the following : If x is a point of []b a,different from b, then there is a point xy>of []b a,such that the interval []y x, can be covered by at most two elements of A.If x has an immediate successor in X, let y be this immediate successor. Then []y x, consists of the two points x and y, so that it can be covered by at most two elements of A. If x has no immediate successor in X, choose an element A of A containing x. Because bx≠and A is open , A contains an interval of the form [)c x,, for some c in []b a,. Choose a point y in ()c x,; then the interal []y x,is covered by the single elementA of A .Step 2. Let C be the set of all points a y > of []b a , such that the interval []y a , can be covered by finitely many element of A . Applying Step1 to the case a x =, we see that there exists at least one such y , so C is not empty. Let c be the least upper bound of the set C : then b c a ≤<.Step 3. We show that c belongs to C ; that is, we show that the interval []c a , can be covered by finitely many elements of A . Choose an elements A of A containing c; since A is open, it contains an interval of the form [)c d , for some d in []b a ,. If c is not in C , there must be a point z of C lying in the interval ()c d ,, because otherwise d would be a smaller upper bound on C than c . Since z is in C , the interval []z a , can be covered by finitely many, say n , element of A . Now []c z , lies in the single element A of A , hence [][][]c z z a c a ,,, = can be covered 1+n elements of A . Thus c is in C , contray to assumption.Step 4. Finally, we show that b c =, and our theorem is proved. Suppose that b c <. Applying Step 1 to the case c x =, we conclude that there exists a point c y > of []b a , such that the interval []y c , can be covered by finitely many elements of A . We proved in Step 3 that c is in C , so []c a , can be covered by finitely many elements of A . Therefore ,the interval[][][]y c c a y a ,,, =can also covered by finitely many elements of A . This means that y is in C , contradicting the fact that c is an upper bound on C .Corollary1 Every closed interval in R is compact.Now we characterize the compact subspaces of n R :Theorem2. A subspace A of n R is compact if and only if it is closed and is bounded in the euclidean metric d or the square metric ρ.Proof. It will suffice to consider only the metric ρ; the inequalities()()()y x n y x d y x ,,,ρρ≤≤impply that A is bound under d if and only if it is bounded under ρ.Supose that A is compact. Then , by theorem2 (in Compact Spaces) it is closed. Consider the collection of open sets()}0{+∈Z m m B P ，whose union is all of n R . Some finite subcollection covers A . It follows that ()M B A p ,0∈ for some M . Therefore , for any two points x and y of A , we have ()M y x 2,≤ρ. Thus A is bounded under ρ.Conversely ,supposed that A is closed and bounded under ρ; suppose that ()N y x ≤,ρ for every pair y x , of points of A . Choose a point 0x of A , and let ()b x =0,0ρ. The triangle inequality implies that ()b N x +≤0,0ρ for every x in A . If b N P +=,then A is subset of the cube []n P P ,-, which is compact. Being closed, A is also compact.◊Students often remember this theorem as stating that the collection of compact sets in a metric space equals the collection of closed and bounded sets. This statement is clearly ridiculous as it stands, because the question as to which sets are bounded depends for its answer on the metric , whereas which sets are copact depedends only on the topology of the space.EXAMPLE1 . The unit sphere 1-n S and the closed unit ball n B in n R are compact because they are closed and bounded. The set()}10{1≤<⨯=x x A xis closed in 2R , but it is not compact because it is not bounded. The set()}10sin {1≤<⨯=x x S xis bound in 2R , but it is not compact because it is not closed.Now we prove the extreme value theorem of calculus, in suitably generalized form. Theorem3 (Extreme value theorem) Let Y X f →: be continuous, where Y is an ordered set in the order topology. If X is compact, then there exist points c and d in X such that ()()()d f x f c f ≤≤ for every X x ∈.The extreme value theorem of calculus is the special case of this theorem that occurs whenwe take X to be a closed interval in A and Y to be R .Proof. Since f is continuous and X is compact, the set ()X f A = is compact. We show that A has a largest element M and a smallest element m . Then since m and M belong to A , we must have ()c f m = and ()d f M = for some points c and d of X .If A has no largest element, then the collection()},{A a a ∈∞-forms an open covering of A . Since A is compact, some finite subcollection()()},,,,{1n a a ∞-∞-covers A . If i a is the largest of the element n a a ,,1 , then i a belongs to none of these sets, contrary to the fact that they cover A .A similar argument shows that A has a smallest element.◊Finally, we prove that the real numbers are uncountable. The interesting thing about this proof is that it involves no algebra at all---no decimal or binary expansions of real numbers or the like —just the order properties of R .In fact, we prove more general result:Theorem4 Let X be a nonempty compact Hausdorff space. If X has no isolated points, then X is uncountable.Proof. Step 1. We show first that given any nonempty open set U of X and any points x of X , there exists a nonempty open set V contained in U such that V . Choose a point of y of U different from x ; this is possible if x is in U because x is not an isolated point of X and it is possible if x is not in U simply because U is nonempty. Now choose disjoint open sets 1W and 2W about x and y , respectively. Then the set 2W U V = is the desired open set; it is contained in U , it is nonempty because it contains y , and its closure does not contain x .Step 2. We show that given X Z f →+:, the function f is not surjective. It follows that X is uncountable.Let ()n f x n =. Apply Step 1 to the nonempty open set X U = to choose a nonempty open set X V ⊂1 such that 1V does not contain 1x . In general, given 1-n V open and nonempty, choose n V to be a nonempty open set such that 1-⊂n n V V and n V does notcontain n x . Consider the nested sequence⊃⊃21V Vof nonempty closed sets of X . Because X is compact, there is a point n V x ∈,by theorem6(in Compact Spaces ). Now x cannot equal n x for any n , since x belongs to n V and n x does not.Corollary2. Every closed interval in R is uncountale.Limit Point CompactnessAs indicated when we first mentioned copact sets, there are other formulations of the notion of compactness that are frequently useful. In this section we introduce one of them. Weaker in general than compactness, it coincides with compactness for metrizable spaces.Definition A space X is said to be limit point compact if every infinite subset of X has a limit point.In some ways this property is more natural and intuitive than that of compactness. In the early days of topology, it was given the name ―compactness‖ , while the open covering formulation was called ―bicompactness‖. Later, the word ―compact‖ was shifted to apply to the open covering definition, leaving this one to search for a new name. It still has not found a name on which everyone agrees. On historical grounds, some call it ―chet e Fr ' compactnes s‖;others call it the ―Bolzano -Weierstrass property‖. We have invented the term ―limit point compactness‖. It seems as good a term as any; at least it describes what the property is about.Theorem1. Compactness implies limit point compactness, but not conversely.Proof. Let X be a conpact space. Given a subset A of X , we wish to prove that if A is infinite, then A has a limit point. We prove the contrapositive-if A has no limit point, then A must be finite.So suppose A has no limit point. Then A contains all its limit points, so that A is closed. Futhermore, for each A a ∈ we can choose a neighborhood a U of a such that a U intersects A in the point a alone. The space X is covered by the open set A X - and the open sets a U ;being compact, it can be covered by finnitely many of these sets. Since A X - does not intersect A ,and each set a U contains only one points of A ,the set A must be finite.◊EXAPLE1. here is a less trivial example. Consider the minimal uncountable well-ordered set ΩS , in the order topology. The space ΩS is not compact, since it has no largest element.However, it is limit point point compact. Let A be an infinite subset of ΩS . Choose a subset B of A that is countably infinite. Being countable, the set B has an upper bound b in ΩS ; then B is a subset of the interval []b a ,0 of ΩS , where 0a is the smallest element of ΩS . Since ΩS has the least upper bound property, the interval []b a ,0 is compact. By the preceding theorem,B has a limit point x in []b a ,0. The point x is also a limit point of A . Thus ΩS is limit point compact.Theorem2. Let X be a metrizable space. Then the following are equivalent:(1) X is compact.(2) X is a limit point compact.(3) X is sequentially compact.Proof. We have proof that (1)⇒(2). To show that (2)⇒(3),assume that X is limit point compact. Given a sequence ()n x of X ,consider the set }{+∈=Z n x A n . If the set A is finite, then there is a point x such that n x x = for infinitely many values of n . In the case ,the sequence ()n x has a subsequence that is constant, and therefore converges trivially. On the other hand, if A is infinite, then A has a limit point x . We difine a subsequence of ()n x converging to x as follow:First choose 1n so that()1,1x B x n ∈.Then suppose that the positive integer 1-i n is given. Because the ball ()i x B 1, intersects A in finitely many points, we can choose an index 1->i i n n such that()i ni x B x 1,∈.Then the subsequence ,,21n n x x converges to x .Finally, we show that (3)⇒(1).First, we show that if X is sequentially compact, then the Lebesgue number lemma holds for X . Let A be an open coveringof X . We assume that there is no 0>δ such that each set of diameter less than δ has an element of A containing it, and derive a contradiction.Our assumption implies in particular that for each positive integer n ,there exists a set of diameter less than n 1 that is not contained in any element of A ; let n C be such a set. Choose a point n n C x ∈, for each n . By hypothesis., some subsequence ()i n x of the。

积分定理
integral theory
莱维单调收敛定理
Levi monotony convergence theorem
法图引理
fatou lemma
富比尼定理
Fubini theorem
有界变差函数
bounded variation function
绝对连续函数
absolutely continuous function
覆盖
cover
有限覆盖
finite cover
可数覆盖
countable cover
等价
equivalence
第三章
Chapter 3 Measure Theory
勒贝格测度Байду номын сангаас
lebesgue measure
形集合
set
形集合
set
波雷尔集合
Borel set
外侧度
exterior measure
可数可加
凸泛函
convex functional
阵列
array
弱紧性
weak compactness
弱连续性
weak continuous
弱收敛
weak convergence
弱星收敛
weak * convergence
内积
inner product
内积空间
inner product space
内点
inner point
C-空间
continuous space
紧集
compact set
完备集合
complete set
不动点
fixed point