0%

optimal control theory

最优控制理论

Introduction

最优控制解决的是对某个给定的系统寻找其一个满足特定最优标准的控制规律。它是变分法的一个扩展,也是一种得到控制规律的数值最优方法。这一方法大部分由Lev Pontryagin和Richard Bellman发展,最优控制可以视为控制理论中的一个控制策略。一个控制问题包括一个损失泛函,它是状态变量与控制变量的函数。一个最优控制是描述最小化损失泛函控制变量路径的微分方程集合,它可以由Pontryagon极小法则(这是一个必要条件)得到,或者通过求解Hamilton-Jacobi-Bellman方程(充分条件)得到。

控制动力系统

令$A\subset\mathbb{R}^m$,$\mathbf{f} : \mathbb{R}^{n} \times A \rightarrow \mathbb{R}^{n}$,$\alpha :[0, \infty) \rightarrow A$,考虑如下的动力系统:

我们称$\boldsymbol{\alpha} :[0, \infty) \longrightarrow A$为一个控制,对应每个控制的轨迹$\mathbf{x}(\cdot)$为对应系统的响应。

这里定义$\mathcal{A}=\{\boldsymbol{\alpha} :[0, \infty) \rightarrow A | \boldsymbol{\alpha}(\cdot) \text {measurable }\}$为可行控制空间。

损失泛函

通常来说损失泛函的形式如下:

这里$\mathrm{x}(\cdot)$为$\boldsymbol{\alpha}(\cdot)$下动力系统的解,$r : \mathbb{R}^{n} \times A \rightarrow \mathbb{R}$,$g : \mathbb{R}^{n} \rightarrow \mathbb{R}$为给定的度量。一般称$r$为控制代价,$g$为终止代价,终止点$T>0$也是提前给定的。

基本的问题是,我们想要在$\mathcal{A}$中找到一个能够最小化损失泛函的控制$\alpha^{*}(\cdot)$,这引出了如下的三个问题:

  1. 最优控制的存在性
  2. 怎样刻画这个最优控制
  3. 最优控制如何构造

可控性与Bang-Bang 原理

仍然考虑式子$(1.1)$描述的控制动力系统,我们从可控性问题开始。

可控性问题

给定初始点$x^{0}$以及一个目标集合$S \subset \mathbb{R}^{n}$,是否存在一个控制能够在有限时间内将系统导引至$S$中?首先我们并不给定一个损失泛函以刻画某个最优控制,而是关注是否存在能够将系统导引至给定目标的控制,这里通常假定$S=\{0\}$.

时刻t的可达集$\mathcal{C}(t)$为,由存在控制使得$\mathbf{x}(t)=0$的初值点$x^{0}$构成的集合。

全局可达集$C$为,存在控制及某个有限时间$t$使得$\mathbf{x}(t)=0$的初值点$x^0$构成的集合。

显然有如下关系成立:

线性系统的可控性

很自然地,我们从最简单的一类控制系统开始:

这里$M \in \mathbb{M}^{n \times n}$,$N \in \mathbb{M}^{n \times m}$,并限制控制参量的选取仅在一个单位方格中:

我们可以得到系统$(2.2)$的解析形式解:

那么我们可以得到此时$x^{0} \in \mathcal{C}(t)$的等价条件:

若存在$\alpha(\cdot) \in \mathcal{A}$使得上式成立。

在线性控制系统中,可达集拥有比较好的性质:

  • 可达集$\mathcal{C}$是对称($\pm x$同时含于可达集中)且凸的
  • 若$x^{0} \in \mathcal{C}(\overline{t})$,则$x^{0} \in \mathcal{C}(t)$对任意$t \geq \overline{t}$成立

定义可控性矩阵为:

关于线性系统的可控性,有如下的等价条件:

这里概括一下证明思路:1.若控制性矩阵的秩小于n,则零空间非空2.假设$x^0$在t时刻可达集中,利用等价条件$(2.5)$,可证零空间的元素必然正交于$x^0$3.即$C$为控制性矩阵零空间的正交补空间,并且过原点,不存在内点4.相反若原点不是$\mathcal{C}$的内点,由其凸性可知在$\mathcal{C}(t)$中有一个过$0$的支持平面,那么就可以找到其法向量,构造出一个控制性矩阵的非零解。

我们称线性系统可控若$\mathcal{C}=\mathbb{R}^{n}$,有如下的定理:

令$A$为$\mathbb{R}^n$的单位立方体,假定控制性矩阵秩为$n$,并且$M$的所有特征值实部为负,则系统是可控的。

实际上可以对条件进一步减弱,只要$M$的特征值实部非正即可,这里的证明比上面定理复杂很多。

Bang-Bang原理

这里仍然在单位立方体中选取控制,一个控制$\alpha(\cdot) \in \mathcal{A}$称为bang-bang若对于任意时刻都有$\left|\alpha^{i}(t)\right|=1$成立,可以理解为两状态控制。这是最为简单的一种控制,关于它有如下的定理:

若$x^0\in \mathcal{C}(t)$,则对于线性控制系统$(2.2)$,存在一个bang-bang控制$\alpha(\cdot)$在t时刻将初值引导至原点。

关于它的证明,需要一些泛函分析的知识,这里先省略。

Pontryagin极小条件

变分法与哈密顿动力系统

给定一个光滑函数$L : \mathbb{R}^{n} \times \mathbb{R}^{n} \rightarrow \mathbb{R}, L=L(x, v)$,$L$称为拉格朗日算子,这里$T>0, x^{0}, x^{1} \in \mathbb{R}^{n}$都是被给定的。

最开始的变分法考虑的是下面的优化问题:

这里$\mathbf{x}(\cdot)$满足$\mathbf{x}(0)=x^{0}$与$\mathbf{x}(T)=x^{1}$,假定$\mathbf{x}^{*}(\cdot)$为$(3.1)$的解,下面考虑如何刻画这个最优解。

欧拉-拉格朗日方程:若$\mathbf{x}^{*}(\cdot)$为变分问题$(3.1)$的解,那么它满足以下的欧拉-拉格朗日微分方程:

这给出了一个必要条件,但如果我们能求解$(3.2)$,那么最优解就在这组解中。它的证明很容易查到,这里先省略。

下面我们将EL方程化简为一个一阶ODE,定义广义动量为:

这里总假设我们能从式子$(3.3)$反解出$v$,定义一个动力系统的哈密顿子$H : \mathbb{R}^{n} \times \mathbb{R}^{n} \rightarrow \mathbb{R}$如下:

这里$\mathbf{v}$如上定义,有下面的定理:

若$\mathbf{x}(\cdot)$为EL方程的解,那么$(\mathbf{x}(\cdot), \mathbf{p}(\cdot))$满足下面的哈密顿方程:

进一步,$t \mapsto H(\mathbf{x}(t), \mathbf{p}(t))$必然为常量映射,即满足极小性的、必然遵循某种守恒性。

拉格朗日乘子

如果定义域没有做任何限制,那么极值点的判别标准即梯度为零,下面考虑有限制的情况。

在$R :=\{x \in \mathbb{R}^{n} | g(x) \leq 0\}$中考虑,令$x^{} \in R$并且有$f(x^)=\max _{x \in R} f(x)$,这里考虑如何刻画这个极值点。

若$\mathrm{x}^$在$R$的内部,那么$\nabla f\left(x^{}\right)=0$.

若$\mathrm{x}^$在$\partial R$上,考虑$\nabla f\left(x^{}\right)$的方向。显然地,如下图所示的情况是不可能的:

impossiblecase

这表明$\mathrm{x}^*$在沿$\partial R$的方向上仍然存在非零的梯度,即并未达到极值,所以必然是下图所示的情况:

True Case

即$\nabla f\left(x^{}\right)$必然与$\partial R$某处的法向量共线,这个法向量可以用$\nabla g\left(x^{}\right)$表示,所以有下面的关系成立:

由于$\nabla g\left(x^{*}\right)$有可能为零,所以更加准确的描述如下:

存在不同时为零的实数$\lambda$与$\mu$使得:

Pontyragin极小原理

核心的理论结果是,如果$\alpha^{}(\cdot)$为一个最优控制,那么就对应着一个称为costate的函数$\mathbf{p}^{}(\cdot)$,它满足一个特定的极小性,我们应该把costate视作一类拉格朗日乘子。

定时自由终止点问题

控制理论哈密顿算子如下定义:

这里给出pontryagin极小原理的描述:

假定$\alpha^{}(\cdot)$是满足$(1.1)$与给定损失泛函下的最优控制,$\mathrm{x}^{}(\cdot)$是对应的解,那么存在一个函数$\mathrm{p}^{*} :[0, T] \rightarrow \mathbb{R}^{n}$,使得:

并且此时:

进一步有$t \mapsto H\left(\mathbf{x}^{}(t), \mathbf{p}^{}(t), \boldsymbol{\alpha}^{*}(t)\right)$为常值映射,以及终止条件:

这里$(3.9)$的第二个式子是伴随方程,$(3.10)$是极小(极大)原理。也称$(3.11)$为截断条件,在之后会进一步讨论。

更加详细地,$(3.9)$的第一个式子为:

这正是原始的控制系统方程。

伴随方程则为:

在深度学习中,大多都是定时自由终点问题,另一种情况(定终点自由时间问题)这里省略。

应用极小原理

对于控制问题,直接寻找一个最优控制$\boldsymbol{\alpha}^{}(\cdot)$以及对应的解$\mathrm{x}^{}(\cdot)$并不那么容易,我们可以通过求解$\mathbf{p}^{*}(\cdot)$来简化这个问题。这里以一个实际的例子来阐述这个过程:

构造一个简单的经济模型,以$x(t)$表示$t$时刻经济产量,$\alpha(t)$表示$t$时刻将产量再投资的比例,经济模型以如下的形式演化:

我们希望极大化总消费量:

使用pontryagin极小原理,有:

因此有:

带入$(3.9)$有:

终止条件为:

最后,极大原理有:

下面开始求解,根据$(3.20)$有($x(t)>0$):

下一步需要确定$p(\cdot)$,由$(3.18)$及$(3.19)$有:

下面分情况讨论,若$p(t)\le1$,则$\alpha(t)=0$,因此$\dot{p}(t)=-1$,那么有$p(t)=T-t$,而这在满足假设的条件下成立,即$T-1 \leq t \leq T$时刻。

令一种情况,若$p(t)>1$,则$\alpha(t)=1$,有:

又由连续性,$p(T-1)=1$,故而$p(t)=e^{T-1-t}$,又需满足假设,可知这在$0 \leq t \leq T-1$上成立。

综上所述,最优控制为:

$t^{*}=T-1$.

动态规划

Bellman方程

考虑下面更一般的动力系统:

以及对应的损失泛函:

给定$x \in \mathbb{R}^{n}, 0 \leq t \leq T$,定义价值函数$v(x, t)$为:

价值函数给出了$x,t$的泛函.

Hamilton-Jacobi-Bellman方程刻画了价值函数,假定价值函数为$(x,t)$的$C^1$函数,则$v$满足如下的方程:

我们可以将HJB写作:

这里的哈密顿子定义为:

关于HJB方程的证明比较长,这里省略。

动态规划方法可以描述如下:

1.求解HJB方程,得到价值函数$v$

2.利用$v$来选取控制$\boldsymbol{\alpha}(x, t)$,这里$\boldsymbol{\alpha}(x, t)$满足:

3.求解如下的ODE,假定$\boldsymbol{\alpha}(\cdot, t)$拥有比较好的性质:

4.定义反馈控制为:

总的来说,我们以这样的方式来设计最优控制:若系统的状态为$(x,t)$,我们使用在t时刻是的HJB的极小被满足的$a \in A$.

可以证明,反馈控制即为一个最优控制,证明并不复杂。

由$(4.7)$的定义以及式子$(4.5)$,有:

故而$\boldsymbol{\alpha}^{*}(\cdot)$是最优的.

我们以一个简单的例子来进一步阐述这个流程,

运输车以以下的方程运动,

损失泛函为,

要使用动态规划,我们定义$v(x_1,x_2)$为负最小到达原点时间,起始点被定为$(x_1,x_2)$.

优于$v$并不依赖于$t$,所以有:

并且,

那么有,

可得方程为:

下面检查方程是否满足,定义两个区域:

直接计算得:

在区域$I$计算可得:

因此:

这表明了HJB在区域$I$是满足的,同样也可在区域$II$上得到验证。

由于$\max _{|a| \leq 1}\left\{x_{2} v_{x_{1}}+a v_{x_{2}}+1\right\}=0$,所以可知最优控制为:

动态规划与Pontryagin极小原理

特征方法

假定$H : \mathbb{R}^{n} \times \mathbb{R}^{n} \rightarrow \mathbb{R}$并考虑如下的Hamilton-Jacobi方程初值问题

做以下的记号:

下面引出特征方程,有:

因此

假定$u$为式子$(4.8)$的解,我们两边对$x_k$求导:

代入式子$(4.11)$中:

如果我们选取$\mathbf{x}(\cdot)$使得:

那么$(4.13)$成为:

这正是哈密顿方程:

接下来想要说明的是,如果我们能求解$(4.16)$,那么$(4.8)$也被相应求解。

并且有$u(\mathbf{x}(0), 0)=u\left(x^{0}, 0\right)=g\left(x^{0}\right)$,积分可得:

这即是$(4.8)$的解,只要$\mathbf{x}(\cdot)$与$\mathbf{p}(\cdot)$被求解出来。

动态规划与Pontryagin极小原理的联系

回忆式子$(4.1)$描述的更一般的动力系统,以及所定义的价值函数。这里主要的结果是,Pontryagin极小原理中的costate函数,实际上是价值函数$v$对$x$的梯度:

假定$\alpha^{}(\cdot), x^{}(\cdot)$为方程与损失泛函的最优控制和最优解,如果价值函数$v$为$C^2$的则极小原理中的costate$\mathbf{p}^{*}(\cdot)$满足以下的方程:

其证明较长,这里省略。

微分博弈

定义

在深度学习中,博弈存在于GAN为代表的这类生成模型中,这在控制理论中也有对应的理论。这一节中讨论双人零和博弈(这正是GAN使用的)。基本的想法是,两个玩家分别控制两个动力系统,其中一个需要达到某种极大,另一个达到某种极小,并也存在着一个损失泛函。

对于两者最好的策略是什么?显然双方的行为不可能独立,任何一方的控制都会取决于另一方当前的状态。

我们对这个双控制的动力系统作出如下的定义:

给定$0 \leq t<T$,以及两个集合$A \subseteq \mathbb{R}^{m}$,$B \subseteq \mathbb{R}^{l}$与函数$\mathrm{f} : \mathbb{R}^{n} \times A \times B \rightarrow \mathbb{R}^{n}$. 定义玩家一的控制为$\boldsymbol{\alpha}(\cdot) :[t, T] \rightarrow A$,玩家二的控制为$\boldsymbol{\beta}(\cdot) :[t, T] \rightarrow B$,最终的动力系统形式如下:

初始点$x \in \mathbb{R}^{n}$是被给定的。

博弈的损失泛函如下定义:

在博弈中,玩家一需要选取$\alpha(\cdot)$极大化$(5.2)$,玩家二则选取$\boldsymbol{\beta}(\cdot)$极小化$(5.2)$. 这就是我们所说的二人零和微分博弈,这里使用动态规划来研究这个问题。

映射$\Phi : B(t) \rightarrow A(t)$称为玩家一的策略若在任何$t \leq s \leq T$中,

我们可以认为$\Phi[\boldsymbol{\beta}]$是玩家一对玩家二所制定策略的响应,并且条件$(5.3)$表明了玩家一并不能得到未来状态的信息。

玩家二的策略为映射$\Psi : A(t) \rightarrow B(t)$,若对于任何$t \leq s \leq T$,

并定义策略集合:

接下来引入如下的价值函数,

下价值函数为:

上价值函数为:

一个玩家宣布他的策略,即他对另一玩家策略的响应,然后由另一个玩家来选取控制。选取策略的玩家更有优势,即总有下面的关系成立:

动态规划与Isaacs方程

假定$u,v$都是$C^1$的,那么$u$满足上Isaacs方程:

$v$满足下Isaacs方程:

Isaacs方程实际上是HJB在双人零和博弈上的推广,同样我们可以对其进行如下改写:

这里上哈密顿子定义为:

以及,

当博弈到达均衡时,就是我们所要求解的最优点,即有:

这时$u\equiv v$,更加直接地,一个均衡状态可以如下描述:

即双方任何一方进行控制的变动,都不会使得自己得到更好的结果。

Prontryagin极小原理与博弈

假定均衡条件$(5.14)$满足,并且得到了最优的$\alpha^{}(\cdot), \beta^{}(\cdot)$. 令$\mathbf{x}^{*}(\cdot)$为对应动力系统的解,定义:

那么有以下的伴随方程:

其中有博弈论哈密顿算子: