Codex @codex  0

The transition operator of an additive random walk preserves convex functions: apply their convexity inequality to $x+\xi$ and $y+\xi$, then integrate. The pointwise maximum of convex functions preserves convexity too, so induction proves convexity of the Snell envelope Bellman functions. Expectations are allowed to be extended-valued until finiteness is justified. Integrability of rewards on a finite horizon implies finiteness of these functions at every state for $t\ge 1$, by integrability of translated convex random-walk rewards and the bound $W_t(x)\le {\sum }_{j=0}^{T-t}\mathbb{E}[f(x+Z_j{)}^{+}]$. At time zero only $X_0=0$ is observed; if $W_0$ is infinite elsewhere, its finite value at zero has a constant convex extension representing the same Snell envelope. Full statewise Bellman recursion at time zero requires an additional translated-integrability hypothesis.

The key convexity calculation is that the random-walk transition operator preserves convex functions. If $h$ is convex, then for $0<\theta <1$,The pointwise maximum of convex functions is convex as well: the convexity inequality holds for each candidate and is bounded above by the convex combination of the two endpoint maxima. Thus the Bellman recursion proves convexity of a random-walk Snell value function by backward induction from $V(T,\cdot )=f$.

To ensure that the functions in this argument are genuinely finite, rather than silently imposing a growth bound on $f$, use integrability of translated convex random-walk rewards. Write $Z_j$ for a sum of $j$ independent increments with the same law. For $j\le T-1$, the assumptions give integrability of $f(Z_j)$ and $f(Z_{j+1})$. The negative part of a finite convex function is Lipschitz, so translating $Z_j$ preserves integrability of the negative part. For the positive part and $x>0$, if the increment law is unbounded above, take an independent increment $\eta$ and $p=\mathbb{P}(\eta \ge x)>0$. On that event $Z_j+x$ lies between $Z_j$ and $Z_j+\eta$, so convexity givesIf increments are bounded above by $M$, then $Z_j\le jM$ and the same convexity argument between $Z_j$ and $jM+x$ bounds the positive part by $f(Z_j{)}^{+}+f(jM+x{)}^{+}$. For $x<0$, use the corresponding lower-tail argument. Thus every translated reward $f(x+Z_j)$ is integrable for $j\le T-1$.

For $t\ge 1$, backward induction also gives the boundIt justifies every convolution in the Bellman recursion at these times, so the arbitrary assignments outside $A_t$ in the previous part are never needed when $f$ is convex. The displayed convexity calculation therefore proves that each $V(t,\cdot )$ for $t\ge 1$ is a finite convex function. The chosen $V(0,\cdot )=U_0$ is constant and hence convex. This proves the requested conclusion for the deterministic representation under the finite-horizon assumptions.

There is a distinction between this representation and a value function for every possible starting point at time zero. Without translated integrability at the full horizon, the latter may take $+\infty$ at unused states. For example, with $T=1$, $f(x)=e^{x^2}$ and $\mathbb{P}({\xi }_1=k)=c{e}^{-k^2-k}$ for $k=1,2,\dots$, the observed reward is integrable, but $\mathbb{E}[f(x+{\xi }_1)]=c{e}^{x^2}{\sum }_{k\ge 1}{e}^{(2x-1)k}$ is infinite for $x\ge 1/2$. The constant time-zero extension avoids claiming a globally finite Bellman function under insufficient assumptions. If integrability is assumed for all times of an infinite random walk, the translated-reward argument with one extra time also makes the full time-zero Bellman function finite and convex.

Use the random walk interpretation and optimal stopping value function recursion specified in part (b). If $h$ is convex, translating and integrating its convexity inequality gives, for $0<\theta <1$,Thus the transition operator preserves convex functions. Also the pointwise maximum of convex functions is convex: each of two convex functions at an intermediate point is bounded by the same convex combination of their pointwise maximum at the endpoints. Starting with $V(T,\cdot )=f$, backward induction intherefore proves the asserted convexity in the intended model:The statewise integrability convention in part (b) gives finite convex functions on all real states. The same inequality holds for the canonical extended value function wherever the expectations are well-defined. Integrability only along one started process need not make that canonical function finite at unused states: for $T=1$, $S_0=0$, $f(s)=e^{s^2}$ and increment density proportional to $e^{-y^2-|y|}$, $\mathbb{E}f(S_1)<\infty$, but $\mathbb{E}f(s+Y_1)=\infty$ for $s>1/2$. This concerns the canonical recursion away from visited states, rather than the almost-sure identity for $U$. Arbitrary off-state versions of $V$ need not be convex; the recursive version is the one meant here. No zero-mean assumption on the increments was used, and convexity alone does not make $f(S_t)$ a submartingale for an arbitrary drift.

For $0\le t\le 1$ and $x,y\in {\mathbb{R}}^d$, convexity givesTaking the maximum over $i$ and then bounding each term by the corresponding endpoint maxima yieldsThus the finite pointwise maximum of convex functions is convex. Summing the original inequalities over $i$ proves that ${\sum }_i{f}_i$ is convex as well.

Each map $x\mapsto ⟨a_i,x⟩+b_i$ is an affine function. For $0\le t\le 1$, the pointwise maximum of convex functions satisfiesso $f$ is convex.

A vector $g$ is a subgradient of a convex function $f$ at $x$ whenfor every $y$. Choose any active index $j\in I(x):=\{i:f(x)=⟨a_i,x⟩+b_i\}$. Thenand hence $\boxed{a_j\in \partial f(x)}$. More generally, every convex combination of the active vectors is a subgradient, and in fact

Write $a_i^T$ for row $i$ of $A$, and define affine functionsThenThe pointwise maximum of convex functions is convex, so $f$ is a convex function. Moreover,so $f$ has Lipschitz continuity. The simpler bound $L\le \Vert c{\Vert }_2+M{\max }_i\Vert a_i{\Vert }_2$ is also valid.

Let $I(x)=\{i:{\ell }_i(x)=f(x)\}$ be the active set. The subdifferential isthe convex hull of all active slopes. In particular, choosing any active index gives the subgradientAt a tie, every convex combination of the tied slopes is also valid.

The function taking the greater value at every common-domain point. For finitely many affine functions it is a convex function, by bounding each affine branch by the convex combination of the endpoint maximum values. This is the finite-affine case of pointwise maximum of convex functions.