Greedy Control

The problem

Control of a parameter dependent system in a robust manner. Fix a control time $T > 0$, an arbitrary initial data $x^0$, and a final target $x^1 \in R^N$ Given $\varepsilon > 0$ we aim at determining a family of parameters $\nu_1,…, , \nu_n$ in $\mathcal{N}$ so that the corresponding controls $u_1, …, u_n$ are such that for every $\nu \in \mathcal{N}$ there exists $u^\star_\nu \in {\rm span}{u_1,…, u_n}$ steering the system to the state $x_\nu^\star(T)$ within the $\varepsilon$ distance from the target $x^1$.

The system

A finite dimensional linear control system:

• $ A( \nu)$ is a $N \times N$−matrix,
• $B$ is a $N\times M$ control operator, $\,M \leq N$,
• $\nu$ is a parameter living in a compact set, $\,\mathcal{N}$ of $\mathbb{R}^d$

Assumptions:

• the system is (uniform) controllable for all $\nu \in N$,
• system dimension $\mathcal{N}$ is large

The greedy approach

$X$ – a Banach space $K\subset X$ – a compact subset. The method approximates $K$ by a a series of finite dimensional linear spaces $V_n$ (a linear method).

A general greedy algorithm

• The first step Choose $x_1 \in K$ such that $$ { {\| x_1 \|}_{X}} = \max_{x \in K} { {\| x \|}_{X}} $$
• The general step Having found $x_1 .. x_n$, denote $$ V_n={\rm span} \{x_1, \ldots,x_n\} $$ Choose the next element $$ x_{n+1}:= \arg\!\max_{x \in K} {\rm dist}(x, V_n) $$
• The algorithm stops when $\sigma_n(K):= \max_{x \in K} {\rm dist}(x, V_n) $ becomes less than the given tolerance $\varepsilon$.
The Kolmogorov $n$ width, $d_n(K) $ measures optimal approximation of $K$ by a $n$-dimensional subspace. $$ d_n(K):=\inf_{\dim Y=n} \sup_{x\in K} \, \inf_{y\in Y} { {\| x-y \|}_{X}}\,. $$ The greedy approximation rates have same decay as the Kolmogorov widths. Figure1: Evolution of a) last 5 system components and b) the approximate control for $\nu=\pi$.

Greedy control

Each control can be uniquely determined by the relation $$ u_{\bf \nu} = {\bf B}^\ast e^{(T-t){\bf A}_{\bf \nu}^\ast} \varphi^0_{\bf \nu}, $$ where $\varphi^0_{\bf \nu}\in { {\bf R}}^N$ is the unique minimiser of a quadratic functional associated to the adjoint problem. This minimiser can be expressed as the solution of the linear system \begin{equation*} \label{phi^0} \Lambda_{\bf \nu} \varphi^0_{\bf \nu} = {\sf x}^1 - e^{T{\bf A}_{\bf \nu}} {\sf x}^0, \end{equation*} where $\Lambda_{\bf \nu} $ is the controllability Gramian \begin{equation*} \Lambda_{\bf \nu}=\int_0^T e^{(T-t){\bf A}_{\bf \nu}}{\bf B}_{\bf \nu} {\bf B}_{\bf \nu}^\ast e^{(T-t){\bf A}_{\bf \nu}^\ast} dt\,. \end{equation*} Perform a greedy algorithm to the manifold $\varphi^0({\cal N})$: $$ \nu \in {\cal N} \to \varphi^0_\nu \in \bf{R}^N\,. $$ The (unknown) quantity ${\rm dist} (\varphi^0_{\bf \nu}, \varphi_i^0)$ to be maximised by the greedy algorithm is replaced by a surrogate: $$ \begin{aligned} {\rm dist} (\varphi^0_{\bf \nu}, \varphi_i^0) &\sim {\rm dist} (\Lambda_{\bf \nu} \varphi^0_{\bf \nu}, \Lambda_{\bf \nu} \varphi^0_i) \cr &= {\rm dist} ({\sf x}^1 - e^{T{\bf A}_{\bf \nu}} {\bf x}^0, \Lambda_{\bf \nu} \varphi^0_i) \,.\cr \end{aligned} $$ The greedy control algorithm results in an optimal decay of the approximation rates.

Numerical examples

Wave equation

We consider the system (1) with: $$ {\bf A}=\left(\begin{matrix} {\bf 0} & -I\cr { \nu} ( N/2+1)^2 \tilde {\bf A} & {\bf 0}\cr \end{matrix}\right), $$ $$ \tilde {\bf A}=\left(\begin{matrix} 2 & -1& 0 & \cdots & 0\cr -1& 2 & -1& \cdots & 0\cr 0 & -1& 2 & \cdots & 0\cr \vdots&\vdots&\vdots&\ddots&\vdots\cr 0 &0& 0 & \cdots &2\cr \end{matrix}\right), \ \ {\bf B}=\left(\begin{matrix} 0\cr 0\cr \vdots\cr 0\cr 1\cr \end{matrix}\right). $$ The system corresponds to the discretisation of the wave equation problem with the control on the right boundary: $$ \begin{equation} \begin{cases} \partial_{tt} v - \nu \partial_{xx} v=0 \ \ (t, x) \in \langle 0, T \rangle \times \langle 0,1 \rangle \\ v(t, 0)=0 \ \ v(t, 1)=u(t) \\ v(0, x)=v_0 \ \ \partial_t v(x, 0)=v_1 \end{cases} \end{equation} $$ We take the following values: $$T=3,\; N=50,\; v_0=\sin(\pi x), \; v_1=0,\; x^1=0 $$ $$ \nu \in [1,10] = \mathcal{N} $$ The greedy control has been applied with $\varepsilon=0.5$ and the uniform discretisation of ${\cal N}$ in $k=100$ values. The offline algorithm stopped after 24 iterations. The 20-D controls manifold is well approximated by a 10-D subspace: Figure2: Evolution of the solution to the semi-discretised problem (2) governed by the approximate control $u_\nu^\star$ for $\nu=\pi$.

Heat equation

For $ {\bf A}=( N+1)^2\tilde{\bf A} $, with $\tilde{\bf A}$ given by: $$ \tilde {\bf A}=\left(\begin{matrix} 2 & -1& 0 & \cdots & 0\cr -1& 2 & -1& \cdots & 0\cr 0 & -1& 2 & \cdots & 0\cr \vdots&\vdots&\vdots&\ddots&\vdots\cr 0 &0& 0 & \cdots &2\cr \end{matrix}\right) $$ and the control operator $ {\bf B}= (0, \ldots,0, ( N+1)^2 )^\top,$ the system (1) corresponds to the space-discretisation of the heat equation problem with $N$ internal grid points and the control on the right boundary: $$ \begin{equation} \begin{cases} \partial_{t} v - \nu \partial_{xx} v=0 \ \ (t, x) \in \langle 0, T \rangle \times \langle 0, 1\rangle\\ v(t, 0)=0 \ \ v(t, 1)=u_\nu(t),\\ v(0, x)=v_0 \\ \end{cases} \end{equation} $$ The parameter $\nu$ represents the diffusion coefficient and is supposed to range within the set $\mathcal{N}=[1,2]$. The system satisfies the Kalman's rank condition for any $\nu\in {\cal N}$ and any target time $T$. We aim to control the system from the initial state $v_0(x)=\sin(\pi x)$ to zero in time $T=0.1$. The greedy control algorithm has been applied for the system of dimension $N=50$ with $\varepsilon=0.0001$, and the uniform discretisation of ${\cal N}$ in $k=100$ values. The algorithm stops after only three iterations. Figure3: Evolution of the solution to the semi-discretised problem (3) governed by the approximate control $u_\nu^\star$ for $\nu=\sqrt 2$.