1. INTRODUCTION

Controlled processes under state constraints are important objects of study in the mathematical theory of optimal control (see, e.g., [1, 2, 3, 4] et al.). The presence of state constraints essentially complicates the investigation of the corresponding optimization problems. Note that an important characteristic of a control process is its reachable sets (see, e.g., [3, 4]). For linear controlled objects in the absence of state constraints, a theory was developed which gives an efficient calculation of reachable sets based on techniques of support functions (see, e.g., [4]). For linear controlled objects under state constraints, the constructive calculation of reachable sets is rather difficult.

This paper is devoted to the approximate calculation of reachable sets for linear controlled objects in the presence of a convex state constraint and a compact set \(P\) bounding the vector control \(u\).

2. THE MAIN PART

Consider a linear controlled object of the form (see [1, 2, 3, 4])

$$\dot{x}=Ax+Bu,$$
(1)

where \(x\in\mathbb{R}^{n}\) (\(n\geq 1\)); \(u\in\mathbb{R}^{p}\) (\(p\geq 1\)); \(A\) and \(B\) are \(n\times n\) and \(n\times p\) matrices, respectively; and the control \(u\in P\) is a convex compact set in \(\mathbb{R}^{p}\). For \(k\geq 1\), we denote by \(\mathbb{R}^{k}\) the Euclidean arithmetic space whose elements are ordered tuples of \(k\) numbers written as columns. The scalar product \(\langle x,y\rangle\) of vectors \(x\), \(y\) from \(\mathbb{R}^{k}\) and the length \(|x|\) of a vector \(x\in\mathbb{R}^{k}\) are introduced in the standard way.

For the controlled object (1), we fix a state constraint \(G\subset\mathbb{R}^{n}\), where \(G\) is a nonempty convex compact set; an initial condition \(x(0)=x_{0}\in G\); and a time \(T>0\). We consider all possible Lebesgue measurable functions \(u(t)\in P\), \(t\in\Delta=[0,T]\), called admissible controls. Denote by \(U\) the set of such functions. For each admissible control \(u(\cdot)\) and initial condition \(x(0)=x_{0}\), there is an absolutely continuous solution \(x(t,u(\cdot),x_{0})\), \(t\in\Delta\), of equation (1). We are interested in the controls \(u(\cdot)\in U\) for which \(x(t,u(\cdot),x_{0})\in G\) for all \(t\in\Delta\); denote the set of such controls by \(W\). In the general case, the set \(W\) can be empty. In what follows, we assume that \(W\neq\varnothing\). For the controlled object under consideration, we define the reachable set \(D(T,x_{0})\) by the formula

$$D(T,x_{0})=\bigcup\limits_{u(\cdot)\in W}x(T,u(\cdot),x_{0}).$$
(2)

Recall that, for \(u(\cdot)\in U\) and the corresponding solution \(x(t)=x(t,u(\cdot),x_{0})\), \(t\in\Delta\), we have the Cauchy formula

$$x(t)=e^{tA}x_{0}+\intop\limits_{0}^{t}e^{(t-s)A}Bu(s)\,ds,$$
(3)

where \(e^{tA}\) is the exponential of the matrix \(tA\), and the integral is understood in the Lebesgue sense. Using this formula and the convexity of the sets \(P\) and \(G\), one can easily prove the convexity of \(D(T,x_{0})\) (see (2)). Using the weak compactness of the set \(U\) in the Hilbert space \(L_{2}^{p}[0,T]\) (see [2]), the closedness of the set \(G\), and formula (3), we can prove that the reachable set \(D(T,x_{0})\) is convex and compact. We will study the problem of approximate (in the sense of the Hausdorff metric) calculation of the set \(D(T,x_{0})\).

Divide the interval \(\Delta\) into \(N\) equal parts (\(N\geq 1\)) by the points

$$t_{i}=ih,$$

where \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\) and \(h=T/N\). Define

$$E(h,K)=\bigcup\limits_{u(\cdot)\in U_{h},y\in K}x(h,u(\cdot),y),$$
(4)

where \(h>0\), \(K\) is an arbitrary nonempty compact set from \(\mathbb{R}^{n}\), \(U_{h}\) is the set of measurable functions \(u(t)\in P\) for \(t\in[0,h]\), and \(x(t,u(\cdot),y)\) is the solution of equation (1) corresponding to the control \(u(\cdot)\in U_{h}\) and the initial condition \(x(0)=y\). For the set \(E(h,K)\) (see (4)), using formula (3), we can prove the formula

$$E(h,K)=e^{hA}K+\intop\limits_{0}^{h}e^{rA}BP\,dr,$$
(5)

where “+” means the algebraic addition of sets, and the integral of the set-valued mapping \(e^{rA}BP\) over \([0,h]\) is understood in the sense of the theory of set-valued mappings (see [4]). Note that if the compact set \(K\) is convex, then \(E(h,K)\) (see (5)) is also a convex compact set. In what follows, we will need the following chain of sets \(F_{i}\):

$$F_{0}=\{x_{0}\},\ \ \ \ F_{i+1}=E(h,F_{i})\cap G,$$
(6)

where \(h=T/N\) and \(i=0,\mathinner{\ldotp\ldotp\ldotp},N-1\). Using the Cauchy formula (3), we can show that, under the above assumptions, all the sets \(F_{i}\), \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\), are nonempty, convex, and compact. We are interested in the set \(F_{N}\) as a certain approximation of the set \(D(T,x_{0})\) as \(N\to+\infty\).

Consider an arbitrary control \(\tilde{u}(\cdot)\in W\). Then the solution \(\tilde{x}(t)=x(t,\tilde{u}(\cdot),x_{0})\) for \(t\in\Delta\) satisfies the inclusion

$$\tilde{x}(t)\in G.$$

Using the Cauchy formula (3), we can show that

$$\tilde{x}(t_{i})\in F_{i}$$

for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\); in particular, \(\tilde{x}(T)\in F_{N}\). The definition of the set \(D(T,x_{0})\) (see (2)) and the inclusion \(\tilde{x}(T)\in F_{N}\) imply that

$$D(T,x_{0})\subset F_{N}.$$
(7)

In what follows, we will use the following definitions.

Definition 1

Let \(X\) and \(Y\) be nonempty compact sets from \(\mathbb{R}^{n}\). The Hausdorff distance \(h(X,Y)\) is defined as the smallest nonnegative number \(\varepsilon\) for which

$$X\subset Y+S_{\varepsilon},\quad Y\subset X+S_{\varepsilon},$$
(8)

where \(S_{\varepsilon}=\{x\in\mathbb{R}^{n}:|x|\leq\varepsilon\}\).    \(\square\)

Definition 2

The support function \(c(X,\psi)\) of a nonempty compact set \(X\subset\mathbb{R}^{n}\) is defined for \(\psi\in\mathbb{R}^{n}\) by the formula

$$c(X,\psi)=\max\limits_{x\in X}\langle x,\psi\rangle.$$

Note that the properties of support functions were discussed in detail in [4].    \(\square\)

The aim of this study is to prove the convergence of the convex compact sets \(F_{N}\) to the convex compact set \(D(T,x_{0})\) as \(N\to+\infty\) in the Hausdorff metric and to derive some upper estimate for this convergence under an additional assumption concerning the controlled object (1), vector \(x_{0}\), and the set \(G\).

Denote by \(U_{N}\) the set of \(\hat{u}(\cdot)\in U\) such that

$$x(t_{i},\hat{u}(\cdot),x_{0})\in F_{i},$$

where \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\). Note that formulas (6) for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\) and the inclusion \(\hat{u}(\cdot)\in U_{N}\) imply the relations

$$x(t_{i},\hat{u}(\cdot),x_{0})\in G$$
(9)

for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\). Using formulas (3)–(6), we can prove that

$$F_{N}=\bigcup\limits_{\hat{u}(\cdot)\in U_{N}}x(T,\hat{u}(\cdot),x_{0})).$$
(10)

Using the compactness of the set \(G\) and formulas (3) and (9), we can prove that, for \(t\in\Delta\) and arbitrary \(\hat{u}(\cdot)\in U_{N}\), the following inequality holds:

$$\rho(x(t,\hat{u}(\cdot),x_{0}),G)\leq ch,$$
(11)

where \(h=T/N\), the constant \(c\) is nonnegative and independent of \(N\), and the value \(\rho(y,G)\) for \(y\in\mathbb{R}^{n}\) is defined by the formula

$$\rho(y,G)=\min\limits_{z\in G}|y-z|.$$

From relation (11), for \(t\in\Delta\), we get the inclusion

$$x(t,\hat{u}(\cdot),x_{0})\in G+S_{ch},$$

where “+” means the algebraic addition of sets,

$$\displaystyle S_{ch}=\{x\in\mathbb{R}^{n}\colon|x|\leq ch\},\ \ \ c\geq 0,\ \ \ h=T/N.$$

Note that

$$W\subset U_{N}.$$

Theorem 1

The sequence of convex compact sets \(F_{N}\)  (see (6), (10)) converges to the convex compact set \(D(T,x_{0})\) as \(N\to+\infty\) in the sense of the Hausdorff metric.

Proof

Fix some positive \(\varepsilon\). In view of relations (7), (8), it is sufficient to prove that

$$F_{N}\subset D(T,x_{0})+S_{\varepsilon}$$

for large \(N\). Assume that this is not so. Then there exists a subsequence \(N_{k}\to+\infty\) such that

$$F_{N_{k}}\not\subset D(T,x_{0})+S_{\varepsilon}.$$

Hence, for some sequence of controls \(\hat{u}_{N_{k}}\in U_{N_{k}}\), we have

$$x(T,\hat{u}_{N_{k}}(\cdot),x_{0})\notin D(T,x_{0})+S_{\varepsilon}.$$
(12)

Let us now use the weak compactness of the set \(U\) in the Hilbert space \(L_{2}^{p}[0,T]\) (see [2]). Passing, if necessary, to a subsequence with the corresponding reindexing, we can assume that the sequence \(\hat{u}_{N_{k}}(\cdot)\) weakly converges as \(N_{k}\to+\infty\) in the sense of the Hilbert space \(L_{2}^{p}[0,T]\) to some control \(u_{0}(\cdot)\), which belongs to the set \(U\) and, at the same time, the sequence of functions \(x(t,\hat{u}_{N_{k}}(\cdot),x_{0})\) converges uniformly on the interval \([0,T]\) to the function \(x(t,u_{0}(\cdot),x_{0})\). Using (11), we can show that \(x(T,u_{0}(\cdot),x_{0})\in D(T,x_{0})\). However, this inclusion, according to the above, contradicts (12). We have come to a contradiction with our assumption.

The theorem is proved.    \(\square\)

For applications, it is useful to have an estimate for the convergence rate of the sequence \(F_{N}\), \(N=1,2,\mathinner{\ldotp\ldotp\ldotp}\), to \(D(T,x_{0})\) in the Hausdorff metric. Such an estimate can be derived under the following assumption.

Assumption

There exist a control \(\overline{u}(\cdot)\in W\) and a constant \(\alpha>0\) such that

$$x(t,\overline{u}(\cdot),x_{0})+S_{\alpha}\subset G,\ \ \ \ t\in\Delta.$$

Theorem 2

Under the above assumption, the Hausdorff distance between the convex compact sets \(F_{N}\) and \(D(T,x_{0})\) can be estimated from above by the value \(c_{1}/N\) as \(N\to+\infty,\) where \(c_{1}\) is some positive constant.

Proof

In view of (7) and (8), it is sufficient to prove that

$$F_{N}\subset D(T,x_{0})+(c_{2}/N)S_{1}$$

for \(N\geq 1\), where \(c_{2}\) is some nonnegative constant independent of \(N\). Then we can take the constant \(c_{2}\) as \(c_{1}\). Fix \(N\geq 1\) and consider some control \(\hat{u}(\cdot)\) from the set \(U_{N}\). This control corresponds to a solution \(\hat{x}(t)=x(t,\hat{u}(\cdot),x_{0})\), and the control \(\overline{u}(\cdot)\) corresponds to a solution \(\overline{x}(t)=x(t,\overline{u}(\cdot),x_{0})\). Let us also consider the control

$$u_{\beta}(t)=\beta\overline{u}(t)+(1-\beta)\hat{u}(t)$$
(13)

on \(\Delta\), where \(\beta\in[0,1]\). It follows from the convexity of the set \(P\) that \(u_{\beta}(\cdot)\in U\). The control \(u_{\beta}(t)\) corresponds to a solution \(x_{\beta}(t)=x_{\beta}(t,x_{0})\) and, by the Cauchy formula (see (3)), we have

$$x_{\beta}(t)=\beta\overline{x}(t)+(1-\beta)\hat{x}(t).$$
(14)

for \(t\in\Delta\). Since the control \(\hat{u}(\cdot)\) belongs to the set \(U_{N}\), we have inequality (11) for \(t\in\Delta\). Let us add algebraically the ball \(\beta S_{\alpha}\) to both sides of (14). In view of the assumption and relation (11), we obtain for \(t\in\Delta\) the inclusion

$$x_{\beta}(t)+\beta S_{\alpha}\subset\beta G+(1-\beta)(G+S_{ch}).$$
(15)

Since \(\beta G+(1-\beta)G=G\), it follows from (15) that

$$x_{\beta}(t)+\beta S_{\alpha}\subset G+(1-\beta)S_{ch}$$
(16)

for \(t\in\Delta\) and \(h=T/N\). Using the techniques of support functions (see [4]), from inclusion (16) we obtain the inequality

$$\langle x_{\beta}(t),\psi\rangle+\beta\alpha|\psi|\leq c(G,\psi)+(1-\beta)ch|\psi|$$

for \(t\in\Delta\), where \(\psi\) is an arbitrary vector from \(\mathbb{R}^{n}\).

The number \(\beta\in[0,1]\) has been arbitrary so far. Let us consider the following equation with respect to \(\beta\):

$$\beta\alpha=(1-\beta)ch.$$
(17)

Its solution is

$$\beta_{h}=ch/(\alpha+ch).$$
(18)

Note that \(\beta_{h}\in[0,1]\). From relations (14)–(18),we get

$$\langle x_{\beta_{h}}(t),\psi\rangle\leq c(G,\psi)$$

for \(t\in\Delta\) and \(\psi\in\mathbb{R}^{n}\). Hence, using the convexity of the compact set \(G\) and the properties of support functions (see [4]), we find that

$$x_{\beta_{h}}(t)\in G,\ \ \ t\in\Delta.$$
(19)

From formula (14), we derive the following relation:

$$x_{\beta_{h}}(T)-\hat{x}(T)=\beta_{h}(\overline{x}(T)-\hat{x}(T)).$$
(20)

Using the Cauchy formula (3), it is easy to prove the inequality

$$|x(T,u(\cdot),x_{0})|\leq c_{3}$$
(21)

for arbitrary \(u(\cdot)\in U\), where \(c_{3}\) is some positive constant, which can be computed constructively. Using inequality (21), we derive from (20) the important inequality

$$|x_{\beta_{h}}(T)-\hat{x}(T)|\leq 2c_{3}{\beta_{h}}.$$
(22)

Note that, since the choice of the control \(\hat{u}(\cdot)\in U_{N}\) was arbitrary, the vectors \(\hat{x}(T)\) in (22) fill the entire set \(F_{N}\). Hence, in view of relations (11), (18), and (19) and the equality \(h=T/N\), we obtain

$$F_{N}\subset D(T,x_{0})+2c_{3}{\beta_{h}}S_{1}\subset D(T,x_{0})+(2cc_{3}T/N \alpha)S_{1}.$$

Now, setting \(c_{2}=2cc_{3}T/\alpha\), we obtain the required inclusion for \(N\geq 1\).

The theorem is proved.    \(\square\)

Remark

Note that a control of the form (13) was used earlier in [2, pp. 927–930] in the proof of Theorem 1, which is devoted to a numerical method of approximate solution of linear control problems with a terminal functional in the presence of a state constraint.