Sparse Optimal Stochastic Control

This work investigates an optimal control problem for non-linear stochastic systems with the $L^{0}$ control cost. This cost functional penalizes the length of the support of control variables, and the optimization based on the criteria tends to make the control input identically zero on a set with positive measures. Consequently, the optimal control is switched off completely on parts of the time domain. Hence, this type of control is also referred to as sparse optimal control. For example, this optimal control framework is applied to actuator placements [22, 8, 16], networked control systems [18, 9, 20], and discrete-valued control [12], to name a few. The sparse optimal control involves the discontinuous and non-convex cost functional. Then, in order to deal with the difficulty of analysis, some relaxed problems with the $L^{p}$ cost functional have been often investigated, akin to methods used in compressed sensing applications [4].

Literature review:  For deterministic control-affine systems, the $L^{1}$ cost functional is analyzed with an aim to show the relationship between the $L^{0}$ optimality and the $L^{1}$ optimality, and an equivalence theorem is derived in [17]. In [10], the result is extended to deterministic general linear systems including infinite-dimensional systems. The $L^{1}$ control cost is also considered in [1, 23, 2]. In [10], the sparsity properties of optimal controls for the $L^{p}$ cost with $p\in(0,1)$ is discussed. The authors investigated this problem from a dynamic programming viewpoint [11]. When it comes to stochastic systems, in [5], a finite horizon optimal control problem with the $L^{1}$ cost functional for stochastic systems is dealt with and the authors propose sampling-based algorithm to solve the problem utilizing forward and backward stochastic differential equations. However, it is not obvious that the $L^{1}$ optimal control achieves the desired sparsity. To the best of the authors’ knowledge, our preliminary work [13] (Theorem 1 below) on the continuity of the value function is the only theoretical result on $L^{0}$ optimal control of stochastic systems.

Contribution:  The goal of this work is to obtain the sparse optimal feedback map (Theorem 4), where the optimal control input has the bang-off-bang property and to reveal the equivalence between the $L^{0}$ optimality and the $L^{1}$ optimality for control-affine stochastic systems (Theorem 5). To this end, we utilize the dynamic programming. In the present paper, we first characterize our value function as a viscosity solution to the Hamilton-Jacobi-Bellman (HJB) equation [7, 24]. Based on the result, we show a necessary and sufficient condition for the $L^{0}$ optimality (Theorem 3), which immediately gives an optimal feedback map. In addition, a sufficient condition for the value function to be a classical solution to the HJB equation (i.e., a solution that satisfies the HJB equation in the usual sense) is given via the equivalence, while, in general, for the deterministic case, we cannot ensure the differentiability of the value function.

In the stochastic case, the HJB equation becomes a second-order equation compared to that of the deterministic case, and hence the results for the deterministic systems [11] cannot be directly applied to the stochastic case. Indeed, several difficulties arise due to the stochasticity. For example, the analysis of the deterministic $L^{0}$ optimality of a control in [11] heavily relies on the local Lipschitz continuity of the value function, which means the almost everywhere differentiability. On the other hand, the value function for the stochastic $L^{0}$ optimal control is at most locally 1/2-Hölder continuous [13]. This implies that we need a quite different approach. Even for the problem formulation, we must be careful about the probability space we work on to correctly apply the dynamic programming principle.

In order to demonstrate the practical usefulness of our theoretical results, an example is exhibited; see Example 2 for more details.

Organization:  The remainder of this paper is organized as follows. In Section 2, we give mathematical preliminaries for our subsequent discussion. In Section 3, we describe the system model and formulate the sparse optimal control problem for stochastic systems. Section 4 is devoted to the general analysis of the stochastic optimal control with the discontinuous $L^{0}$ cost. We first characterize the value function as a viscosity solution to the associated HJB equation and next show a necessary and sufficient condition for the $L^{0}$ optimality. Section 5 characterizes the sparse optimal stochastic control. We show the relationship with the $L^{1}$ optimization problem and some basic properties of the sparse optimal stochastic control for control-affine systems with box constraints. In Section 6 we offer concluding remarks.

This section reviews notation that will be used throughout the paper.

Let $N$, $N_{1}$, and $N_{2}$ be positive integers. For a matrix $M\in{\mathbb{R}}^{N_{1}\times N_{2}}$, $M^{\top}$ denotes the transpose of $M$. For a matrix $M\in{\mathbb{R}}^{N\times N}$, $\mathrm{tr}(M)$ denotes the trace of $M$. Denote by ${\mathcal{S}}^{N}$ the set of all symmetric $N\times N$ matrices and by ${\mathcal{S}}_{+}^{N}$ the set of all positive semidefinite matrices. Denote the Frobenius norm of $M\in{\mathbb{R}}^{N_{1}\times N_{2}}$ by $\|M\|$, i.e., $\|M\|\triangleq\sqrt{\textrm{tr}(M^{\top}M)}$. For a vector $a=[a^{(1)},a^{(2)},\dots,a^{(N)}]^{\top}\in\mathbb{R}^{N}$, we denote the Euclidean norm by $\|a\|\triangleq(\sum_{i=1}^{N}(a^{(i)})^{2})^{1/2}$ and the open ball with center at $a$ and radius $r>0$ by $B(a,r)$, i.e., $B(a,r)\triangleq\{x\in\mathbb{R}^{N}:\|x-a\|<r\}$. We denote the inner product of $a\in\mathbb{R}^{N}$ and $b\in\mathbb{R}^{N}$ by $a\cdot b$.

For $p\in\{0,1\}$ and a continuous-time signal $u_{s}=[u_{s}^{(1)},u_{s}^{(2)},\dots,u_{s}^{(N)}]^{\top}\in{\mathbb{R}}^{N}$ over a time interval $[t,T]$, the $L^{p}$ norm of $u=\{u_{s}\}_{t\leq s\leq T}$ is defined by

with the Lebesgue measure $\mu_{L}$ on $\mathbb{R}$. The $L^{0}$ norm is also expressed by $\|u\|_{0}=\int_{t}^{T}\psi_{0}(u_{s})ds$, where $\psi_{0}:\mathbb{R}^{N}\to\mathbb{R}$ is a function that returns the number of non-zero components, i.e.,

with $0^{0}=0$.

For a given set $\Omega\subset\mathbb{R}^{N}$, $C(\Omega)$ denotes the set of all continuous functions on $\Omega$. For $T>0$, $C^{1,2}((0,T)\times{\mathbb{R}}^{N})$ denotes the set of all functions $\phi$ on $(0,T)\times{\mathbb{R}}^{N}$ whose partial derivatives $\frac{\partial\phi}{\partial s},\frac{\partial\phi}{\partial x^{(i)}},\frac{\partial^{2}\phi}{\partial x^{(i)}\partial x^{(j)}},i,j=1,\ldots,N,$ exist and are continuous on $(0,T)\times{\mathbb{R}}^{N}$. Denote by $C^{1,2}([0,T)\times{\mathbb{R}}^{N})$ the set of all $\phi\in C^{1,2}((0,T)\times{\mathbb{R}}^{N})\cap C([0,T)\times{\mathbb{R}}^{N})$ such that $\frac{\partial\phi}{\partial s},\frac{\partial\phi}{\partial x^{(i)}},\frac{\partial^{2}\phi}{\partial x^{(i)}\partial x^{(j)}},i,j=1,\ldots,N,$ can be extended to continuous functions on $C([0,T)\times{\mathbb{R}}^{N})$. For $\phi\in C^{1,2}([0,T)\times{\mathbb{R}}^{N})$, $\phi_{t}$ denotes the partial derivative with respect to the first variable, $D_{x}\phi$ denotes the gradient with respect to the last $N$ variables, and $D_{x}^{2}\phi$ denotes the Hessian matrix with respect to the last $N$ variables. For $p\geq 2$, denote by $C_{p}^{1,2}([0,T]\times{\mathbb{R}}^{N})$ the set of all $\phi\in C^{1,2}([0,T)\times{\mathbb{R}}^{N})\cap C([0,T]\times{\mathbb{R}}^{N})$ satisfying

for some constant $K>0$ and any $\rho\in\{\phi,D_{x}\phi,D_{x}^{2}\phi,\phi_{t}\}$. A function $\rho:[0,T]\times{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}$ is said to satisfy a polynomial growth condition or to be at most polynomially growing if there exist constants $K>0$ and $p\geq 2$ such that (2) holds.

Let $\alpha\in(0,1]$. A function $f:{\mathbb{R}}^{N_{1}}\rightarrow{\mathbb{R}}^{N_{2}}$ is called $\alpha$-Hölder continuous if there exists a constant $L>0$ such that, for all $x,y\in{\mathbb{R}}^{N_{1}}$, $\|f(x)-f(y)\|\leq L\|x-y\|^{\alpha}$. Especially when $\alpha=1$, $f$ is called Lipschitz continuous. A function $f$ is called locally $\alpha$-Hölder continuous if for any $x\in{\mathbb{R}}^{N_{1}}$, there exists a neighborhood $U_{x}$ of $x$ such that $f$ restricted to $U_{x}$ is $\alpha$-Hölder continuous.

The notation $o(s)$ denotes a real-valued function $f$ defined on some subset of ${\mathbb{R}}$ such that $\lim_{s\rightarrow 0}f(s)/s=0$.

For $0\leq t\leq T$, let $(\Omega,{\mathcal{F}},\{{\mathcal{F}}_{s}\}_{s\geq t},{\mathbb{P}})$ be a filtered probability space, and ${\mathbb{E}}$ be the expectation with respect to ${\mathbb{P}}$. For $S={\mathbb{R}}^{N}{\rm~{}or~{}}{\mathcal{S}}^{N}$, denote by ${\mathcal{L}}_{{\mathcal{F}}}^{2}(t,T;S)$ the set of all $\{{\mathcal{F}}_{s}\}_{s\geq t}$-adapted $S$-valued processes $\{X_{s}\}_{s\geq t}$ such that ${\mathbb{E}}\left[\int_{t}^{T}\|X_{s}\|^{{\color[rgb]{0,0,0}{2}}}ds\right]<+\infty$. In what follows, we omit the subscript of stochastic processes when no confusion occurs, e.g., $\{X_{s}\}=\{X_{s}\}_{s\geq t}$.

This paper considers the sparse optimal control for stochastic systems. This section provides the system description and formulates the main problem.

We consider the following stochastic system where the state is governed by a stochastic differential equation valued in ${\mathbb{R}}^{n}$:

The initial value $x\in{\mathbb{R}}^{n}$ is deterministic, and $\{w_{s}\}$ is a $d$-dimensional Wiener process. The range of the control ${\mathbb{U}}\subset{\mathbb{R}}^{m}$ is a compact set that contains $0\in{\mathbb{R}}^{m}$, and we fix a finite horizon $0<T<\infty$.

We are interested in the optimal control that minimizes the cost functional

We assume the following conditions for functions $f,\sigma,g$:

1. $(A_{1})$

   The functions $f$ and $\sigma$ are globally Lipschitz, namely, there exist positive constants $L$, $\bar{M}$ and a nondecreasing function $\bar{m}\in C([0,+\infty))$ such that $f:{\mathbb{R}}^{n}\times{\mathbb{U}}\to{\mathbb{R}}^{n}$ and $\sigma:{\mathbb{R}}^{n}\times{\mathbb{U}}\to{\mathbb{R}}^{n\times d}$ satisfy the following condition:

   	$\displaystyle\|f({{x}},u)-f(y,v)\|+\|\sigma({{x}},u)-\sigma(y,v)\|$
   	$\displaystyle\quad\leq L\|{{x}}-y\|+\bar{m}(\|u-v\|)$		(5)

   for all ${{x}},y\in{\mathbb{R}}^{n}$, $u,v\in{\mathbb{U}}$, where $\bar{m}(\cdot)\leq\bar{M}$ and $\bar{m}(0)=0$;

2. $(A_{2})$

   There exist constants $\hat{C}>0$ and $p\geq 2$ such that $g:{\mathbb{R}}^{n}\to{\mathbb{R}}$ satisfies the following growth condition:

   $$|g({{x}})|\leq\hat{C}(1+\|{{x}}\|^{p})$$

   (6)

   for all ${{x}}\in{\mathbb{R}}^{n}$;

3. $(A_{3})$

   $g:{\mathbb{R}}^{n}\to{\mathbb{R}}$ is continuous.

Given a probability space with the filtration $\{{\mathcal{F}}_{s}\}_{s\geq t}$ generated by a Wiener process, Assumption $(A_{1})$ ensures the existence and uniqueness of a strong solution to the stochastic differential equation (3) with any initial condition ${{x}}_{t}=x,(t,x)\in[0,T]\times{\mathbb{R}}^{n}$, and any $\{{\mathcal{F}}_{s}\}_{s\geq t}$-progressively measurable and ${\mathbb{U}}$-valued control process $\{u_{s}\}$. In addition, under assumptions $(A_{1})$ and $(A_{2})$, the cost functional $J^{\sf s}(t,x,u)$ is finite; see Appendix A. Assumption $(A_{3})$ is introduced to show the continuity of the value function defined later in (7).

For our analysis, we utilize the method of dynamic programming. In order to establish the dynamic programming principle (Lemma 1), we need to consider a family of optimal control problems with different initial times and states $(t,x)\in[0,T]\times{\mathbb{R}}^{n}$ along a state trajectory. Let us consider a state trajectory starting from $x_{0}=x$ on a filtered probability space $(\Omega,{\mathcal{F}},\{{\mathcal{F}}_{s}\}_{s\geq 0},{\mathbb{P}})$. For any $s>0$, $x_{s}$ is a random variable. However, an $\{{\mathcal{F}}_{s}\}_{s\geq 0}$-progressively measurable control $\{u_{s}\}$ knows the information of the system up to the current time. In particular, the current state $x_{s}$ is deterministic under a different probability measure ${\mathbb{P}}(\cdot|{\mathcal{F}}_{s})$. This observation naturally leads us to vary the probability spaces as well as control processes; for details see e.g., [24, 19, 6]. For this reason, we adopt the so-called weak formulation of the stochastic optimal control problem; see also Remark 1.

For each fixed $t\in[0,T)$, we denote by ${\mathcal{U}}^{\sf s}[t,T]$ the set of all 5-tuples $(\Omega,{\mathcal{F}},{\mathbb{P}},\{w_{s}\},\{u_{s}\})$ satisfying the following conditions:

• (i)

  $(\Omega,{\mathcal{F}},{\mathbb{P}})$ is a complete probability space,

• (ii)

  $\{w_{s}\}$ is a $d$-dimensional Wiener process on $(\Omega,{\mathcal{F}},{\mathbb{P}})$ over $[t,T]$ (with $w_{t}=0$ almost surely),

• (iii)

  The control $\{u_{s}\}$ is an $\{{\mathcal{F}}_{s}\}_{s\geq t}$-progressively measurable and ${\mathbb{U}}$-valued process on $(\Omega,{\mathcal{F}},{\mathbb{P}})$ where ${\mathcal{F}}_{s}$ is the $\sigma$-field generated by $\{w_{r}\}_{t\leq r\leq s}$.

For $(\Omega,{\mathcal{F}},{\mathbb{P}},\{w_{s}\},\{u_{s}\})\in{\mathcal{U}}^{\sf s}[t,T]$, we call $\{u_{s}\}$ and $(\Omega,{\mathcal{F}},{\mathbb{P}},\{w_{s}\})$ an admissible control process and a reference probability space, respectively. For notational simplicity, we sometimes write $u\in{\mathcal{U}}^{\sf s}[t,T]$ instead of $(\Omega,{\mathcal{F}},{\mathbb{P}},\{w_{s}\},\{u_{s}\})\in{\mathcal{U}}^{\sf s}[t,T]$. Note that in $\eqref{eq:cost_stoc}$ the expectation ${\mathbb{E}}$ is with respect to ${\mathbb{P}}$. For given $(t,x)\in[0,T]\times{\mathbb{R}}^{n}$ and $u\in{\mathcal{U}}^{\sf s}[t,T]$, we denote by $\{{{x}}_{s}^{t,x,u}\}_{t\leq s\leq T}$ the unique solution of (3). When there is no confusion, we omit the subscript.

Then, we are ready to formulate the main problem as follows:

The value function for Problem 1 is defined by

This section is devoted to the preliminary analysis of the stochastic $L^{0}$ optimal control problem. We first characterize the value function as a viscosity solution to the associated HJB equation. Then, we derive a necessary and sufficient condition for the $L^{0}$ optimality.