# A Moment Problem for Discrete Nonpositive Measures on a Finite Interval

Authors: M. U. Kalmykov; S. P. Sidorov
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

We will estimate the upper and the lower bounds of the integral∫01Ω(t)dμ(t), where μ runs over all discrete measures, positive on some cones of
generalized convex functions, and satisfying certain moment conditions with respect
to a given Chebyshev system. Then we apply these estimations to find the error of
optimal shape-preserving interpolation.


---

## Body

## 1. Introduction

Let{u0,…,uk} be a Chebyshev system on [0, 1]. A function f, defined on [0, 1], is said to be convex relative to the system{u0,…,uk} (we will write f∈C(u0,…,uk)) if
(1.1)|u0(t0)u0(t1)⋯u0(tk+1)⋯⋯⋯⋯uk(t0)uk(t1)⋯uk(tk+1)f(t0)f(t1)⋯f(tk+1)|≥0
for all choices of 0<t0<t1<⋯<tk+1<1.In particular, ifu0(x)≡1, then C(u0) is a cone of all increasing functions on (0, 1). If u0(x)≡1, u1(x)≡x, then C(u0,u1) is a cone of all convex functions on (0, 1). The review of some results of the theory of generalized convex functions can be found in the book in [1].Letk≥0, σ=(σ0,…,σk)∈ℝk+1 with σi∈{-1,0,1}, σ0,σk≠0. As usual, ℝ denotes the set of real numbers, and ℝn denotes the vector space of all real n-tuples (columns).Denote byWl+1 the set of all continuous functions defined on [0, 1] and convex relative to the system {u0,…,ul}, that is,(1.2)Wl+1∶={f∈C[0,1]:f∈C(u0,…,ul)},l=0,…,k-1.
Denote W0:={f∈ℂ[0,1]:f≥0}. Following ideas of [2] we consider the cone(1.3)W0,k(σ)=⋂l=0kσlWl.
For example, if k=2, σ=(1,0,1), u0(x)≡1, u1(x)≡x, then W0,2(σ) is the cone of all positive and convex continuous functions defined on [0, 1].Let0≤x1<x2<⋯<xn≤1, and denote Ig=(g(x1),…,g(xn))T∈ℝn, g∈ℂ[0,1]. Let(1.4)V0,k(σ)∶={If∈Rn:f∈W0,k(σ)}.
Denote by(1.5)V0,k*(σ):={μ∈Rn:(If)Tμ≥0∀If∈V0,k(σ)}
the dual cone.Let{f0,…,fp} be a Chebyshev system on [0, 1]. Let us consider the moment space with respect to the system {f0,…,fp} defined by(1.6)Mp+1,k(σ)∶={c=(c0,…,cp)∈Rp+1:(Ifi)Tμ=ci,i=0,…,p},
where μ runs over V0,k*(σ).Givenc0=(c00,c10,…,cp0)∈Mp+1,k(σ), denote(1.7)K0,k(c0)={μ∈V0,k*(σ):(Ifi)Tμ=ci0,i=0,1,…,p}.
In this paper we find the lower and upper bound of the value (If)Tμ, where μ∈K0,k(c0). This problem is similar to the classical moment problem (see, e.g., [1, Chapter  2] and [3, Chapter  4]), but the measure we are interested in is discrete and positive on some cones of generalized convex functions.The main result of this paper can be stated as follows.Theorem 1.1.
Letc0 be an internal point of Mp+1,k(σ), and let f∈ℂ[0,1] be such that P+ and P- are nonempty sets, then
(1.8)sup⁡μ∈K0,k(c0)(If)Tμ=inf⁡g∈P-g(c0),(1.9)inf⁡μ∈K0,k(c0)(If)Tμ=sup⁡g∈P+g(c0),
where
(1.10)P+={g∈span⁡{f0,…,fp}:I(g-f)∈V0,k(σ)},P-={g∈span⁡{f0,…,fp}:I(f-g)∈V0,k(σ)}.Note that the motivation of consideration of the problems(1.11)sup⁡μ∈K0,k(c0)(If)Tμ,inf⁡μ∈K0,k(c0)(If)Tμ
has arisen from the theory of shape-preserving approximation. As we will show in Section 3, the estimation of the error of optimal recovery by means of shape-preserving algorithms can be reduced to the problems of type (1.11).


## 2. Duality Theorems and the Proof of Theorem1.1

First we consider a conic programming problem, and we prove weak and strong duality theorems relative to this problem.LetA∈ℝm×n, b∈ℝm, c∈ℝn, m<n, m,n∈ℕ.Consider the problem(2.1)min⁡x∈McTx,whereM∶={x∈Rn:Ax=b,x∈V0,k*(σ)}.
It follows from [4], that the dual problem can be written in the following way:(2.2)max⁡y∈M*bTy,whereM*∶={y∈Rm:ATy+s=c,s∈V0,k(σ)}.Lemma 2.1.
The setQ∶={Ax:x∈V0,k*(σ)} is a nonempty, convex, closed set.Proof.
It is clear thatQ is a convex set. Moreover, since the origin of ℝn belongs to Q, the set Q is nonempty. To show that Q is closed, suppose that qk is a sequence in Q, such that qk→q. Our goal is to show that q∈Q.
Consider the optimization problem(2.3)min⁡x∈V0,k*(σ)‖q-Ax‖∞,
where ∥·∥∞ defined by ∥a∥∞=maxi|ai|, a=(ai)i=1n∈ℝn.
It can be rewritten as follows:(2.4)min⁡t,
where minimum is taken over all x∈V0,k*(σ) such that
(2.5)t≥qi-(AxT)i,i=1,…,n,(2.6)-t≥-qi+(AxT)i,i=1,…,n.
Note that x∈V0,k*(σ) if and only if xTv*≥0, where v* runs over all extreme rays of the cone V0,k(σ). Thus, the set of all x∈V0,k*(σ) satisfying inequalities (2.5), (2.6) is a nonlinear polyhedron. It is obvious that there is an optimal solution (x*,t*) such that t*≥0. Assume that t*>0. Since qk→q, there is an index k′ such that ∥q-qk′∥∞=t′<t*, where qk′∈Q. Let x′∈V0,k*(σ) be such that qk′=Ax′. It implies that (x′,t′) is a feasible solution of the system (2.5), (2.6). It contradicts that (x*,t*) is optimal. Thus, we have t*=0 which implies q=Ax*, and therefore q∈Q.Lemma 2.2.
LetA∈ℝm×n, b∈ℝm. Only one of the following sets is not empty:
(2.7){x∈Rn:Ax=b,x∈V0,k*(σ)},(2.8){y∈Rm:-ATy∈V0,k(σ),bTy>0}.Proof.
Assume the opposite, that is, there existx*∈ℝn and y*∈ℝm which belong to the sets (2.7) and (2.8), respectively. It follows from -ATy*∈V0,k(σ) and x*∈V0,k*(σ) that 0≥(ATy*)Tx*=(y*TA)x*=y*T(Ax*)=y*Tb=bTy*. This contradicts to bTy*>0. Hence, we conclude that at most one of (2.7) or (2.8) is not empty.
Now, it remains to show that if (2.7) is empty, then (2.8) is not. Consider the nonempty closed and convex set Q={Ax,x∈V0,k*(σ)}. Since (2.7) is empty, we have b∉Q. It follows from the separating hyperplane theorem that there exists y∈ℝm such that yT(Ax)<yTb for all x∈V0,k*(σ). As 0∈Q, bTy>0. Since bTy>0, the definition of set (2.7) implies -ATy∈V0,k(σ).Lemma 2.3.
Suppose the feasible setsM and M* of problems (2.1) and (2.2) are both not empty. Let x*∈ℝn be the optimal solution of (2.1) and y*∈ℝm the optimal solution of (2.2). Then bTy*≤cTx*.Proof.
The proposition follows from(2.9)bTy*=(Ax*)Ty*=(x*TAT)y*≤x*T(ATy*+s)=x*Tc,
where s∈V0,k(σ), x*∈V0,k*(σ), and ATy*+s=c by definition.Theorem 2.4 (strong duality theorem).
If the problem (2.1) has an optimal solution x*∈ℝn, then the problem (2.2) also has an optimal solution y*∈ℝm and
(2.10)bTy*=cTx*.Proof.
Assume that the feasible setM of the problem (2.1) is not empty, and denote by  x*∈ℝn the optimal solution of the problem (2.1). Let us show that the set of all (x,t), x∈ℝn, t∈ℝ, satisfying
(2.11)Ax-bt=0,cTx-(cTx*)t=-1<0,x∈V0,k*(σ),t≥0,
is empty.
Assume that(x′,t′) satisfies the system (2.11) and t′>0. Then (x′/t′) is a solution of (2.1) and cT(x′/t′)<cTx*, which contradicts to the optimality of x*. On the other hand, if t′=0, then x*+x′ is a solution of (2.1), and cT(x*+x′)=cTx*-1<cTx*, which contradicts to the optimally of x*.
Now, it follows from [4]that there is y*∈ℝm such that c-ATy*≥0 and -cTx*+bTy*≥0. It implies that y* is a solution of (2.2). Moreover, it follows from Lemma 2.2 that bTy*≤cTx*.Now we are ready to prove Theorem1.1. Note that the set Mp+1,k(σ) defined in Section 1 is a closed convex cone. Let 0≤t0<t1<⋯<tp≤1 be arbitrary points in [0, 1]. Since {f0,…,fp} is a Chebyshev system, we may conclude that points(2.12)ci=(f0(ti),…,fp(ti))∈Mp+1,k(σ),i=0,…,p,
are linearly independent. Thus, the cone Mp+1,k(σ) is not contained in any p-dimensional subspaces.Proof of Theorem1.1.
We will prove (1.9). Consider the conic programming problem
(2.13)min⁡μ∈K0,k(c0)(If)Tμ.
Denote
(2.14)M0,k*(σ)∶={y∈Rp+1:I(f-∑i=0pyifi)∈V0,k(σ)}.
The dual problem of the problem (2.13) is the problem
(2.15)max⁡y∈M0,k*(σ)cTy.
It follows from Lemma 2.3 that
(2.16)inf⁡μ∈K0,k(c0)(If)Tμ=max⁡y∈M0,k*(σ)yTc0.
Equality (1.9) follows from the equality
(2.17)max⁡y∈M0,k*(σ)yTc0=sup⁡g∈P+g(c0).
Equality (1.8) can be proved similarly.


## 3. The Error of Optimal Interpolation by Means of Shape Preserving Algorithms

Let0≤x1<x2<⋯<xn≤1, If=(f(x1),…,f(xn))T∈ℝn, f∈ℂ[0,1]. Let Φ denote the class of all linear algorithms A:ℝn→ℝ based on information I. The error of the problem of optimal linear interpolation of f∈ℂ[0,1] at point ζ∈[0,1] on the basis of information If, f∈W, is defined by(3.1)eζ(f,I)∶=inf⁡A∈Φ|f(ζ)-A(If)|.
Note that for every A∈Φ there exists μ∈ℝn such that A(If)=(If)Tμ for all f∈ℂ[0,1]. Then(3.2)eζ(f,I)=inf⁡μ∈Rn|f(ζ)-(If)Tμ|.
Optimal recovery problems arise in many applications of the approximation theory and have received much attention. In-depth study can be found in papers [5, 6], and in book in [7].In various applications it is necessary to approximate a function preserving properties such as monotonicity, convexity, and concavity. In the theory of shape-preserving approximation by means of polynomials and splines the last 25 years have seen extensive research. The most significant results were summarized in [8, 9].If a functionf has some shape properties, then it usually means that the element f belongs to a cone in ℂ[0,1].One of the tasks of the theory of shape-preserving approximation is to estimate value (3.1), where infimum is taken over all linear algorithms, which are satisfied additional (shape-preserving) properties.LetK be a cone in ℂ[0,1]. Let Φ(K) denote the class of all linear algorithms A:ℝn→ℝ, based on information I and such that A(v)≥0 for all v∈V, V∶={If:f∈K}⊂ℝn.Define by(3.3)eζ(f,I,K)∶=inf⁡A∈Φ(K)|f(ζ)-A(If)|
the error of optimal linear interpolation of f∈ℂ[0,1] at point ζ∈[0,1] on the basis of information If, f∈W, with respect to the coneK.Denote byV*∶={u∈ℝn:uTv≥0forallv∈V} the cone dual to V. Note that for every A∈Φ(K) there exists μ∈V* such that A(If)=(If)Tμ for all f∈ℂ[0,1]. Then(3.4)eζ(f,I,K)=inf⁡μ∈V*|f(ζ)-(If)Tμ|.
The next proposition demonstrates how we can use Theorem 1.1 to obtain the error of optimal linear interpolation.We will consider the casek=2, σ=(1,0,1), u0(x)≡1, u1(x)≡x. Then W0,2(σ) is the cone of all positive and convex functions on [0,1], V0,2(σ)={If:f∈W0,2(σ)} and, V0,2*(σ)={μ∈ℝn:(If)Tμ≥0forallIf∈V0,2(σ)}.In the next proposition we consider the problem of interpolation by means of shape-preserving algorithmsA, which have some properties of shape-preserving projections (i.e., A(f)=f for every f from a certain finite-dimensional subspace). Note that a deep study of linear shape preserving projections was undertaken in papers [10–12].Corollary 3.1.
Letf∈ℂ[0,1] be a strictly convex function on [0,1], ζ∈[0,1], and let 1≤k≤n-1 be such that xk<ζ<xk+1. Denote
(3.5)D∶={μ∈V0,2*(σ):(Iui)Tμ=ui(ζ),i=0,1}.
Then
(3.6)inf⁡μ∈D|f(ζ)-(If)Tμ|=(xk+1-ζ)(ζ-xk)[xk,ζ,xk+1]f,
where [xk,ζ,xk+1]f denotes the divided difference of f at xk<ζ<xk+1.Proof.
Consider the problem(3.7)min⁡μ∈D(f(ζ)-(If)Tμ).
It follows from Theorem 1.1 that
(3.8)min⁡μ∈D(f(ζ)-(If)Tμ)=max⁡(f(ζ)+y0u0(ζ)+y1u1(ζ)),
where maximum is taken over all y0,y1∈ℝ such that I(f+y0u0+y1u1)∈V0,2(σ).
It follows fromxk<ζ<xk+1 and strictl convexity of f that
(3.9)max⁡(f(ζ)+y0u0(ζ)+y1u1(ζ))=(xk+1-ζ)(ζ-xk)[xk,ζ,xk+1]f.
Consider the problem
(3.10)min⁡μ∈D(-f(ζ)+(If)Tμ).
It follows from Theorem 1.1 that
(3.11)min⁡μ∈D(-f(ζ)+(If)Tμ)=max⁡(-f(ζ)+y0u0(ζ)+y1u1(ζ)),
where maximum is taken over all y0,y1∈ℝ such that I(-f+y0u0+y1u1)∈V0,2(σ).
It follows fromxk<ζ<xk+1 and strictl convexity of f that
(3.12)max⁡(f(ζ)+y0u0(ζ)+y1u1(ζ))=(xn-ζ)(ζ-x1)[x1,ζ,xn]f.
Now (3.6) follows from (3.8), (3.9), (3.11), and (3.12).



---

*Source: 545780-2011-05-19.xml*