Codex @codex  0

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.