Exploiting homogeneity for the optimal control of discrete-time systems: application to value iteration

Mathieu Granzotto, Romain Postoyan, Lucian Buşoniu, Dragan Nešić and Jamal Daafouz Mathieu Granzotto, Romain Postoyan and Jamal Daafouz are with the Université de Lorraine, CNRS, CRAN, F-54000 Nancy, France (e-mails: {name.surname}@univ-lorraine.fr).Lucian Buşoniu is with the Department of Automation, Technical University of Cluj-Napoca, Memorandumului 28, 400114 Cluj-Napoca, Romania (e-mail: [email protected]).Dragan Nešić is with the Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC 3010, Australia (e-mail: [email protected]). This work was supported by the Australian Research Council under the Discovery Project DP210102600 and by the France-Australia collaboration project IRP-ARS CNRS.

Abstract

To investigate solutions of (near-)optimal control problems, we extend and exploit a notion of homogeneity recently proposed in the literature for discrete-time systems. Assuming the plant dynamics is homogeneous, we first derive a scaling property of its solutions along rays provided the sequence of inputs is suitably modified. We then consider homogeneous cost functions and reveal how the optimal value function scales along rays. This result can be used to construct (near-)optimal inputs on the whole state space by only solving the original problem on a given compact manifold of a smaller dimension. Compared to the related works of the literature, we impose no conditions on the homogeneity degrees. We demonstrate the strength of this new result by presenting a new approximate scheme for value iteration, which is one of the pillars of dynamic programming. The new algorithm provides guaranteed lower and upper estimates of the true value function at any iteration and has several appealing features in terms of reduced computation. A numerical case study is provided to illustrate the proposed algorithm.

I Introduction

Optimal control seeks for inputs that minimize a given cost function along the trajectories of the considered plant dynamics, see, e.g., [21, 2, 11]. While we know how to systematically construct optimal inputs for linear systems and quadratic costs since the 60’s [9], optimal control of general nonlinear systems with general cost functions remains very challenging in general. In this setting, dynamic programming provides various algorithms to construct near-optimal inputs based on Bellman equation [2, 3]. When the state and input spaces are continuous, as in this work, dynamic programming algorithms cannot be implemented exactly. A typical procedure consists in considering compact subsets of the state and input spaces, respectively, which are then discretized to make the implementation of the algorithm tractable. A drawback of this approach is that we obtain (near-)optimal inputs for states in the considered compact set only. In addition, it is not always obvious that a solution initialized in this set would remain in it for all future times. Also, there is no clear recipe on how to select the compact set and typically this is done on a case by case basis by the user.

In this work, we explain how these drawbacks can be addressed when the system and the cost functions satisfy homogeneity properties. The underlying idea is that, in this case, we only have to solve the original optimal control problem on a given well-defined compact set to derive (near-)optimal inputs for any state in the fully unbounded state space. This approach was investigated in e.g., [17, 5, 7, 16, 13, 18] for continuous-time systems. The results on discrete-time systems we are aware of are more scarce [8, 18] on the other hand, and only consider homogeneous properties of degree $1$ (or $0$ depending on the convention), which limits their applicability. This restriction is due to the homogeneity notion used in [8, 18], which does not allow to derive scaling properties of the plant solutions along homogeneous rays when the degree is different from $1$ or $0$ . In this paper, we relax this degree constraint by exploiting a homogeneity definition recently proposed in the literature in [20, 19]. In that way, we can derive scaling properties of the solutions for any homogeneity degree including those featured in [8, Proposition 2] and [18, proof of Corollary 1] as particular cases. We are thus able to consider a much broader class of systems, which include polynomial systems for instance.

To this end, we first extend the definition in [20, 19] to be applicable for systems with inputs. We then derive a new scaling property of the system solutions, provided the sequence of inputs is suitably modified. Assuming the stage and terminal costs are also homogeneous, we explain how the optimal value function scales along homogeneous rays. As a result, by solving the original control problem at a given state, we obtain a solution to a different optimal control problem by scaling the obtained sequence of inputs when moving along the corresponding ray. This differs from [17] where continuous-time systems are studied, as the results here employ scaled weighting constants, while [17] features instead scaled cost horizons. Here, we deduce optimal sequences of inputs for the same cost function along the considered ray in some specific but important cases, which include minimum-time control and maximum hands-off control [15, 14], thereby covering and generalizing the results of [8].

We then explain how the general scaling property of the optimal value function can be exploited to obtain a new approximation scheme for value iteration (VI), which is one of the core algorithms of dynamic programming. This new scheme has the following appealing features. First, it only requires to solve the original VI equation on a given compact manifold whose dimension is strictly smaller than the dimension of the state space. Second, the estimates of the value function are defined on the whole state space. Finally, the proposed algorithm is applied to the optimal control of a van der Pol oscillator.

The rest of the paper is organized as follows. The notation is defined in Section II. The main results are given in Section III, where the homogeneous scaling properties are stated. The new approximation scheme for VI is presented in Section IV. The numerical case study is provided in Section VI, and Section VII concludes the paper.

II Preliminaries

Let $\mathbb{R}$ be the set of real numbers, $\mathbb{R}_{\geq 0}:=[0,\infty)$ , $\overline{\mathbb{R}}_{\geq 0}=[0,\infty]$ , $\mathbb{R}_{>0}:=(0,\infty)$ , $\mathbb{Z}$ be the set of integers, $\mathbb{Z}_{\geq 0}:=\{0,1,2,\ldots\}$ and $\mathbb{Z}_{>0}:=\{1,2,\ldots\}$ . Given a matrix $P\in\mathbb{R}^{n\times n}$ with $n\in\mathbb{Z}_{>0}$ , we write $P\geq 0$ when $P$ is positive semi-definite and we denote by $|x|_{P}:=x^{\top}Px$ , for $x\in\mathbb{R}^{n}$ , the $P$ induced norm. For any $d_{1},\ldots,d_{n}\in\mathbb{R}$ with $n\in\mathbb{Z}_{>0}$ , $\text{diag}(d_{1},\ldots,d_{n})$ stands for the $n\times n$ diagonal matrix, whose diagonal components are $d_{1},\ldots,d_{n}$ . The notation $(x,y)$ stands for $[x^{\top},\,y^{\top}]^{\top}$ , where $x\in\mathbb{R}^{n}$ , $y\in\mathbb{R}^{m}$ and $n,m\in\mathbb{Z}_{>0}$ . The Euclidean norm of a vector $x\in\mathbb{R}^{n}$ with $n\in\mathbb{Z}_{>0}$ is denoted by $|x|$ . We also use the so-called $\ell_{0}$ norm, which we denote $|x|_{0}$ for $x\in\mathbb{R}^{n}$ with $n\in\mathbb{Z}_{>0}$ , which is the number of components of $x$ that are not equal to $0$ . For any set $\mathcal{A}\subseteq\mathbb{R}^{n}$ , $x\in\mathbb{R}^{n}$ and $c\in\overline{\mathbb{R}}_{\geq 0}$ , the map $\delta^{c}_{\mathcal{A}}:\mathbb{R}^{n}\to\overline{\mathbb{R}}_{\geq 0}$ is defined as $\delta^{c}_{\mathcal{A}}(x)=0$ when $x\in\mathcal{A}$ and $\delta^{c}_{\mathcal{A}}(x)=c$ when $x\notin\mathcal{A}$ . Given vectors $x_{1},\ldots,x_{m}\in\mathbb{R}^{n}$ with $n,m\in\mathbb{Z}_{>0}$ , $\text{vect}(x_{1},\ldots,x_{m})$ is the vectorial space generated by the family $(x_{1},\ldots,x_{m})$ . For any $x\in\mathbb{R}$ and $a\in\mathbb{R}_{>0}$ , $\lceil{x}\rfloor^{a}:=\text{sign}(x)|x|^{a}$ . We denote a sequence $\mathbf{u}_{d}=(u_{0},\ldots,u_{d-1})$ of (possibly infinitely many) $d$ elements, with $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ and $u_{i}\in\mathbb{R}^{n}$ for any $i\in\{{0},\ldots,{d-1}\}$ , $n\in\mathbb{Z}_{>0}$ .

The homogeneity definitions used in this work involve the next maps and sets. Given $r=(r_{1},\ldots,r_{n})\in\mathbb{R}_{>0}^{n}$ with $n\in\mathbb{Z}_{>0}$ , the dilation map $\lambda^{r}_{n}:\mathbb{R}_{>0}\times\mathbb{R}^{n}\to\mathbb{R}^{n}$ is defined as $\lambda^{r}_{n}(\varepsilon,x)=(\varepsilon^{r_{1}}x_{1},\ldots,\varepsilon^{r_{n}}x_{n})$ for any $\varepsilon\in\mathbb{R}_{>0}$ and $x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ . We denote $\lambda^{r}_{n}(\varepsilon,x)$ as $\lambda^{r}(\varepsilon)x$ when the dimension $n$ is clear from the context for the sake of convenience. We say that a dilation map is standard when $r=c(1,\ldots,1)\in\mathbb{R}^{n}$ for some $c\in\mathbb{R}_{>0}$ . We call homogeneous ray (induced by dilation map $\lambda^{r}$ ) passing at $x\in\mathbb{R}^{n}$ , the set $\mathcal{R}_{r}(x):=\{\lambda^{r}(\varepsilon)x\in\mathbb{R}^{n}\,:\,\varepsilon\in\mathbb{R}_{>0}\}$ . When $x_{1},x_{2}\in\mathcal{R}_{r}(x)$ , we say that $x_{1}$ and $x_{2}$ belong to the same homogeneous ray. Given a set $\mathcal{A}\subseteq\mathbb{R}^{n}$ and $\varepsilon>0$ , we also denote by $\lambda^{r}(\varepsilon)\mathcal{A}$ the set $\left\{y\in\mathbb{R}^{n}\,{:}\,\exists x\in\mathcal{A},\quad y=\lambda^{r}(\varepsilon)x\right\}$ . Given $r=(r_{1},\ldots,r_{n})\in\mathbb{R}_{>0}^{n}$ with $n\in\mathbb{Z}_{>0}$ , $c\in\mathbb{R}$ and $k\in\mathbb{Z}_{>0}\cup\{\infty\}$ , we denote by $\Lambda_{n,c,k}^{r}:\mathbb{R}_{>0}\times(\mathbb{R}^{n})^{k}\to(\mathbb{R}^{n})^{k}$ the map defined as $\Lambda_{n,c,k}^{r}(\varepsilon,\mathbf{u}_{k}):=\Big{(}\lambda^{r}(\varepsilon)u_{0},\lambda^{r}(\varepsilon)^{c}u_{1},\ldots,\lambda^{r}(\varepsilon)^{c^{k-1}}u_{k-1}\Big{)}$ for any $\mathbf{u}_{k}=(u_{0},\ldots,u_{k-1})\in(\mathbb{R}^{n})^{k}$ and $\varepsilon\in\mathbb{R}_{>0}$ . We write $\Lambda_{c,k}^{r}(\varepsilon)\mathbf{u}_{k}$ instead of $\Lambda_{n,c,k}^{r}(\varepsilon,\mathbf{u}_{k})$ again when the dimension of $n$ is clear from context for the sake of convenience.

III Main results

In this section, we describe the homogeneity assumptions we make on the system and the stage cost, and how these allow to derive various scaling properties along homogeneous rays of the solutions, the stage cost and finally of the optimal value function.

III-A Homogeneous system

Consider the discrete-time nonlinear system

x^{+}=f(x,u),

(1)

where $x\in\mathbb{R}^{n_{x}}$ is the plant state, $u\in\mathbb{R}^{n_{u}}$ is the control input and $n_{x},n_{u}\in\mathbb{Z}_{>0}$ . We assume throughout the paper that $f=(f_{1},\ldots,f_{n_{x}}):\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\to\mathbb{R}^{n_{x}}$ satisfies the homogeneity property stated next.

Standing Assumption 1 (SA1)

There exist $\nu\in\mathbb{R}_{>0}$ , $r=(r_{1},\ldots,r_{n_{x}})\in\mathbb{R}_{>0}^{n_{x}}$ , and $q=(q_{1},\ldots,q_{n_{u}})\in\mathbb{R}_{>0}^{n_{u}}$ such that $f$ is homogeneous of degree $\nu\in\mathbb{R}_{>0}$ with respect to the dilation pair $(\lambda^{r},\lambda^{q})$ in the sense that for any $(x,u)\in\mathbb{R}^{n_{x}\times n_{u}}$ and $\varepsilon\in\mathbb{R}_{>0}$ , $f_{i}(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=\varepsilon^{r_{i}\nu}f_{i}(x,u)$ , or, equivalently, $f(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=\lambda^{r}(\varepsilon)^{\nu}f(x,u)$ . $\Box$

The homogeneity property in SA1 is inspired by [20, Definition 2] and extends it to vector fields with inputs. Some classes of vector fields $f$ satisfying SA1 are provided in Section V-A. Homogeneity definitions commonly found in the literature, as in, e.g., [8, 18], require $f_{i}(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=\varepsilon^{r_{i}+\nu}f(x,u)$ instead of $f_{i}(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=\varepsilon^{r_{i}\nu}f(x,u)$ as in SA1. The homogeneity notions in [20, Definition 2] and SA1 are better suited for vector fields arising in discrete-time dynamical systems. Indeed, they allow deriving scaling properties of the solutions as in [20, Lemma 3], which is extended below to systems equipped with inputs. In terms of notation, we use $\phi(k,x,\mathbf{u}_{d})$ to denote the solution to system (1) with initial condition $x$ and inputs sequence $\mathbf{u}_{d}\in{(\mathbb{R}^{n_{u}})^{d}}$ of length $d\geq k$ at time $k\in\{0,\ldots,d\}$ with the convention that $\phi(0,x,\cdot)=x$ .

Lemma 1

For any $x\in\mathbb{R}^{n_{x}}$ , $\varepsilon>0$ , $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $\mathbf{u}_{d}\in{(\mathbb{R}^{n_{u}})^{d}}$ and $k\in\mathbb{Z}_{\geq 0}$ with $k\leq d$ ,

\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d})=\lambda^{r}(\varepsilon)^{\nu^{k}}\phi(k,x,\mathbf{u}_{d}).

(2)

$\Box$

Proof: Let $x\in\mathbb{R}^{n_{x}}$ , $\varepsilon>0$ and $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ . We proceed by induction. Considering the definition of $\phi$ , we obtain

\phi(0,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d})=\lambda^{r}(\varepsilon)x,

(3)

which corresponds to (2) at $k=0$ . Furthermore, by the definitions of $\phi$ and $\Lambda^{q}_{\nu,{d}}$ , it follows that

\begin{split}&\phi(1,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d})\\ &{}=f\Big{(}\phi(0,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d}),\lambda^{q}(\varepsilon)u_{0}\Big{)}\\ &{}=f\Big{(}\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u_{0}\Big{)}.\end{split}

(4)

We derive from SA1

\begin{split}\phi(1,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d})&{}=\lambda^{r}(\varepsilon)^{\nu}f(x,u_{0})\\ &{}=\lambda^{r}(\varepsilon)^{\nu}\phi(1,x,\mathbf{u}_{d}),\end{split}

(5)

which corresponds to (2) for $k=1$ .

Suppose now that (2) holds for ${k}\in\mathbb{Z}_{\geq 0}$ . We have

\phi(k+1,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d})\\ {}=f\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}\mathbf{u}_{d}),\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}\Big{)}.

(6)

By assumption $\phi(k,\!\lambda^{r}(\varepsilon)x,\!\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d})\!=\!\lambda^{r}(\varepsilon)^{\nu^{k}}\!\phi(k,\!x,\!\mathbf{u}_{d})$ , thus

\phi(k+1,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d})\\ {}=f\Big{(}\lambda^{r}(\varepsilon)^{\nu^{k}}\phi(k,x,\mathbf{u}_{d}),\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}\Big{)}.

(7)

Noting that $\lambda^{r}(\varepsilon)^{\nu^{k}}=\lambda^{r}(\varepsilon^{\nu^{k}})$ and $\lambda^{q}(\varepsilon)^{\nu^{k}}=\lambda^{q}(\varepsilon^{\nu^{k}})$ in view of the definition of $\lambda^{r}$ , we derive that by SA1

\begin{split}&\phi(k+1,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d})\\ &{}=f\Big{(}\lambda^{r}(\varepsilon^{\nu^{k}})\phi(k,x,\mathbf{u}_{d}),\lambda^{q}(\varepsilon^{\nu^{k}})u_{k}\Big{)}\\ &{}=\lambda^{r}(\varepsilon^{\nu^{k}})^{\nu}f\Big{(}\phi(k,x,\mathbf{u}_{d}),u_{k}\Big{)}\\ &{}=\lambda^{r}(\varepsilon)^{\nu^{k+1}}f\Big{(}\phi(k,x,\mathbf{u}_{d}),u_{k}\Big{)}\\ &{}=\lambda^{r}(\varepsilon)^{\nu^{k+1}}\phi(k+1,x,\mathbf{u}_{d}),\end{split}

(8)

which corresponds to the desired property, namely (2) at $k+1$ . We have proved that when (2) holds for some $k\in\mathbb{Z}_{>0}$ , it also does for $k+1$ . The induction proof is complete.

$\blacksquare$

Lemma 1 provides an explicit relationship between the solutions to system (1) initialized on the same homogeneous ray (as defined in Section II), provided their successive inputs are appropriately scaled by the map $\Lambda^{q}_{\nu,{d}}$ .

Next, we introduce the cost function and the homogeneity properties we assume it satisfies.

III-B Homogeneous cost

We consider the cost function of horizon $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , for any $x\in\mathbb{R}^{n_{x}}$ and any sequence of inputs of length $d$ $\mathbf{u}_{d}\in{(\mathbb{R}^{n_{u}})^{d}}$ ,

J_{d,\gamma_{1},\gamma_{2}}(x,\mathbf{u}_{d}):=\displaystyle\sum_{k=0}^{d-1}\gamma_{1}^{\gamma_{2}^{k}}\ell\Big{(}\phi(k,x,\mathbf{u}_{d}),u_{k}\Big{)}\\ {}+\gamma_{1}^{\gamma_{2}^{d}}\jmath(\phi(d,x,\mathbf{u}_{d})),

(9)

where $\ell:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\to\overline{\mathbb{R}}_{\geq 0}$ is the stage cost, $\jmath:\mathbb{R}^{n_{x}}\to\overline{\mathbb{R}}_{\geq 0}$ is the terminal cost, moreover $\gamma_{1}\in\mathbb{R}_{>0}$ and $\gamma_{2}\in\mathbb{R}$ are weighting constants whose role is to capture the scaling effects due to homogeneity properties as it will be clarified in the sequel. When $d=\infty$ , $\jmath$ is the zero function. The stage and terminal costs $\ell$ and $\jmath$ are assumed to satisfy the next homogeneity property.

Standing Assumption 2 (SA2)

There exists $\mu\in\mathbb{R}$ such that $\ell$ and $\jmath$ are homogeneous of degree $\mu$ with respect to dilation pairs $(\lambda^{r},\lambda^{q})$ and $\lambda^{r}$ , respectively, in the sense that for any $(x,u)\in\mathbb{R}^{n_{x}\times n_{u}}$ and $\varepsilon\in\mathbb{R}_{>0}$ , $\ell(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=\varepsilon^{\mu}\ell(x,u)$ and $\jmath(\lambda^{r}(\varepsilon)x)=\varepsilon^{\mu}\jmath(x)$ . $\Box$

Examples of stage and terminal costs ensuring SA2 are given in Section V-B. The next result is a consequence of Lemma 1 and SA2.

Lemma 2

For any $x\in\mathbb{R}^{n_{x}}$ , $\varepsilon>0$ , $d\in\mathbb{Z}_{>0}$ , $\mathbf{u}_{d}\in{(\mathbb{R}^{n_{u}})^{d}}$ and $k\in\mathbb{Z}_{\geq 0}$ with $k\leq d-1$ , follows $\ell\!\left(\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d},\lambda^{q}(\varepsilon)^{\nu^{k}}\!u_{k}\right)\!=\varepsilon^{\mu\nu^{k}}\!\ell(\phi(k,x,\mathbf{u}_{d}),\allowbreak u_{k})$ and $\jmath\left(\phi({d},\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,{d}}(\varepsilon)\mathbf{u}_{d})\right)=\varepsilon^{\mu\nu^{d}}\jmath\left(\phi({d},x,\mathbf{u}_{d})\right)$ where $\nu$ , $\mu$ respectively come from SA1 and SA2. $\Box$

Proof: Let $x\in\mathbb{R}^{n_{x}}$ , $\varepsilon>0$ , $d\in\mathbb{Z}_{>0}$ , $k\in\{0,\ldots,d-1\}$ and $\mathbf{u}_{d}\in{(\mathbb{R}^{n_{u}})^{d}}$ . In view of (2), $\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d}),\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}\Big{)}=\ell\Big{(}\lambda^{r}(\varepsilon)^{\nu^{k}}\phi(k,x,\mathbf{u}_{d}),\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}\Big{)}$ . Since $\lambda^{r}(\varepsilon)^{\nu^{k}}=\lambda^{r}(\varepsilon^{\nu^{k}})$ and $\lambda^{q}(\varepsilon)^{\nu^{k}}=\lambda^{q}(\varepsilon^{\nu^{k}})$ , in view of SA2, $\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{d}),\lambda^{q}(\varepsilon^{\nu^{k}})u_{k}\Big{)}=\left(\varepsilon^{\nu^{k}}\right)^{\mu}\ell\Big{(}\phi(k,x,\mathbf{u}_{d}),u_{k}\Big{)}$ , which corresponds to the first equality in Lemma 2. We similarly derive the second equality in Lemma 2. $\blacksquare$

We are ready to analyse the optimal value function associated to (9).

III-C Scaling property of the optimal value function

Given $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $\gamma_{1}\in\mathbb{R}_{>0}$ , $\gamma_{2}\in\mathbb{R}$ and $x\in\mathbb{R}^{n_{x}}$ , we define the optimal value function associated to cost $J_{d,\gamma_{1},\gamma_{2}}$ at $x$ as

V_{d,\gamma_{1},\gamma_{2}}(x):=\displaystyle\min_{\mathbf{u}_{d}}J_{d,\gamma_{1},\gamma_{2}}(x,\mathbf{u}_{d}),

(10)

which is assumed to exist, per the next assumption.

Standing Assumption 3 (SA3)

For any $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $\gamma_{1}\in\mathbb{R}_{>0}$ , $\gamma_{2}\in\mathbb{R}$ and $x\in\mathbb{R}^{n_{x}}$ , there exists a $d$ -length sequence of inputs $\mathbf{u}_{{d}}^{\star}$ such that $V_{d,\gamma_{1},\gamma_{2}}(x)=J_{d,\gamma_{1},\gamma_{2}}(x,\mathbf{u}_{{d}}^{\star})<\infty$ . $\Box$

General conditions on $f$ and $\ell$ for SA3 to hold can be found in [10] for example.

The next theorem provides an explicit relationship on the optimal value function along homogeneous rays.

Theorem 1

For any $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $x\in\mathbb{R}^{n_{x}}$ , denote $\mathbf{u}_{{d}}^{\star}$ an optimal sequence of inputs for the cost $J_{d,1,1}$ at $x$ , then for any $\varepsilon>0$ ,

V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)=V_{d,1,1}(x),

(11)

where $\nu$ and $\mu$ respectively come from SA1-SA2, and $\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{{d}}^{\star}$ is an optimal sequence of inputs for cost $J_{d,\varepsilon^{-\mu},\nu}$ at $\lambda^{r}(\varepsilon)x$ , i.e., $J_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{{d}}^{\star})=V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)$ , or, equivalently, $V_{d,1,1}(\lambda^{r}(\varepsilon)x)=V_{d,\varepsilon^{\mu},\nu}(x)$ , and, for $\mathbf{u}_{{d}}^{\star}$ an optimal sequence of inputs for costs $J_{d,1,1}$ at $\lambda^{r}(\varepsilon)(x)$ , $\Lambda^{q}_{\nu,d}(\varepsilon^{-1})\mathbf{u}_{{d}}^{\star}$ is an optimal sequence of inputs for cost $J_{d,\varepsilon^{\mu},\nu}$ at $x$ , i.e., $J_{d,\varepsilon^{\mu},\nu}(x,\Lambda^{q}_{\nu,d}(\varepsilon^{-1})\mathbf{u}_{{d}}^{\star})=V_{d,\varepsilon^{\mu},\nu}(x)$ . $\Box$

Proof: Let $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $x\in\mathbb{R}^{n_{x}}$ , $\mathbf{u}_{{d}}^{\star}$ be an optimal sequence of inputs for cost $J_{d,1,1}$ at $x$ , which exists according to SA3, and let $\varepsilon\in\mathbb{R}_{>0}$ . From the definitions of $V_{d,1,1}$ , $\lambda^{r}$ , $\lambda^{q}$ and $\Lambda^{q}_{\nu,d}$ , we derive that

	$\displaystyle V_{d,1,1}(x)=\displaystyle\sum_{k=0}^{d-1}\ell\Big{(}\phi(k,x,\mathbf{u}_{{d}}^{\star}),u_{k}^{\star}\Big{)}+\jmath(\phi(d,x,\mathbf{u}_{{d}}^{\star}))$
	$\displaystyle{}=\displaystyle\sum_{k=0}^{d-1}\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon^{-1})\lambda^{r}(\varepsilon)x,\Lambda^{q}_{{\nu,d}}(\varepsilon^{-1})\Lambda^{q}_{{\nu,d}}(\varepsilon)\mathbf{u}_{{d}}^{\star}),$
	$\displaystyle{}\qquad\qquad\lambda^{q}(\varepsilon^{-1})^{\nu^{k}}\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}^{\star}\Big{)}$
	$\displaystyle{}+\jmath\left(\phi(d,\lambda^{r}(\varepsilon^{-1})\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon^{-1})\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{{d}}^{\star})\right).$		(12)

Hence, in view of Lemma 2 and by definition of $V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)$ , we have

	$\displaystyle V_{d,1,1}(x)$		(13)
	$\displaystyle{}=\displaystyle\sum_{k=0}^{d-1}\varepsilon^{-\mu\nu^{k}}\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{{\nu,d}}(\varepsilon)\mathbf{u}_{{d}}^{\star}),\lambda^{q}(\varepsilon)^{\nu^{k}}u_{k}^{\star}\Big{)}$
	$\displaystyle{}+\varepsilon^{-\mu\nu^{d}}\jmath\left(\phi(d,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\mathbf{u}_{{d}}^{\star})\right)\geq V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x).$

On the other hand,

	$\displaystyle V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)$	$\displaystyle=\displaystyle\sum_{k=0}^{d-1}\varepsilon^{-\mu\nu^{k}}\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\mathbf{v}_{{d}}^{\star}),v_{k}^{\star}\Big{)}$
		$\displaystyle\quad{}+\varepsilon^{-\mu\nu^{d}}\jmath(\phi(d,\lambda^{r}(\varepsilon)x),\mathbf{v}_{{d}}^{\star}),$		(14)

where $\mathbf{v}_{{d}}^{\star}$ is an optimal sequence of inputs for cost $J_{d,\varepsilon^{-\mu},\nu}$ at initial state $\lambda^{r}(\varepsilon)x$ , which exists by SA3. We have that

	$\displaystyle V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)$
	$\displaystyle{}=\displaystyle\sum_{k=0}^{d-1}\varepsilon^{-\mu\nu^{k}}\ell\Big{(}\phi(k,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{{\nu,d}}(\varepsilon)\Lambda^{q}_{{\nu,d}}(\varepsilon^{-1})\mathbf{v}_{{d}}^{\star}),$
	$\displaystyle\qquad\qquad\qquad\quad\lambda^{q}(\varepsilon)^{\nu^{k}}\lambda^{q}(\varepsilon^{-1})^{\nu^{k}}v_{k}^{\star}\Big{)}$		(15)
	$\displaystyle\quad{}+\varepsilon^{-\mu\nu^{d}}\jmath\Big{(}\phi(d,\lambda^{r}(\varepsilon)x,\Lambda^{q}_{\nu,d}(\varepsilon)\Lambda^{q}_{\nu,d}(\varepsilon^{-1})\mathbf{v}_{{d}}^{\star})\Big{)},$

from which we derive, in view of Lemma 2 and the definition of $V_{d,1,1}(x)$ ,

	$\displaystyle V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)$
	$\displaystyle=\displaystyle\sum_{k=0}^{d-1}\ell\Big{(}\phi(k,x,\Lambda^{q}_{{\nu,d}}(\varepsilon^{-1})\mathbf{v}_{{d}}^{\star}),\lambda^{q}(\varepsilon^{-1})^{\nu^{k}}v_{k}^{\star}\Big{)}$
	$\displaystyle\quad{}+\jmath\Big{(}\phi(d,x,\Lambda^{q}_{\nu,d}(\varepsilon^{-1})\mathbf{v}_{{d}}^{\star}))\Big{)}\geq V_{d,1,1}(x).$		(16)

We deduce from (III-C) and (16) that $V_{d,\varepsilon^{-\mu},\nu}(\lambda^{r}(\varepsilon)x)=V_{d,1,1}(x)$ . As a consequence, in view of the equality in (III-C), $\Lambda^{q}_{\nu,d}{(\varepsilon)}\mathbf{v}_{{d}}^{\star}$ is an optimal sequence of inputs for cost $J_{d,\varepsilon^{-\mu},\nu}$ at $\lambda^{r}(\varepsilon)x$ .

We now prove the last part of Theorem 1. Let $z:=\lambda^{r}(\varepsilon)x$ . In view of the first part, $V_{d,1,1}(z)=V_{d,\varepsilon^{\mu},\nu}(\lambda^{r}(\varepsilon^{-1})z)$ , which, by using the definition of $z$ , is equivalent to $V_{d,1,1}(\lambda^{r}(\varepsilon)x)=V_{d,\varepsilon^{\mu},\nu}(x)$ . We have obtained the desired result. $\blacksquare$

Theorem 1 provides a scaling-like property of the optimal value function along homogeneous rays. In particular, by computing $V_{d,1,1}$ and an associated sequence of optimal inputs at some $x\in\mathbb{R}^{n_{x}}\setminus\{0\}$ , we can deduce a scaled version of the optimal value function and an associated sequence of optimal inputs for any point on the homogeneous ray $\mathcal{R}_{r}(x)$ . However, the obtained optimal value function differs in general in Theorem 1, except in two specific cases formalized in the next corollary, the second one being novel, which is a direct application of Theorem 1.

Corollary 1

Suppose that either SA1 holds with $\nu=1$ or SA2 holds with $\mu=0$ . Then, for any $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $x\in\mathbb{R}^{n_{x}}$ , denote $\mathbf{u}_{{d}}^{\star}$ an optimal sequence of inputs for cost $J_{d,1,1}$ at $x$ , then for any $\varepsilon>0$

V_{d,1,1}(\lambda^{r}(\varepsilon)x)=\varepsilon^{\mu}V_{d,1,1}(x),

(17)

and $\Lambda^{q}_{1,d}(\varepsilon)\mathbf{u}_{{d}}^{\star}$ is an optimal sequence of inputs for cost $J_{d,1,1}$ at $\lambda^{r}(\varepsilon)x$ . $\Box$

Proof: Let $x\in\mathbb{R}^{n_{x}}$ and $\varepsilon>0$ . When SA1 holds with $\nu=1$ and $\mu\in\mathbb{R}$ , (11) gives

V_{d,\varepsilon^{-\mu},1}(\lambda^{r}(\varepsilon)x)=\varepsilon^{-\mu}V_{d,1,1}(\lambda^{r}(\varepsilon)x).

(18)

Hence, in view of (11),

V_{d,1,1}(\lambda^{r}(\varepsilon)x)=e^{\mu}V_{d,1,1}(x).

(19)

When SA2 holds with $\mu=0$ and $\nu\in\mathbb{R}_{>0}$ , (11) gives

V_{d,1,\nu}(\lambda^{r}(\varepsilon)x)=V_{d,1,1}(\lambda^{r}(\varepsilon)x).

(20)

Hence, in view of (11),

V_{d,1,1}(\lambda^{r}(\varepsilon)x)=V_{d,1,1}(x)

(21)

and the proof is complete. $\blacksquare$

In Corollary 1, the optimal value function is proportional along homogeneous rays under extra conditions compared to Theorem 1. As a result, by computing the optimal value function on any $n_{x}$ -sphere of $\mathbb{R}^{n_{x}}$ centered at the origin for instance and an associated sequence of optimal inputs, we can obtain the value of the optimal value function as well as a sequence of optimal inputs for any point in $\mathbb{R}^{n_{x}}\setminus\{0\}$ . Note that, by SA1-SA2, $f(0,0)=0$ and $\ell(0,0)=0$ , hence the optimal sequence at the origin is the 0 sequence of appropriate length, and $V_{d,\gamma_{1},\gamma_{2}}(0)=0$ for any $d\in\mathbb{Z}_{>0}\cup\{\infty\}$ , $\gamma_{1}\in\mathbb{R}_{>0}$ and $\gamma_{2}\in\mathbb{R}$ . The extra condition imposed by Corollary 1 is on the homogeneity degree of $f$ , which needs to be equal to $1$ , or on the one of $\ell$ and $\jmath$ , which needs to be equal to $0$ . The first case corresponds to [8, Proposition 2], up to the minor difference that here the cost can have an infinite horizon. The second case, namely when the homogeneity degree of $\ell$ and $\jmath$ is $0$ , is new as far as we know, and is important as it covers minimum time control and maximum hands off control as particular cases, as explained in more detail in Section V-B.

Remark 1

Theorem 1 may also be useful when the primary control objective is to constrain the state in a given set $\mathcal{S}\subset\mathbb{R}^{n_{x}}$ . This requirement can be incorporated in the definition of the stage cost using the function $\delta_{\mathcal{S}}^{\infty}$ , which is zero when the argument is in $\mathcal{S}$ and infinite elsewhere, as $\delta_{\mathcal{S}}$ satisfies the desired homogeneity property when $\mathcal{S}$ is homogeneous, as discussed in more details in Section V-B. In this case, even though the sequence of optimal inputs obtained at $x$ can be scaled to minimize another cost function on $\mathcal{R}_{r}(x)$ according to Theorem 1, the obtained sequence of inputs ensures the cost is bounded and thus that the solution remain in $\mathcal{S}$ for all future times. Indeed, if the solution for the scaled state did not remain in $\mathcal{S}$ , the scaled cost would be infinite from the cost incurred by $\delta_{\mathcal{S}}^{\infty}$ when the state is not in $\mathcal{S}$ . Since the scaled cost is finite, the state is always in $\mathcal{S}$ . $\Box$

IV Approximate VI scheme

We explain in this section how the scaling property of the optimal value function established in Theorem 1 can be exploited to derive a new approximation scheme for VI [2] for homogeneous systems and homogeneous costs satisfying SA1–SA3.

IV-A Value iteration

We recall that VI is an iterative procedure to solve optimal control problems [2]. We consider in this section an infinite-horizon cost, i.e., $d=\infty$ and $\jmath=0$ in (9), and the goal is to derive (near-)optimal sequence of inputs for any state $x\in\mathbb{R}^{n_{x}}$ . VI works as follows. Given an initial value function denoted $V_{0}:\mathbb{R}^{n_{x}}\to\mathbb{R}_{\geq 0}$ , at iteration $i+1\in\mathbb{Z}_{\geq 0}$ , an estimate of the optimal value function $V_{\infty,1,1}$ is obtained by solving, for any $x\in\mathbb{R}^{n_{x}}$ ,

V_{i+1}(x)=\displaystyle\min_{u}\left[\ell(x,u)+V_{i}(f(x,u))\right],

(22)

assuming the minimum exists. When solving (22), we can retrieve a minimizer $h_{i+1}(x)$ for any $x\in\mathbb{R}^{n_{x}}$ , which is used for control. Note that VI trivially accepts the finite-horizon case by initializing with $V_{0}=\jmath$ and stopping at $i=d$ , but we do not consider this case here for convenience.

To exactly solve (22) for any $x\in\mathbb{R}^{n_{x}}$ is in general impossible for system (1) and stage cost $\ell$ . Instead, most of the time we compute an approximation of $V_{i}$ on a compact set of interest, see, e.g., [4, 6]. The drawbacks of this approach are that (i) the selection of the compact set is not always rigorously established, (ii) the approximation is only defined on the considered set, (iii) we therefore need to make sure this set is forward invariant for the considered controlled system with the obtained control policy, which is not true in general, (iv) the computational cost may still be prohibitive. In the next section, we propose to exploit homogeneity to mitigate these issues.

IV-B Algorithm

The idea is to solve (22) only on a given compact set $\mathcal{D}$ and to derive the value of $V_{i}$ elsewhere in the state space thanks to Theorem 1, under SA1-SA3. The proposed algorithm works as follows.

The compact set $\mathcal{D}\subset\mathbb{R}^{n_{x}}$ is selected such that

\displaystyle\bigcup_{x\in\mathcal{D}}\mathcal{R}_{r}(x)=\mathbb{R}^{n_{x}}\setminus\{0\},

(23)

that is, the union of all possible dilations of $x\in\mathcal{D}$ spans $\mathbb{R}^{n_{x}}\setminus\{0\}$ . Examples of set $\mathcal{D}$ include the unit $n_{x}$ -sphere or $\left\{x\in\mathbb{R}^{n_{x}}\,:\,|x_{1}|^{\frac{1}{\mu r_{1}}}+\ldots+|x_{n_{x}}|^{\frac{1}{\mu r_{n_{x}}}}=1\right\}$ , where $(r_{1},\allowbreak\ldots,r_{n_{x}})$ come from SA1 and $\mu>0$ can take any value. Note that both of these examples are manifolds of degree $n_{x}-1$ while the state space is of dimension $n_{x}$ . Again, the origin is excluded in (23) as we know that the optimal value function is equal to $0$ in this case, as so are $f(0,0)$ and $\ell(0,0)$ in view of SA1-SA2.

We initialize the modified version of VI with $\underline{V}_{0}=\overline{V}_{0}=V_{0}$ where $V_{0}:\mathbb{R}^{n_{x}}\to\mathbb{R}_{\geq 0}$ is homogeneous of degree $\mu$ with respect to dilation pair $(\lambda^{r},\lambda^{q})$ , i.e., for any $x\in\mathbb{R}^{n_{x}}$ and any $\varepsilon>0$ , $V_{0}(\lambda^{r}(\varepsilon)x)=\varepsilon^{\mu}V_{0}(x)$ . We can simply take $V_{0}=0$ for instance. At iteration $i+1\in\mathbb{Z}_{\geq 0}$ , we generate a lower and an upper bound of $V_{i+1}$ in (22), which are respectively denoted $\underline{V}_{i+1}$ and $\overline{V}_{i+1}$ , like in relaxed dynamic programming [12]. In particular, $\underline{V}_{i}(0)=\overline{V}_{i}(0)=0$ and, for any $x\in\mathcal{D}$ and $\varepsilon>0$ ,

\left\{\begin{aligned} \underline{V}_{i+1}(x)&{}=\displaystyle\min_{u}\left[\ell(x,u)+\underline{V}_{i}(f(x,u))\right]\\ \underline{V}_{i+1}(\lambda^{r}(\varepsilon)x)&{}=\min\{\varepsilon^{\mu},\varepsilon^{\mu\nu^{i+1}}\}\underline{V}_{i+1}(x)\end{aligned}\right.

(24)

and

\left\{\begin{aligned} \overline{V}_{i+1}(x)&{}=\displaystyle\min_{u}\left[\ell(x,u)+\overline{V}_{i}(f(x,u))\right]\\ \overline{V}_{i+1}(\lambda^{r}(\varepsilon)x)&{}=\max\{\varepsilon^{\mu},\varepsilon^{\mu\nu^{i+1}}\}\overline{V}_{i+1}(x).\end{aligned}\right.

(25)

In both (24) and (25), VI equation (22) is only solved for $x$ in $\mathcal{D}$ . The values of $\underline{V}_{i}$ and $\overline{V}_{i}$ when $x\notin\mathcal{D}$ do not require solving (22): these are instead derived through the second equation of (24) and (25), respectively. Note that the two equations in (24) and (25) match when $\varepsilon=1$ as $\lambda^{r}(1)x=x$ .

Remark 2

Compared to classical VI (22), we only have to solve the first line of (24) and (25) in the given set $\mathcal{D}$ , e.g., in an $n_{x}$ -sphere centered at the origin. Moreover, an implementation of (22) in a forward invariant compact set will have the value functions defined only for states in such set, which in contrast the approximation scheme (24) and (25) provide values for the whole state space $\mathbb{R}^{n_{x}}$ , in view of their respective second line. However, executing the minimization exactly for all states in set $\mathcal{D}$ is still difficult in general, we will study the effect of the induced approximation errors in future work.

$\Box$

IV-C Guarantees

The next proposition ensures that $\underline{V}_{i}$ and $\overline{V}_{i}$ are indeed lower and upper bounds of $V_{i}$ on $\mathbb{R}^{n_{x}}$ .

Proposition 1

For any $i\in\mathbb{Z}_{\geq 0}$ and any $x\in\mathbb{R}^{n_{x}}$ ,

\underline{V}_{i}(x)\leq V_{i}(x)\leq\overline{V}_{i}(x),

(26)

where $V_{i}$ is defined by iteration (22) and is initialized with $\underline{V}_{0}(x)=V_{0}(x)=\overline{V}_{0}(x)$ . In addition, when $\mu=0$ or $\nu=1$ , $\underline{V}_{i}(x)=V_{i}(x)=\overline{V}_{i}(x)$ for any $x\in\mathbb{R}^{n_{x}}$ . $\Box$

Proof: In view of (24) and (25), $\underline{V}_{i}(0)=\overline{V}_{i}(0)=0$ . Since SA1-SA2 hold, $V_{i}(0)=0$ . Hence, we only need to prove that (26) holds for any $x\in\mathbb{R}^{n_{x}}\setminus\{0\}$ , which is equivalent to proving that, for any $x\in\mathcal{D}$ and $\varepsilon>0$ ,

\underline{V}_{i}(\lambda^{r}(\varepsilon)x)\leq V_{i}(\lambda^{r}(\varepsilon)x)\leq\overline{V}_{i}(\lambda^{r}(\varepsilon)x),

(27)

in view of the property of $\mathcal{D}$ in (23). We proceed by induction to prove (27).

$i=0$ . Property (27) holds as $\underline{V}_{0}=\overline{V}_{0}=V_{0}$ .

$i\Rightarrow i+1$ . We assume that (27) holds for $i\in\mathbb{Z}_{\geq 0}$ and we aim at proving that this is also satisfied for $i+1$ . Let $x\in\mathcal{D}$ and $\varepsilon>0$ . When $\varepsilon=1$ , in view of (24),

\underline{V}_{i+1}(x)=\displaystyle\min_{u}\left[\ell(x,u)+\underline{V}_{i}(f(x,u))\right].

(28)

By assumption $\underline{V}_{i}\leq V_{i}$ , thus, in view of (22),

\begin{split}\underline{V}_{i+1}(x)&{}\leq\displaystyle\min_{u}\left[\ell(x,u)+V_{i}(f(x,u))\right]\\ &{}=V_{i+1}(x).\end{split}

(29)

When $\varepsilon\neq 1$ , from (22),

$\displaystyle V_{i+1}(\lambda^{r}(\varepsilon)x)$	$\displaystyle{}=\displaystyle\min_{u}\left[\ell(\lambda^{r}(\varepsilon)x,u)+V_{i}(f(\lambda^{r}(\varepsilon)x,u))\right]$
	$\displaystyle{}=\displaystyle\min_{u}\left[\ell(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)\lambda^{q}(\varepsilon^{-1})u)\right.$	(30)
	$\displaystyle\qquad\left.{}+V_{i}(f(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)\lambda^{q}(\varepsilon^{-1})u))\right].$

We derive from SA1-2 and the fact that $\lambda^{q}(\varepsilon^{-1})\mathbb{R}^{n_{u}}=\mathbb{R}^{n_{u}}$ ,

	$\displaystyle V_{i+1}(\lambda^{r}(\varepsilon)x)$
	$\displaystyle{}=\displaystyle\min_{u}\left[\varepsilon^{\mu}\ell(x,\lambda^{q}(\varepsilon^{-1})u)+V_{i}(\lambda^{r}(\varepsilon)^{\nu}f(x,\lambda^{q}(\varepsilon^{-1})u))\right]$
	$\displaystyle{}=\displaystyle\min_{v}\left[\varepsilon^{\mu}\ell(x,v)+V_{i}(\lambda^{r}(\varepsilon)^{\nu}f(x,v))\right].$		(31)

Since $\underline{V}_{i}\leq V_{i}$ by assumption,

V_{i+1}(\lambda^{r}(\varepsilon)x)\geq\displaystyle\min_{v}\left[\varepsilon^{\mu}\ell(x,v)+\underline{V}_{i}(\lambda^{r}(\varepsilon)^{\nu}f(x,v))\right].

(32)

We have from (24) that $\underline{V}_{i}(\lambda^{r}(\varepsilon)^{\nu}f(x,v))=\min\{\varepsilon^{\mu\nu},\varepsilon^{\mu\nu^{i+1}}\}\underline{V}_{i}(f(x,v))$ for any $v\in\mathbb{R}^{n_{u}}$ , hence

	$\displaystyle V_{i+1}(\lambda^{r}(\varepsilon)x)$
	$\displaystyle{}\geq\displaystyle\min_{v}\left[\varepsilon^{\mu}\ell(x,v)+\min\{\varepsilon^{\mu\nu},\varepsilon^{\mu\nu^{i+1}}\}\underline{V}_{i}(f(x,v))\right]$
	$\displaystyle{}\geq\displaystyle\min\{\varepsilon^{\mu},\varepsilon^{\mu\nu},\varepsilon^{\mu\nu^{i+1}}\}\min_{v}\left[\ell(x,v)+\underline{V}_{i}(f(x,v))\right].$		(33)

Since $\min\{\varepsilon^{\mu},\varepsilon^{\mu\nu},\varepsilon^{\mu\nu^{i+1}}\}=\min\{\varepsilon^{\mu},\varepsilon^{\mu\nu^{i+1}}\}$ and in view of (24),

\begin{split}V_{i+1}(\lambda^{r}(\varepsilon)x)&{}\geq\displaystyle\min\{\varepsilon^{\mu},\varepsilon^{\mu\nu^{i+1}}\}\underline{V}_{i+1}(x)\\ &{}=\underline{V}_{i+1}(\lambda^{r}(\varepsilon)x).\end{split}

(34)

The proof that $V_{i+1}(\lambda^{r}(\varepsilon)x)\leq\overline{V}_{i+1}(\lambda^{r}(\varepsilon)x)$ follows similar lines as above. Consequently, (27) holds for $i+1$ . The proof by induction is complete: (26) is guaranteed.

When $\mu=0$ or $\nu=1$ , $\varepsilon^{\mu}=\varepsilon^{\mu\nu^{i}}$ for any $i\in\mathbb{Z}_{\geq 0}$ . Hence, since $\underline{V}_{0}=\overline{V}_{0}=V_{0}$ , we derive from (24) and (25) that $\underline{V}_{i}(x)=\overline{V}_{i}(x)$ for any $i\in\mathbb{Z}_{\geq 0}$ and $x\in\mathbb{R}^{n_{x}}$ . Consequently, $\underline{V}_{i}(x)=\overline{V}_{i}(x)=V_{i}(x)$ for any $i\in\mathbb{Z}_{\geq 0}$ and $x\in\mathbb{R}^{n_{x}}$ in view of (26). $\blacksquare$

Proposition 1 ensures that the exact value function given by VI at any iteration $i\in\mathbb{Z}_{\geq 0}$ , i.e., $V_{i}$ in (22) is lower and upper-bounded by $\underline{V}_{i}$ and $\overline{V}_{i}$ as defined in (24) and (25), respectively. We can then exploit these bounds to construct a control law by taking, at any iteration $i\in\mathbb{Z}_{\geq 0}$ and for any $x\in\mathbb{R}^{n_{x}}$ ,

\hat{h}_{i}(x)\in\displaystyle\min_{u}\left[\ell(x,u)+\widehat{V}_{i}(f(x,u))\right],

(35)

where $\widehat{V}_{i}:\mathbb{R}^{n_{x}}\to\mathbb{R}$ is any function such that $\underline{V}_{i}\leq\widehat{V}_{i}\leq\overline{V}_{i}$ . Compared to relaxed dynamic programming [12] where lower and upper-bounds on $V_{i}$ are used to derive near-optimal inputs, $\underline{V}_{i}$ and $\overline{V}_{i}$ in (24) and (25) do not require to solve minimization problems on the whole state space, but only on $\mathcal{D}$ , which is favourable for practical implementation. Moreover, when $\mu=0$ or $\nu=1$ as in Corollary 1, we only need to solve (22) on $\mathcal{D}$ at each iteration to deduce the value of $V_{i}$ on the whole state space $\mathbb{R}^{n_{x}}$ , in view of the last part of Proposition 1. We investigate numerically the tightness of the bounds of the proposed scheme in Section VI.

V Ensuring the standing assumptions

In this section, we provide examples of vector fields $f$ in (1) and stage cost $\ell$ , which verify SA1-2. SA3, on the other hand, can be analysed using the results in [10] as already mentioned.

V-A Standing Assumption 1

The next result may be used to ensure the satisfaction of SA1.

Proposition 2

Suppose that there exist $r=(r_{1},\ldots,r_{n_{x}})\in\mathbb{R}^{n_{x}}_{>0}$ , $q=(q_{1},\ldots,q_{n_{u}})\in\mathbb{R}^{n_{u}}_{>0}$ , scalar fields $g_{i,j}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\to\mathbb{R}$ that are homogeneous of degree $\nu_{i,j}$ with respect to a dilation pair $(\lambda^{r},\lambda^{q})$ and $N\in\mathbb{Z}_{>0}$ such that, for any $i\in\{1,\ldots,n_{x}\}$ and $(x,u)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}$ ,

f_{i}(x,u)=\displaystyle\sum_{j=0}^{N}g_{i,j}(x,u).

(36)

For any $(x,u,w)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\times\mathbb{R}$ , the vector field $\tilde{f}=(\tilde{f}_{1},\ldots,\tilde{f}_{n_{x}},\tilde{f}_{n_{x}+1})$ with

\begin{split}\tilde{f}_{i}(x,w,u)&{}=\displaystyle\sum_{j=0}^{N}w^{(r_{i}\nu-\nu_{i,j})\nu}g_{i,j}(x,u)\\ \tilde{f}_{n_{x}+1}(x,w,u)&{}=\lceil{w}\rfloor^{\nu},\end{split}

(37)

and $\nu:=\displaystyle 1+\max\left\{\frac{\nu_{i,j}}{r_{i}}\,:\,(i,j)\in\{1,\ldots,n_{x}\}\times\{1,\ldots,N\}\right\}\allowbreak\in\mathbb{Z}_{>0}$ , satisfies SA1, in particular it is homogeneous of degree $\nu\in\mathbb{Z}$ with respect to the dilation pair $(\lambda^{(r,1/\nu)},\lambda^{q})$ .

$\Box$

Proof: Let $(x,u,w)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\times\mathbb{R}$ and $\varepsilon>0$ . From the homogeneity property of $g_{i,j}$ for any $(i,j)\in\{1,\ldots,n_{x}\}\times\{1,\ldots,N\}$ ,

\begin{split}&\tilde{f}_{i}(\lambda^{r}(\varepsilon)x,\lambda^{1/\nu}(\varepsilon)w,\lambda^{q}(\varepsilon)u)\\ &{}=\displaystyle\sum_{j=0}^{N}\varepsilon^{r_{i}\nu-\nu_{i,j}}w^{(r_{i}\nu-\nu_{i,j})\nu}\varepsilon^{\nu_{i,j}}g_{i,j}(x,u)\\ &{}=\varepsilon^{r_{i}\nu}\displaystyle\sum_{j=0}^{N}w^{(r_{i}\nu-\nu_{i,j})\nu}g_{i,j}(x,u)\\ &{}=\varepsilon^{r_{i}\nu}\tilde{f}_{i}(x,w,u).\end{split}

(38)

On the other hand, $\tilde{f}_{n_{x}+1}(\lambda^{r}(\varepsilon)x,\lambda^{1/\nu}(\varepsilon)w,\lambda^{q}(\varepsilon)u)=\lceil{\varepsilon^{1/\nu}w}\rfloor^{\nu}=\varepsilon\lceil{w}\rfloor^{\nu}=\varepsilon^{\nu\frac{1}{\nu}}\tilde{f}_{n_{x}+1}(x,w,u)$ . Hence, $\tilde{f}$ is homogeneous of degree $\nu\in\mathbb{Z}$ with respect to dilation pair $(\lambda^{(r,1/\nu)},\lambda^{q})$ , which concludes the proof. $\blacksquare$

Proposition 2 implies that when the components of $f$ , namely the $f_{i}$ ’s, can be written as the sum of (scalar) homogeneous functions with respect to the same dilation pair, SA1 can always be ensured by adding a variable $w$ , whose dynamics is $w^{+}=\lceil{w}\rfloor^{\nu}$ . By initializing $w$ at $1$ , we note that $w(k)=1$ for any $k\in\mathbb{Z}_{\geq 0}$ and we have $f(x,u)=(\tilde{f}_{1}(x,1,u),\ldots,\tilde{f}_{n_{x}}(x,1,u))$ . The idea to add the extra dynamics $w$ to ensure the desired homogeneity property is common in the homogeneous systems literature, see for instance [1] where a different homogeneity property is studied for polynomial vector fields. Notice that there is no loss of generality by considering the same integer $N$ for all components $\tilde{f}_{i}$ of $f$ in (36) as we can always add zero-valued functions if needed.

Proposition 2 applies to polynomial vector fields as a particular case. Indeed, suppose $f$ is a polynomial vector field of degree $d\in\mathbb{Z}_{\geq 0}$ , then $f_{i}$ can be written as in (36) with $N=\left(\begin{array}[]{c}n_{x}+n_{u}+d\\ d\end{array}\right)-1$ and $g_{i,j}$ are monomials of $(x,u)$ multiplied by a constant. Proposition 2 also covers the case where $f$ is a rational function of components of $(x,u)$ using the same technique as in [1].

Proposition 2 reduces the homogeneity analysis of $f$ to those of the components of $f_{i}$ , which may be derived from the next simple though useful lemma. Its proof directly follows from the homogeneity properties of the considered functions and is therefore omitted.

Lemma 3

Consider homogeneous scalar functions $g_{1},g_{2}:\mathbb{R}\to\mathbb{R}$ of degree $\nu_{1}$ and $\nu_{2}$ respectively, then

(i)

for any $\lambda\in\mathbb{R}$ , $\lambda g_{1}$ is homogeneous of degree $\nu_{1}$ ,
(ii)

$g_{1}\circ g_{2}$ is homogeneous of degree $\nu_{1}+\nu_{2}$ ,
(iii)

$(z_{1},z_{2})\mapsto g_{1}(z_{1})g_{2}(z_{2})$ is homogeneous of degree $\nu_{1}+\nu_{2}$ ,
(iv)

$(z_{1},z_{2},w)\mapsto w^{\max(\nu_{1},\nu_{2})}\left(w^{-\nu_{1}}g_{1}(z_{1})+w^{-\nu_{2}}g_{2}(z_{2})\right)$ is homogeneous of degree $\max(\nu_{1},\nu_{2})$ . $\Box$

Examples of functions $g_{1}$ and $g_{2}$ as in Lemma 3 include $z\mapsto z^{a}$ with $a\in\mathbb{Z}_{>0}$ , $z\mapsto\lceil{z}\rfloor^{a}$ with $a\in\mathbb{R}_{>0}$ , ReLU functions $z\mapsto\max(0,z)$ and $z\mapsto\max(z,\epsilon z)$ with $\epsilon\in(0,1)$ to mention a few. In view of Lemma 3, any vector field $f=(f_{1},\ldots,f_{n_{x}})$ which involves compositions, products or linear combinations of such elementary homogeneous functions can be suitably modified using variable $w$ as in Proposition 2 to ensure the satisfaction of SA1.

V-B Standing Assumption 2

First, we have the next lemma, which shows that the linear combination of homogeneous stage (terminal) costs of different degrees but with respect to the same dilation pair can be modified by adding an extra dummy variable $w$ as in Proposition 2 to ensure the satisfaction of SA2.

Lemma 4

Let $m\in\mathbb{Z}_{>0}$ and $\ell_{1},\ldots,\ell_{m}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\to\overline{\mathbb{R}}_{\geq 0}$ (respectively, $\jmath_{1},\ldots,\jmath_{m}:\mathbb{R}^{n_{x}}\to\overline{\mathbb{R}}_{\geq 0}$ ) be homogeneous with respect to a dilation pair $(\lambda^{r},\lambda^{q})$ (respectively, $\lambda^{r}$ ) of degree $\mu_{1},\ldots,\mu_{m}\in\mathbb{Z}_{\geq 0}$ . Let $\mu=\max\{\mu_{i}\,:\,i\in\{1,\ldots,m\}\}$ . Then, for any $(x,w,u)\in\mathbb{R}^{n_{x}+1}\times\mathbb{R}^{n_{u}}$ , $\ell(x,w,u)=\displaystyle\sum_{i=1}^{m}w^{\mu-\mu_{i}}\ell_{i}(x,u)$ is homogeneous of degree $\mu$ with respect to the dilation pair $(\lambda^{(r,1)},\lambda^{q})$ (respectively, $\jmath(x,w,u)=\displaystyle\displaystyle\sum_{i=1}^{m}w^{\mu}\jmath_{i}(x)$ is homogeneous of degree $\mu$ with respect to $\lambda^{(r,1)}$ ). When $\mu_{1}=\ldots=\mu_{m}=\mu$ , $\ell=\displaystyle\sum_{i=1}^{m}\ell_{i}$ is homogeneous of degree $\mu$ with respect to the dilation pair $(\lambda^{r},\lambda^{q})$ (respectively, $\jmath=\displaystyle\displaystyle\sum_{i=1}^{m}\jmath_{i}$ is homogeneous of degree $\mu$ with respect to $\lambda^{r}$ ). $\Box$

Proof: Let $(x,w,u)\in\mathbb{R}^{n_{x}+1}\times\mathbb{R}^{n_{u}}$ and $\varepsilon>0$ . In view of the homogeneity properties of $\ell_{1},\ldots,\ell_{m}$ ,

	$\displaystyle\ell(\lambda^{r}(\varepsilon)x,\lambda^{1}(\varepsilon)w,\lambda^{q}(\varepsilon)u)$	$\displaystyle{}=\displaystyle\sum_{i=1}^{m}\varepsilon^{\mu-\mu_{i}}w^{\mu-\mu_{i}}\varepsilon^{\mu_{i}}\ell_{i}(x,u)$
		$\displaystyle{}=\displaystyle\varepsilon^{\mu}\ell(x,w,u).$		(39)

We have proved that $\ell$ is homogeneous of degree $\mu$ with respect to dilation pair $(\lambda^{(r,1)},\lambda^{q})$ . When $\mu_{1}=\ldots=\mu_{m}=\mu$ , we directly derive the desired result from the above development. Finally, the case of $\jmath$ similarly follow. $\blacksquare$

The next lemma provides a condition for the dilation maps from SA1 under which SA2 is verified with quadratic(-like) costs.

Lemma 5

The following holds.

(i)

Let $\ell:(x,u)\mapsto|x|_{Q}+|u|_{R}$ , where $Q=Q^{\top}\geq 0$ , $R=R^{\top}\geq 0$ . For any $\mu\in\mathbb{Z}_{>0}$ , SA2 holds with degree $2\mu$ and for any dilation pair $(\lambda^{r},\lambda^{q})$ of the form $r=\mu(1,\ldots,1)\in\mathbb{R}^{n_{x}}$ and $q=\mu(1,\ldots,1)\in\mathbb{R}^{n_{u}}$ .
(ii)

For any $r=(r_{1},\ldots,r_{n_{x}})\in\mathbb{R}^{n_{x}}_{>0}$ , $q=(q_{1},\ldots,\allowbreak q_{n_{u}})\in\mathbb{R}^{n_{u}}_{>0}$ , $\mu\in\mathbb{Z}_{>0}$ , $Q=Q^{\top}\geq 0$ , and $R=R^{\top}\geq 0$ , $\displaystyle\ell:(x,u)\mapsto\left|\left(\lceil{x_{1}}\rfloor^{\frac{\mu}{2r_{1}}},\ldots,\lceil{x_{n_{x}}}\rfloor^{\frac{\mu}{2r_{n_{x}}}}\right)\right|_{Q}+\left|\left(\lceil{u_{1}}\rfloor^{\frac{\mu}{2q_{1}}},\ldots,\lceil{u_{n_{u}}}\rfloor^{\frac{\mu}{2r_{n_{u}}}}\right)\right|_{R}$ satisfies SA2 with degree $\mu$ and dilation pair $(\lambda^{r},\lambda^{q})$ . $\Box$

Proof: Let $(x,u)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}$ and $\varepsilon>0$ .

Item (i): From the definitions of $\ell$ , $r$ and $q$ , we have

	$\displaystyle\ell(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)$	$\displaystyle{}=\left\|(\varepsilon^{\mu}x)\right\|_{Q}+\left\|(\varepsilon^{\mu}u)\right\|_{R}$
		$\displaystyle{}=\displaystyle\varepsilon^{2\mu}\ell(x,u),$		(40)

from which we derive that $\ell$ is homogeneous of degree $2\mu$ with respect to dilation pair $(\lambda^{p},\lambda^{q})$ .

Item (ii): From the definitions of $\ell$ , $r$ and $q$ , we have

\begin{array}[]{rlll}\ell(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)&=&\displaystyle\sum_{i=1}^{n_{x}}\theta_{i}\varepsilon^{2\mu}x_{i}^{2}+\sum_{j=1}^{n_{u}}\vartheta_{j}\varepsilon^{2\mu}u_{j}^{2}\\ &=&\displaystyle\varepsilon^{2\mu}\ell(x,u),\end{array}

(41)

from which we derive that $\ell$ is homogeneous of degree $2\mu$ with respect to dilation pair $(\lambda^{p},\lambda^{q})$ .

Item (ii): Let $r=(r_{1},\ldots,r_{n_{x}})\in\mathbb{R}^{n_{x}}_{>0}$ , $q=(q_{1},\ldots,q_{n_{u}})\in\mathbb{R}^{n_{u}}_{>0}$ , $\mu\in\mathbb{Z}_{>0}$ , $Q=Q^{\top}\geq 0$ , and $R=R^{\top}\geq 0$ . Since, for any $z\in\mathbb{R}$ and $c_{1},c_{2}\in\mathbb{R}_{>0}$ , $\lceil{c_{1}z_{1}z_{2}}\rfloor^{c_{2}}=c_{1}^{c_{2}}\lceil{z_{1}}\rfloor^{c_{2}}$ in view of the definition of $\lceil{\cdot}\rfloor$ , we derive

\begin{split}&\ell(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)\\ &{}=\left|\left(\lceil{\varepsilon^{r_{1}}x_{1}}\rfloor^{\frac{\mu}{2r_{1}}},\ldots,\lceil{\varepsilon^{r_{n_{x}}}x_{n_{x}}}\rfloor^{\frac{\mu}{2r_{n_{x}}}}\right)\right|_{Q}\\ &\quad{}+\left|\left(\lceil{\varepsilon^{q_{1}}u_{1}}\rfloor^{\frac{\mu}{2q_{1}}},\ldots,\lceil{\varepsilon^{q_{n_{u}}}u_{n_{u}}}\rfloor^{\frac{\mu}{2r_{n_{u}}}}\right)\right|_{R}\\ &{}=\varepsilon^{\mu}\ell(x,u).\end{split}

(42)

Hence $\ell$ is homogeneous of degree $\mu$ with respect to dilation pair $(\lambda^{r},\lambda^{q})$ . $\blacksquare$

Item (i) of Lemma 5 shows that quadratic stage costs satisfy SA2 when SA1 holds with $r_{1}=\ldots=r_{n_{x}}=q_{1}=\ldots=q_{n_{u}}$ . When the dilation pair does not satisfy this property, the stage cost can always be modified as in item (ii) of Lemma 5 to enforce SA2. This change of cost was proposed in the paragraph before [8, Proposition 1], except that the function $\lceil{\cdot}\rfloor$ is used here instead of the absolute value for generality. Regarding the terminal cost $\jmath$ , the results of Lemma 5 apply by setting $R=0$ .

We have seen at the end of Section III that having a stage cost and a terminal cost of homogeneity degree $0$ can be exploited to simplify the computation of the optimal value functions and of a sequence of optimal inputs for any $x\in\mathbb{R}^{n_{x}}$ . It appears that the examples of stage and terminal costs in Lemma 3 are not homogeneous of degree zero. The next lemma provides relevant examples ensuring homogeneity with degree $0$ , but before that we need to recall the notion of homogeneous sets.

Definition 1

Let $r=(r_{1},\ldots,r_{n_{x}})\in\mathbb{R}^{n_{x}}_{>0}$ . A set $\mathcal{S}\subseteq\mathbb{R}^{n_{x}}$ is homogeneous with respect to a dilation $\lambda^{r}$ when, for any $x\in\mathbb{R}^{n_{x}}$ , $x\in\mathcal{S}$ if and only is $\lambda^{r}(\varepsilon)x\in\mathcal{S}$ . $\Box$

We write for short that a set is homogeneous when there exists a dilation with respect to which it is homogeneous. Examples of homogeneous sets include $\{0\}$ and $\text{vect}(e_{i_{1}},\ldots,e_{i_{m}})$ where $i_{1},\ldots,i_{m}\in\{1,\ldots,n_{x}\}$ and $e_{1},\ldots,e_{n_{x}}$ are the standard unit vectors of $\mathbb{R}^{n_{x}}$ for any dilation map. We are ready to present examples of functions, which can be used to define stage and terminal costs ensuring SA2 with $0$ -homogeneity degree.

Lemma 6

Let $t=(t_{1},\ldots,t_{m})\in\mathbb{R}^{m}$ with $m\in\mathbb{Z}_{>0}$ and $\mathcal{S}\subseteq\mathbb{R}^{m}$ be a homogeneous set with respect to $\lambda^{t}$ . For any $c\in\overline{}\mathbb{R}_{\geq 0}$ , $\delta^{c}_{\mathcal{S}}$ is homogeneous of degree $0$ with respect to dilation $\lambda^{t}$ . $\Box$

Proof: Let $y\in\mathbb{R}^{m}$ , $c\in\overline{}\mathbb{R}_{\geq 0}$ and $\varepsilon>0$ , $\delta^{c}_{\mathcal{S}}(\lambda^{t}(\varepsilon)y)=0$ when $\lambda^{t}(\varepsilon)y\in\mathcal{S}$ , which is equivalent to $y\in\mathcal{S}$ by homogeneity of $\mathcal{S}$ , and $\delta^{c}_{\mathcal{S}}(\lambda^{t}(\varepsilon)y)=c$ when $y\not\in\mathcal{S}$ for the same reason. Hence $\delta^{c}_{\mathcal{S}}(\lambda^{t}(\varepsilon)y)=\delta^{c}_{\mathcal{S}}(y)$ , which corresponds to the desired result. $\blacksquare$

In view of Lemma 6 and the fact that the linear combination of $0$ -degree homogeneous functions is homogeneous of degree $0$ in view of Lemma 4, we derive that important optimal control problems correspond to the stage and terminal costs of degree $0$ including

•

minimum time control to a homogeneous set $\mathcal{S}_{x}\subset\mathbb{R}^{n_{x}}$ , in which case $d=\infty$ , $\ell=\delta^{1}_{\mathcal{S}_{x}}$ and thus $\jmath=0$ ,
•

maximum hands off control where the objective is to drive the state in a given homogeneous set $\mathcal{S}_{x}\subset\mathbb{R}^{n_{x}}$ in $d\in\mathbb{Z}_{>0}$ steps while using a zero input as frequently as possible, see [15, 14]. In this case, $\ell(x,u)=|u|_{0}$ for any $(x,u)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}$ and $\jmath=\delta^{\infty}_{\mathcal{S}_{x}}$ ; noting that the $\ell_{0}$ norm is also homogeneous of degree $0$ with respect to any dilation map.

VI Numerical case study

We illustrate the results of Section V. In particular, we study how conservative the bounds in Proposition 1 are.

VI-A System and cost

We consider the optimal control of the discretized model of a van der Pol oscillator using Euler’s direct method, $(x_{1}^{+},x_{2}^{+})=(x_{1}+Tx_{2},x_{2}+T(a(1-x_{1}^{2})x_{2}-bx_{1}+u))$ where $x_{1},x_{2}\in\mathbb{R}$ are the states, $u\in\mathbb{R}$ is the control input, $a,b\in\mathbb{R}_{>0}$ is a parameter and $T\in\mathbb{R}_{>0}$ is the sampling period used for discretization.

To ensure the satisfaction of SA1, we add a variable $x_{3}$ so that the extended system is of the form of (1) with $x:=(x_{1},x_{2},x_{3})$ and $f(x,u):=(x_{1}x_{3}^{2}+Tx_{2}x_{3}^{2},x_{2}x_{3}^{2}+Ta(x_{3}^{2}-x_{1}^{2})x_{2}-Tbx_{1}x_{3}^{2}+Tu,x_{3}^{3})$ . Like in Proposition 2, by initializing $x_{3}(0)=1$ , the $(x_{1},x_{2})$ -component of the solutions to (1) with $f$ defined above matches the solution to the original system initialized at the same point and, with a careful choice of the stage cost in the sequel, will solve the same optimal control problem. The vector field $f$ satisfies SA1 with $r=(1,1,1)$ , $q=3$ and $\nu=3$ . Indeed, for any $x\in\mathbb{R}^{3}$ , $u\in\mathbb{R}$ and $\varepsilon>0$ , $f(\lambda^{r}(\varepsilon)x,\lambda^{q}(\varepsilon)u)=(\varepsilon^{3}x_{1}x_{3}^{2}+T\varepsilon^{3}x_{2}x_{3}^{2},\varepsilon^{3}x_{2}x_{3}^{2}+Ta\varepsilon^{3}(x_{3}^{2}-x_{1}^{2})x_{2}-Tb\varepsilon^{3}x_{1}x_{3}^{2}+\varepsilon^{3}Tu,\varepsilon^{3}x_{3}^{3})=\lambda^{r}(\varepsilon)^{3}f(x,u).$ We fix $a=b=T=1$ in the sequel.

We choose a quadratic stage cost. Hence, for any $x\in\mathbb{R}^{3}$ and $u\in\mathbb{R}$ , let $\ell(x,u):=|x|_{Q}+|u|_{R}$ with $Q:=\text{diag}(1,1,0)\geq 0$ and $R:=1$ . By item (i) of Proposition 5, $\ell$ is homogeneous of degree $\mu=2$ . Hence, SA2 is verified with $\mu=2$ . Note that there is no cost associated to the component $x_{3}$ in either the stage or the terminal cost as we wish for the incurred cost along solutions of $f$ to coincide with the original system when $x_{3}=1$ . We also need to check that SA3 holds. We apply [10, Theorem 2] for this purpose. Indeed, items a) to c) of [10, Theorem 1] hold. Furthermore, item $d_{3})$ of [10, Theorem 2] is satisfied as $|u|\leq\ell(x,u)$ , hence $u\to\infty$ implies $\ell(x,u)\to\infty$ for any $x\in\mathbb{R}^{3}$ . The last condition to check is item e) of [10, Theorem 2], i.e., that for any initial condition there is a sequence of inputs which makes the cost $J_{\infty,\gamma_{1},\gamma_{2}}$ finite. For any $x\in\mathbb{R}^{3}$ , we can construct a linearizing feedback that brings the state to the set $\left\{x\in\mathbb{R}^{3}:x_{1}=x_{2}=0\right\}$ in at most two steps, while the trivial input $\mathbf{u}_{\infty}=0$ has cost $J_{\infty,\gamma_{1},\gamma_{2}}((0,0,x_{3}),\mathbf{u}_{\infty})=0$ for any $x_{3}\in\mathbb{R}$ . Therefore an infinite sequence with finite cost exists, and by invoking [10, Theorem 2] we conclude that $V_{d,\gamma_{1},\gamma_{2}}$ exists and SA3 holds.

All the required conditions hold, we can thus apply Proposition 1. We will do so by taking $V_{0}(x):=\underline{V}_{0}(x):=\overline{V}_{0}(x):=|x|_{P}$ for any $x\in\mathbb{R}^{3}$ , where $P\geq 0$ is derived as the LQ optimal cost of the original system linearized around the origin. That is, $P:=\left((6.8,4,0),(4,11.5,0),(0,0,0)\right)$ . Note that $x\mapsto|x|_{P}$ is indeed homogeneous of degree $\mu=2$ , in view of Proposition 5.

VI-B Numerical implementation

We first describe the details of the implementation of the new algorithm in Section IV-B. We take the compact set $\mathcal{D}:=\{x\in\mathbb{R}^{3},|x|=1.5\}$ , which verifies (23).

Because we do not know how to solve the minimization steps in (24) and (25) analytically in general, we proceed numerically. We rewrite the problem in polar coordinates and we consider a finite difference approximation of $N=501^{2}$ points equally distributed in $[-\pi,\pi]\times\left[0,\dfrac{\pi}{2}\right]$ , representing the azimuth and elevation angles of the upper-hemisphere of $\mathcal{D}$ , and $M=501$ equally distributed quantized inputs in $[-5,5]$ .

To evaluate the accuracy of the proposed algorithm, we need to compute $V_{i}$ given by standard VI with $V_{0}(x):=|x|_{P}$ . We consider for this purpose a finite difference approximation of $N=501^{2}$ points equally distributed in $\mathcal{X}:=[-1,1]\times[-1,1]\times\{1\}$ for the state space, and $M=501$ equally distributed quantized inputs in $[-3,3]$ centered at $0$ . Note that the classical VI only produces the value function on $\mathcal{X}$ , contrary to $\underline{V_{1}}(x)$ and $\overline{V_{1}}(x)$ which are defined for any $x\in\mathbb{R}^{3}$ . Moreover, this issue is exacerbated at certain points $x\in\mathcal{X}$ where $f(x,u)\not\in\mathcal{X}$ for all $u\in[-3,3]$ . For standard (approximate) VI schemes to be well defined, an unclear but consequential assessment has to be made to assign values for $V_{0}(f(x,u))$ when $f(x,u)\not\in\mathcal{X}$ .

VI-C Results

We illustrate the difference between $V_{1}(x)$ and $\underline{V_{1}}(x)$ for $x\in\mathcal{X}$ in Figure 1, and similarly Figure 2 shows the difference between $\overline{V_{1}}(x)$ and $V_{1}(x)$ . As expected, $\underline{V_{1}}(x)$ and $\overline{V_{1}}(x)$ under and over estimate $V_{1}(x)$ , respectively. We note from Figure 1 that the error is small near the intersection of set $\mathcal{D}$ and $\mathbb{R}^{2}\times\{1\}$ , which is expected as it corresponds to points where the minimization in (24) and (25) coincides with (22). We have then a circle of radius $\sqrt{1.5^{2}-1}=1.12$ where the error is small, and grows when moving to points outside this circle. The error near the origin is also small despite not being part of $\mathcal{D}$ , which is explained by the fact that $V_{1}$ , $\underline{V}_{1}$ and $\overline{V}_{1}$ vanish at the origin. Similar observations can be made for the upper bound in Figure 2, even when varying the size of the radius for the compact set $\mathcal{D}$ , that is, by taking $\mathcal{D}:=\{x\in\mathbb{R}^{3},|x|=r\}$ for different values of $r>0$ . Hence, by exploiting homogeneity, we have a VI scheme that is calculated only for points in the compact set $\mathcal{D}$ but has analytical guarantees for any state in $\mathbb{R}^{n_{x}}$ , and not just for states in (the forward invariant subset) of $\mathcal{X}$ as in the classical VI implementation.

Refer to caption — Figure 1: Difference between ${V_{1}}(x)$ and $\underline{V}_{1}(x)$ for $x\in\mathcal{X}$

VII Concluding remarks

In this work, we have first adapted the homogeneity notion for discrete-time systems proposed in [20] to be applicable to systems with inputs. We have then provided several scaling properties of the system, cost and optimal value function. The latter is particularly important as it implies that we only need to solve the original optimal control problem on a given compact manifold of dimension strictly smaller than the dimension of the state space to derive (near-)optimal inputs for any state. We then exploit this observation to derive a new approximation scheme for VI.

Future work will include further investigation of the error of approximation when solving VI on the set $\mathcal{D}$ in Section IV, as well as other ways to construct upper and lower bounds of the function generated by VI.

References

[1] J. Baillieul. The geometry of homogeneous polynomial dynamical systems. Nonlinear Anal.-Theor., 4(5):879 – 900, 1980.
[2] D. P. Bertsekas. Dynamic Programming and Optimal Control, volume 2. Athena Scientific, Belmont, U.S.A., 4th edition, 2012.
[3] D.P. Bertsekas. Value and policy iterations in optimal control and adaptive dynamic programming. IEEE Transactions on Neural Networks and Learning Systems, 28(3):500–509, 2015.
[4] D.P. Bertsekas. Abstract Dynamic Programming. Athena Scientific, Belmont, U.S.A., 2nd edition, 2018.
[5] S. P. Bhat and D. S. Bernstein. Geometric homogeneity with applications to finite-time stability. Mathematics of Control, Signals and Systems, 17(2):101–127, 2005.
[6] L. Buşoniu, D. Ernst, B. De Schutter, and R. Babuška. Approximate dynamic programming with a fuzzy parameterization. Automatica, 46(5):804–814, 2010.
[7] J.-M. Coron, L. Grüne, and K. Worthmann. Model predictive control, cost controllability, and homogeneity. SIAM Journal on Control and Optimization, 58(5):2979–2996, 2020.
[8] G. Grimm, M.J. Messina, S.E. Tuna, and A.R. Teel. Model predictive control: for want of a local control Lyapunov function, all is not lost. IEEE Transactions on Automatic Control, 50(5):546–558, 2005.
[9] R. E. Kalman. Contributions to the theory of optimal control. Bol. soc. mat. mexicana, 5(2):102–119, 1960.
[10] S.S. Keerthi and E.G. Gilbert. An existence theorem for discrete-time infinite-horizon optimal control problems. IEEE Transactions on Automatic Control, 30(9):907–909, 1985.
[11] D. Liberzon. Calculus of variations and optimal control theory: a concise introduction. Princeton university press, 2011.
[12] B. Lincoln and A. Rantzer. Relaxing dynamic programming. IEEE Transactions on Automatic Control, 51(8):1249–1260, 2006.
[13] K. Mino. On the homogeneity of value function of the optimal control problem. Economics Letters, 11(1-2):149–154, 1983.
[14] M. Nagahara, J. Østergaard, and D.E. Quevedo. Discrete-time hands-off control by sparse optimization. EURASIP Journal on Advances in Signal Processing, 2016(1):1–8, 2016.
[15] M. Nagahara, D.E. Quevedo, and D. Nešić. Maximum hands-off control: a paradigm of control effort minimization. IEEE Transactions on Automatic Control, 61(3):735–747, 2015.
[16] N. Nakamura, H. Nakamura, Y. Yamashita, and H. Nishitani. Homogeneous stabilization for input affine homogeneous systems. IEEE Transactions on Automatic Control, 54(9):2271–2275, 2009.
[17] A. Polyakov. Generalized homogeneity in systems and control. Springer, 2020.
[18] M. Rinehart, M. Dahleh, and I. Kolmanovsky. Value iteration for (switched) homogeneous systems. IEEE TAC, 54(6):1290–1294, 2009.
[19] T. Sanchez, D. Efimov, and A. Polyakov. Discrete-time homogeneity: Robustness and approximation. Automatica, 122:109275, 2020.
[20] T. Sanchez, D. Efimov, A. Polyakov, J.A. Moreno, and W. Perruquetti. A homogeneity property of discrete-time systems: Stability and convergence rates. Int. J. Robust Nonlin., 29(8):2406–2421, 2019.
[21] E. Trélat. Optimal control and applications to aerospace: some results and challenges. J. Optimiz. Theory App., 154(3):713–758, 2012.