Dynamic programming and dimensionality in convex stochastic optimization and control
Teemu Pennanen, Ari-Pekka Perkkiö · 2025
Read Dynamic programming and dimensionality in convex stochastic optimization and control by Teemu Pennanen, Ari-Pekka Perkkiö (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12787.txt.
Introduction
Teemu Pennanen and Ari-Pekka Perkkio study how to solve staged decision problems under uncertainty while keeping the state small, in a paper from 2025. Such problems arise in control and finance, and their cost to go functions can grow too large to compute. They focus on a form where choices come both before and after each random event.
That form can need a smaller state than the classic orders of play. Their main result describes best solutions and values through generalized Bellman equations. Solutions are shown to exist under broad conditions, with no need for compact sets. In the case where randomness depends only on the current state, the equations shrink in size just as in classic forms.
Catalog record
| CREATOR | Teemu Pennanen, Ari-Pekka Perkkiö |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12787
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dynamic programming and dimensionality in convex stochastic optimization and control Teemu Pennanen, Ari-Pekka Perkkiö Abstract This paper studies stochastic optimization problems and associated Bellman equations in formats that allow for reduced dimensionality of the cost-to-go functions. In particular, we study stochastic control problems in the “decision-hazard-decision” form where at each stage, the system state is controlled both by predictable as well as adapted controls. Such an information structure may result in a lower dimensional system state than what is required in more traditional “decision-hazard” or “hazard-decision” formulations. The dimension is critical for the complexity of numerical dynamic programming algorithms and, in particular, for cutting plane schemes such as the stochastic dual dynamic programming algorithm. Our main result characterizes optimal solutions and optimum values in terms of solutions to generalized Bellman equations. Existence of solutions to the Bellman equations is established under general conditions that do not require compactness. We allow for general randomness but show that, in the Markovian case, the dimensionality of the Bellman equations reduces with respect to randomness just like in more traditional control formulations. No data are associated with this article. No external funding was involved and there are no conflicts of interest. Keywords. Stochastic optimal control, dynamic programming, convexity AMS subject classification codes. 93E20, 90C39, 26B25 1 Introduction Let (\Omega,{\cal F},P) be a probability space with a filtration ({\cal F}_{t})_{t=0}^{T} and consider the optimal control problem \displaystyle\mathop{\rm minimize}\limits \displaystyle E\Bigg[\sum_{t=0}^{T-1} \displaystyle L_{t}(X_{t},U^{b}_{t},U^{a}_{t+1})+J(X_{T})\Bigg]\ \mathop{\rm over}\ \ (X,U^{b},U^{a})\in{\cal N}, (1) \displaystyle\mathop{\rm subject\ to}\ \displaystyle X_{t+1} \displaystyle=F_{t}(X_{t},U^{b}_{t},U^{a}_{t+1})\quad t=0,\dots,T-1\ a.s., where the state X_{t} and the controls U^{b}_{t} and U^{a}_{t} are random variables taking values in \mathbbm{R}^{N} , \mathbbm{R}^{M^{b}} and \mathbbm{R}^{M^{a}} . The functions L_{t}:\mathbbm{R}^{N}\times\mathbbm{R}^{M^{b}}\times\mathbbm{R}^{M^{a}}\times\Omega\to\overline{\mathbbm{R}} and J:\mathbbm{R}^{N}\times\Omega\to\overline{\mathbbm{R}} are extended real-valued convex normal integrands and, for each t , the function F_{t}:\mathbbm{R}^{N}\times\mathbbm{R}^{M^{b}}\times\mathbbm{R}^{M^{a}}\times\Omega\to\mathbbm{R}^{N} is given by F_{t}(X_{t},U^{b}_{t},U^{a}_{t+1},\omega):=A_{t+1}(\omega)X_{t}+B^{b}_{t+1}(\omega)U^{b}_{t}+B^{a}_{t+1}(\omega)U^{a}_{t+1}+W_{t+1}(\omega), where A_{t+1} , B^{b}_{t+1} and B^{a}_{t+1} are {\cal F}_{t+1} -measurable random matrices of appropriate dimensions and W_{t+1} are {\cal F}_{t+1} -measurable random vectors. The set {\cal N} denotes the space of adapted stochastic processes, i.e. those where (X_{t},U^{b}_{t},U^{a}_{t}) is {\cal F}_{t} -measurable for each t=0,\ldots,T . Accordingly, we will assume that {\cal F}_{0} only consists of sets of measure zero or one, so that any {\cal F}_{0} -measurable function is almost surely constant. The constrains in ( 1 ) are called the system equations . Problems of the form ( 1 ) were introduced in [ 3 ] as a unification of more common formulations of stochastic control problems where one of the control variables U^{b}_{t} or U^{a}_{t} is absent. While U^{b}_{t} represents control decisions taken under the information available at time t only, the control U^{a}_{t+1} may depend on information available at time t+1 after e.g. the values of the matrices A_{t+1} and B_{t+1} in the system equations are observed. Problems with controls U^{b}_{t} only are sometimes said to be in the “decision-hazard” format while problems with U^{a}_{t} only are said to be in “hazard-decision” format. Accordingly, in [ 3 ] problems of the form ( 1 ) are said to be in the “decision-hazard-decision” format. Such problems arise naturally e.g. in “two-timescale” stochastic optimization models that are convenient e.g. in energy systems modelling; see [ 10 ] and its references. It is possible to reformulate problem ( 1 ) in the hazard-decision format by augmenting the system state X by the here-and-now control variable U^{b}_{t} ; see Remark 5 below. This, however, increases the dimensionality of the dynamic programming equations by the dimension of U^{b}_{t} . Dynamic programming algorithms are often sensitive to the dimension of the system state so the state augmentation may be problematic from the computational point of view. The dimension is particularly critical for cutting plane-based algorithms such as stochastic dual dynamic programming (SDDP); see [ 9 , Section 3.3.1] . It was discovered in [ 3 , Section 6] that the extended control formulation of ( 1 ) allows for dynamic programming equations in the original state space thus avoiding the state augmentation of Remark 5 . Indeed, [ 3 , Theorem 13] expresses the optimum value of ( 1 ) as J_{0}(X_{0}) where the initial state X_{0} is fixed and the function J_{0} is given recursively by the dynamic programming equations (aka Bellman equations) J_{t}(X_{t})=\inf_{U^{b}_{t}\in\mathbbm{R}^{M^{b}}}E_{t}\left[\inf_{U^{a}_{t+1}\in\mathbbm{R}^{M^{a}}}\{L_{t}(X_{t},U^{b}_{t},U^{a}_{t+1})+J_{t+1}(F_{t}(X_{t},U^{b}_{t},U^{a}_{t+1}))\}\right]. (2) Here and in what follows, we use the short hand notation E_{t}=E^{{\cal F}_{t}} for the {\cal F}_{t} -conditional expectation of a random variable. Theorem 13 of [ 3 ] assumed that the randomness is driven by a sequence of stagewise independent random variables and the cost functions L_{t} were assumed to be “lower semianalytic” in order to establish sufficient measurability so that the expectations in ( 2 ) are well-defined. When the underlying probability space is finite, all the measurability questions disappear. In practice, however, one is often faced with continuously distributed random variables. This paper extends [ 3 , Theorem 13] in the convex case by 1. giving optimality conditions for ( 1 ) in terms of the Bellman functions J_{t} , 2. providing sufficient conditions for existence of solutions (J_{t})_{t=0}^{T} to the Bellman equations ( 2 ), 3. allowing for general randomness in the cost functions and system equations in problem ( 1 ). Moreover, we will show that, under an appropriate Markov property, the dimensionality of the cost-to-go functions J_{t} reduces with respect to the underlying randomness. The last section describes an extension of the Stochastic Dual Dynamic Programming algorithm for ( 1 ) alluded to at the end of [ 3 , Section 6] . Moreover, we prove the above results in an extended problem format (in Section 4 ) that is even more general than ( 1 ) while allowing for Bellman equations with the same dimensionality reductions as for ( 1 ). The main results are derived from the theory developed in the recent book [ 11 ] . Closely related stochastic optimization models were studied in [ 11 , Section 2.3] but without specifying the structure required for dimensionality reduction in the Bellman equations. The rest of the paper is organized as follows. The following section presents a dynamic programming theory for problem ( 1 ). The proofs of the three results in Section 2 will be given in Section 5 as consequences of the dynamic programming theory developed in Section 4 . The results in Section 4 are, in turn, derived from the results on the abstract Lagrangian problem format in Section 3 . 2 Dynamic programming in optimal control This section gives the main results concerning dynamic programming for problem ( 1 ). The proofs will be obtained in Section 5 as applications of corresponding results for a more general problem format to be introduced in Section 4 . Much like [ 17 ] and [ 5 ] , our approach is based on the theory of normal integrands developed for optimization problems involving integral functionals; see e.g. [ 14 ] , [ 2 ] , [ 19 , Chapter 14] and the references there. Recall that a function h:\mathbbm{R}^{n}\times\Omega\to\overline{\mathbbm{R}} is a normal integrand if the epigraphical mapping \omega\mapsto\mathop{\rm epi}\nolimits h(\cdot,\omega) is closed-valued and measurable; see [ 19 , Chapter 14] . Given a sub- \sigma -algebra {\cal G} of {\cal F} , the {\cal G} -conditional expectation of h ,