Lemma 4.2. If Xo < yo then -Ca(yo-Xo,yo) + Dχ(xo) + δ D+V(f(x0)) ≥ 0.
Proof. If x0 < y0 then x0+ is feasible from y0 for sufficiently small . By the principle of optimality it
follows that liminf t0 [C(y0-x0-ε,y0) + D(x0+ε) + δV(f(x0+ε)) - C(y0-x0,y0) - D(x0) - δV(f(x0))]∕ε ≥ 0. The
result follows immediately. ■
Lemma 4.3. D+V(f(x0)) ≤ [Ca(a1,y1)+Cy(a1,y1)]fs(x0)∙
Proof. Since x1 is feasible from f(x0+ε) the principle of optimality implies V(f(x0+ε))-V(f(x0)) ≤
C(f(x0+ε)-x1,f(x0+ε)) + D(x1) + δV(f(x1)) - C(f(x0)-x1,f(x0)) - D(x1) - δV(f(x1)). Dividing by ε and taking
the liminfε t0 on both sides and simplifying completes the proof. ■
Lemma 4.4. If a1 > 0 then DV(f(x0)) ≥ [Ca(a1,y1)+Cy(a1,y1)]‰).
Proof. Since a1 > 0, x1 is feasible from f(x0- ) for sufficiently small . By the principle of optimality it
follows that V(f(x0)) - V(f(x0-ε)) ≥ C(f(x0)-xbf(x0)) + D(x∙) + δV(f(xJ) - C(f(x0-ε)-x1,f(x0-ε)) - D(x∙) -
δV(f(x1)). Once again, dividing by ε and taking the liminfε t0 on both sides and simplifying completes the
proof. ■
The proof of part a of Lemma 4 follows from Lemmas 4.2 and 4.3 while combining Lemmas 4.1 and 4.4
yields part b. Part c is a joint implication of all four lemmas. ■
Proof of Proposition 1. Suppose not. Then there exists an optimal program (yt,xt,at)0~ where y1 = f(x0) ≥
y, i.e., x0 ≥f'1(y). Since, y1 e [y,f(y)], it follows that x1<y1. Therefore, using Lemma 4, we have
Ca(y-x0, y) ≥Dχ(x0) + δ[Ca(f(x0)-X1,f(x0)+Cy(f(x0)-X1,f(x0))]fχ(x0)
which violates the inequality in the statement of the Proposition. ■
25