Convex Computation of Value-at-risk Bounds for Stochastic Processes

This article formulates algorithms to upper-bound the maximum value-at-risk (VaR) of a state function along trajectories of stochastic processes. The VaR is upper bounded by two methods: minimax tail-bounds (Cantelli/Vysochanskij-Petunin) and Expected Shortfall (ES)/Conditional VaR. Tail-bounds lead to an infinite-dimensional second order cone program (SOCP) in occupation measures, while the ES approach creates a linear program (LP) in occupation measures. Under compactness and regularity conditions, there is no relaxation gap between the infinite-dimensional convex programs and their nonconvex optimal-stopping stochastic problems. Upper-bounds on the SOCP and LP are obtained by a sequence of semidefinite programs through the moment-sum-of-squares hierarchy. The VaR upper-bounds are demonstrated on example continuous-time and discrete-time polynomial stochastic processes.