In this paper, we show that the complementᏹ\Ᏺis not only of the first Baire category but also aσ-porous set

(1)

P. G. HOWLETT AND A. J. ZASLAVSKI Received 1 August 2003

We study the minimization problem f(x)→min,x∈C, where f belongs to a complete metric spaceᏹ of convex functions and the setCis a countable intersection of a de- creasing sequence of closed convex setsC_iin a reflexive Banach space. LetᏲbe the set of all f ∈ᏹfor which the solutions of the minimization problem over the setCicon- verge strongly asi→ ∞to the solution over the setC. In our recent work we show that the setᏲcontains an everywhere denseG_δ subset ofᏹ. In this paper, we show that the complementᏹ\Ᏺis not only of the first Baire category but also aσ-porous set.

1. Introduction

LetXbe a reflexive Banach space with the norm · and let C_∞=

∞ i=1

Ci= ∅, (1.1)

whereC_i+1⊂C_ifor eachi=1, 2,. . .and where eachC_iis a closed convex subset ofX. We study the minimization problem

f(x)−→min, x∈C_∞, (1.2)

where f belongs to a complete metric spaceᏹof convex functions defined onC1. In [8]

we show that for a generic function f ∈ᏹthe solutions of the minimization problem over the setCiconverge strongly asi→ ∞to the solution over the setC_∞.

When we say that a certain property holds for a generic element of a complete metric spaceYwe mean that the set of points which have this property contains aG_δeverywhere dense subset ofY. A setGis said to belong to the classGδif it can be expressed as a countable intersection of open sets. Such an approach, when a certain property is investigated for the whole spaceY, and not just for a single point inY, has already been successfully applied in many areas of analysis. We mention, for instance, the theory of dynamical sys- tems [5,13,15], optimization [3,7,8,9,11,12], variational analysis [1], approximation theory [6], the calculus of variations [2,4,9,18] and optimal control [19,20,21].

(2)

In this paper, we study the set of all functions f ∈ᏹfor which the solutions of the minimization problem over the setsC_iconverge strongly asi→ ∞to the solution of the minimization problem over the setC_∞. We show that the complement of this set is not only of the first Baire category but also aσ-porous set.

We now recall the concept of porosity [5,6,7,12].

Let (Y,d) be a complete metric space. We denote byBd(y,r) the closed ball of center y∈Y and radiusr >0. A subsetE⊂Y is called porous in (Y,d) if there existα∈(0, 1]

andr0>0 such that for eachr∈(0,r0] and eachy∈Y there existsz∈Yfor which

Bd(z,αr)⊂Bd(y,r)\E. (1.3)

Hence every ball under a certain size includes a smaller ball of fixed proportional size that is contained in the complement ofE.

Remark 1.1. In the above definition of porosity it is known that the point ycan be as- sumed to belong toE.

A subset of the spaceYis calledσ-porous in (Y,d) if it is a countable union of porous subsets in (Y,d).

Other notions of porosity have been used in the literature [16,17]. We use the rather strong notion which appears in [5,6,7,12].

Since porous sets are nowhere dense, allσ-porous sets are of the first category. That is, eachσ-porous set can be expressed as a countable union of nowhere dense subsets. IfY is a finite-dimensional Euclidean space, then allσ-porous sets are of Lebesgue measure zero. In fact, the class ofσ-porous sets in such a space is smaller than the class of sets which have measure zero and are of the first category [16]. Furthermore every complete metric space without isolated points contains a closed nowhere dense set which is not σ-porous [17].

To diﬀerentiate between porous and nowhere dense sets note that ifE⊂Y is nowhere dense,y∈Y, andr >0, then there is a pointz∈Yand a numbers >0 such thatBd(z,s)⊂ B_d(y,r)\E. If, however,Eis also porous, then for small enoughrwe can chooses=αr, whereα∈(0, 1) is a constant which depends only onE.

2. The main result

We use the convention that∞ − ∞ =0 and∞/∞ =1. LetXbe a reflexive Banach space with the norm · and let

C_∞=^∞

i=1

C_i= ∅, (2.1)

whereCi+1⊂Cifor eachi=1, 2,. . .and where eachCiis a closed convex subset ofX. Let ϕ:C1→R¹satisfy

ϕ(x)−→ ∞ asx −→ ∞. (2.2)

(3)

Denote byᏹthe set of all convex lower semicontinuous functions f :C1→R¹∪ {∞}

which are not identically infinity onC_∞and satisfy

f(x)≥ϕ(x) ∀x∈C1. (2.3)

For each f ∈ᏹand each nonempty setC⊂C1set

inf(f;C)=inff(x)|x∈C. (2.4) It is well known that for each f ∈ᏹand eachi∈ {1, 2,. . .} ∪ {∞}, the following minimization problem:

(P_i^f) f(x)→min,x∈Ci

has a solution. Denote byᏹ1the set of all finite-valued functions f ∈ᏹand byᏹ2the set of all finite-valued continuous functions f ∈ᏹ. Next we endow the setᏹwith a metricd. For each f,g∈ᏹand eachm∈N, we first set

dm(f,g)=supf(x)−g(x):x∈C1andx ≤m (2.5) and then define

d(f,g)= ∞ m=1

2⁻^mdm(f,g)dm(f,g) + 1⁻¹ (2.6) (see the convention at the start of this section). We adopt the convention that the supre- mum of the empty set is zero. Clearly (ᏹ,d) is a complete metric space. It is also not diﬃcult to see that the collection of sets

E(m,δ)=

(f,g)∈ᏹ×ᏹ|f(x)−g(x)≤δfor eachx∈C1satisfyingx ≤m, (2.7) wherem∈Nandδ >0, is a base for the uniformity generated by the metricd. Evidently ᏹ1andᏹ2are closed subsets of the metric space (ᏹ,d). In the sequel we assign to all these spaces the same metricd.

In [8] for a function f ∈ᏹ2we studied the convergence of solutions to the problem (P_i^f) for eachi=1, 2,. . .to a solution of the problem (P∞^f). IfX is a Hilbert space with inner product·,·and

f(x)= x,x forx∈X, (2.8)

then this convergence property was established by Semple [14]. A similar result was also obtained for certain Banach spaces and the distance function by Israel Jr. and Reich [10].

In [8] we showed that the convergence property holds for most functions f ∈ᏹ2. More precisely, we considered the metric space (ᏹ2,d) with

ϕ(x)=a1x −a2 forx∈C1, (2.9) wherea1anda2are positive numbers, and showed that there exists a subset ofᏹ2which is a countable intersection of open everywhere dense sets such that for each function

(4)

belonging to this subset the convergence property holds. Note that this result is true for reflexive Banach spaces but not necessarily for nonreflexive Banach spaces. For more in- formation consider [8, Examples 1 and 2].

In this paper for the spacesᏹ,ᏹ1, andᏹ2we show that the complements of subsets of functions which have the convergence property are not only of the first Baire category but are alsoσ-porous sets. We will establish the following result.

Theorem2.1. LetᏭbe eitherᏹ,ᏹ1, orᏹ2. There exists a setᏲ⊂Ꮽsuch that the com- plementᏭ\Ᏺisσ-porous in(Ꮽ,d)and such that for each f ∈Ᏺthe following properties hold.

(P1)There exists a unique pointxf ∈C_∞such that f(xf)=inf(f;C_∞).

(P2)For each i=1, 2,. . .,let xi∈Ci with f(xi)=inf(f;Ci). Then xi−xf →0 as i→ ∞.

(P3)For each>0there exist a neighborhoodUof f in(Ꮽ,d), a numberδ >0, and a natural numberpsuch that for eachg∈U, eachi∈ {p,p+ 1,. . .} ∪ {∞}, and each

y∈C_isatisfying

g(y)≤infg;Ci

+δ, (2.10)

the relationy−xf ≤also holds.

3. Auxiliary results We begin with a lemma.

Lemma3.1. Let f ∈ᏹandδ >0. Choosem=m(f)∈Nso that

z∈C1andϕ(z)≤inff;C_∞+ 1=⇒ z ≤m (3.1)

and defineU(m,δ)= {g∈ᏹ|(f,g)∈E(m,δ)}. Then for eachi∈ {1, 2,. . .} ∪ {∞}and eachg∈U(m,δ),

infg;C_i≤inff;C_i+δ. (3.2) Proof ofLemma 3.1. Leti∈ {1, 2,. . .} ∪ {∞}andz∈Ciwith f(z)≤inf(f;Ci) + 1. Since Ci⊂C1 and ϕ(z)≤ f(z)≤inf(f,Ci) + 1≤inf(f,C_∞) + 1 it follows thatz ≤m and hence that|f(z)−g(z)| ≤δ. Therefore for eachi∈ {1, 2,. . .} ∪ {∞},

infg;C_i≤infg(z)|z∈C_iand f(z)≤inff;C_i+ 1

≤inff(z) +δ|z∈Ciand f(z)≤inff;Ci

+ 1

≤inff(z)|z∈Ciand f(z)≤inff;Ci + 1+δ

≤inff;C_i+δ.

(3.3) The next proposition introduces a useful property.

(5)

Proposition 3.2. Let f ∈ᏹ. Suppose there exists a unique point x_f ∈C_∞ such that f(x_f)=inf(f;C_∞)and suppose that the following property holds.

(P4)For each >0there existδ=δ()>0and p=p()∈N such that for eachi∈ {p,p+ 1,. . .} ∪ {∞}and eachy∈Cisatisfyingf(y)≤inf(f;Ci) +δthe inequality y−x_f ≤is valid.

Then properties (P1), (P2), and (P3) also hold.

Proof ofProposition 3.2. Property (P1) holds by virtue of the first assumption. For each i=1, 2,. . ., we choosexi∈Ciwith f(xi)=inf(f;Ci). The truth of property (P4) clearly implies the truth of (P2). We will show that property (P3) also holds. Choose>0. By property (P4) there existδ∈(0, 1/2) andp∈Nsuch that if

i∈ {p,p+ 1,. . .} ∪ {∞}, y∈Ci, f(y)≤inff;Ci

+ 3δ, (3.4)

theny−x_f ≤. Choosem=m(f)∈Nand defineU=U(m,δ) as inLemma 3.1. Let i∈ {p,p+ 1,. . .} ∪ {∞}andg∈U. Assume thatz∈Ciwithg(z)≤inf(g;Ci) +δ. From Lemma 3.1it follows that

ϕ(z)≤g(z)≤infg;Ci

+δ≤inff;Ci

+ 2δ <inff;C_∞+ 1 (3.5) and hencez ≤mand|f(z)−g(z)| ≤δ. Since

f(z)≤g(z) +δ≤infg;C_i+ 2δ≤inff;C_i+ 3δ (3.6) it follows thatz−x_f ≤. Hence property (P3) is also true.

Lemma3.3. Let f ∈ᏹ. Then

limi→∞inff;C_i=inff;C_∞. (3.7) Lemma 3.3is similar to [8, Lemma 2.1]. The proof is also similar and is omitted.

4. Proof of the main result

It is convenient to split the proof into several smaller parts. We use the notationᏭto denote eitherᏹ,ᏹ1, orᏹ2.

Lemma4.1. For eachn∈NletᏲndenote the set of all f ∈Ꮽwith the following property.

(Q1)There existxn∈C_∞,δn>0, and pn∈Nsuch that fori∈ {pn,pn+ 1,. . .} ∪ {∞}

and eachy∈Ciwithf(y)≤inf(f;Ci) +δnthe inequalityy−xn ≤1/nis valid.

If f ∈Ᏺ=_∞

n=1Ᏺn, then properties (P1), (P2), and (P3) all hold.

Proof ofLemma 4.1. Letx_f ∈C_∞satisfyf(x_f)=inf(f;C_∞). By property (Q1) withi= ∞ andy=xf we know that

xf−xn≤1

n (4.1)

(6)

for alln∈N. Hencex_f =limn→∞x_n. Thereforex_f is the unique minimizer of f onC_∞. Let>0 andn∈Nbe such thatn >2/. For eachi∈ {p_n,p_n+ 1,. . .} ∪ {∞}and each y∈Ciwith f(y)≤inf(f;Ci) +δn, it follows from property (Q1) that

y−x_n≤1

n. (4.2)

Hencey−xf ≤. Thus property (P4) is valid and hence also properties (P1), (P2), and

(P3).

Remark 4.2. To complete the proof ofTheorem 2.1, we need to show thatᏭ\Ᏺisσ- porous in (Ꮽ,d). SinceᏭ\Ᏺ=_∞

n=1(Ꮽ\Ᏺn) it is suﬃcient to show that the setᏭ\Ᏺn

isσ-porous in (Ꮽ,d) for anyn∈N. For eachm∈Ndenote byEmthe subset of all f ∈Ꮽ with the following property.

(Q2) Ifx∈C1andϕ(x)≤inf(f;C_∞) + 1, thenx ≤m.

Since^∞_m₌₁Em=ᏭandᏭ\Ᏺn=_∞

m=1(Em\Ᏺn) it is suﬃcient to show that for each m,n∈Nthe setE_m\Ᏺnis porous in (Ꮽ,d).

Lemma4.3. Letm∈Nand suppose f ∈E_m. Letx_f ∈C_∞with f(x_f)=inf(f;C_∞). If

fγ(x)= f(x) +γx−xf (4.3)

is defined for eachγ >0and allx∈C1, thenf_γ∈Ꮽandd(f_γ,f)≤γ.

Proof ofLemma 4.3. Clearly f_γ∈Ꮽ. We will estimated(f_γ,f). Since ϕxf

≤fxf

=inff;C_∞ (4.4)

it follows from property (Q2) thatx_f_≤m. For eachk₌1, 2,. . .we have dk

fγ,f=supfγ(x)−f(x)|x∈C1andx ≤k

=supγx−xf|x∈C1andx ≤k

≤γsupx+xf|x∈C1andx ≤k

≤γ(m+k)

(4.5)

and hence

dfγ,f≤ ∞ k=1

2⁻^kγ(m+k)γ(m+k) + 1⁻¹≤γ ∞ k=1

2⁻^k=γ. (4.6) Lemma4.4. Letm,n∈N. Choose a real numberr with0< r≤1 and choose real num- bersγ=γ(r)=(1−1/2^m+3)randθ=θ(r,m,n)=r/(2^m+4n). If f ∈E_m andg∈Ꮽwith d(g,fγ)≤θ, theng∈Ᏺnandd(g,f)< r.

Proof ofLemma 4.4. Let f ∈Em,g∈Ꮽ, and d(g,fγ)≤θ. Then by elementary algebra we can show that dm(g,fγ)≤2^m+1θ. If x∈Ci and ϕ(x)≤inf(f;Ci) + 1, then ϕ(x)≤ inf(f;C_∞) + 1 and since f ∈E_mit follows thatx ≤m. Hence

g(x)−fγ(x)≤2^m+1θ. (4.7)

(7)

Note also that ify∈C_i and f_γ(y)≤inf(f_γ;C_i) + 1, thenϕ(y)≤ f_γ(y)≤inf(f_γ;C_i) + 1≤inf(f_γ;C_∞) + 1 and since inf(f_γ;C_∞)= f_γ(x_f)= f(x_f)=inf(f;C_∞) it follows that ϕ(y)≤inf(f;C_∞) + 1. Since f ∈Emwe deduce thaty ≤mand hence also that

g(y)−fγ(y)≤2^m+1θ. (4.8)

Since this holds for any suchy, we obtain infg;Ci

≤inffγ;Ci

+ 2^m+1θ. (4.9)

Assume that z∈Ci and g(z)≤inf(g;Ci) + 2^m+1θ then ϕ(z)≤g(z)≤inf(g;Ci) + 2^m+1θ≤inf(fγ;Ci) + 2^m+2θ <inf(fγ;C_∞) + 1=inf(f;C_∞) + 1. Hencez ≤mand

g(z)−fγ(z)≤2^m+1θ. (4.10)

We can now deduce that fγ(z)≤g(z) + 2^m+1θ≤inf(g;Ci) + 2^m+2θ≤inf(fγ;Ci) + 3.2^m+1θ

≤inf(f,C_∞) + 3.2^m+1θ. If we choosepso large that inf(f;Ci)≥inf(f,C_∞)−2^m+1θwhen i∈ {p,p+ 1,. . .} ∪ {∞}, then

f_γ(z)≤inff,C_i+ 2^m+3θ≤ f(z) + 2^m+3θ (4.11) and hence

z−xf≤2^m+3θ γ ^≤

1

n. (4.12)

Sincez∈Ciandg(z)≤inf(g;Ci) + 2^m+1θfori∈ {p,p+ 1,. . .} ∪ {∞}implies thatz− x_f ≤1/n, we have shown thatg∈Ᏺn. Finally we note thatd(g,f)≤d(g,f_γ) +d(f_γ,f)≤

θ+γ < r.

We can now complete the proof of the main result.

Proof ofTheorem 2.1. InRemark 4.2, we observed that the proof ofTheorem 2.1would be complete if we could show that for eachm,n∈Nthe setEm\Ᏺnis porous in (Ꮽ,d).

Let f ∈E_m\Ᏺn. Choose any real numberr with 0< r≤1 and choose real numbers γ=γ(r) andθ=θ(r,m,n) as inLemma 4.4. If we defineα=α(m,n) by the formula

α= 1

2^m+4n, (4.13)

thenθ=αrand for eachrwith 0< r≤1 we can see fromLemma 4.4that g∈Ꮽ|dg,fγ

≤αr⊂

g∈Ꮽ|d(g,f)≤r∩Ᏺn. (4.14) Hence each suﬃciently small ballBd(f,r)⊂(Ꮽ,d) centred at a point f ∈Em\Ᏺncon- tains a smaller ballBd(fγ,αr) of fixed proportional radius centred at the point fγand lying entirely withinᏲn. HenceE_m\Ᏺnis porous in (Ꮽ,d). This completes the proof.

(8)

References

[1] E. Asplund,Fr´echet diﬀerentiability of convex functions, Acta Math.121(1968), 31–47.

[2] J. M. Ball and N. S. Nadirashvili,Universal singular sets for the one-dimensional variational prob- lems, Calc. Var. Partial Diﬀerential Equations1(1993), no. 4, 429–438.

[3] G. Beer and R. Lucchetti,Convex optimization and the epi-distance topology, Trans. Amer. Math.

Soc.327(1991), no. 2, 795–813.

[4] A. Cellina and C. Mariconda,The existence question in the calculus of variations: a density result, Proc. Amer. Math. Soc.120(1994), no. 4, 1145–1150.

[5] F. S. De Blasi and J. Myjak,Sur la porosit´e de l’ensemble des contractions sans point fixe, C. R.

Acad. Sci. Paris S´er. I Math.308(1989), no. 2, 51–54 (French).

[6] ,On a generalized best approximation problem, J. Approx. Theory94(1998), no. 1, 54–

72.

[7] R. Deville and J. P. Revalski,Porosity of ill-posed problems, Proc. Amer. Math. Soc.128(2000), no. 4, 1117–1124.

[8] P. G. Howlett and A. J. Zaslavski,On the minimization of convex functions in reflexive Banach spaces, Commun. Appl. Anal.5(2001), no. 4, 535–545.

[9] A. D. Ioﬀe and A. J. Zaslavski,Variational principles and well-posedness in optimization and calculus of variations, SIAM J. Control Optim.38(2000), no. 2, 566–581.

[10] M. M. Israel Jr. and S. Reich,Extension and selection problems for nonlinear semigroups in Ba- nach spaces, Math. Japon.28(1983), no. 1, 1–8.

[11] S. Reich and A. J. Zaslavski,Generic convergence of descent methods in Banach spaces, Math.

Oper. Res.25(2000), no. 2, 231–242.

[12] ,The set of divergent descent methods in a Banach space isσ-porous, SIAM J. Optim.11 (2001), no. 4, 1003–1018.

[13] ,The set of noncontractive mappings isσ-porous in the space of all nonexpansive map- pings, C. R. Acad. Sci. Paris S´er. I Math.333(2001), no. 6, 539–544.

[14] J. Semple,Infinite positive-definite quadratic programming in a Hilbert space, J. Optim. Theory Appl.88(1996), no. 3, 743–749.

[15] G. Vidossich,Most of the successive approximations do converge, J. Math. Anal. Appl.45(1974), 127–131.

[16] L. Zaj´ıˇcek,Porosity andσ-porosity, Real Anal. Exchange13(1987/1988), no. 2, 314–350.

[17] , Small non-σ-porous sets in topologically complete metric spaces, Colloq. Math. 77 (1998), no. 2, 293–304.

[18] A. J. Zaslavski,Dynamic properties of optimal solutions of variational problems, Nonlinear Anal.

27(1996), no. 8, 895–931.

[19] , Generic well-posedness of optimal control problems without convexity assumptions, SIAM J. Control Optim.39(2000), no. 1, 250–280.

[20] ,Existence of solutions of optimal control problems for a generic integrand without con- vexity assumptions, Nonlinear Anal. Ser. A: Theory Methods43(2001), no. 3, 339–361.

[21] ,Well-posedness and porosity in optimal control without convexity assumptions, Calc. Var.

Partial Diﬀerential Equations13(2001), no. 3, 265–293.

P. G. Howlett: Centre for Industrial and Applied Mathematics (CIAM), University of South Aus- tralia, Mawson Lakes, SA 5059, Australia

E-mail address:[email protected]

A. J. Zaslavski: Department of Mathematics, Technion – Israel Technology Institute, Haifa 32000, Israel

E-mail address:[email protected]