# A New Nonsmooth Bundle-Type Approach for a Class of Functional Equations in Hilbert Spaces

Authors: Jie Shen; Miao Tian; Fang-Fang Guo; Jun-Nan Zhang
Journal: Journal of Function Spaces
 (2017)

---

## Abstract

A new bundle-type approach for solving a class of functional equations is presented by combining bundle idea for nonsmooth optimization with common iterative process for functional equations. Our strategy is to approximate the nonsmooth function in functional equation by a sequence of convex piecewise linear functions, as in the bundle method; this makes the problem more tractable and reduces the difficulty of implementation of method. We only require the piecewise linear convex approximate functions, rather than the actual function, to satisfy the uniform boundedness condition with respect to one variable at stability centers. One example is given to demonstrate the application of the proposed method.


---

## Body

## 1. Introduction

Theory of functional equations is a branch of mathematics, whose significance lies not only in its vast applications in a number of other branches of mathematics, but also in many practical problems of natural sciences and engineering, for example, economy and information theory. Consider the following functional equation arising from dynamic programming of multistage decision process:(1)fx=infy∈D⁡ux,y+inf⁡vx,y,pix,y+qix,yfaix,y∣i=1,2,3,∀x∈S,where x and y stand for state and decision vectors, respectively, H is a Hilbert space with norm · induced by its inner product ·,·. S⊂H, D⊂H, and u:S×D→R+, v,pj,qj:S×D→R, j=1,2,3, aj:S×D→S, j=1,2,3, represent the transformation of the process, and f:S→R denotes the optimal return function with initial state x. It is well known that many practical problems can be formulated as problem (1). The authors [1] establish the existence, uniqueness, and iterative approximation to solutions for problem (1) in Banach spaces and complete metric space, respectively, and it extends, improves, and generalizes the results due to several authors [2–4]. However, the construction of iterative approximation to solutions for problem (1) needs uniform boundedness of ux,y with respect to y on the whole space S×D, and this requirement is too strong and difficult to be realized in some cases. So it is worth studying more easier conditions and methods for solving problem (1).Bundle method is among the most efficient methods for nonsmooth optimization problems and plays an important role in variational inequalities as well [5–7]. The minimization of a nonsmooth lower semicontinuous proper convex function, which is maybe very hard to solve, can be replaced by minimizing a sequence of more tractable convex functions; see [8–10]. The key strategy is to approximate the actual function by a sequence of piecewise linear convex functions, that is, the so-called cutting planes method, the predecessor of bundle method introduced by Lemaréchal [11]. Bundle methods have been successfully used in many practical applications.Thus it appears reasonable to claim that functional equations with nonsmooth functions can benefit from bundle methods. We try to combine bundle idea with classical iterative process [1] in order to approximate the solutions for problem (1) in complete metric space BBS. It is the first time that bundle idea is introduced to functional equations. The result obtained in this paper is quite different from the one in [1] in the way of constructing the iterative sequence which converges to the solution to problem (1). The generation of sequence wnn≥0 relies on the previous iteration term wn-1 and the approximation function un-1, which relaxes the strong conditions imposed on u itself. And at the same time, the requirement imposed on the corresponding functions is weaker than that in [1]: instead of requiring ux,y to be uniformly bounded with respect to y∈D for all x∈S, we only require the piecewise linear convex approximations uix,y, i=0,1,…, constructed in this paper to possess this property at some special points, that is, at stability centers defined below. It is not difficult to be realized.The rest of this paper is organized as follows. In Section2 we review some basic notations and results. Section 3 presents the concrete iteration approximation sequence wnn≥0 which converges to the unique solution for (1). One example is provided to show the validity of the results.


## 2. Preliminaries and Notations

The following notation is adopted throughout the paper:R=-∞,+∞, R+=0,+∞, R-=-∞,0. For all t, t denotes the largest integer not exceeding t and H is a Hilbert space with inner product ·, its norm ∥·∥ is induced by its inner product, and H is also a Banach space. S⊂H is the state space; D⊂H is the decision space. Define (2)Φ1=φ∣φ:R+⟶R+isnondecreasing;Φ2=φ∣φ:R+⟶R+,∑n=0∞φnt<∞fort>0;Φ3=φ,ψ∣φ,ψ∈Φ1,ψt>0,∑n=0∞ψφnt<∞fort>0;BBS=f:f:S⟶RisboundedonboundedsubsetsofS. For any positive integer k and f,g∈BBS, define(3)dkf,g=sup⁡fx-gx∣x∈B¯0,k,df,g=∑k=1∞12k·dkf,g1+dkf,g,where B¯0,k={x∈S∣x≤k}. A sequence xnn≥0 in BBS is said to converge to a point in BBS if for any k≥1, dkxm,xn→0 as n,m→∞. It is clear that BBS,d is a complete metric space.


## 3. Solutions for Functional Equation (1) via Bundle Method

Suppose the functionu:S×D→R+ in problem (1) is a nonsmooth lower semicontinuous proper convex function. Construct the following approximate functions unx,y to ux,y:(4)unx,y=maxi∈In=0,1,2,…,n⁡ux,yi+si,y-yi,x,y∈S×D,n=0,1,2,…,where yi∈D, si∈∂yux,yi, i=0,1,2,…,n, and ∂yux,yi={y∗∣ux,y≥ux,yi+y∗,y-yi,∀y} denotes the partial subdifferential of ux,y with respect to y at yi. Define the linearization error of u with respect to y at x,yn to be (5)0≤ei=ux,yn-ux,yi-si,yn-yi,i=1,2,…,n;unx,y can be written equivalently in the form (6)unx,y=ux,yn+maxi∈In⁡-ei+si,y-yn,x,y∈S×D,n=0,1,2,…. It is easy to prove the following three properties of the approximate functions unx,y:P1
un+1x,y≥unx,y,forallx,y∈S×D,n=0,1,2,….P2
unx,y→ux,yasn→∞,forallx,y∈S×D.P3
unx,y≤ux,y,forallx,y∈S×D,n=0,1,2,….Next we present a bundle algorithm which produces two sequencesy¯n and yn; the sequence yn is called the candidate point sequence; it is used to construct and improve the approximate functions unx,y, and the sequence y¯n consists of the candidate points yn that decrease sufficiently the function ux,y in the sense of the descent test given below, and we call y¯n stability centers. Note that y¯n is a subsequence of yn. These two sequences will be employed to provide the conditions that assure the existence and uniqueness of solutions to problem (1).Algorithm 1.
Step
1 (initialization). Let m∈0,1 and μmax be given parameters. Choose μ0≤μmax,y0∈D and x∈S; compute ux,y0 and s0∈∂yux,y0. Construct the model u0x,y (see (4)). Set y¯0=y0, k=0, and δ0=∞.
Step
2(computation of candidate point). Compute (7)yn+1∈arg⁡miny∈D⁡unx,y+μn2y-y¯n2.
Defineδn+1=ux,y¯n-unx,yn+1+μn/2yn+1-y¯n2.
Step
3(descent test). If ux,y¯n-ux,yn+1≥mδn+1, set y¯n+1=yn+1 (descent step); otherwise, set y¯n+1=y¯n (null step).
Step
4(improving the model). Append yn+1 to model (4); that is, construct un+1x,y again. Choose μn+1≥μn such that μn+1≤μmax. Change n to n+1; go to Step 2.Remark 2.
According to [12], the sequence y¯n is bounded and converges to y¯ if Algorithm 1 generates infinitely many descent steps, where y¯ satisfies ux,y¯=miny∈Dux,y for given x∈S. Otherwise, Algorithm 1 generates a last descent step y¯nlast, followed by infinitely many null steps; then yn converges to y¯nlast and y¯nlast minimizes ux,y with respect to y∈D for given x∈S.Remark 3.
As the constructions ofunx,y go along, the number of elements in bundle In increases. We clean and compress the bundle by employing “aggregation technique” to control the size of bundle without impairing the original properties of global convergence. Suppose the bundle In has pn couples si,ei; we call indispensable couples (resp., dispensable) the pairs si,ei in the bundle In corresponding to active (resp., inactive) indices, that is, to i such that α¯i>0 (resp., α¯i=0); here, for i∈In, α¯i is the optimal multiplier associated with yn+1 in Step 2 of Algorithm 1. When the number pn becomes too big, the following steps are executed:(i)
It selects the dispensable couples, which can be discarded.(ii)
If the remaining couples are still too many, compress the indispensable information into a single couple∑i=1pnα¯isi‍,∑i=1pnα¯iei‍. The corresponding affine function is called aggregate linearization: (8)uax,y=ux,yn-∑i=1pnα¯iei+∑i=1pnα¯isi,y-yn. Obviously, ux,y≥uax,y. The synthetic couple ∑i=1pnα¯isi‍,∑i=1pnα¯iei‍ is added to the new bundle In+1 for keeping the information of the discarded indispensable couples since it summaries all the information generated up to n.
Now we are ready to present our main results of this article.Theorem 4.
Letu:S×D→R+,v,pj,qj:S×D→R, aj:S×S→S for j=1,2,3 be mappings, let r be in Φ1∩Φ2 and r,ψ be in Φ3, unx,y is given by (4), and sequences ynn=0∞ and y¯nn=o∞ are generated by Algorithm 1. Suppose the following conditions are satisfied:
C
1  For all x,y∈S×D, unx,y≥0, n=0,1,2,….
C
2  uix,y¯i≤x,i=0,1,2; uix,y¯i≤r2i-1x,i≥3, for all x∈S.
C
3  ux,y¯i≤ψx, vx,y¯i≤ψx,pjx,y¯i≤ψx,j=1,2,3,i=0,1,2,… for all x∈S.
C
4  max⁡ajx,y¯i∣j=1,2,3≤rx, for all x∈S, i=0,1,2,….
C
5  max⁡qjx,y∣j=1,2,3≤1, for all x,y∈S×D.
Then the functional equation (1) possesses a solution w∈BBS that satisfies the following conditions.
C
6  The sequence wnx defined by (9)w0x=infy∈D⁡u0x,y+inf⁡vx,y,pjx,y∣j=1,2,3,x∈S;wnx=infy∈D⁡un-1x,y+inf⁡vx,y,pjx,y+qjx,ywn-1ajx,y∣j=1,2,3,x∈S,n≥1, converges to w.
C
7  For given x0∈S, the sequence y~n⊂D is generated by Algorithm 1; take xn∈{ajxn-1,y~n∣j=1,2,3}, n∈N, then limn→∞⁡wxn=0.
C
8  w is unique with respect to condition C7.Proof.
Sincer,ψ is in Φ3, it is easy to see that(10)rt<t,fort>0.Given u·,·, for each h∈BBS, Hu is defined by(11)Huhx=infy∈D⁡ux,y+inf⁡vx,y,pjx,y+qjx,y·hajx,y∣j=1,2,3.According to C4, we have(12)max⁡ajx,y¯i∣j=1,2,3≤rx≤k,∀x∈B¯0,k,i=0,1,2,…,which implies that there exists a constant θk,h>0 with(13)maxhajx,y¯i∣j=1,2,3≤θk,h,∀x∈B¯0,k,i=0,1,2,….By virtue of our assumptions, (11), (12), and (13), we deduce that (14)Huhx≤ux,y¯i+inf⁡vx,y¯i,pjx,y¯i+qjx,y¯i·hajx,y¯i∣j=1,2,3≤ψk+max⁡ψk,ψk+θk,h≤2ψk+θk,h,∀x∈B-0,k,i=0,1,2,…. Thus, Hu is a self-mapping on BBS for given u.
Givenu·,·, for k≥1, x∈B¯,0,k, ε>0, and h,g∈BBS, there exist y,z∈D satisfying (15)Huhx≤ux,y+inf⁡vx,y,pjx,y+qjx,y·hajx,y∣j=1,2,3,Hugx≤ux,z+inf⁡vx,z,pjx,z+qjx,z·gajx,z∣j=1,2,3,Hugx>ux,y+inf⁡vx,y,pjx,y+qjx,y·gajx,y∣j=1,2,3-ε,Huhx>ux,z+inf⁡vx,z,pjx,z+qjx,z·hajx,z∣j=1,2,3-ε. In terms of the above inequalities and C5, we get (16)Huhx-Hugx≤max⁡max⁡qjx,y·hajx,y-gajx,y∣j=1,2,3,max⁡qjx,z·hajx,z-gajx,z∣j=1,2,3+ε≤max⁡hajx,y-gajx,y,hajx,z-gajx,z∣j=1,2,3+ε, which means that (17)Huhx-Hugx≤dkh,g+ε,∀h,g∈BBS. It follows that (18)dkHuh,Hug≤dkh,g+ε,∀h,g∈BBS. As ε↓0, we have dkHuh,Hug≤dkh,g. Furthermore, we obtain (19)dHuh,Hug=∑k=1∞12kdkHuh,Hug1+dkHuh,Hug≤∑k=1∞12kdkh,g1+dkh,g=dh,g. That is to say, Hu is nonexpansive for given u·,·; therefore, Hu is continuous for given ux,y.
Next, we assert that forn=0,1,2,3(20)wnx≤∑j=0nrjx+∑j=0nψrjx, and for n≥4(21)wnx≤∑j=n-32n-3rjx+∑j=0nψrjx. By definitions of w0x and w1x, we have (22)w0x≤u0x,y¯0inf⁡vx,y¯0,pjx,y¯0∣j=1,2,3≤x+ψx,∀x∈S,w1x≤u0x,y¯0+inf⁡vx,y¯0,pjx,y¯0+qjx,y¯0·w0ajx,y¯0∣j=1,2,3≤x+ψx+max⁡ajx,y¯0+ψajx,y¯0∣j=1,2,3≤x+r1x+ψx+ψrx,∀x∈S,=∑j=01rjx+∑j=01ψrjx,∀x∈S.Similarly, (20) holds for n=2 and n=3. For w4x, it follows from C2–C5 that (23)w4x≤u3x,y¯3+inf⁡vx,y¯3,pjx,y¯3+qjx,y¯3·w3ajx,y¯3∣j=1,2,3≤r5x+ψx+max⁡∑j=03rjaix,y¯3+∑j=03ψrjaix,y¯3∣i=1,2,3≤∑j=15rjx+∑j=04ψrjx,∀x∈S. Suppose that, for kk≥4, it holds that wkx≤∑j=k-32k-3rj‍x+∑j=0kψ‍rjx; then, for k+1, we have from C2–C5 that (24)wk+1x≤ukx,y¯k+inf⁡vx,y¯k,pjx,y¯k+qjx,y¯k·wkajx,y¯k∣j=1,2,3≤r2k-1x+ψx+max⁡∑j=k-32k-3rjaix,y¯k+∑j=0kψrjaix,y¯k∣i=1,2,3≤r2k-1x+ψx+∑j=k-22k-2rjx+∑j=1k+1ψrjx≤∑j=k-22k+1-3rjx+∑j=0k+1ψrjx,∀x∈S. Hence (21) holds for k+1. According to mathematical induction, (21) holds for n≥4.
Next we claim thatwnn≥0 is a Cauchy sequence in BBS. For k≥1, x0∈B¯0,k, ε>0, and n,m∈N, there exist y,z∈D satisfying (25)wnx0≤un-1x0,y+inf⁡vx0,y,pjx0,y+qjx0,y·wn-1ajx0,y∣j=1,2,3,wnx0≤un-1x0,z+inf⁡vx0,z,pjx0,z+qjx0,z·wn-1ajx0,z∣j=1,2,3,wm+nx0>um+n-1x0,y+inf⁡vx0,y,pjx0,y+qjx0,y·wm+n-1ajx0,y∣j=1,2,3-ε2,wm+nx0>um+n-1x0,z+inf⁡vx0,z,pjx0,z+qjx0,z·wm+n-1ajx0,z∣j=1,2,3-ε2. According to B5 and the above four inequalities, we have(26)wnx0-wm+nx0≤un-1x0,y-um+n-1x0,y+max⁡qjx0,y·wn-1ajx0,y-wm+n-1ajx0,y∣j=1,2,3+ε2,(27)wm+nx0-wnx0≥um+n-1x0,z-un-1x0,z-max⁡qjx0,z·wm+n-1ajx0,z-wn-1ajx0,z∣j=1,2,3-ε2.Combining (26) with (27), and noting property P1, we obtain(28)wm+nx0-wnx0≤max⁡um+n-1x0,z-un-1x0,z,um+n-1x0,y-un-1x0,y+max⁡wm+n-1ajx0,z-wn-1ajx0,z,wm+n-1ajx0,y-wn-1ajx0,y∣j=1,2,3+ε2=um+n-1x0,z~1-un-1x0,z~1+wm+n-1x1-wn-1x1+ε2,where y~1,z~1∈y,z, x1∈ajx0,y~1∣j=1,2,3. Proceeding in this way, we can choose y~j,z~j∈y,z, xj∈aixj-1,y~j∣i=1,2,3, such that for j=1,2,3,…(29)wm+n-1x1-wn-1x1≤um+n-2x0,z~2-un-2x0,z~2+wm+n-2x2-wn-2x2+ε22,wm+n-2x2-wn-2x2≤um+n-3x0,z~3-un-3x0,z~3+wm+n-3x3-wn-3x3+ε23,⋮wm+1xn-1-w1xn-1≤umx0,z~n-u0x0,z~n+wmxn-w0xn+ε2n.It follows from C1, C4, P1, (10), (21), (28), and (29) that(30)wm+nx0-wnx0≤wmxn-w0xn+∑i=1nε2i+∑i=0n-1um+ix0,z~n-i-uix0,z~n-i≤wmxn+w0xn+ε+∑i=0n-1um+ix0,z~n-i≤∑j=m-32m-3rjxn+∑j=0mψrjxn+xn+ψxn+ε+∑i=0n-1r2m+i-1x0≤∑j=n-1m+nψrjk+∑j=m+n-32m+n-3rjk+∑j=2m-12m+n-2r2jk+rnk+ε,which implies that(31)dkwm+n,wn≤∑j=n-1m+nψrjk+∑j=m+n-32m+n-3rjk+∑j=2m-12m+n-2r2jk+rnk+ε.As ε↓0, we deduce that(32)dkwm+n,wn≤∑j=n-1m+nψrjk+∑j=m+n-32m+n-3rjk+∑j=2m-12m+n-2r2jk+rnk.Since ∑i=0∞ψ‍rit<∞, ∑i=0∞ri‍t<∞ for each t>0, the four terms on the right-hand side of (32) can be arbitrarily small when n and m are large sufficiently. It means that, for any ε¯>0, there exists N¯; when m>n>N¯, we have dkwm+n,wn≤ε¯. Therefore wnn≥0 is a Cauchy sequence in BBS,d. Suppose wnn≥0 converges to w∈BBS; note that Hu is nonexpansive for given u and the definition of wn; we have wn+1=Hunwn. So it is easy to obtain (33)dw,Huw≤dw,Hunwn+dHunwn,Hunw+dHunw,Huw≤dw,wn+1+dwn,w+dHunw,Huw. It follows from P2 that Hunw→Huw as n→∞. Therefore, Huw=w; that is to say, the functional equation (1) possesses one solution w in BBS,d.
For anyε>0, given x0∈S, the sequence y~jj≥1 is generated by Algorithm 1; take xj∈{aixj-1,y~j∣i=1,2,3}, j≥1. Let k=x0+1; there exists a positive integer m such that(34)dkw,wn+∑j=2n-33n-3rjk+∑j=n2nψrjk<ε,forn>m.By virtue of C4, (21), and (34), we infer that (35)wxn≤wxn-wnxn+wnxn≤dkw,wn+∑j=n-32n-3rjxn+∑j=0nψrjxn≤dkw,wn+∑j=2n-33n-3rjx0+∑j=n2nψrjx0≤dkw,wn+∑j=2n-33n-3rjk+∑j=n2nψrjk≤ε, which means limn→∞wxn=0.
The last conclusionC8 is quite similar to Theorem  10 in [1], so we omit the proof.Remark 5.
By comparing with [1] we find that during the process of constructing the iterative sequence which converges to the unique solution for (1), the approximate functions unx,u to ux,y and the sequence y¯i of descent steps are employed so that we can relax the conditions on ux,y by only requiring unx,u to satisfy the uniform boundedness condition at stability centers y¯i instead of ux,y itself on the whole space S×D. The introduction of approximate functions unx,y makes problem (1) easier to solve since it is a piecewise linear convex function and is not hard to satisfy uniform boundedness condition. Besides that, the functions vx,y and pjx,y,j=1,2,3, are only required to be uniformly bounded at stability centers for x∈S, not on the whole space S×D, which is another difference between [1] and our algorithm.Example 6.
SupposeX=Y=R, S=D=1,+∞, ψt=4t4, and rt=t/2 for all t∈R+. Consider the following functional equation: (36)fx=inf⁡x21+x2y2hhhhhhhhh+inf⁡x31+sin2⁡x+2y+3,2x31+x+yhhhhhhhhhhhhhhh+sin2⁡x+2yfx21+x2y2,hhhhhhhhhhhhhhhx8x5+cos2⁡x+2y+1hhhhhhhhhhhhhhh+11+xyfx31+x4+y4,hhhhhhhhhhhhhhhx41+xy+cos2⁡x+y3hhhhhhhhhhhhhhh·fxsin2⁡x+2y2+xy2,x∈S. It is easy to verify that the conditions C1,C3,C4, and C5 of Theorem 4 are satisfied. Now let us see C2; note that ∂u/∂y=-2x4y/1+x2y22; take y≥y0≥1; it follows from the definition of u0x,y that (37)u0x,y=ux,y0+s0,y-y0=x21+x2y02+-2x4y01+x2y022,y-y0=x2+3x4y02-2x4yy01+x2y022≤x21+x2y02≤x21+x2≤x22x=x2≤x. Similarly, if we take y≥yi≥1, i=0,1,2, it can be proved that u1x,y≤x,u2x,y≤x. For u3x,y=max0≤i≤3ux,yi+si,y-yi, if we take y≥yi≥24, i=0,1,2,3, then we can obtain u3x,y≤r5x=x/25, which is just the case for i=3 in C2. By imitating the above process, we have the following conclusion: if we take y≥yj≥22i-2, j=0,1,2,…,i, it holds that uix,y≤r2i-1x=x/22i-1, i≥3. In other words, if we choose yi to be a sequence such that it approaches infinity as i→∞, the conditions C2 in Theorem 4 are also satisfied. Therefore, this functional equation possesses a unique solution w∈BBS,d.



---

*Source: 3941084-2017-08-08.xml*