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
[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
2009-Mustata-On the approximation of the global extremum-MeditterJ
On the Approximation of the Global Extremum of a Semi-Lipschitz Function
Costică Mustăţ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, extension 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 nn of the evaluations to be performed. In the latter case the method is called an nn-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)M_{f} of a real semi-Lipschitz function ff, the algorithm we propose determines a decreasing sequence of numbers (M_(n))_(n >= 1)\left(M_{n}\right)_{n \geq 1}, having the limit M_(f)M_{f}. Each number M_(n)(n=1,2,dots)M_{n}(n=1,2, \ldots) is the absolute maximum of a special semi-Lipschitz function U_(n)(f)U_{n}(f). This function has a very simple analytical expression compared to the given function ff (which is assumed only to be semi-Lipschitz). For determining U_(n)(f)(x)U_{n}(f)(x) one requires on one hand
the computation of the value of ff at a certain point, and the values of ff at the nn point from the previous step, and on the other hand the quasi-distances from the current point xx to the n+1n+1 points. One can see therefore that the determining of the maximum M_(n+1)M_{n+1} of U_(n+1)(f)U_{n+1}(f) requires a small amount of computation. The absolute minimum of ff is given by the absolute maximum of -f-f.
We present in the following the framework of the described method.
Let XX be a non-empty set. A function d:X xx X rarr[0,oo)d: X \times X \rightarrow[0, \infty) is called a quasimetric on XX [21] (see also [7], [27]) if the following conditions hold
{:[AM1),d(x","y)=d(y","x)=0" iff "x=y],[AM2),d(x","z) <= d(x","y)+d(y","z)]:}\begin{array}{ll}
A M 1) & d(x, y)=d(y, x)=0 \text { iff } x=y \\
A M 2) & d(x, z) \leq d(x, y)+d(y, z)
\end{array}
for all x,y,z in Xx, y, z \in X.
The function bar(d):X xx X rarr[0,oo)\bar{d}: X \times X \rightarrow[0, \infty) defined by bar(d)(x,y)=d(y,x)\bar{d}(x, y)=d(y, x) for all x,y in Xx, y \in X is also a quasi-metric on XX, called the conjugate quasi-metric of dd. A pair ( X,dX, d ), where XX is a non-empty set and dd a quasi-metric on XX, is called a quasi-metric space. Obviously, the function d^(s)(x,y)=max{d(x,y), bar(d)(x,y)}d^{s}(x, y)=\max \{d(x, y), \bar{d}(x, y)\} is a metric on XX. Each quasi-metric dd on XX induces a topology tau(d)\tau(d) on XX which has as a base the family of balls (forward open balls [7]).
B^(+)(x,epsi):={y in X:d(x,y) < epsi},x in X,epsi > 0.B^{+}(x, \varepsilon):=\{y \in X: d(x, y)<\varepsilon\}, x \in X, \varepsilon>0 .
This topology is called the forward topology of X([7],[15])X([7],[15]) and is denoted by tau_(+)\tau_{+}. Analogously, the quasi-metric bar(d)\bar{d} induces the topology tau( bar(d))\tau(\bar{d}) on XX which has as a base the family of backward open balls ([7])
B^(-)(x,epsi):={y in X:d(y,x) < epsi},x in X,epsi > 0.B^{-}(x, \varepsilon):=\{y \in X: d(y, x)<\varepsilon\}, x \in X, \varepsilon>0 .
This topology is called the backward topology of XX ([7], [15]) and is denoted by tau_(-)\tau_{-}。
Note that the topology tau_(+)\tau_{+}is a T_(0)T_{0}-topology. If the condition AM1) is replaced by the condition: AM0) d(x,y)=0d(x, y)=0 iff x=yx=y, then tau_(+)\tau_{+}is a T_(1)T_{1}-topology. The pair ( X,dX, d ) is called a T_(0)T_{0} quasi-metric space, respectively a T_(1)T_{1} quasi-metric space (see [21] and [22]).
Let (X,d)(X, d) be a quasi-metric space. A sequence (x_(k))_(k >= 1)d\left(x_{k}\right)_{k \geq 1} d-converges to x_(0)in Xx_{0} \in X (respectively bar(d)\bar{d}-converges to x_(0)in Xx_{0} \in X ) iff
A set K sub XK \subset X is called dd-compact if every open cover of KK with respect to the forward topology has a finite subcover. We say that KK is dd-sequentially compact if every sequence in KK has a dd-convergent subsequence with limit in KK (Definition 4.1 in [7]). Finally, the set YY in ( X,dX, d ) is called ( d, bar(d)d, \bar{d} )-sequentially compact if every sequence (y_(n))_(n >= 1)\left(y_{n}\right)_{n \geq 1} in YY has a subsequence (y_(n_(k)))d\left(y_{n_{k}}\right) d-convergent to u in Yu \in Y and bar(d)\bar{d} convergent to v in Yv \in Y.
Observe that, if ( X,dX, d ) is a quasi-metric space ( d, bar(d)d, \bar{d} )-sequentially compact and T_(0)T_{0}-separated, then it is possible to find sequences with all subsequences both dd-convergent and bar(d)\bar{d}-convergent, but to different limits. For example, let X=[0,1]X=[0,1]
and d(x,y)=(y-x)vv0,x,y in[0,1]d(x, y)=(y-x) \vee 0, x, y \in[0,1]. Then bar(d)(x,y)=(x-y)vv0\bar{d}(x, y)=(x-y) \vee 0 and the sequence ((1)/(n))_(n >= 1)\left(\frac{1}{n}\right)_{n \geq 1} satisfies the property that every subsequences dd-converges to 0 and bar(d)\bar{d} converges to 1 . But if ( X,dX, d ) is ( d, bar(d)d, \bar{d} )-sequentially compact and T_(1)T_{1}-separated, then by Lemma 3.1 of [7] it follows that if (x_(n))_(n >= 1)sub X\left(x_{n}\right)_{n \geq 1} \subset X is dd-convergent to x_(0)in Xx_{0} \in X and bar(d)\bar{d}-convergent to y_(0)in Xy_{0} \in X, then x_(0)=y_(0)x_{0}=y_{0}. This fact is essential in the proof of Theorem 3.1 from bellow.
Definition 1.1 ([21]). Let YY be a non-empty subset of a quasi-metric space ( X,dX, d ). A function f:Y rarrRf: Y \rightarrow \mathbb{R} is called dd-semi-Lipschitz if there exists L >= 0L \geq 0 (named a dd-semi-Lipschitz constant for f)f) such that
{:(1.1)f(x)-f(y) <= Ld(x","y)","" for all "x","y in Y.:}\begin{equation*}
f(x)-f(y) \leq L d(x, y), \text { for all } x, y \in Y . \tag{1.1}
\end{equation*}
A function f:Y rarrRf: Y \rightarrow \mathbb{R} is called <= _(d)\leq_{d}-increasing if f(x) <= f(y)f(x) \leq f(y) whenever d(x,y)=0d(x, y)=0.
Denote by R_( <= _(d))^(Y)\mathbb{R}_{\leq_{d}}^{Y} the set of all <= _(d)\leq_{d}-increasing functions on YY. This set is a cone in the linear space R^(Y)\mathbb{R}^{Y} of all real-valued functions defined on YY, i.e., for each f,g inR_( <= _(d))^(Y)f, g \in \mathbb{R}_{\leq_{d}}^{Y} and lambda >= 0\lambda \geq 0 it follows that f+g inR_( <= _(d))^(Y)f+g \in \mathbb{R}_{\leq_{d}}^{Y} and lambda f inR_( <= _(d))^(Y)\lambda f \in \mathbb{R}_{\leq_{d}}^{Y}.
For a dd-semi-Lipschitz function ff on YY, put [21]
{:(1.2)||f|_(d)=s u p_({:[d(x","y) > 0],[x","y in Y]:})((f(x)-f(y)))vv0)/(d(x,y)).:}:}\begin{equation*}
\left||f|_{d}=\sup _{\substack{d(x, y)>0 \\ x, y \in Y}} \frac{(f(x)-f(y))) \vee 0}{d(x, y)} .\right. \tag{1.2}
\end{equation*}
Then ||f|_(d):}\left||f|_{d}\right. is the smallest dd-semi-Lipschitz constant for f([18])f([18]).
For a fixed element theta in Y\theta \in Y denote
If ( X,dX, d ) is a T_(1)T_{1} quasi-metric space, then every f inR^(X)f \in \mathbb{R}^{X} is <= _(d)\leq_{d}-increasing ([21]).
The set defined by (1.3) is a subcone of the cone R_( <= _(d))^(Y)\mathbb{R}_{\leq_{d}}^{Y}, and the functional |||_(d):d-\|\left.\right|_{d}: d- SLip _(0)Y rarr[0,oo)_{0} Y \rightarrow[0, \infty) defined by (1.2) is an asymmetric norm, i.e., it is subadditive, positive homogeneous and ||f|_(d)=0\|\left. f\right|_{d}=0 iff f-=0f \equiv 0. The pair ( dd-SLip _(0)Y,|||_(d){ }_{0} Y, \|\left.\right|_{d} ) is called the normed cone of real semi-Lipschitz functions on YY, vanishing at the fixed point theta in Y([22])\theta \in Y([22]).
In [22] some properties of the normed cone ( dd-SLip _(0)Y,|||_(d){ }_{0} Y, \|\left.\right|_{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 in d-Sf \in d-S Lip _(0)Y_{0} Y. A function FF in d-Sd-S Lip _(0)X_{0} X satisfying the inequality
for all u,v in Xu, v \in X and such that F(y)=f(y)F(y)=f(y) for all y in Yy \in Y is called an extension of ff (preserving the asymmetric norm ||f|_(d)\|\left. f\right|_{d} ).
It follows that each extension F in d-SF \in d-S Lip _(0)X_{0} X of f in d-Sf \in d-S Lip _(0)Y_{0} Y satisfies
{:(2.1)F|_(Y)=f" and "||F|_(d)=||f|_(d):}\begin{equation*}
\left.F\right|_{Y}=f \text { and }\left.\left\|\left.F\right|_{d}=\right\| f\right|_{d} \tag{2.1}
\end{equation*}
The existence of such an extension for each f in d-Sf \in d-S Lip _(0)Y_{0} Y follows from the following theorem proved in [18]. For the sake of completeness we include the proof.
Theorem 2.1. Let ( X,dX, d ) be a quasi-metric space, theta in X\theta \in X a fixed element, and YY a subset of XX with theta in Y\theta \in Y. Then for every f in d-Sf \in d-S Lip _(0)Y_{0} Y there exists at least a function F in dF \in d-SLip _(0)X{ }_{0} X such that F|_(Y)=f\left.F\right|_{Y}=f and ||F|_(d)=||f|_(d)\left.\left\|\left.F\right|_{d}=\right\| f\right|_{d}.
Proof. For f in d-Sf \in d-S Lip _(0)Y_{0} Y let
{:(2.2)F_(d)(f)(x)=i n f_(y in Y)[f(y)+||f|_(d)d(x,y)}","x in X:}\begin{equation*}
F_{d}(f)(x)=\inf _{y \in Y}\left[f(y)+\|\left. f\right|_{d} d(x, y)\right\}, x \in X \tag{2.2}
\end{equation*}
First we show that F_(d)(f)F_{d}(f) is well defined.
Let x in Xx \in X. For any y in Yy \in Y we have
{f(y)+||f|_(d)d(x,y):y in Y}:}\left\{f(y)+\left||f|_{d} d(x, y): y \in Y\right\}\right.
is bounded from below and, consequently, the infimum in (2.2) is finite.
Now we show that F_(d)(f)|_(Y)=f,quadF_(d)(f)in d-S\left.F_{d}(f)\right|_{Y}=f, \quad F_{d}(f) \in d-S Lip _(0)X_{0} X and ||F_(d)(f)|_(d)=||f|_(d)\left.\left\|\left.F_{d}(f)\right|_{d}=\right\| f\right|_{d}. For every y in Yy \in Y we have
F_(d)(f)(x) <= f(y)+||f|_(d)d(x,y),x in X,F_{d}(f)(x) \leq f(y)+\|\left. f\right|_{d} d(x, y), x \in X,
which for x=yx=y yields
F_(d)(f)(y) <= f(y).F_{d}(f)(y) \leq f(y) .
On the other hand, for y in Yy \in Y and all y^(')in Yy^{\prime} \in Y,
so that the equality ||F_(d)(f)|_(d)=||f|_(d)\left.\left\|\left.F_{d}(f)\right|_{d}=\right\| f\right|_{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 in df \in d-SLip _(0)Y{ }_{0} Y, the set of all extensions preserving the asymmetric norm ||f|_(d)\|\left. f\right|_{d}, i.e.
{:(2.3)E_(d)(f)={H in d-SLip_(0)X:H|_(Y)=f" and "||H|_(d)=||f|_(d)}:}:}\begin{equation*}
\mathcal{E}_{d}(f)=\left\{H \in d-S L i p_{0} X:\left.H\right|_{Y}=f \text { and } \|\left. H\right|_{d}=\left||f|_{d}\right\}\right. \tag{2.3}
\end{equation*}
is nonempty, because F_(d)(f)inE_(d)(f)F_{d}(f) \in \mathcal{E}_{d}(f) where F_(d)(f)F_{d}(f) is given by (2.2).
Analogously, one proves that the function
{:(2.4)G_(d)(f)=s u p_(y in Y){f(y)-||f|_(d)( bar(d))(x,y)}","x in X:}\begin{equation*}
G_{d}(f)=\sup _{y \in Y}\left\{f(y)-\|\left. f\right|_{d} \bar{d}(x, y)\right\}, x \in X \tag{2.4}
\end{equation*}
is in E_(d)(f)\mathcal{E}_{d}(f).
Remark 2.3. Obviously, the set E_(d)(f)\mathcal{E}_{d}(f) is convex, i.e. for every H_(1),H_(2)inE_(d)(f)H_{1}, H_{2} \in \mathcal{E}_{d}(f) and lambda in[0,1]\lambda \in[0,1] it follows lambdaH_(1)+(1-lambda)H_(2)inE_(d)(f)\lambda H_{1}+(1-\lambda) H_{2} \in \mathcal{E}_{d}(f). Moreover for every H inE_(d)(f)H \in \mathcal{E}_{d}(f) we have:
{:(2.5)G_(d)(f)(x) <= H(x) <= F_(d)(f)(x)","x in X.:}\begin{equation*}
G_{d}(f)(x) \leq H(x) \leq F_{d}(f)(x), x \in X . \tag{2.5}
\end{equation*}
The function F_(d)(f)F_{d}(f) defined by (2.2) is called the maximal extension of ff, and G_(d)(f)G_{d}(f) defined by (2.4) is called the minimal extension of ff.
Remark 2.4. If theta inY_(1)subY_(2)sub Y\theta \in Y_{1} \subset Y_{2} \subset Y and f in df \in d-SLip _(0)Y{ }_{0} Y, then for each u in Yu \in Y we can easily obtain:
i n f_(y inY_(1)){f(y)+||f|_(d)d(u,y)} >= i n f_(y inY_(2)){f(y)+||f|_(d)d(u,y)}\inf _{y \in Y_{1}}\left\{f(y)+\|\left. f\right|_{d} d(u, y)\right\} \geq \inf _{y \in Y_{2}}\left\{f(y)+\|\left. f\right|_{d} d(u, y)\right\}
and
s u p_(y inY_(1)){f(y)-||f|_(d)( bar(d))(u,y)} <= s u p_(y inY_(2)){f(y)-||f|_(d)( bar(d))(u,y)}.\sup _{y \in Y_{1}}\left\{f(y)-\|\left. f\right|_{d} \bar{d}(u, y)\right\} \leq \sup _{y \in Y_{2}}\left\{f(y)-\|\left. f\right|_{d} \bar{d}(u, y)\right\} .
Remark 2.5. Observe that Theorem 2.1 is the "nonsymmetric" analog of McShane's theorem [14] for metric spaces.
Theorem 2.6. Let (X,d)(X, d) be a quasi-metric space and Y sube XY \subseteq X. Then
(a) Every f in df \in d-SLip YY is upper semicontinuous on (Y, bar(d))(Y, \bar{d});
(b) If YY is bar(d)\bar{d}-sequentially compact, then every f in df \in d-SLip YY attains its maximum value on YY.
Proof. Let f in df \in d-SLipY. If ||f|_(d)=0\|\left. f\right|_{d}=0 then f(y)=f(y)= constant for all y in Yy \in Y and this function is upper semicontinuous. Let y_(0)in Yy_{0} \in Y and ||f|_(d) > 0\|\left. f\right|_{d}>0. Then the inequality
For epsi > 0\varepsilon>0 and y in Yy \in Y such that d(y,y_(0)) < (epsi)/(||f|_(d))d\left(y, y_{0}\right)<\frac{\varepsilon}{\|\left. f\right|_{d}} it follows
showing that ff is upper semicontinuous on (Y, bar(d))(Y, \bar{d}).
Let YY be bar(d)\bar{d}-sequentially compact in ( X,dX, d ) and M=s u p f(Y)M=\sup f(Y), where M inRuu{+oo}M \in \mathbb{R} \cup\{+\infty\}. Then there exists a sequence (y_(n))_(n >= 1)\left(y_{n}\right)_{n \geq 1} in YY such that lim_(n rarr oo)f(y_(n))=M\lim _{n \rightarrow \infty} f\left(y_{n}\right)= M. Because YY is bar(d)\bar{d}-sequentially compact there exists y_(0)in Yy_{0} \in Y and a subsequence (y_(n_(k)))_(k >= 1)\left(y_{n_{k}}\right)_{k \geq 1} of (y_(n))_(n >= 1)\left(y_{n}\right)_{n \geq 1} such that lim_(k rarr oo)d(y_(n_(k)),y_(0))=0\lim _{k \rightarrow \infty} d\left(y_{n_{k}}, y_{0}\right)=0. By the upper semicontinuity of ff in y_(0)y_{0} it follows:
M=lim_(k rarr oo)f(y_(n_(k)))=l i m s u p f(y_(n_(k))) <= f(y_(0)) <= MM=\lim _{k \rightarrow \infty} f\left(y_{n_{k}}\right)=\limsup f\left(y_{n_{k}}\right) \leq f\left(y_{0}\right) \leq M
implying M < ooM<\infty and f(y_(0))=Mf\left(y_{0}\right)=M.
By Theorem 2.6 it follows that for Y bar(d)Y \bar{d}-sequentially compact, the functional |||_(oo):d-S\|\left.\right|_{\infty}: d-S Lip _(0)Y rarr[0,oo)_{0} Y \rightarrow[0, \infty) defined by
||f|_(oo)=max{f(y):y in Y}\|\left. f\right|_{\infty}=\max \{f(y): y \in Y\}
is an asymmetric norm on d-Sd-S Lip _(0)Y_{0} Y.
Indeed, for every ff in dd-SLip _(0)Y{ }_{0} Y we have ||f|_(oo) >= f(theta)=0\|\left. f\right|_{\infty} \geq f(\theta)=0. If ||f|_(oo) > 0\|\left. f\right|_{\infty}>0 then there exists y_(0)in Yy_{0} \in Y such that f(y_(0)) > 0=f(theta)f\left(y_{0}\right)>0=f(\theta). Consequently, because f inR_( <= _(d))^(Y)f \in \mathbb{R}_{\leq_{d}}^{Y} it follows d(y_(0),theta) > 0d\left(y_{0}, \theta\right)>0, and
It follows f!=0f \neq 0, because |||_(d)\|\left.\right|_{d} is asymmetric norm on dd-SLip _(0)Y{ }_{0} Y. Obviously, ||f+g|_(oo) <= ||f|_(oo)+||g|_(oo)" and "||lambda f|_(oo)= lambda||f|_(oo)\left||f+g|_{\infty} \leq\left||f|_{\infty}+\left||g|_{\infty} \text { and }\right|\right| \lambda f\right|_{\infty}=\left.\lambda| | f\right|_{\infty} for all f,g in d-Sf, g \in d-S Lip _(0)Y_{0} Y and lambda >= 0\lambda \geq 0.
3. The sequential method
Let ( X,dX, d ) be a quasi-metric space, theta in X\theta \in X a fixed element, and Y sub XY \subset X with theta in Y\theta \in Y. Suppose that YY is bar(d)\bar{d}-sequentially compact, and f in df \in d-SLip _(0)Y{ }_{0} Y. Let
M_(f)=s u p{f(y):y in Y}M_{f}=\sup \{f(y): y \in Y\}
and
E_(f)={y in Y:f(y)=M_(f)}.E_{f}=\left\{y \in Y: f(y)=M_{f}\right\} .
We want to find the maximum value M_(f)M_{f} of ff and a point y_(0)inE_(f)y_{0} \in E_{f}.
For this goal we consider the following sequential method, supposing that q > 0q>0 is an upper bound for ||f|_(d)\|\left. f\right|_{d} on YY, i.e. ||f|_(d) <= q\|\left. f\right|_{d} \leq q.
Firstly, let ZZ be a nonempty subset of YY with theta in Z\theta \in Z. From the proof of Theorem 2.1, the functions
U(f)(y)=i n f{f(z)+qd(y,z):z in Z},y in YU(f)(y)=\inf \{f(z)+q d(y, z): z \in Z\}, y \in Y
and
u(f)(y)=s u p{f(z)-qd(z,y):z in Z},y in Yu(f)(y)=\sup \{f(z)-q d(z, y): z \in Z\}, y \in Y
Taking the infimum with respect to z in Zz \in Z it follows
f(y) <= U(f)(y),y in Y.f(y) \leq U(f)(y), y \in Y .
Analogously,
f(z)-f(y) <= qd(z,y),f(z)-f(y) \leq q d(z, y),
implies
f(y) >= f(z)-qd(z,y).f(y) \geq f(z)-q d(z, y) .
Taking the supremum with respect to z in Zz \in Z one obtains
u(f)(y) <= f(y),y in Y.u(f)(y) \leq f(y), y \in Y .
If
M_(U):=max{U(f)(y):y in Y},M_{U}:=\max \{U(f)(y): y \in Y\},
then
M_(f) <= M_(U).M_{f} \leq M_{U} .
We define now two sequences (y_(n))_(n >= 0)\left(y_{n}\right)_{n \geq 0} in YY and (M_(n))_(n >= 0)\left(M_{n}\right)_{n \geq 0} in R\mathbb{R} in the following way. Let
U_(0)(f)(y)=f(theta)+qd(y,theta)=qd(y,theta),y in Y,U_{0}(f)(y)=f(\theta)+q d(y, \theta)=q d(y, \theta), y \in Y,
i.e. U_(0)(f)U_{0}(f) is an extension (the maximal extension) of f|_({theta})\left.f\right|_{\{\theta\}} with the semi-Lipschitz constant qq. Then, by the above considerations, it follows
{:[f(y) <= U_(0)(f)(y)","y in Y","],[U_(0)(f) in d-SLip_(0)Y.]:}\begin{aligned}
f(y) & \leq U_{0}(f)(y), y \in Y, \\
U_{0}(f) & \in d-S L i p_{0} Y .
\end{aligned}
If y_(0)in Yy_{0} \in Y is such that
U_(0)(f)(y_(0))=M_(0):=s u pU_(0)(f)(Y),U_{0}(f)\left(y_{0}\right)=M_{0}:=\sup U_{0}(f)(Y),
then
M_(f) <= M_(0).M_{f} \leq M_{0} .
Let Z_(1)={theta,y_(0)}Z_{1}=\left\{\theta, y_{0}\right\} and let
U_(1)(f)(y)=i n f_(z inZ_(1)){f(z)+qd(y,z)},y in Y,U_{1}(f)(y)=\inf _{z \in Z_{1}}\{f(z)+q d(y, z)\}, y \in Y,
be the maximal extension of f|_(Z_(1))\left.f\right|_{Z_{1}} with semi-Lipschitz constant qq. Then U_(1)in dU_{1} \in dSS Lip _(0)Y_{0} Y and by Remark 2.3, it follows:
{:[f(y) <= U_(1)(f)(y) <= U_(0)(f)(y)","y in Y","],[f|_(Z_(1))=U_(1)(f)|_(Z_(1))=U_(0)(f)|_(Z_(1)).]:}\begin{aligned}
f(y) & \leq U_{1}(f)(y) \leq U_{0}(f)(y), y \in Y, \\
\left.f\right|_{Z_{1}} & =\left.U_{1}(f)\right|_{Z_{1}}=\left.U_{0}(f)\right|_{Z_{1}} .
\end{aligned}
If y_(1)in Yy_{1} \in Y is such that
U_(1)(f)(y_(1))=M_(1):=s u pU_(1)(f)(Y),U_{1}(f)\left(y_{1}\right)=M_{1}:=\sup U_{1}(f)(Y),
for all y in Yy \in Y.
Choose y_(n)in Yy_{n} \in Y such that
U_(n)(f)(y_(n))=M_(n):=s u pU_(n)(Y).U_{n}(f)\left(y_{n}\right)=M_{n}:=\sup U_{n}(Y) .
Continuing in this manner we obtain the sequences
{:[(3.1){theta,y_(0),y_(1),dots,y_(n),dots} sub Y", and "],[{M_(0),M_(1),dots,M_(n),dots} subR". "]:}\begin{align*}
\left\{\theta, y_{0}, y_{1}, \ldots, y_{n}, \ldots\right\} & \subset Y \text {, and } \tag{3.1}\\
\left\{M_{0}, M_{1}, \ldots, M_{n}, \ldots\right\} & \subset \mathbb{R} \text {. }
\end{align*}
The following theorem contains the properties of these two sequences, if YY is ( d, bar(d)d, \bar{d} )-sequentially compact.
Theorem 3.1. Let ( X,dX, d ) be a T_(1)T_{1} quasi-metric space, theta in X\theta \in X fixed, and YY a (d, bar(d))(d, \bar{d}) sequentially compact subset of XX with theta in Y\theta \in Y. Let f in d-Sf \in d-S Lip _(0)Y,q >= ||f|_(d)_{0} Y, q \geq \|\left. f\right|_{d} and let ( y_(n)y_{n} ) and ( M_(n)M_{n} ) be the sequences in (3.1). Then
(a) (M_(n))\left(M_{n}\right) converges to M_(f)M_{f};
(b) lim_(n rarr oo)i n f{d(y_(n),y):y inE_(f)}=0\lim _{n \rightarrow \infty} \inf \left\{d\left(y_{n}, y\right): y \in E_{f}\right\}=0.
Proof. (a). Since for every n >= 1n \geq 1
U_(n)(f)(y) <= U_(n-1)(f)(y),y in Y,U_{n}(f)(y) \leq U_{n-1}(f)(y), y \in Y,
it follows
M_(n)=s u pU_(n)(f)(Y) <= s u pU_(n-1)(f)(Y)=M_(n-1)M_{n}=\sup U_{n}(f)(Y) \leq \sup U_{n-1}(f)(Y)=M_{n-1}
Therefore, the sequence ( M_(n)M_{n} ) is decreasing. Since U_(n)(f)(theta)=0U_{n}(f)(\theta)=0 we have M_(n) >= 0M_{n} \geq 0 for all n >= 0n \geq 0. It follows that there exists M >= 0M \geq 0 such that
Since YY is (d, bar(d))(d, \bar{d})-sequentially compact, the sequence (y_(n))\left(y_{n}\right) contains a subsequence (y_(n_(k)))_(k >= 1)\left(y_{n_{k}}\right)_{k \geq 1} which is dd - and bar(d)\bar{d}-convergent to an element bar(y)in Y\bar{y} \in Y, i.e.,
Taking lim sup as k rarr ook \rightarrow \infty, we get
M <= lim_(k rarr oo)s u p f(y_(n_(k)-1))+epsi <= M_(f)+epsi.M \leq \lim _{k \rightarrow \infty} \sup f\left(y_{n_{k}-1}\right)+\varepsilon \leq M_{f}+\varepsilon .
As epsi > 0\varepsilon>0 was arbitrarily chosen, we obtain M <= M_(f)M \leq M_{f}. Because the inequality M_(f) <= MM_{f} \leq M is also true, it follows that (a) holds.
(b). For the proof of (b), supposing that the sequence
(i n f{d(y_(n),y):y inE_(f)})_(n >= 1)\left(\inf \left\{d\left(y_{n}, y\right): y \in E_{f}\right\}\right)_{n \geq 1}
does not converge to 0 , then there exist epsi > 0\varepsilon>0 and an infinite sequence n_(1) < n_(2) < dotsn_(k) < dotsn_{1}<n_{2}< \ldots n_{k}<\ldots such that
i n f{d(y_(n_(k)),y):y inE_(f)} >= epsi,AA k inN.\inf \left\{d\left(y_{n_{k}}, y\right): y \in E_{f}\right\} \geq \varepsilon, \forall k \in \mathbb{N} .
By the ( d, bar(d)d, \bar{d} )-sequentially compactness of YY, the sequence (y_(n_(k)))_(k >= 1)\left(y_{n_{k}}\right)_{k \geq 1} contains a subsequence (y_(n_(k_(i))))_(i >= 1)\left(y_{n_{k_{i}}}\right)_{i \geq 1} that converges to an element bar(y)in Y\bar{y} \in Y such that f( bar(y))=M_(f)f(\bar{y})=M_{f}, i.e. bar(y)inE_(f)\bar{y} \in E_{f}, in contradiction to the inequality
i n f{d(y_(n_(k)),y):y inE_(f)} >= epsi.\inf \left\{d\left(y_{n_{k}}, y\right): y \in E_{f}\right\} \geq \varepsilon .
The theorem is proved.
Remark 3.2. Let bar(M)_(n)=max{f(theta),f(y_(0)),f(y_(1)),dots,f(y_(n))}\bar{M}_{n}=\max \left\{f(\theta), f\left(y_{0}\right), f\left(y_{1}\right), \ldots, f\left(y_{n}\right)\right\}. Then bar(M)_(n) <= M_(f) <= M_(n)\bar{M}_{n} \leq M_{f} \leq M_{n} for every n=1,2,3,dotsn=1,2,3, \ldots. It follows that
The last inequality is a convenient upper bound for the error M_(f)- bar(M)_(n)M_{f}-\bar{M}_{n}.
Because
U_(n)(f)(y)=i n f_(z in{theta,y_(0),y_(1),dots,y_(n-1)}=Z_(n).){f(z)+qd(y,z)},y in YU_{n}(f)(y)=\inf _{z \in\left\{\theta, y_{0}, y_{1}, \ldots, y_{n-1}\right\}=Z_{n} .}\{f(z)+q d(y, z)\}, y \in Y
has a simple expression depending essentially on d(y,z),z inZ_(n)d(y, z), z \in Z_{n} and y in Yy \in Y, it is easy - at least in principle - to compute the number
Remark 3.3. A function ff belongs to dd-SLip _(0)Y{ }_{0} Y if and only if -f-f belongs to bar(d)\bar{d}SLip_(0)YS L i p_{0} Y and for every f in d-SLip_(0)Y,||f|_(d)=||-f|_( bar(d)):}f \in d-S L i p_{0} Y,\left||f|_{d}=\left||-f|_{\bar{d}}\right.\right. ([22], Corollary 1, page 59).
It follows that -f-f is upper semicontinuous on ( Y,dY, d ) and attains its maximum on YY, if YY is dd-sequentially compact (see Theorem 2.6).
By Theorem 2.1 and Remark 2.2 it follows that the maximal extension of -f-f in bar(d)-SLip_(0)Y\bar{d}-S L i p_{0} Y is
{:(3.2)F_( bar(d))(-f)(x)=i n f{(-f)(y)+||f|_(d)( bar(d))(x,y)}","x in X:}\begin{equation*}
F_{\bar{d}}(-f)(x)=\inf \left\{(-f)(y)+\|\left. f\right|_{d} \bar{d}(x, y)\right\}, x \in X \tag{3.2}
\end{equation*}
i.e.
(-f)|_(Y)=F_( bar(d))(-f)|_(Y)" and "||f|_(d)=||-f|_( bar(d))=||F_( bar(d))(-f)|_( bar(d))\left.(-f)\right|_{Y}=\left.F_{\bar{d}}(-f)\right|_{Y} \text { and }\left\|\left.f\right|_{d}=\right\|-\left.f\right|_{\bar{d}}=\|\left. F_{\bar{d}}(-f)\right|_{\bar{d}}
The algorithm described above may be applied for searching the global maximum of -f-f, i.e. the global minimum of ff, if the set YY is (d, bar(d))(d, \bar{d})-sequentially compact, and XX is T_(1)T_{1}-separated.
References
[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. Cobzaş, Separation of convex sets and best approximation in spaces with asymmetric norm, Quaest. Math. 27 (no. 3) (2004), 275-296.
[4] S. Cobzaş, Asymmetric locally convex spaces, Int. J. Math. Math. Sci. 16 (2005), 2585-2608.
[5] S. Cobzaş and C. Mustăţa, Norm-preserving extyension of convex Lipschitz functions, J. Approx. Theory 24 (no. 3) (1978), 236-244.
[6] S. Cobzaş and C. Mustăţa, Extension of bounded linear functionals and best approximation in spaces with asymmetric norm, Rev. Anal. Numér. Théor. Approx. 32 (no. 1) (2004),39-50(2004), 39-50.
[7] J. Collins, and J. Zimmer, An asymmetric Arzelà-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ánchez-Pérez, 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ánchez-Pérez, 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ünzi, 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ăţa, Best approximation and unique extension of Lipschitz functions, J. Approx. Theory 19 (no. 3) (1977), 222-230.
[17] C. Mustăţa, Extension of Hölder Functions and some related problems of best approximation, "Babeş-Bolyai" University, Faculty of Mathematics, Research Seminars, Seminar onf Mathematical Analysis (1991) 71-86.
[18] C. Mustăţa, Extension of semi-Lipschitz functions on quasi-metric spaces, Rev. Anal. Numér. Théor. Approx. 30 (no. 1) (2001), 61-67.
[19] C. Mustăţa, On the extremal semi-Lipschitz functions, Rev. Anal. Numér. Théor. Approx. 31 (no. 1) (2002), 61-67.
[20] V. Pestov and A. Stojmirović, 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-Álvarez and M. Sanchis, El espacio de funciones semiLipschitz, VI Jornadas de Matemática Aplicada, Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, 1-3 septiembrie, 2005.
[24] J. M. Sánchez-Álvarez, 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ć, 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ă Mustăţ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.
This research has been supported by the Romanian Ministry of Education and Research under Grant 2-CEx-06-11-96/2006.