inf k∈Ksup f ∈F ||f − k|| and the elements in K which attain the above infimum are called a best simultaneous approximation for F from K

Volume 23, No. 3, September 2010

REMARK FOR CALCULATING THE BEST SIMULTANEOUS APPROXIMATIONS

Hyang Joo Rhee*

Abstract. This paper is concerned with algorithm for calculating one-sided best simultaneous approximation, in the case of continu- ous functions. we will apply any subgradient algorithm. In other words, we consider the algotithms from a mathematical, rather then computational, point of view.

1. Introduction

We assume that W is a normed linear space and K is a nonempty subset of W . For any subset F of W , we define

d(F, K) := inf

k∈Ksup

f ∈F

||f − k||

and the elements in K which attain the above infimum are called a best simultaneous approximation for F from K.

Lemma 1.1. [6] Suppose that K is a nonempty closed convex subset of a finite-dimensional subspace of a normed linear space W . For any compact subset F ⊂ W , there exists a best simultaneous approximation for F from K.

Throughout this article, we denote that X is a compact subset of R^m satisfying X = intX, S is an n-dimensional subspace of C(X) with the L₁(X, µ)-norm where µ is an admissible measure on X.

Received March 08, 2010; Accepted August 12, 2010.

2010 Mathematics Subject Classification: Primary 41A28, 41A65.

Key words and phrases: one-sided simultaneous approximation, linear pro- gramming.

This work was completed with the support by a fund of Duksung Women’s Uni- versity in 2009.

Suppose that we are given l−tuple F = {f₁, · · · , f_`} in C(X) with S(F ) =

\` i=1

{s ∈ S| s ≤ f_i} is non-empty. We define

d(F, S(F )) := inf

s∈S(F )sup

f ∈F

||f − s||₁

and the elements in S(F ) which attain the above infimum are called a one-sided best simultaneous approximation for F from S(F ). The case by ` = 1, we called a one-sided best approximation for f from S(f ) [5].

Finding a one-sided best simultaneous approximation for F from S(F ) is equivalent to finding a s ∈ S(F ) satisfying

sup{

Z

X

s dµ| s ∈ S(F )}.

Since S(F ) is closed and convex, we have that S(F ) 6= φ for all l−tuple F = {f₁, · · · , f_`} in C(X) if and only if S contains a strictly positive function. By lemma 1.0.1., if S(F ) is nonempty, then there exists a one- sided best simultaneous approximation for F from S(F ). We choose and fix a basis s₁, · · · , s_n for S where s₁ is strictly positive and

Z

X

s₁dµ = 1,

while Z

X

s_idµ = 0, i = 2, · · · , n.

Thus our problem can be reformulated as max{a₁ |

Xn i=1

a_is_i ≤ f_j, j = 1, · · · , `}.

For each ˆa = (a₂, · · · , a_n) ∈ Rⁿ⁻¹, define h_j(ˆa) = min{f_j(x) −P_n

i=2a_is_i(x)

s₁(x) : x ∈ X}

and H(ˆa) = min_1≤j≤`h_j(ˆa).

Remark 1.2. Since s₁ is strictly positive, max{a₁ |

Xn i=1

a_is_i ≤ f_j, j = 1, · · · , `} = max

ˆ

a∈Rⁿ⁻¹ min

1≤j≤`h_j(ˆa)

= max

ˆ

a∈Rⁿ⁻¹H(ˆa).

2. A subgadient to H at ˆa

In this section, we shall consider vector in Rⁿ⁻¹ as being indexed 2 to n. This algorithm is based on ideas from gradients and subgradients.

Corollary 2.1. The function H is a continuous concave function on Rⁿ⁻¹.

Proof. For each h_j (1 ≤ j ≤ `), the continuity and concavity may be proved as follows. The continuity is obvious. Let ˆa, ˆb ∈ Rⁿ⁻¹. By definition

f_j ≥ h_j(ˆa)s₁+ Xn

i=2

a_is_i

f_j ≥ h_j(ˆb)s₁+ Xn

i=2

b_is_i on all of X. Thus, for any λ ∈ [0, 1],

f_j ≥ (λh_j(ˆa) + (1 − λ)h_j(ˆb))s₁+ Xn i=2

(λa_i+ (1 − λ)b_i)s_i on X. Which implies that

h_j(λˆa + (1 − λ)ˆb) ≥ λh_j(ˆa) + (1 − λ)h_j(ˆb).

Thus h_j is concave. By definition, H(ˆa) = min_1≤j≤`h_j(ˆa), the function H is a continuous concave function on a one-sided best simultaneous approximation for F from S(F ).

We also have by definition that H is finite on Rⁿ⁻¹. We claim that

||ˆa||→∞lim H(ˆa) = −∞

where || · || is any norm on Rⁿ⁻¹. To see this, set T = span {s₂, · · · , s_n}.

Since T is a finite dimensional subspace of C(X), and R

Xtdµ = 0 for all t ∈ T , we necessarily have

||ˆa||→∞lim max{

Xn i=2

a_is_i(x) : x ∈ X} = ∞.

Thus

||ˆa||→∞lim min{f_j(x) −P_n

i=2a_is_i(x)

s₁(x) : x ∈ X} = −∞, i.e., lim_{||ˆa||→∞}h_j(ˆa) = −∞, so lim_{||ˆa||→∞}H(ˆa) = −∞.

Maximizing H over Rⁿ⁻¹ is therefore a problem of maximizing a concave function.

Definition 2.2. Let H be as above and ˆa ∈ Rⁿ⁻¹. A vector g ∈ Rⁿ⁻¹ is said to be a subgradient to H at ˆa if

H(ˆb) − H(ˆa) ≤ (g, ˆb − ˆa)

for all ˆb ∈ Rⁿ⁻¹. We let G(ˆa) denote the set of subgradients to H at ˆa.

Definition 2.3. Let H be as above and if G(ˆa) is a singleton, then this singleton is called the gradient to H at ˆa.

By definition, a gradient to H exists at ˆa if and only if there is a unique supporting hyperplane to H at ˆa. Thus we can take a remark that a^∗ is a maximum point of H if and only if 0 ∈ G(a^∗).

Since G(ˆa) is a compact convex set, it is uniquely determined by its extreme points. These extreme points are related to one-sided direc- tional derivatives as follows.

Proposition 2.4. [4] Let H be as above and ˆa ∈ Rⁿ⁻¹. For each d ∈ Rⁿ⁻¹

t→0lim⁺

H(ˆa + td) − H(ˆa)

t = H_d⁰(ˆa) exists. Furthermore,

H_d⁰(ˆa) = min{(g, d) : g ∈ G(ˆa)}.

As a consequence of proposition, the above definition of a gradient implies the existence of the partial derivatives to H at ˆa.

For any ˆa ∈ Rⁿ⁻¹, set Z(ˆa) = {x : (f_{j 0}− H(ˆa)s₁−

Xn i=2

a_is_i)(x) = 0 where h_{j 0}(ˆa) = H(ˆa)}.

By definition Z(ˆa) 6= φ for each ˆa ∈ Rⁿ⁻¹. For each x ∈ Z(ˆa), set g^x = (−s₂(x)/s₁(x), · · · , −s_n(x)/s₁(x)).

Let ˜G(ˆa) denote the convex hull of the set of vectors {g^x : x ∈ Z(ˆa)}.

Then the set ˜G(ˆa) is closed since Z(ˆa) are closed.

Theorem 2.5. The set ˜G(ˆa) is the set of subgradients to H at ˆa.

Proof. For each x ∈ Z(ˆa), there exists j ∈ {1, · · · , `} such that f_j(x) = H(ˆa)s₁(x) +

Xn i=2

a_is_i(x)

= h_j(ˆa)s₁(x) + Xn i=2

a_is_i(x).

By definition, that is f_j ≥ h_j(ˆb)s₁+P_n

i=2b_is_i, for each ˆb ∈ Rⁿ⁻¹, f_j(x) ≥ h_j(ˆb)s₁(x) +

Xn i=2

b_is_i(x)

≥ H(ˆb)s₁(x) + Xn

i=2

b_is_i(x).

Since s₁(x) ≥ 0,

H(ˆb) − H(ˆa) ≤ Xn

i=2

a_is_i(x) s₁(x)−

Xn i=2

b_is_i(x) s₁(x)

= Xn

i=2

(a_i− b_i)s_i(x) s₁(x)

= (g^x, ˆb − ˆa).

So g^x is a subgradient to H at ˆa, that is, ˜G(ˆa) ⊂ G(ˆa).

It remains to prove that all subgradients to H at ˆa are in ˜G(ˆa).

Suppose that ˜G(ˆa) 6= G(ˆa). Then ˜G(ˆa) ⊂ G(ˆa), and ˜G(ˆa), G(ˆa) are both convex and compact, there exists a g^∗ ∈ G(ˆa) and d ∈ Rⁿ⁻¹ for which

(g, d) > (g^∗, d) for all g ∈ ˜G(ˆa). Thus

min{(g, d) : g ∈ ˜G(ˆa)} > min{(g, d) : g ∈ G(ˆa)} = H_d⁰(ˆa).

If the strictly inequality will be equality, we have proved our result.

It suffices to prove that, for each d ∈ Rⁿ⁻¹, there exists a g ∈ ˜G(ˆa) for which

H_d⁰(ˆa) = lim

t→0⁺

H(ˆa + td) − H(ˆa)

t = (g, d).

We therefore calculate H_d⁰(ˆa). Set g(x) = f_{j 0}(x) −P_n

i=2a_is_i(x)

s₁(x) − H(ˆa)

and v_i(x) = ^s_sⁱ₁^(x)_(x), i = 2, · · · , n, where h_{j 0}(ˆa) = H(ˆa). Note that min{g(x) : x ∈ X} = 0.

Now, for each d ∈ Rⁿ⁻¹, H(ˆa + td) − H(ˆa)

t = 1

t[h_{j 0}(ˆa + td) − h_{j 0}(ˆa)]

= 1 t[min

x∈X

f_{j 0}(x) −P_n

i=2(a_i+ td_i)s_i(x)

s₁(x) −min

x∈X

f_{j 0}(x) −P_n

i=2a_is_i(x)

s₁(x) ]

= 1 t[min

x∈X

f_{j 0}(x) −P_n

i=2a_is_i(x) − tP_n

i=2d_is_i(x)

s₁(x) − H(ˆa)]

= 1 t min

x∈X[f_{j 0}(x) −P_n

i=2a_is_i(x)

s₁(x) − t

Xn i=2

d_iv_i(x) − H(ˆa)]

= 1 t min

x∈X{g(x) − t Xn i=2

d_iv_i(x)}.

For each x ∈ Z(ˆa), 1

t{g(x) − t Xn i=2

d_iv_i(x)} = − Xn

i=2

d_iv_i(x).

Thus

H_d⁰(ˆa) = lim

t→0⁺

H(ˆa + td) − H(ˆa)

t = lim

t→0⁺

1 t min

x∈X{g(x) − t Xn

i=2

d_iv_i(x)}

≤ min

x∈Z(ˆa)− Xn i=2

d_iv_i(x)

= min

x∈Z(ˆa)(g^x, d).

If equality holds, that is, for each d ∈ Rⁿ⁻¹, there exists a g ∈ ˜G(ˆa) for which

H_d⁰(ˆa) = min{(g^x, d) : g^x ∈ G(ˆa)}

= min{(g^x, d) : g^x∈ ˜G(ˆa)},

then by proposition 2.0.6., the proof is complete, that is, ˜G(ˆa) = G(ˆa).

We assume that equality does not hold. Set c^∗ = min

x∈Z(ˆa)− Xn

i=2

d_iv_i(x) = − max

x∈Z(ˆa)

Xn i=2

d_iv_i(x).

Assume that, there exists a δ > 0 such that H_d⁰(a) ≤ c^∗− δ.

Let t_k→ 0 and x_k ∈ X satisfy H_d⁰(ˆa) = lim

k→∞

1

t_k{g(x_k) − t_k Xn i=2

d_iv_i(x_k)} ≤ c^∗− δ.

Because the limit exists, it follows that

k→∞lim g(x_k) = 0.

Since X is compact, there exists a subsequence of the {x_k}, again de- noted by {x_k}, converging to some x^∗. Since g is continuous and therefore g(x^∗) = 0, i.e., x^∗ ∈ Z(ˆa).

The functionP_n

i=2d_iv_i is continuous and there exists a K₁ such that for all k ≥ K₁

| Xn

i=2

d_iv_i(x_k) − Xn

i=2

d_iv_i(x^∗)| < δ 2. Thus for k ≥ K₁

c^∗+ Xn

i=2

d_iv_i(x_k) = − max

x∈Z(ˆa)

Xn i=2

d_iv_i(x) + Xn i=2

d_iv_i(x_k)

≤ − Xn

i=2

d_iv_i(x^∗) + Xn

i=2

d_iv_i(x_k) < δ 2. There exists a K₂ such that for all k ≥ K₂

g(x_k) ≤ t_k{c^∗− δ 2+

Xn i=2

d_iv_i(x_k)}.

Thus, for all k ≥ max{K₁, K₂}, g(x_k) ≤ t_k{c^∗− δ

2+ Xn i=2

d_iv_i(x_k)} < 0.

Hence g(x) ≥ 0 for all x ∈ X. This contradiction proves the theorem.

As we have shown, the subgradients to H at ˆa are easily determined theoretically. We can apply any subgradient algorithm. Suffice it to say that convergence is generally very slow, at least in theory. This paper is concerned with algorithms for calculating best one-sided simultaneous approximations. And this algorithms will expand the algorithms for calculating best two-sided simultaneous approximations.

References

[1] L. Elsner, I. Koltracht and M. Neumann, Convergence of sequential and asyn- chronous nonlinear paracontractions, Numerische mathematik 62 (1992), 305- 319.

[2] S. H. Park and H. J. Rhee, Characterization of best simultaneous approximation for a compact set, Bull K. Math. Soc. 33 (1996), 435-444.

[3] S. H. Park and H.J. Rhee, One-sided best simultaneous L1-approximation, J.

K. Math. Soc. 33 (1996), 155-167.

[4] A. Pinkus, On L1-approximation, Cambridge Tracts in Mathematics, 93 Cam- bridge University Press, Cambridge-New York, 1989.

[5] H. J. Rhee , An algorithm of the one-sided best simultaneous approximation, K. Ann. Math. 24 (2007), 69-79.

[6] I. Singer , Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces, Springer-Verlag, New York, 1970.

*

Department of Mathematics Duksung Women’s University Seoul 132-714, Republic of Korea E-mail: rhj@duksung.ac.kr