On the approximation of the global extremum of a semi-Lipschitz function

Costica Mustata
(original), Approximation Theory, asymmetric norm, ISI/JCR, paper

Abstract

In this paper one obtains a sequential procedure for determining the global extremum of a semi-Lipschitz real-valued function defined on a quasi-metric (asymmetric metric) space.

Authors

Costica Mustata
“Tiberiu Popoviciu” Institute of Numerical Analysis  Cluj-Napoca, Romanian Academy

Keywords

Spaces with asymmetric metric; semi-Lipschitz functions; extension and approximation

Paper coordinates

C. Mustăța, On the approximation of the global extremum of a semi-Lipschitz function, Mediterr. J. Math. 6 (2009), 169–180,
doi: 10.1007/s00009-009-0003-x

PDF

https://ictp.acad.ro/wp-content/uploads/2025/07/2009-Mustata-Mediterr.-J.-Math-On-the-approximation-of-the-global-extremum.pdf

About this paper

Journal

Mediterranean Journal of Mathematics

Publisher Name

Springer

DOI

10.1007/s00009-009-0003-x

Print ISSN

1660-5446

 

 

Online ISSN

1660-5454

Google Scholar Profile

?

[1] P. Basso, Optimal search for the global maximum of functions with bounded seminorm, SIAM J. Numer. Anal. 22 (no. 5) (1985), 888–905.
[2] P. A. Borodin, The Banach-Mazur theorem for spaces with asymetric norm and its applications in convex analysis, Mat. Zametki 69 (no. 3) (2001), 329–337.
[3] S. Cobzas, Separation of convex sets and best approximation in spaces with asymmetric norm, Quaest. Math. 27 (no. 3) (2004), 275–296.
[4] S. Cobzas, Asymmetric locally convex spaces, Int. J. Math. Math. Sci. 16 (2005), 2585–2608.
[5] S. Cobzas and C. Mustata, Norm-preserving extyension of convex Lipschitz functions, J. Approx. Theory 24 (no. 3) (1978), 236–244.
[6] S. Cobzas and C. Mustata, Extension of bounded linear functionals and best approximation in spaces with asymmetric norm, Rev. Anal. Num´er. Th´eor. Approx. 32 (no.1) (2004), 39–50.
[7] J. Collins, and J. Zimmer, An asymmetric Arzela-Ascoli theorem, Topology Appl. 154 (no. 11) (2007), 2312–2322.
[8] P. Fletcher and W. F. Lindgren, Quasi-uniform Spaces, Marcel Dekker, New-York, 1982.
[9] S. Garcia-Ferreira, S. Romaguera and M. Sanchis, Bounded subsets and Grothendieck’s theorem for bispaces, Houston. J. Math. 25 (no. 2) (1999), 267–283.
[10] L. M. Garcia-Raffi, S. Romaguera and E. A. S´anchez-P´erez, The dual space of an asymmetric normed linear space, Quaest. Math. 26 (no. 1) (2003), 83–96.
[11] L. M. Garcia-Raffi, S. Romaguera and E. A. S´anchez-P´erez, On Hausdorff asymmetric normed linear spaces, Houston J. Math. 29 (no. 3) (2003), 717–728.
[12] M. G. Krein and A. A. Nudelman, The Markov Moment Problem and Extremum Problems, Nauka, Moscov, 1973 (in Russian), English translation: AMS, Providence, R.I., 1977.
[13] H. P. A. K¨unzi, Nonsymmetric distances and their associated topologies: about the origin of basic ideas in the area of asymmetric topology, Handbook of the History of General Topology, ed. by C.E. Aull and R. Lower, vol. 3, Hist. Topol. 3, Kluwer Acad. Publ. (Dordrecht, 2001), 853–968.
[14] E. J. McShane, Extension of range of functions, Bull. Amer. Math. Soc. 40 (1934), 837–842.
[15] A. Mennucci, On asymmetric distances, Technical report, Scuola Normale Superiore, Pisa, 2004.
[16] C. Mustata, Best approximation and unique extension of Lipschitz functions, J. Approx. Theory 19 (no. 3) (1977), 222–230.
[17] C. Mustata, Extension of H¨older Functions and some related problems of best approximation, ”Babes-Bolyai” University, Faculty of Mathematics, Research Seminars, Seminar onf Mathematical Analysis (1991) 71–86.
[18] C. Mustata, Extension of semi-Lipschitz functions on quasi-metric spaces, Rev. Anal. Numer. Theor. Approx. 30 (no. 1) (2001), 61–67.
[19] C. Mustata, On the extremal semi-Lipschitz functions, Rev. Anal. Numer. Theor. Approx. 31 (no. 1) (2002), 61–67.
[20] V. Pestov and A. Stojmirovic, Indexing schemes for similarity search: an illustrated paradigm, Fund. Inf. 70 (no. 4) (2006), 367–385.
[21] S. Romaguera and M. Sanchis, Semi-Lipschitz functions and best approximation in quasi-metric spaces, J. Approx. Theory 103 (2000), 292–301.
[22] S. Romaguera and M. Sanchis, Properties of the normed cone of semi-Lipschitz functions, Acta Math. Hungar 108 (nos. 1-2) (2005), 55–70.
[23] S. Romaguera, J. M. Sanchez-Alvarez and M. Sanchis, ´ El espacio de funciones semiLipschitz, VI Jornadas de Matem´atica Aplicada, Departamento de Matem´atica Aplicada, Universidad Polit´ecnica de Valencia, 1-3 septiembrie, 2005.
[24] J. M. Sanchez-Alvarez, On semi-Lipschitz functions with values in a quasi-normed linear space, Appl. Gen. Top. 6 (no. 2) (2005), 217–228.
[25] B. Shubert, A sequential method seeking the global maximum of a function, SIAM J. Num. Anal. 9 (1972), 379–388.
[26] A. Stojmirovic, Quasi-metric spaces with measures, Proc. 18th Summer Conference on Topology and its Applications, Topology Proc. 28 (no. 2) (2004), 655–671.
[27] W. A. Wilson, On quasi-metric spaces, Amer. J. Math. 53 (no. 3) (1931), 75–684.

Paper (preprint) in HTML form

On the Approximation of the Global Extremum of a Semi-Lipschitz Function Costic˘a Must˘ at ¸a Abstract. In this paper one obtains a sequential procedure for determining the global extremum of a semi-Lipschitz real-valued function defined on a quasi-metric (asymmetric metric) space. Mathematics Subject Classification (2000). Primary 68W25; Secondary 46A22. Keywords. Spaces with asymmetric metric, semi-Lipschitz functions, exten- sion and approximation. 1. Introduction For a function from a specified class, a method for seeking its extremum deals with the problem of estimating the global maximum or/and minimum values of the function and locating the points where the extremum is attained. An important class of such methods is the class of sequential methods i.e. in which the choice of each evaluation point, except for the first one, depends on the location and the values of the function at the previous points and, possibly, on the number n of the evaluations to be performed. In the latter case the method is called an n-step method. In the following, a sequential method is obtained for evaluating the global maximum and the global minimum of a semi-Lipschitz real-valued function defined on a subset of a quasi-metric space, sometimes called asymmetric metric space (see [7], [27]). In order to determine the absolute maximum M f of a real semi-Lipschitz function f, the algorithm we propose determines a decreasing sequence of numbers (M n ) n≥1 , having the limit M f . Each number M n (n =1, 2, ...) is the absolute maximum of a special semi-Lipschitz function U n (f ). This function has a very simple analytical expression compared to the given function f (which is assumed only to be semi-Lipschitz). For determining U n (f )(x) one requires on one hand
the computation of the value of f at a certain point, and the values of f at the n point from the previous step, and on the other hand the quasi-distances from the current point x to the n + 1 points. One can see therefore that the determining of the maximum M n+1 of U n+1 (f ) requires a small amount of computation.The absolute minimum of f is given by the absolute maximum of −f. We present in the following the framework of the described method. Let X be a non-empty set. A function d : X × X → [0, ∞) is called a quasi- metric on X [21] (see also [7], [27]) if the following conditions hold AM 1) d(x, y)= d(y,x) = 0 iff x = y, AM 2) d(x, z) ≤ d(x, y)+ d(y,z), for all x, y, z ∈ X. The function d : X × X → [0, ∞) defined by d(x, y)= d(y,x) for all x, y ∈ X is also a quasi-metric on X, called the conjugate quasi-metric of d. A pair (X, d), where X is a non-empty set and d a quasi-metric on X, is called a quasi-metric space. Obviously, the function d s (x, y) = max{d(x, y), d(x, y)} is a metric on X. Each quasi-metric d on X induces a topology τ (d) on X which has as a base the family of balls (forward open balls [7]). B + (x, ε) := {y ∈ X : d(x, y) <ε},x ∈ X, ε > 0. This topology is called the forward topology of X ([7], [15]) and is denoted by τ + . Analogously, the quasi-metric d induces the topology τ ( d) on X which has as a base the family of backward open balls ([7]) B − (x, ε) := {y ∈ X : d(y,x) <ε},x ∈ X, ε > 0. This topology is called the backward topology of X ([7], [15]) and is denoted by τ − . Note that the topology τ + is a T 0 -topology. If the condition AM1) is replaced by the condition: AM0) d(x, y) = 0 iff x = y, then τ + is a T 1 -topology. The pair (X, d) is called a T 0 quasi-metric space, respectively a T 1 quasi-metric space (see [21] and [22]). Let (X, d) be a quasi-metric space. A sequence (x k ) k≥1 d-converges to x 0 ∈ X (respectively d-converges to x 0 ∈ X) iff lim k→∞ d(x 0 ,x k )=0, respectively lim k→∞ d(x k ,x 0 ) = lim k→∞ d(x 0 ,x k )=0. A set K ⊂ X is called d-compact if every open cover of K with respect to the forward topology has a finite subcover. We say that K is d-sequentially compact if every sequence in K has a d-convergent subsequence with limit in K (Definition 4.1 in [7]). Finally, the set Y in (X, d) is called (d, d)-sequentially compact if every sequence (y n ) n≥1 in Y has a subsequence (y n k ) d-convergent to u ∈ Y and d- convergent to v ∈ Y. Observe that, if (X, d) is a quasi-metric space (d, d)-sequentially compact and T 0 -separated, then it is possible to find sequences with all subsequences both d-convergent and d-convergent, but to different limits. For example, let X = [0, 1]
and d(x, y)=(y − x) ∨ 0, x, y ∈ [0, 1]. Then d(x, y)=(x − y) ∨ 0 and the sequence ( 1 n ) n≥1 satisfies the property that every subsequences d-converges to 0 and d- converges to 1. But if (X, d) is (d, d)-sequentially compact and T 1 -separated, then by Lemma 3.1 of [7] it follows that if (x n ) n≥1 ⊂ X is d-convergent to x 0 ∈ X and d-convergent to y 0 ∈ X, then x 0 = y 0 . This fact is essential in the proof of Theorem 3.1 from bellow. Definition 1.1 ([21]). Let Y be a non-empty subset of a quasi-metric space (X, d). A function f : Y → R is called d-semi-Lipschitz if there exists L ≥ 0 (named a d-semi-Lipschitz constant for f ) such that f (x) − f (y) ≤ Ld(x, y), for all x, y ∈ Y. (1.1) A function f : Y → R is called ≤ d -increasing if f (x) ≤ f (y) whenever d(x, y)=0. Denote by R Y ≤ d the set of all ≤ d -increasing functions on Y. This set is a cone in the linear space R Y of all real-valued functions defined on Y, i.e., for each f,g ∈ R Y ≤ d and λ ≥ 0 it follows that f + g ∈ R Y ≤ d and λf ∈ R Y ≤ d . For a d-semi-Lipschitz function f on Y , put [21] f | d = sup d(x,y)>0 x,y∈Y (f (x) − f (y))) ∨ 0 d(x, y) . (1.2) Then f | d is the smallest d-semi-Lipschitz constant for f ([18]). For a fixed element θ ∈ Y denote d-SLip 0 Y := {f ∈ R Y ≤ d : f | d < ∞ and f (θ)=0}. (1.3) If (X, d) is a T 1 quasi-metric space, then every f ∈ R X is ≤ d -increasing ([21]). The set defined by (1.3) is a subcone of the cone R Y ≤ d , and the functional | d : d-SLip 0 Y → [0, ∞) defined by (1.2) is an asymmetric norm, i.e., it is sub- additive, positive homogeneous and f | d = 0 iff f ≡ 0. The pair (d-SLip 0 Y, | d ) is called the normed cone of real semi-Lipschitz functions on Y, vanishing at the fixed point θ ∈ Y ([22]). In [22] some properties of the normed cone (d-SLip 0 Y, | d ) are presented. Similar properties in the case of semi-Lipschitz functions on a quasi-metric space with values in a quasi-normed linear space (space with asymmetric norm) are discussed in [24]. For more information concerning other properties of quasi-metric spaces and their applications, see [7], [8], [13], [20], [26]. 2. Results Let f ∈ d-SLip 0 Y. A function F in d-SLip 0 X satisfying the inequality F (u) − F (v) ≤f | d d(u, v), for all u, v ∈ X and such that F (y)= f (y) for all y ∈ Y is called an extension of f (preserving the asymmetric norm f | d ).
It follows that each extension F ∈ d-SLip 0 X of f ∈ d-SLip 0 Y satisfies F | Y = f and F | d =f | d . (2.1) The existence of such an extension for each f ∈ d-SLip 0 Y follows from the following theorem proved in [18]. For the sake of completeness we include the proof. Theorem 2.1. Let (X, d) be a quasi-metric space, θ ∈ X a fixed element, and Y a subset of X with θ ∈ Y. Then for every f ∈ d-SLip 0 Y there exists at least a function F ∈ d-SLip 0 X such that F | Y = f and F | d = f | d . Proof. For f ∈ d-SLip 0 Y let F d (f )(x) = inf y∈Y [f (y)+ f | d d(x, y)},x ∈ X. (2.2) First we show that F d (f ) is well defined. Let x ∈ X. For any y ∈ Y we have f (y)+ f | d d(x, y)= f | d d(x, y) − (f (θ) − f (y)) ≥f | d d(x, y) −f | d d(θ, y) = f | d (d(x, y) − d(θ, y)) ≥−f | d d(θ, x), showing that for every x ∈ X the set {f (y)+ f | d d(x, y): y ∈ Y } is bounded from below and, consequently, the infimum in (2.2) is finite. Now we show that F d (f )| Y = f, F d (f ) ∈ d-SLip 0 X and F d (f ) | d =f | d . For every y ∈ Y we have F d (f )(x) ≤ f (y)+ f | d d(x, y),x ∈ X, which for x = y yields F d (f )(y) ≤ f (y). On the other hand, for y ∈ Y and all y ∈ Y, f (y) − f (y ) ≤f | d d(y,y ) implies f (y) ≤ f (y )+ f | d d(y,y ). Taking the infimum with respect to y ∈ Y one obtains f (y) ≤ F d (f )(y), so that F d (f )(y)= f (y),y ∈ Y. Let x 1 ,x 2 ∈ X and ε> 0. Choosing y ∈ Y such that F d (f )(x 1 ) ≥ f (y)+ f | d d(x 1 ,y) − ε we get F d (f )(x 2 ) − F d (f )(x 1 ) ≤ f (y)+ f | d · d(x 2 ,y) − (f (y)+ f | d d(x 1 ,y) − ε) = f | d (d(x 2 ,y) − d(x 1 ,y)) + ε.
Because d(x 2 ,y) − d(x 1 ,y) ≤ d(x 2 ,x 1 ) it follows that F d (f )(x 2 ) − F d (f )(x 1 ) ≤f | d d(x 2 ,x 1 ). This means that F d (f ) ∈ d-SLip 0 X, and by the last inequality F d (f )| d ≤f | d . By the definitions of an asymmetric norm F d (f )| d ≥F d (f )| Y | d = f | d , so that the equality F d (f )| d = f | d holds. The following Remarks 2.2 and 2.3 are taken from [18] and [19]. Remark 2.2. By Theorem 2.1 it follows that for every f ∈ d-SLip 0 Y , the set of all extensions preserving the asymmetric norm f | d , i.e. E d (f )= {H ∈ d-SLip 0 X : H| Y = f and H| d = f | d } (2.3) is nonempty, because F d (f ) ∈E d (f ) where F d (f ) is given by (2.2). Analogously, one proves that the function G d (f ) = sup y∈Y {f (y) −f | d d(x, y)},x ∈ X, (2.4) is in E d (f ). Remark 2.3. Obviously, the set E d (f ) is convex, i.e. for every H 1 ,H 2 ∈E d (f ) and λ ∈ [0, 1] it follows λH 1 + (1 − λ)H 2 ∈E d (f ). Moreover for every H ∈E d (f ) we have: G d (f )(x) ≤ H(x) ≤ F d (f )(x),x ∈ X. (2.5) The function F d (f ) defined by (2.2) is called the maximal extension of f , and G d (f ) defined by (2.4) is called the minimal extension of f . Remark 2.4. If θ ∈ Y 1 ⊂ Y 2 ⊂ Y and f ∈ d-SLip 0 Y, then for each u ∈ Y we can easily obtain: inf y∈Y1 {f (y)+ f | d d(u, y)}≥ inf y∈Y2 {f (y)+ f | d d(u, y)} and sup y∈Y1 {f (y) −f | d d(u, y)}≤ sup y∈Y2 {f (y) −f | d d(u, y)}. Remark 2.5. Observe that Theorem 2.1 is the “nonsymmetric” analog of Mc- Shane’s theorem [14] for metric spaces. Theorem 2.6. Let (X, d) be a quasi-metric space and Y ⊆ X. Then (a) Every f ∈ d-SLipY is upper semicontinuous on (Y, d); (b) If Y is d-sequentially compact, then every f ∈ d-SLipY attains its maximum value on Y.
Proof. Let f ∈ d-SLipY. If f | d = 0 then f (y)= constant for all y ∈ Y and this function is upper semicontinuous. Let y 0 ∈ Y and f | d > 0. Then the inequality f (y) − f (y 0 ) ≤f | d d(y,y 0 ) implies f (y) ≤ f (y 0 )+ f | d d(y,y 0 ). For ε> 0 and y ∈ Y such that d(y,y 0 ) < ε f | d it follows f (y) ≤ f (y 0 )+ ε, showing that f is upper semicontinuous on (Y, d). Let Y be d-sequentially compact in (X, d) and M = sup f (Y ), where M ∈ R ∪{+∞}. Then there exists a sequence (y n ) n≥1 in Y such that lim n→∞ f (y n )= M. Because Y is d-sequentially compact there exists y 0 ∈ Y and a subsequence (y n k ) k≥1 of (y n ) n≥1 such that lim k→∞ d(y n k ,y 0 )=0. By the upper semicontinuity of f in y 0 it follows: M = lim k→∞ f (y n k ) = lim sup f (y n k ) ≤ f (y 0 ) ≤ M implying M< ∞ and f (y 0 )= M. By Theorem 2.6 it follows that for Y d-sequentially compact, the functional | ∞ : d-SLip 0 Y → [0, ∞) defined by f | ∞ = max{f (y): y ∈ Y } is an asymmetric norm on d-SLip 0 Y. Indeed, for every f in d-SLip 0 Y we have f | ∞ ≥ f (θ)=0. If f | ∞ > 0 then there exists y 0 ∈ Y such that f (y 0 ) > 0= f (θ). Consequently, because f ∈ R Y ≤ d it follows d(y 0 ,θ) > 0, and f | d ≥ f (y 0 ) − f (θ) d(y 0 ,θ) > 0. It follows f =0, because | d is asymmetric norm on d-SLip 0 Y. Obviously, f + g| ∞ ≤f | ∞ + g| ∞ and λf | ∞ = λ f | ∞ for all f,g ∈ d-SLip 0 Y and λ ≥ 0. 3. The sequential method Let (X, d) be a quasi-metric space, θ ∈ X a fixed element, and Y ⊂ X with θ ∈ Y. Suppose that Y is d-sequentially compact, and f ∈ d-SLip 0 Y. Let M f = sup{f (y): y ∈ Y } and E f = {y ∈ Y : f (y)= M f }. We want to find the maximum value M f of f and a point y 0 ∈ E f . For this goal we consider the following sequential method, supposing that q> 0 is an upper bound for f | d on Y, i.e. f | d ≤ q.
Firstly, let Z be a nonempty subset of Y with θ ∈ Z. From the proof of Theorem 2.1, the functions U (f )(y) = inf {f (z)+ qd(y,z): z ∈ Z },y ∈ Y and u(f )(y) = sup{f (z) − qd(z,y): z ∈ Z },y ∈ Y satisfy the conditions: U(f )| Z = u(f )| Z = f | Z and U (f )| d = u(f )| d = q ≥f | d on Y. Moreover u(f )(y) ≤ f (y) ≤ U (f )(y),y ∈ Y. Indeed, for y ∈ Y and each z ∈ Z ⊂ Y we have f (y) − f (z) ≤f | d d(y,z) ≤ qd(y,z) and f (y) ≤ f (z)+ qd(y,z). Taking the infimum with respect to z ∈ Z it follows f (y) ≤ U (f )(y),y ∈ Y. Analogously, f (z) − f (y) ≤ qd(z,y), implies f (y) ≥ f (z) − qd(z,y). Taking the supremum with respect to z ∈ Z one obtains u(f )(y) ≤ f (y),y ∈ Y. If M U := max{U (f )(y): y ∈ Y }, then M f ≤ M U . We define now two sequences (y n ) n≥0 in Y and (M n ) n≥0 in R in the following way. Let U 0 (f )(y)= f (θ)+ qd(y,θ)= qd(y,θ),y ∈ Y, i.e. U 0 (f ) is an extension (the maximal extension) of f | {θ} with the semi-Lipschitz constant q. Then, by the above considerations, it follows f (y) ≤ U 0 (f )(y),y ∈ Y, U 0 (f ) ∈ d-SLip 0 Y. If y 0 ∈ Y is such that U 0 (f )(y 0 )= M 0 := sup U 0 (f )(Y ),
then M f ≤ M 0 . Let Z 1 = {θ, y 0 } and let U 1 (f )(y) = inf z∈Z1 {f (z)+ qd(y,z)},y ∈ Y, be the maximal extension of f | Z1 with semi-Lipschitz constant q. Then U 1 ∈ d- SLip 0 Y and by Remark 2.3, it follows: f (y) ≤ U 1 (f )(y) ≤ U 0 (f )(y),y ∈ Y, f | Z1 = U 1 (f )| Z1 = U 0 (f )| Z1 . If y 1 ∈ Y is such that U 1 (f )(y 1 )= M 1 := sup U 1 (f )(Y ), then M f ≤ M 1 ≤ M 0 . Let now Z 2 = {θ, y 0, y 1 }. Supposing that, following the described procedure, we have constructed the sets Z n = {θ, y 0 ,y 1 ,...,y n−1 } and {M 0 ,M 1 ,M 2 ,...,M n−1 }. Put U n (f )(y)= inf z∈Zn {f (z)+ qd(y,z)},y ∈ Y. It follows f (y) ≤ U n (f )(y) ≤ ... ≤ U 1 (f )(y) ≤ U 0 (f )(y) for all y ∈ Y. Choose y n ∈ Y such that U n (f )(y n )= M n := sup U n (Y ). Continuing in this manner we obtain the sequences {θ, y 0 ,y 1 ,...,y n ,...}⊂ Y, and (3.1) {M 0 ,M 1 ,...,M n ,...}⊂ R. The following theorem contains the properties of these two sequences, if Y is (d, d)-sequentially compact. Theorem 3.1. Let (X, d) be a T 1 quasi-metric space, θ ∈ X fixed, and Y a (d, d)- sequentially compact subset of X with θ ∈ Y. Let f ∈ d − SLip 0 Y, q ≥f | d and let (y n ) and (M n ) be the sequences in (3.1). Then (a) (M n ) converges to M f ; (b) lim n→∞ inf {d(y n ,y): y ∈ E f } =0.
Proof. (a). Since for every n ≥ 1 U n (f )(y) ≤ U n−1 (f )(y),y ∈ Y, it follows M n = sup U n (f )(Y ) ≤ sup U n−1 (f )(Y )= M n−1 . Therefore, the sequence (M n ) is decreasing. Since U n (f )(θ) = 0 we have M n ≥ 0 for all n ≥ 0. It follows that there exists M ≥ 0 such that M = lim n→∞ M n . Since Y is (d, d) -sequentially compact, the sequence (y n ) contains a subsequence (y n k ) k≥1 which is d- and d-convergent to an element y ∈ Y, i.e., lim k→∞ d(y n k , y) = 0 and lim k→∞ d( y,y n k )=0. Furthermore lim k→∞ U n k (f )(y n k ) = lim k→∞ M n k = M. On the other hand, by the upper semicontinuity of the function f, it follows lim sup k→∞ f (y n k ) ≤ f ( y) ≤ M f . By the definitions of the extensions U n (f )(n ≥ 1) we have U n k (f )(y n k ) − U n k (f )(y n k −1 ) ≤ qd(y n k ,y n k −1 ) ≤ q(d(y n k , y)+ d( y,y n k −1 )) → 0, as k →∞. It follows that for every ε> 0 there exists k 0 ∈ N such that for all k ≥ k 0 , U n k (f )(y n k ) − f (y n k −1 ) < ε, or equivalently, U n k (f )(y n k ) <f (y n k −1 )+ ε. Taking lim sup as k →∞, we get M ≤ lim k→∞ sup f (y n k −1 )+ ε ≤ M f + ε. As ε> 0 was arbitrarily chosen, we obtain M ≤ M f . Because the inequality M f ≤ M is also true, it follows that (a) holds. (b). For the proof of (b), supposing that the sequence (inf {d(y n ,y): y ∈ E f }) n≥1 does not converge to 0, then there exist ε> 0 and an infinite sequence n 1 <n 2 < ...n k < ... such that inf {d(y n k ,y): y ∈ E f }≥ ε, ∀k ∈ N. By the (d, d)-sequentially compactness of Y, the sequence (y n k ) k≥1 contains a subsequence (y n k i ) i≥1 that converges to an element y ∈ Y such that f ( y)= M f , i.e. y ∈ E f , in contradiction to the inequality inf {d(y n k ,y): y ∈ E f }≥ ε.
The theorem is proved. Remark 3.2. Let M n = max{f (θ),f (y 0 ),f (y 1 ),...,f (y n )}. Then M n ≤ M f ≤ M n for every n =1, 2, 3, .... It follows that M f − M n ≤ M n − M n ,n =1, 2, .... The last inequality is a convenient upper bound for the error M f − M n . Because U n (f )(y)= inf z∈{θ,y0,y1,...,yn−1}=Zn. {f (z)+ qd(y,z)},y ∈ Y has a simple expression depending essentially on d(y,z),z ∈ Z n and y ∈ Y, it is easy - at least in principle - to compute the number M n = max U n (f )(Y ). Also 0 ≤ U n+1 (f )(y n+1 ) − U n+1 (f )(y n ) ≤ qd(y n+1 ,y n) i.e. 0 ≤ M n+1 − f (y n ) ≤ qd(y n+1, y n ) , and because M n+1 ≥ f (y n ) it follows that 0 ≤ M n+1 − M n+1 ≤ M n+1 − f (y n ) ≤ qd(y n+1, y n ). This means that M n+1 − M n+1 = O(d(y n+1, y n )) and, consequently, M f − M n = O(d(y n ,y n−1 )). Remark 3.3. A function f belongs to d-SLip 0 Y if and only if −f belongs to d- SLip 0 Y and for every f ∈ d-SLip 0 Y, f | d = −f | d ([22], Corollary 1, page 59). It follows that −f is upper semicontinuous on (Y,d) and attains its maximum on Y, if Y is d-sequentially compact (see Theorem 2.6). By Theorem 2.1 and Remark 2.2 it follows that the maximal extension of −f in d-SLip 0 Y is F d (−f )(x) = inf {(−f )(y)+ f | d d(x, y)},x ∈ X, (3.2) i.e. (−f )| Y = F d (−f )| Y and f | d = −f | d = F d (−f )| d . The algorithm described above may be applied for searching the global maximum of −f, i.e. the global minimum of f, if the set Y is (d, d)-sequentially compact, and X is T 1 -separated.
References [1] P. Basso, Optimal search for the global maximum of functions with bounded semi- norm, SIAM J. Numer. Anal. 22 (no. 5) (1985), 888–905. [2] P. A. Borodin, The Banach-Mazur theorem for spaces with asymetric norm and its applications in convex analysis, Mat. Zametki 69 (no. 3) (2001), 329–337. [3] S. Cobza¸s, Separation of convex sets and best approximation in spaces with asym- metric norm, Quaest. Math. 27 (no. 3) (2004), 275–296. [4] S. Cobza¸s, Asymmetric locally convex spaces, Int. J. Math. Math. Sci. 16 (2005), 2585–2608. [5] S. Cobza¸s and C. Must˘at ¸a, Norm-preserving extyension of convex Lipschitz functions, J. Approx. Theory 24 (no. 3) (1978), 236–244. [6] S. Cobza¸s and C. Must˘at ¸a, Extension of bounded linear functionals and best approx- imation in spaces with asymmetric norm, Rev. Anal. Num´er. Th´eor. Approx. 32 (no. 1) (2004), 39–50. [7] J. Collins, and J. Zimmer, An asymmetric Arzel` a-Ascoli theorem, Topology Appl. 154 (no. 11) (2007), 2312–2322. [8] P. Fletcher and W. F. Lindgren, Quasi-uniform Spaces, Marcel Dekker, New-York, 1982. [9] S. Garcia-Ferreira, S. Romaguera and M. Sanchis, Bounded subsets and Grothen- dieck’s theorem for bispaces, Houston. J. Math. 25 (no. 2) (1999), 267–283. [10] L. M. Garcia-Raffi, S. Romaguera and E. A. S´anchez-P´erez, The dual space of an asymmetric normed linear space, Quaest. Math. 26 (no. 1) (2003), 83–96. [11] L. M. Garcia-Raffi, S. Romaguera and E. A. S´anchez-P´erez, On Hausdorff asymmet- ric normed linear spaces, Houston J. Math. 29 (no. 3) (2003), 717–728. [12] M. G. Krein and A. A. Nudelman, The Markov Moment Problem and Extremum Problems, Nauka, Moscov, 1973 (in Russian), English translation: AMS, Providence, R.I., 1977. [13] H. P. A. K¨ unzi, Nonsymmetric distances and their associated topologies: about the origin of basic ideas in the area of asymmetric topology, Handbook of the History of General Topology, ed. by C.E. Aull and R. Lower, vol. 3, Hist. Topol. 3, Kluwer Acad. Publ. (Dordrecht, 2001), 853–968. [14] E. J. McShane, Extension of range of functions, Bull. Amer. Math. Soc. 40 (1934), 837–842. [15] A. Mennucci, On asymmetric distances, Technical report, Scuola Normale Superiore, Pisa, 2004. [16] C. Must˘at ¸a, Best approximation and unique extension of Lipschitz functions, J. Ap- prox. Theory 19 (no. 3) (1977), 222–230. [17] C. Must˘at ¸a, Extension of H¨ older Functions and some related problems of best approx- imation, ”Babe¸s-Bolyai” University, Faculty of Mathematics, Research Seminars, Seminar onf Mathematical Analysis (1991) 71–86. [18] C. Must˘at ¸a, Extension of semi-Lipschitz functions on quasi-metric spaces, Rev. Anal. Num´er. Th´eor. Approx. 30 (no. 1) (2001), 61–67. [19] C. Must˘at ¸a, On the extremal semi-Lipschitz functions, Rev. Anal. Num´er. Th´eor. Approx. 31 (no. 1) (2002), 61–67.
[20] V. Pestov and A. Stojmirovi´c, Indexing schemes for similarity search: an illustrated paradigm, Fund. Inf. 70 (no. 4) (2006), 367–385. [21] S. Romaguera and M. Sanchis, Semi-Lipschitz functions and best approximation in quasi-metric spaces, J. Approx. Theory 103 (2000), 292–301. [22] S. Romaguera and M. Sanchis, Properties of the normed cone of semi-Lipschitz func- tions, Acta Math. Hungar 108 (nos. 1-2) (2005), 55–70. [23] S. Romaguera, J. M. Sanchez- ´ Alvarez and M. Sanchis, El espacio de funciones semi- Lipschitz, VI Jornadas de Matem´atica Aplicada, Departamento de Matem´atica Apli- cada, Universidad Polit´ecnica de Valencia, 1-3 septiembrie, 2005. [24] J. M. S´anchez- ´ Alvarez, On semi-Lipschitz functions with values in a quasi-normed linear space, Appl. Gen. Top. 6 (no. 2) (2005), 217–228. [25] B. Shubert, A sequential method seeking the global maximum of a function, SIAM J. Num. Anal. 9 (1972), 379–388. [26] A. Stojmirovi´c, Quasi-metric spaces with measures, Proc. 18th Summer Conference on Topology and its Applications, Topology Proc. 28 (no. 2) (2004), 655–671. [27] W. A. Wilson, On quasi-metric spaces, Amer. J. Math. 53 (no. 3) (1931), 75–684. Costic˘a Must˘at ¸a “Tiberiu Popoviciu” Institute of Numerical Analysis P.O. Box. 68-1 400110 Cluj-Napoca Romania e-mail: cmustata2001@yahoo.com Received: June 19, 2008. Revised: September 29, 2008. Accepted: March 5, 2009.
2009

Related Posts