0 ≤ -Cβ(y-x,y) + Dχ(x) + δ[Ca(A(f(x)),f(x))+Cy(A(f(x)),f(x))]fx(x)
≤ -Ca(0,x) + Dχ(x) + δ[Ca(f(x),f(x))+Cy(f(x),f(x))]fχ(x). (using Caa + Cay ≥ 0 twice)
Define H(x) ≡ -Ca(0,x) + Dx(x) + δ[Ca(f(x),f(x))+Cy(f(x),f(x))]fx(x) ≥ 0. The condition in 5b implies H(0)
< 0 and by the continuity of H one can pick an sufficiently close to 0 such that H(χ) < 0. This yields a
contradiction. ■
Proof of Proposition 7. a. Suppose not. Then, there exists y0 ≥ f(X) and an optimal path {yt} such that
y1< f(X), i.e., X0 < X. Using Lemma 4, we have Ca(y -x ,y ) ≤Dχ(x0) + δ[Ca(a1,f(χ)) + Cyffx).
Then x0 < x implies Ca(y0-x,y0) ≤ Ca(y -x ,y ) ≤ Dx(x0) + δ[Ca(abf(x0)) + C/afxJMfXx) ≤ Dx(x) +
δ[Ca(at+1,f(xt)) + Cy(at+1,f(xt))]fx(xt) which violates the condition in part a.
b. Suppose not. Then, there exists optimal path {yt} such that f(x0) = y1 < y0 = f(x), i.e., x0 < x. Lemma 4
implies Ca(y0 -x0,y0) = Ca(f(x)-x0,f(x)) ≤ Dx(x0) + δ[Ca(a1,f(xc)) + Cyffx). Since X(y) is
monotone under Caa + Cay ≥ 0 and x0 < x, then x1 ≤ x0. Using Caa + Cay ≥ 0 twice, this implies Ca(f(x0)-
x0,f(x0)) ≤ Ca(f(x)-x0,f(x)) ≤ Dx(x0) + δ[Ca(f(x0)-x1,f(x0)) + Cβ(f(x0)-x1,f(x0))]fx(x0) ≤ Dx(x0) +
δ[Ca(f(x0),f(x0)) + Ca(f(x0),f(x0))]fx(x0). This violates the condition in part b. ■
28