Turnpike and Linear Systems Theory

Jan Heiland (MPI Magdeburg)

CSC Seminar – 7 April 2020

Introduction

\[ \DeclareMathOperator{\inva}{d} \newcommand\mxp[1]{e^{\{#1\}}} \def\AP{A _ +} \def\bAP{\bar{A} _ +} \def\APs{A _ +^ * } \def\APms{A _ +^{- * }} \def\bAPms{\bar{A} _ +^{- * }} \def\PP{P _ +} \]

What is turnpike?

Let \(x\) solve an optimal control problem on a finite time horizon \([0,t_1]\). Then the turnpike property holds, if there is an \(x_s\) such that
for \(c\), \(\lambda >0\) independent of \(t_1\) and \(0\leq t \leq t_1\), \[ \| x(t) - x_s \| \leq c(\mxp{-t\lambda} + \mxp{-(t_1-t)\lambda}). \]

The Finite Time LQR Problem

For \(t_1>0\), \[\frac 12 \int_{0}^{t_1} \|Cx(s)-y_c\|^2+ \|u(s)\|^2 \inva{s} + \frac 12 \|F x(t_1)-y_e\|^2 \to \min_u\] subject to \[\dot x(t) = Ax(t) + Bu(t), \quad x(0)=x_0.\]

The Solution

Without conditions on \(A\), \(B\), \(C\), \(F\), the finite time problem is solved by

\[ \dot x = (A-BB^ * P(t))x - BB^ * w(t), \quad x(0)=x_0, \]

where \(P\) solves the differential Riccati equation \[ -\dot P = A^ * P + PA -PBB^ * P+C^ * C, \quad P(t _ 1)=F^ * F \] and the feedforward \(w\) solves \[ -\dot w = (A^ * -P(t)BB^ * )w + C^ * y _ c, \quad w(t _ 1)=-F^ * y _ e. \]

Theorem: Callier&Willems&Winkin’93

Let there exist a unique stabilizing solution \(P _ +\) to \[A^ * X+XA-XBB^ * X+C^ * C=0 .\]

  • If \(P(t) \to P _ +\) as \(t_1\to \infty\), then, for some \(\sigma>0\), \[\|x _ h(t) - \mxp{t(A-BB^ * P _ +)}x_0\| \leq Ce^{\{-(t_1-t)\sigma \}},\] where \(x _ h\) is the solution with \(y _ e\), \(y _ c=0\).

  • The solution to the differential Riccati equation \(P\) converges to \(P _ +\) as \(t_1\to \infty\) if, and only if, the nullspace of \(F^ * F\) and the undetectable subspace of \((C,A)\) have no intersection.

Explicit Formulas

For the affine LQR Problem

\[\frac 12 \int_{0}^{t_1} \|Cx(s)-y_c\|^2+ \|u(s)\|^2 \inva{s} + \frac 12 \|F x(t_1)-y_e\|^2 \to \min_u\]

with \(y_e\), \(y_c \neq 0\).

Assumptions

  • The ARE has a unique stabilizing solution \(P _ +\).

  • \(A _ + := A - BB^ * P _ +\).

Lemma

Let the ARE have a unique stabilizing solution \(P _ +\). Then the fundamental solution matrix \(U\) to \[ \dot U(t) = (A-BB^*P(t))U(t), \quad U(t_1)=I, \] where \(P\) solves the DRE with \(P(t_1)=F^ * F\), is given as \[ U(t) = \mxp{-(t_1-t)\AP}\bigl(I-[W-\mxp{(t_1-t)\AP}W\mxp{(t_1-t)\APs}](\PP-F^ * F)\bigr), \] where \(W:=\int_0^\infty \mxp{sA _ +}BB^ * \mxp{sA _ +^ * }\inva s\).

\[\square\]

Proof: See, e.g., Behr&Benner&H’19, proof of Theorem 3.4.

Lemma

The feedforward \(w\) that solves \[ -\dot w = (A^ * -P(t)BB^ * )w + C^ * y _ c, \quad w(t _ 1)=-F^ * y _ e. \] is given as \[ w(t) =-U(t)^{- * }U(t_1)^ * F^ * y _ e + \int_{t_1}^tU(t)^{-*}U(s)^*C^ * y _ c \inva s \] and can be expressed as \[ w(t) = w_h(t) + \APms C^ * y _ c - \mxp{(t_1-t)\APs}C^ * y _ c + g(t, t_1), \] where \(g\) collects all the remainder integral terms.

Lemma

The optimal state \(x\) is given as \[ x(t) = U(t)U(0)^{-1}x_0 - \int_0^t U(t)U(s)^{-1}BB^ * w(s)\inva s \] and, with the help of the formulas for \(w\) and \(U(t)U(s)^{-1}\), it can be expressed as \[ x(t) = x_h(t) + \AP ^{-1} BB^ * \APms C^ * y_c + G(t, t_1), \] with a function \(G\) that satisfies the estimate \[ \|G(t,t_1)\| \leq c\mxp{-(t_1 - t)\sigma}. \]

Theorem

Let the ARE have a unique stabilizing solution.
Then the affine finite time LQR problem enjoys the turnpike property, if, and only if, the nullspace of \(F^ * F\) and the undetectable subspace of \((C,A)\) have no intersection.

Remark

  • The turnpike is \(\AP ^{-1} BB^ * \APms C^ * y_c\), which is the solution to the steady state optimal control problem \[ \frac 12 \|Cx - y _ c\|^2 + \frac 12 \|u\|^2 \to \min_u, \quad \text{subject to}\quad 0=Ax+Bu. \]

Some Pictures

Case 1

\[ \begin{split} A &= \begin{bmatrix} 2 & 0 \\ 0 & -1 \end{bmatrix}\quad B = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\\ C &= \begin{bmatrix} 0 & 2 \end{bmatrix} \\ &\to\text{ not detectable,} \\ &\to\text{ $P _ +$ exists,}\\ F &= C= \begin{bmatrix} 0 & 2 \end{bmatrix}\\ &\to\text{no turnpike!} \end{split} \]

Case 2

\[ \begin{split} A &= \begin{bmatrix} 2 & 0 \\ 0 & -1 \end{bmatrix}\quad B = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\\ C &= \begin{bmatrix} 0 & 2 \end{bmatrix} \\ &\to\text{ not detectable,} \\ &\to\text{ $P _ +$ exists,}\\ F &\perp C = \begin{bmatrix} 2 & 0 \end{bmatrix}\\ &\to\text{turnpike!} \end{split} \]

Turnpike for DAEs

The Finite Time LQR Problem

\[ \def\daE{\mathcal E} \def\daA{\mathcal A} \def\daF{\mathcal F} \def\daC{\mathcal C} \def\daB{\mathcal B} \def\daP{\mathcal P} \def\daPP{\mathcal P _ +} \def\daPs{\mathcal P^ * } \def\daPD{\mathcal P _ \Delta} \def\daPDs{\mathcal P _ \Delta^ * } \def\daAP{\mathcal A _ +} \def\daAPs{\mathcal A _ +^ * } \def\ao{A _ {11}} \def\ato{A _ {21}} \def\aot{A _ {12}} \def\at{A _ {22}} \def\atmo{A _ {22}^{-1}} \def\atms{A _ {22}^{- * }} \def\boo{B _ {11}} \def\bto{B _ {21}} \def\btos{B _ {21}} \def\btt{B _ {22}} \def\daPDii{\ensuremath{P _ {\Delta;1}}} \]

For \(t_1>0\), \[\frac 12 \int_{0}^{t_1} \|\daC x(s)-y_c\|^2+ \|u(s)\|^2 \inva{s} + \frac 12 \|\daF x(t_1)-y_e\|^2 \to \min_u\] subject to \[\daE\dot x(t) = \daA x(t) + \daB u(t), \quad \daE x(0)=\daE x_0.\]

Question

What is the associated steady state problem? Certainly not simply \(0=\daA x + \daB u\).

Assumptions

  • The matrix pair \((\daE, \daA)\) is regular, i.e., there exists an \(s\in \mathbb C\) such that \(s\daE - \daA\) is invertible.

  • WLOG: the matrix \(\daE = \begin{bmatrix} I & 0 \\ 0 & 0 \end{bmatrix}\) is in semi-explicit form.

  • The generalized algebraic Riccati equation \[ \daA^*X + X^*\daA - X^*\daB\daB^*X + \daC^*\daC = 0, \quad \daE^*X=X^ * \daE \] has a stabilizing solution \(\daPP\).

Assumptions ctd

  • Here, stabilizing means that with \[\daA-\daB\daB^ * \daPP =:\daAP= \begin{bmatrix} \ao & \aot \\ \ato & \at \end{bmatrix},\]

  • the pencil \((\daE, \daAP)\) is finite dynamics stable and impulse free,

which means (because of \(\daE\) semi-explicit) that

  • \(\at\) is invertible and

  • \(\ao-\aot \at ^{-1} \ato\) is stable.

The Hamiltonian System

With \(\daPP\) at hand we can consider the Hamiltonian system \[ \begin{bmatrix} \daE & 0 \\ 0 & \daE^* \end{bmatrix} \frac{d}{dt} \begin{bmatrix} V_{11} \\ V_{12} \\ \tilde V_{21} \\ \tilde V_{22} \end{bmatrix}(t) = \begin{bmatrix} \daAP & -\daB\daB^* \\ 0 & -\daAP^* \end{bmatrix} \begin{bmatrix} V_{11} \\ V_{12} \\ \tilde V_{21} \\ \tilde V_{22} \end{bmatrix}(t) \]

  • plus initial and terminal conditions,

  • with, e.g, \(V _ {11}(t)\in \mathbb R^{d\times d}\), where \(d\) is the rank of \(\daE\).

Theorem

Under reasonable compatibility assumptions on \(\daF\), the partial solution \(V _ {11}(t)\) is invertible, and with \[ \daPD(t):= \begin{bmatrix} \tilde V_{21}V_{11}^{-1} & 0 \\ -A_{22}^{-*}A_{12}^ * \tilde V_{21}V_{11}^{-1} & 0 \end{bmatrix}, \] the matrix function \(\daP(t) := \daPP + \daPD(t)\) solves the generalized differential Riccati equation \[ -\daE^*\dot \daP = \daA^*\daP + \daP^*\daA - \daP^*\daB\daB^*\daP + \daC^*\daC, \quad \daE^*\daP=\daP^*\daE. \]

Corollary

For \(y _ e\), \(y _ c=0\) and with \[x= \begin{bmatrix} x_1(t) \\ x_2(t) \end{bmatrix} \quad \text{and}\quad \daB\daB^ * = \begin{bmatrix} \boo & \bto^ * \\ \bto & \btt \end{bmatrix}\] partitioned in accordance with \(\daE\), the optimal state reads

\[ \begin{bmatrix} x_1(t) \\ x_2(t) \end{bmatrix}= \begin{bmatrix} V_{11}(t)V_{11}(t_0)^{-1}x_1(t_0) \\ A_{22}^{-1} A_{21}x_1(t) - A_{22}^{-1} [B_{21}+B_{22}A_{22}^{-*}A_{12}^*]V_{21}(t)V_{11}(t)^{-1}x_1(t) \end{bmatrix}. \]

and the Callier/Willems/Winkin result for \(x_1\) is immediate.

Proof

  • The Hamiltonian system is j first order necessary condition.

  • Leaving aside the initial condtions, for any \(k\) constant, \[\begin{bmatrix} x_1(t) \\ x_2(t) \\ \tilde \lambda_1(t) \\ \tilde \lambda_2(t) \end{bmatrix} = \begin{bmatrix} V_{11}(t) \\ V_{12}(t) \\ \tilde V_{21}(t) \\ \tilde V_{22}(t) \end{bmatrix} k\] defines a solution.

  • With the invertibility of \(V _ {11}\), we can apply the initial condition: \[ k = V _ {11}(t_0)^{-1}x_0. \]

  • By the DAE stability, we have that \[ \begin{bmatrix} V_{12}(t) \\ \tilde V_{22}(t) \end{bmatrix} = \begin{bmatrix} s_{11} & s_{12} \\ s_{21} & s_{22} \end{bmatrix} \begin{bmatrix} V_{11}(t) \\ \tilde V_{21}(t) \end{bmatrix} . \]

  • Computing the entries \(s_{11}\) and \(s_{12}\), we obtain \[ \begin{bmatrix} x_1(t) \\ x_2(t) \end{bmatrix}= \begin{bmatrix} V_{11}V_{11}(t_0)^{-1}x_1(t_0) \\ A_{22}^{-1} A_{21}x_1 - A_{22}^{-1} [B_{21}+B_{22}A_{22}^{-*}A_{12}^*]V_{21}V_{11}^{-1}x_1 \end{bmatrix}. \]

\[\square\]

What is the DAE Turnpike then?

For a general \(y _ c\), it turns out that \[ x_1(t) \to \bAP ^{-1} \bar B\bar B^ * \bAPms \bar C^ * y_c \quad\text{as}\quad t_1 \to \infty, \] where \[ \bAP:= \ao-\aot\atmo\ato, \quad \bar B:=B_1-\aot\atmo B_2, \quad \] \[ \bar C:=C_1-C_2\atmo\ato. \]

The DAE turnpike is defined via the Schur complement of the closed-loop “index-1” system.

Conclusion

Summary

  • Turnpike for a large class of LQR Problems can be derived from classical systems theory results

  • and also extends to DAEs.

Outlook

  • A DAE example?

  • Formulation for infinite-dimensional systems.

  • Make use of higher convergence rates when treating nonlinear problems.

Thank You!

  • For your attention.

  • And thanks to Enrique Zuazua and the ERC DyCon Project for the support.

References

Behr, Maximilian, Peter Benner, and Jan Heiland. 2019. “Invariant Galerkin Ansatz Spaces and Davison-Maki Methods for the Numerical Solution of Differential Riccati Equations.” arXiv E-Prints, October, 1–33. http://arxiv.org/abs/1910.13362.

Callier, Frank M., Joseph Winkin, and Jacques L. Willems. 1994. “Convergence of the Time-Invariant Riccati Differential Equation and LQ-Problem: Mechanisms of Attraction.” International Journal of Control 59 (4): 983–1000. https://doi.org/10.1080/00207179408923113.

// reveal.js plugins