Silviase/jgov_v1.4_full_ann huggingface dataset:
分ける必要がある。

一般に、非線形システムを含むシステムの最適制御系の設計は、目的関数（evaluation function あるいは損失関数 loss function）を最適化にするようにシステムの入力を決定するという最適制御問題（optimal control problem）として定式化される。

制御対象のシステムを

$$ \begin{aligned}&\mathbf{x}\left(\mathbf{t}\right)=\mathbf{f}\left(\mathbf{x}\left(\mathbf{t}\right),\mathbf{u}\left(\mathbf{t}\right),\mathbf{t}\right)\quad&: 状態方程式 \\&\mathbf{y}\left(\mathbf{t}\right)=\mathbf{g}\left(\mathbf{x}\left(\mathbf{t}\right),\mathbf{u}\left(\mathbf{t}\right),\mathbf{t}\right)\quad&: 観測方程式 \\&\mathbf{x}(0)=\mathbf{x}_{0}\quad&: 初期状態 \end{aligned} $$

$$ \mathbf{u}(\mathbf{t})\in\mathbf{R}^{\mathrm{m}},\;\mathrm{y}(\mathbf{t})\in\mathbf{R}^{\mathrm{p}},\;\mathrm{x}(\mathbf{t})\in\mathbf{R}^{\mathrm{n}} $$

とし、目的関数を

$$ \mathbf{J}(\mathbf{x(t)},\mathbf{y(t)},\mathbf{u(t)},\mathbf{t}) $$

とすれば、最適制御問題は一般に

《制約条件》

：状態方程式

：観測方程式

：初期条件

$$ \mathbf{x}(\mathbf{t}_{\mathrm{f}})\in\Omega_{\mathrm{~f~}} $$

：终端条件

$$ \mathbf{u}(\mathbf{t})\in\Omega_{\mathbf{u}}(\mathbf{t}_{0}\leqq\mathbf{t}<\mathbf{t}_{\mathrm{f}}) $$

: 制御の許容可能性の条件

$$ \mathbf{x}(\mathbf{t})\in\Omega_{\mathrm{x}}(\mathbf{t}_{0}\leqq\mathbf{t}<\mathbf{t}_{\mathrm{f}}) $$

: 状態の許容可性の条件

のもとで、

$$ \begin{aligned}&《目的関数》\\&\quad\mathbf{J}(\mathbf{x}(\mathbf{t}),\mathbf{y}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\end{aligned} $$

を最小にする $ \mathbf{u}^{*}(\mathbf{t})(\mathbf{t}_{0} \leq \mathbf{t} < \mathbf{t}_{\mathrm{f}}) $ を求める

という問題となる。このとき、得られる最適入力 $ \mathbf{u}^{*}(\mathbf{t}) $ を、この最適制御問題における最適制御（optimal control input）といい、 $ \mathbf{u}^{*}(\mathbf{t}) $ に対する内部状態の変化の軌跡 $ \mathbf{x}^{*}(\mathbf{t}) (\mathbf{t}_{0} \leq \mathbf{t} \leq \mathbf{t}_{\mathrm{f}}) $ をこの問題の解あるいは最適経路（optimal trajectory）という。

システムの出力の観測に誤差はないとすれば、出力は内部状態によって間接的に評価できるので、目的関数は

$$ \mathbf{J}(\mathbf{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t}) $$

となり、制約条件中の観測方程式も不要になる。

一般に目的関数は、システムのエネルギー消費やコスト、目標とする内部状態の変化に対する実際の内部状態の変化のずれなど、入力や出力、内部状態が初期時点からたどって行く経路に関して設定される。すなわち一般に

$$ \mathbf{J}{=}\int_{t0}^{t f}\mathbf{J}_{1}(\mathbf{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\mathbf{d t} $$

と表現される。また終端条件は、制御終了時刻において内部状態を指定された状態にしなければならないという制約である。しかしときには、完全に指定の状態に一致しなくても、その状態からのずれが小さければ小さいほど良いという評価でもよいことがある。このような場合は、制約条件から終端条件をはずして、目的関数を

$$ \mathbf{J}{=}\int\text{t}_{0}^{\mathrm{tf}}\mathbf{J}_{1}(\mathbf{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\mathbf{d}\mathbf{t}{+}\mathbf{J}_{2}(\mathbf{x}(\mathbf{t}_{\mathrm{f}}),\mathbf{t}_{\mathrm{f}}) $$

のように定式化するのが一般的である。

ところで上の定式化では、最適制御を特定の初期条件の下での入力 u(t) の時間的な変化として求めている。これは開ループ制御によって最適制御を行うことに他ならない。しかし実際の制御問題においては、特定の初期条件だけを考慮したような制御は、望ましい制御とはいえない。したがって、最適制御でも閉ループ制御を考えて、目的関数を最小にする最適制御規則 (optimal control rule)
$$ \mathbf{u}^{*}(\mathbf{t}){=}\boldsymbol{\varphi}^{*}(\mathbf{x}(\mathbf{t}),\mathbf{t}) $$

を求めるような問題も考えられる。しかし一般にこの問題を解くのは特殊な場合を除いて非常に難しい。

最近のコンピュータの性能の向上には目ざましいものがあり、実際の制御の場面で、ある初期条件下での開ループ制御の最適解ならば、かなり高速に求められるものが少なくない。そこで、適当な間隔でシステムの状態を観測し、これを初期条件として毎回最適な開ループ制御を計算してシステムに入力するという制御方式も行われており、開ループ制御による最適制御の意義も改めて見直されている。

最適制御問題は、目的関数の形式によって以下のように分類される。

a）Bolza 型

$$ \mathbf{J}{=}\int\limits_{t0}^{\mathrm{tf}}\mathbf{J}_{1}(\mathbf{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\mathbf{dt}+\mathbf{J}_{2}(\mathbf{x}(\mathbf{t}_{\mathrm{f}}),\mathbf{t}_{\mathrm{f}}) $$

b) Mayer 型

$$ \mathbf{J}=\mathbf{J}_{2}(\mathbf{x}(\mathbf{t}_{\mathrm{f}}),\mathbf{t}_{\mathrm{f}}) $$

c) Lagrange 型

$$ \mathbf{J}{=}\int\limits_{t0}^{\mathrm{t f}}\mathbf{J}_{1}(\mathbf{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\mathrm{d}\mathbf{t} $$

しかし、これはあくまで最適制御問題の表現上の分類であって、同一の制御問題を状態変数を付け加えるなどの操作を施すことによって、いずれの型としても定式化することが可能である。

一方、最適制御問題は、終端条件に現れる最終時刻 $ t_{f} $ と最終状態 $ x(t_{f}) $ に課せられる制約により、次の4つの型に分類される。

1）固定終端時間・固定終端条件問題

$ t_{f} $ が指定されており、 $ \Omega_{f} $ は $ R_{n} $

の真部分集合

2）固定終端時間・自由終端条件問題

$ t_{f} $ が指定されており、 $ \Omega_{f}=R_{n} $

3）自由終端時間・固定終端条件問題

$ t_{f} $ は指定されず、 $ \Omega_{f} $ は $ R_{n} $ の

真部分集合

4）自由終端時間・自由終端条件問題

$ t_{f} $ は指定されず、 $ \Omega_{f}=R_{n} $

もちろん、1)や3)の固定終端条件問題では、a) Bolza 型や b) Mayer 型の目的関数に含まれる J₂ は事実上意味を失う。

上のそれぞれの終端条件の型によって、最適制御の実際的な意味は異なる。たとえば1）は決められた時刻にシステムの内部状態を特定の値にするようなコストを最小にする最適制御、2）は決められた時刻までにかかるコストを最小にするような最適制御、3）はシステムの内部状態を最短時間で目標値にするような最適制御の問題である。4）は特殊な最適制御問題であり、J_{1}が特殊な関数であるときに限り意味のある問題となる。

最適制御理論においてシステムが線形であり、さらに目的関数 J が 2 次形式(quadratic form)

$$ \mathbf{J}=\frac{1}{2}\int\limits_{t0}^{t f}\left\{\begin{array}{l l}\left|\begin{array}{l l}\mathbf{x}(\mathbf{t})&\end{array}\right|_{Q(\mathbf{t})}^{2}+\left|\begin{array}{l l}\mathbf{u}(\mathbf{t})&\end{array}\right|_{R(\mathbf{t})}^{2}\end{array}\right.\mathbf{d}\mathbf{t}+\frac{1}{2}\left.\begin{array}{l l}\mathbf{x}(\mathbf{t}_{f})&\end{array}\right|_{F}^{2} $$

で与えられるような問題を線形2次形式問題と呼んで、特別に扱っている。これは、最適制御問題では以下に述べるように、一般には最適制御（問題の解）の必要条件しか得られないのに対して、線形2次形式問題では必要十分条件が、状態フィードバックによる最適制御規則として得られるからである。特に、線形2次形式問題
の最適解において $ t_{f} \rightarrow \infty $ としたときに得られる フィードバック制御系をレギュレーターと呼ぶ。

#### 2.2.2 最大原理と最適制御の必要条件

最適制御問題は、システムへの入力の時間的な変化と、それによって生じる内部状態の時間的な変化の組合せの中で、システムにとって許容される（admissible）もののうち両者の汎関数（目的関数）を最小にするものを求める問題である。一般に、ある汎関数の極値を求める問題は変分問題と呼ばれる。そしてその解法は変分法（variational calculus）といわれて、主に解析力学などで用いられてきた。したがって、最適制御問題も変分法によって解くことができる。現在の最適制御理論では、主に現実の制御問題に適用できるように変分法を一般化し、それを最大原理（maximum principle）と呼んで、最適制御の条件を求めるのに用いている。

さきに述べたように、最適制御問題にはさまざまな定式化があり、それぞれの形式は互いに変換することができる。したがって、ある1つの形式に対する最大原理を求めておけば、別の形式に対する最大原理は形式的に変換するだけで得られる。そこで、ここでは基本形としてb) Mayer型を取り上げ、この型の最適制御問題に対する最大原理を導出する。他の型の最適制御問題に対する最大原理に関しては、巻末にあげた最適制御理論に関する参考例を参照されたい。

ところで、一般的な最適制御問題の定式化ではシステムのとりうる内部状態に制約（状態の許容可能性の条件）がある。このような制約は制御問題の理論的解析を非常に困難にする。そこで、以下では解析的な扱い易さの点を考慮して、システムの入力のみに制約（制御の許容可能性の条件）がある最適制御問題を考える。

ここで改めて、基本となる固定終端時間・自由終端条件の Mayer 型問題を定式化する。

## 【基本問題】

$ u(t)\in\mathbb{R}^{m},x(t)\in\mathbb{R}^{n} $ として、

《制約条件》

$$ \begin{aligned}&\dot{\mathbf{x}}\left(\mathbf{t}\right)=\mathbf{f}\left(\mathbf{x}\left(\mathbf{t}\right),\mathbf{u}\left(\mathbf{t}\right)\right)\quad&: 状態方程式 \\&\mathbf{x}(0)=\mathbf{x}_{0}\quad&: 初期条件 \\&\mathbf{u}\left(\mathbf{t}\right)\in\Omega_{\mathbf{u}}(0\leq\mathbf{t}<\mathbf{t}_{\mathrm{f}})\quad&: 制御の許容可 \\&& 性能性の条件 \\&\mathbf{t}_{\mathrm{f}}\quad&: 固定終端時間 \\&&( 指定 )\end{aligned} $$

の下で、

《目的関数》

$$ \mathbf{J}=\mathbf{K}^{\mathrm{T}}\mathbf{x}(\mathbf{t}_{\mathrm{f}}),\mathbf{K}\in\mathbf{R}^{\mathrm{n}}: 定数 \mathrm{ ベクトル } $$

を最小にする $ \mathbf{u}^{*}(\mathbf{t})(0 \leq \mathbf{t} < \mathbf{t}_{\mathrm{f}}) $ を求める

ここで、システムの状態方程式 f が時刻 t の陽（explicit）な関数でなくなっているのは、人工的な状態変数 $ t=x_{n+1} $ を導入することによって上の形式に変換できるからである。また、この形式では初期時刻 $ t_{0}=0 $ としても一般性を失わない。

## ところで、一般に状態方程式が

$$ \dot{\mathbf{x}}(\mathbf{t})=\mathbf{A}(\mathbf{t})\mathbf{x}(\mathbf{t}),\mathbf{x}(\mathbf{t})\in\mathbf{R}^{n} $$

で表せる線形システムに対して、状態方程式が

$$ \mathbf{\dot{p}(t)=-\Lambda(t)^{T}p(t),p(t)\in R^{n}} $$

となるようなシステムを、もとのシステムの随伴（共状態）システム（ad-joint（or costate）system）といい、p(t)を随伴（共状態）ベクトル（ad-joint（or costate）vector）と呼ぶ。また随伴システムの状態方程式を随伴（共状態）方程式（adjoint（or costate）equation）と呼ぶ。そして、もとのシステムの状態方程式の任意の解とそれに対する随伴方程式の解の内積は、一定
$$ \begin{aligned}&\dot{\mathbf{p}}^{*}(\mathbf{t})=-\Big[\frac{\partial\mathbf{f}}{\partial\mathbf{x}}\Big]^{\mathrm{T}}\mathbf{x}^{*}(\mathbf{t}),\mathbf{u}^{*}(\mathbf{t})\mathbf{p}^{*}(\mathbf{t})\\ &\\&\mathbf{P}^{*}(\mathbf{t}\mathbf{f})=-\mathbf{K}\\ \end{aligned} $$

の解 $ p^{*}(t) $ が存在する

ことで与えられる。これを最大原理という。

最大原理において $ p^{*}(t) $ および $ x^{*}(t) $ は未知であるので、この式を満たす制御入力 $ u^{*}(t) $ は

$$ \mathbf{u}^{*}(\mathbf{t})=\mathbf{h}(\mathbf{p}^{*}(\mathbf{t}),\mathbf{x}^{*}(\mathbf{t})) $$

のように $ p^{*}(t) $ と $ x^{*}(t) $ の関数としてしか求まらない。そこで、実際に入力を時間の関数として与えるためには、この関数を状態方程式および随伴方程式に代入して

$$ \begin{aligned}&\dot{\mathbf{x}}^{*}(\mathbf{t})=\mathbf{f}\left\{\mathbf{x}^{*}(\mathbf{t}),\mathbf{h}(\mathbf{p}^{*}(\mathbf{t}),\mathbf{x}^{*}(\mathbf{t}))\right\}\\&\dot{\mathbf{p}}^{*}(\mathbf{t})=-\left[\frac{\partial\mathbf{f}\left\{\mathbf{x}^{*}(\mathbf{t}),\mathbf{h}(\mathbf{p}^{*}(\mathbf{t}),\mathbf{x}^{*}(\mathbf{t}))\right\}}{\mathbf{x}}\right]^{\mathrm{T}}\begin{aligned}\\ &\mathbf{x}^{*}(\mathbf{t})&\mathbf{p}^{*}(\mathbf{t})\\ &\mathbf{h}(\mathbf{p}^{*}(\mathbf{t}),\mathbf{x}^{*}(\mathbf{t}))\\ &\end{aligned}\\ \end{aligned} $$

を連立させて、境界条件

$$ \begin{aligned}&\mathbf{x}^{*}(0)=\mathbf{x}_{0}\\&\mathbf{p}^{*}(\mathbf{t}_{\mathrm{f}})=-\mathbf{K}\\ \end{aligned} $$

のもとで解くことが必要である。

このようにして、最大原理を満たす制御入力 $ u^{*}(t) $ は開ループ制御の形で求めることができる。ここで、最大原理は最適制御のための必要条件であるので、 $ u^{*}(t) $ は必ずしも最適制御となっていないこともあることに注意しなければならない（つまり最大原理は必要条件であって十分条件ではない）。もちろん、 $ u^{*}(t) $ が最適制御であれば最大原理を満たし、このとき得られる $ x^{*}(t) $ は最適経路になる。

ここで、最大原理を満たす制御入力 $ \mathbf{u}^{*}(\mathbf{t}) $ が閉ループ制御として求められるような最適制御問題として、固定終端時間・自由終端条件の線形 2 次形式問題を紹介しておく。

【線形 2 次形式問題】

u(t)∈R^{m}, x(t)∈R^{n} とし、A(t) と B(t) はそれぞれ n×n, n×m 行列とする。このとき

《制約条件》

$$ \begin{aligned}&\dot{\mathbf{x}}\left(\mathbf{t}\right)=\mathbf{A}\left(\mathbf{t}\right)\mathbf{x}\left(\mathbf{t}\right)+\mathbf{B}\left(\mathbf{t}\right)\mathbf{u}\left(\mathbf{t}\right)\quad&: 状態方程式 \\&\mathbf{x}(0)=\mathbf{x}_{0}\quad&: 初期条件 \\&\mathbf{t}_{f}\quad&: 固定終端 \\&& 時間 ( 指定 )\end{aligned} $$

ものとで

《目的関数》

$$ \begin{aligned}\mathbf{J}=&\frac{1}{2}\int\limits_{0}^{\mathbf{t}_{\mathrm{f}}}\mathbf{\Omega}\left\{\left.\right|\mathbf{x}(\mathbf{t})\left.\right|_{\mathbf{Q}(\mathbf{t})}^{2}+\left.\right|\mathbf{u}(\mathbf{t})\left.\right|_{\mathbf{R}(\mathbf{t})}^{2}\right\}\mathbf{d}\mathbf{t}+\\&\frac{1}{2}\left.\right|\mathbf{x}(\mathbf{t}_{\mathrm{f}})\left.\right|_{\mathbf{F}}^{2}\end{aligned} $$

を最小にする $ u^{*}(t)(0 \leq t < t_{\mathrm{f}}) $ を求める

ただし R(t) は $ m \times m $ の正定対称行列、F と Q(t) は $ n \times n $ の非負定対称行列とする

この線形2次形式の最適制御問題の最適制御を求めよう。

上に述べた随伴ベクトルを $ p^{*}(t) $ とすれば、これは

$$ \begin{aligned}\dot{\textbf{p}}^{*}(\textbf{t})&=-\mathrm{A}^{\mathrm{T}}(\textbf{t})\textbf{p}^{*}(\textbf{t})+\mathrm{Q}(\textbf{t})\textbf{x}^{*}(\textbf{t})\\\textbf{p}^{*}(\textbf{t}_{\mathrm{f}})&=-\mathrm{F}\textbf{x}^{*}(\textbf{t}_{\mathrm{f}})\end{aligned} $$
を満たす。最適制御 u*(t) は、最大原理によって Hamilton 関数

$$ \begin{aligned}&\mathrm{H}(\mathrm{p}^{*}(\mathrm{t}),\mathrm{x}^{*}(\mathrm{t}),\mathrm{u}(\mathrm{t}))\\=&\mathrm{p}^{*\mathrm{T}}(\mathrm{t})(\mathrm{A}(\mathrm{t})\mathrm{x}^{*}(\mathrm{t})+\mathrm{B}(\mathrm{t})\mathrm{u}(\mathrm{t}))\\&-\frac{1}{2}\mathrm{x}^{*\mathrm{T}}(\mathrm{t})\mathrm{Q}(\mathrm{t})\mathrm{x}^{*}(\mathrm{t})-\frac{1}{2}\mathrm{u}^{\mathrm{T}}(\mathrm{t})\mathrm{R}(\mathrm{t})\mathrm{u}(\mathrm{t})\end{aligned} $$

を最大にするので

$$ \left[\frac{\partial\mathrm{~H~}}{\partial\mathrm{~u~}}\right]=0 $$

として

$$ \mathbf{u}^{*}(\mathbf{t})=-\mathbf{R}^{\cdot1}(\mathbf{t})\mathbf{B}^{\mathrm{T}}(\mathbf{t})\mathbf{p}^{*}(\mathbf{t}) $$

を得る。この結果をもとの制約条件の式に代入して、随伴ベクトルの満たす微分方程式と並べて書けば、次のような2点境界値問題が得られる。

$$ \begin{aligned}&\dot{\mathbf{x}}^{*}(\mathbf{t})=\mathbf{A}(\mathbf{t})\mathbf{x}^{*}(\mathbf{t})+\mathbf{B}(\mathbf{t})\mathbf{R}^{\cdot1}(\mathbf{t})\mathbf{B}^{\mathrm{T}}(\mathbf{t})\mathbf{p}^{*}(\mathbf{t})\\&\dot{\mathbf{p}}^{*}(\mathbf{t})=-\mathbf{A}(\mathbf{t})^{\mathrm{T}}\mathbf{p}^{*}(\mathbf{t})\mathbf{Q}(\mathbf{t})\mathbf{x}^{*}(\mathbf{t})\\&\mathbf{x}^{*}(0)=\mathbf{x}_{0}\\&\mathbf{p}^{*}(0)=-\mathbf{F}\mathbf{x}^{*}(\mathbf{t}_{\mathrm{f}})\\ \end{aligned} $$

このとき $ p^{*}(0) $ を $ p_{0} $ と書くと、これは未知ではあるが、終端条件を用いて $ x_{0} $ の 1 次式で表すことができる。すると $ x^{*}(t) $ も $ p^{*}(t) $ も、ともに $ x_{0} $ の式（ $ x_{0} $ からの時間発展）で書けることになり、結局 $ p^{*}(t) $ は $ x^{*}(t) $ によって、次の形で与えられる。

$$ \mathbf{\Gamma}-\mathbf{p}^{*}(\mathbf{t})=-\mathbf{P}(\mathbf{t})\mathbf{x}^{*}(\mathbf{t}) $$

ただし P(t) は

$$ \begin{aligned}-\dot{\mathbf{P}}(\mathbf{t})=&\mathbf{A}^{\mathrm{T}}(\mathbf{t})\mathbf{P}(\mathbf{t})+\mathbf{P}(\mathbf{t})\mathbf{A}(\mathbf{t})\\&-\mathbf{P}(\mathbf{t})\mathbf{B}(\mathbf{t})\mathbf{R}^{\cdot1}(\mathbf{t})\mathbf{B}^{\mathrm{T}}(\mathbf{t})\mathbf{P}(\mathbf{t})+\mathbf{Q}(\mathbf{t})\end{aligned} $$

$$ \mathbf{P}(\mathbf{t}_{\mathrm{f}})=\mathbf{F}\mathbf{x}^{*}(\mathbf{t}_{\mathrm{f}}) $$

によって与えられる行列である。

この結果を上の u*(t) の式に代入すれば、最適制御は

$$ \mathbf{u}^{*}(\mathbf{t})=-\mathbf{R}^{\cdot1}(\mathbf{t})\mathbf{B}^{\mathrm{T}}(\mathbf{t})\mathbf{P}(\mathbf{t})\mathbf{x}^{*}(\mathbf{t}) $$

の形、すなわち状態フィードバック（最適制御規則）として得られることになる。

#### 2.2.3 最適制御問題の解法：動的計画法

## (DP) と非線形計画法 (NLP)

最適制御の必要条件は最大原理によって与えられるので、最大原理を満たす内部状態の変化 x*(t) および随伴状態の変化 p*(t) を求めることによって、最適制御 u*(t) を得ることができる。これを、最適制御問題の間接解法という。しかし、一般に解析的にこれを求めるのはほとんどの場合不可能であり、実際には数値計算に頼らざるを得ない。これに対して、どうせ数値計算で解くのであれば、最大原理を用いずに、許容可能な制御の中で目的関数を最小にするものを、数理計画法における最適化の手法によって求めることも考えられる。このように、動的計画法（DP：dynamic programming）や非線形計画法（NLP：non-linear programming）などの最適化の手法によって、最適制御を直接に求める方法を直接解法という。

動的計画法による最適制御問題の解法は、最適性原理（optimality principle）とよばれる原理に基づいて、最適制御問題を特殊な形式で定式化することによって与えられる。もちろん、最適制御理論における最大原理は、動的計画法の定式化に基づいて導出することもできる。一方、非線形計画法による解法は、最適制御問題を目的関数を最小にする許容可能な制御を探索することであり、もとの問題を静的な最適化問題として定式化することによって得られる。このとき、非線形計画法における最適解の必要条件、すなわち Kuhn-Tucker 条件は、最適制御理論における最大原理と等価な条件と考えることができる。
## (1) 動的計画法 (DP)

一般の動的計画法の定式化では、最適決定問題は「順序付けられた多段階（multi-stage）」の最適決定問題に分割される。そして、ある段階における決定はそれ以降の段階の決定問題にのみ影響を与えるようにする。このように分割すれば、全体の最適解は各段階の最適解の系列としてあたえられる。この自明の事実を述べたものが最適性原理である。

[最適性原理] 多段階決定過程において、各段階の決定が全体の最適決定を与えるためには、各段階における決定は、その段階の初期状態やそれ以前の段階での決定がどんなものであるかによらず、最適な決定になっていなければならない。

動的計画法は、この原理を順序付けられた段階に対して帰納的に（動的に）適用することにより、もとの問題をより解きやすい小さな問題の系列に変換して徐々に解いて行く手法である。

もちろん、「順序付けられた段階」という概念は必ずしも静的なものだけを意味するのではなく、離散的な時間で表現された動的なシステムの各期間を段階と考えることもできるし、連続的な時間で表現された動的システムでも、次のよりにして段階を定義することができる。すなわち、連続時間システムの最適制御問題における最適制御 $ \mathbf{u}^{*}(\mathbf{t})(\mathbf{t}_{0} \leq \mathbf{t} < \mathbf{t}_{\mathrm{f}}) $ は、指定された時間区間 $ [t_{0}, t_{f}] $ を $ [t_{0}, t_{1}] $ , $ [t_{1}, t_{2}] $ , $ \cdot \cdot \cdot $ , $ [t_{n}, t_{f}] $ のように適当な区間に区切って考えれば、各区間内の最適制御の系列 $ \mathbf{u}^{*}(\mathbf{t}) (\mathbf{t}_{0} \leq \mathbf{t} < \mathbf{t}_{1}) $ , $ \mathbf{u}^{*}(\mathbf{t}) (\mathbf{t}_{0} \leq \mathbf{t} < \mathbf{t}_{2}) $ , $ \cdot \cdot \cdot $ , $ \mathbf{u}^{*}(\mathbf{t}) (\mathbf{t}_{n} \leq \mathbf{t} < \mathbf{t}_{\mathrm{f}}) $ と考えることができる。したがって、動的計画法は連続時間システムの最適制御問題にも適用できる。しかしこのような問題では、最適制御が解析的に求められる場合を除いて、数値計算を行うときには離散時間システムの最適制御問題として扱うのが普通である。そこで、ここでは離散時間システムの最適制御問題に対する動的計画法による解法を述べる。

【離散時間最適制御問題】

《制約条件》

$$ \begin{aligned}&x(t+1)=f(x(t),u(t),t)\quad&: 状態方程式 \\&(t=0,1,\cdot\cdot\cdot,T-1)\\&x^{*}(0)=x_{0}\quad&: 初期条件 \\&T\quad&: 終端期間（指定 )\\&u(t)\in\Omega_{u}(t=0,1,\cdot\cdot\cdot,T-1): 制御 \emptyset\\& 許容可能性条件 \end{aligned} $$

を満たし

《目的関数》

$$ \mathbf{J}=\sum_{t=0}^{T-1}\mathbf{v}(\mathbf{x}(t),\mathbf{u}(t),\mathbf{t})+\mathbf{v}_{T}(\mathbf{x}(T)) $$

$$ \begin{aligned}& を最小にする \mathbf{u}^{*}(\mathbf{t}),(\mathbf{t}=0,1,\cdot\cdot\cdot,\mathbf{T}\cdot1)\\& を求める \end{aligned} $$

を考える。ここで、状態方程式が離散的な時間（期間）t の陽（explicit）な関数であるのは時変システムであることを意味し、目的関数が t の陽な関数であるのは、このシステムが各期間において目的関数が変化してもよいことを表す。もちろん、この問題は定係数システムや目的関数が変化しない場合を含んでいる。また、目的関数中の $ v_{T} $ は最終状態に対する評価を表す。

さて、この問題における離散な時間 t=0 から t=T-1 を決定の「順序付けられた段階」と解釈し、第 t 段階での決定の満たすべき条件を考える。

いま、第 t-1 段階までの制御が決定されているとすれば、第 t 段階におけるシステムの状態 x(t) は与えられたものと考えられる。このとき、第 t 段階以降第 T-1 段階（最後の制御）までの最適制御の系列は、x(t) によって決まるはずである。これを

$$ \mathbf{u}^{*}(\mathbf{t}),\mathbf{u}^{*}(\mathbf{t}+1),\ldots,\mathbf{u}^{*}(\mathrm{T}-2),\mathbf{u}^{*}(\mathrm{T}-1) $$
とする。しかし、この系列は第 t 段階においては未知であるので、もちろん u*(t) を決定することはできない。そこで、第 t 段階において任意の制御 u(t) を行ったとし、これによって決まる x(t+1) に対して、第 t+1 段階以降第 T-1 段階までは最適制御を行ったと仮定すると、第 t+1 段階以降の最適制御の系列は上とは異なり

$$ \begin{aligned}&u^{**}(t+1),\ldots,u^{**}(T-2),u^{**}(T-1)\\ &\\ & となるはずである。\\ & 最適性原理は、第 t 段階において u(t)=u^{*}(t)\\ & と決定したときには \\ &\\ &\quad u^{*}(t+1),\ldots,u^{*}(T-2),u^{*}(T-1)\\ &\\ &\quad と \\ &\\ &\quad u^{**}(t+1),\ldots,u^{**}(T-2),u^{**}(T-1)\\ &\\ & は一致しなければならないことを主張するものである。\\ \end{aligned} $$

この最適性原理を用いれば、上の問題の解法は以下のようにして与えられる。

まず、第 t 段階の目的関数おける $ v(x(t), u(t), t) $ は、第 t 段階での損失と考えることができるので、第 t 段階の状態 $ x(t) $ を与えたときに第 t 段階から第 T 段階までの総損失は、 $ x(t) $ および、 $ u(t), u(t+1), \ldots, u(T-2), u(T-1) $ の関数として与えることができる。これを $ V_{t}(x(t), u(t), \ldots, u(T-1)) $ とする。このとき明らかに

$$ \begin{aligned}&\mathrm{V}_{\mathrm{t}}(\mathrm{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\ldots,\mathbf{u}(\mathrm{T}-1))\\=&\mathrm{v}(\mathrm{x}(\mathbf{t}),\mathbf{u}(\mathbf{t}),\mathbf{t})\\&+\mathrm{V}_{\mathrm{t}+1}(\mathrm{x}(\mathbf{t}+1),\mathbf{u}(\mathbf{t}+1),\ldots,\mathbf{u}(\mathrm{T}-1))\end{aligned} $$

となっている。ただし、第 T 段階においては制御を考える必要がないので、

$$ \mathrm{V}_{\mathrm{T}}(\mathrm{x}(\mathrm{T}))=\mathrm{v}_{\mathrm{T}}(\mathrm{x}(\mathrm{T})) $$

である。

ここで、第 t 段階の状態が $ x(t) $ であるという条件のもとで、第 t 段階以降第 T-1 段階まで最適制御を行ったとしたときの $ V_{t} $ の値を $ V^{*}_{t}(x(t)) $ とすれば、先に述べた最適性原理によって

$$ \begin{aligned}&V^{*}{}_{t}(x(t))=V_{t}(x(t),u^{*}(t),\ldots,u^{*}(T-1))\\ &\begin{aligned}\\ =&\min\left\{v(x(t),u(t),t)\right\}\\&u(t)\\&+V_{t+1}(x(t+1),u^{**}(t+1),\ldots,\\&u^{**}(T-1))\\ &\end{aligned},\\ &\\=&\min\left\{v(x(t),u(t),t)\right\}\\&u(t)\\&+V_{t+1}(x(t+1),u^{*}(t+1),\ldots,\\&u^{*}(T-1))\\ &\end{aligned},\\ &\\=&\min\left\{v(x(t),u(t),t)\right\}+V^{*}{}_{t+1}(x(t+1))\\&u(t)\\ &\\&V^{*}{}_{T}(x(T))=v_{T}(x(T))\\ \end{aligned} $$

となっていなければならない。この式は $ V^{*} $ (x(t))(t=0,1,...T-1)に関する逆向きの漸化式になっており、第t段段での最適制御u*(t)および $ V^{*} $ (x(t))の値は、 $ V^{*} $ (x(t+1))が与えられればx(t)の関数u*(x(t))として求められる。したがって、全段階にわたる最適制御を求めるには、システムの状態方程式を使って以下のように計算すればよい。

$$ \begin{aligned}&1)\quad\mathbf{t}=\mathbf{T}-1\ とすると \\\ &\begin{aligned}\mathrm{V}^{*\mathrm{T}\cdot1}(\mathrm{x}(\mathrm{T}-1))=&\min_{\mathrm{u}(\mathrm{T}-1)}\{\mathrm{v}(\mathrm{x}(\mathrm{T}-1),\mathrm{u}(\mathrm{T}-1),\\&\mathrm{T}-1)\}+\mathrm{v}_{\mathrm{T}}(\mathrm{x}(\mathrm{T}))\end{aligned}\\ &\begin{aligned}\\ =&\min_{\mathrm{u}(\mathrm{T}-1)}\{\mathrm{v}(\mathrm{x}(\mathrm{T}-1),\mathrm{u}(\mathrm{T}-1),\mathrm{T}-1)\}+\\ &\end{aligned}\\ \end{aligned} $$
$$ \mathrm{v}_{\mathrm{T}}(\mathrm{f}(\mathrm{x}(\mathrm{T}-1),\mathbf{u}(\mathrm{T}-1),\mathrm{T}-1) $$

となるので、すべての x(T - 1) に対する最適制御 u*(x(T - 1)) と V^{*_{T·1}}(x(T - 1)) を求めておく。

2）t=T-2とすると

$$ \begin{aligned}\mathrm{V}^{*}_{\mathrm{T}\cdot2}(\mathrm{x}(\mathrm{T}-2))=&\min_{\mathrm{u}(\mathrm{T}-2)}\{\mathrm{v}(\mathrm{x}(\mathrm{T}-2),\mathrm{u}(\mathrm{T}-2),\\&\mathrm{T}-2)\}+\mathrm{V}^{*}_{\mathrm{T}\cdot1}(\mathrm{x}(\mathrm{T}-1))\end{aligned} $$

となるが、 $ \mathrm{x}(\mathrm{T}-1)=\mathrm{f}(\mathrm{x}(\mathrm{T}-2),\mathrm{u}(\mathrm{T}-2),\mathrm{T}-2) $ であるので、1）で求めた $ \mathrm{V}^{*_{\mathrm{T}-1}}(\mathrm{x}(\mathrm{T}-1)) $ を使えばすべての $ \mathrm{x}(\mathrm{T}-2) $ に対して上の式を満たすような $ \mathrm{u}^{*}(\mathrm{x}(\mathrm{T}-2)) $ および $ \mathrm{V}^{*_{\mathrm{T}-2}}(\mathrm{x}(\mathrm{T}-2)) $ を求めることができる。そして、1）で得られている $ \mathrm{u}^{*}(\mathrm{x}(\mathrm{T}-1)) $ 、 $ \mathrm{u}^{*}(\mathrm{x}(\mathrm{T}-2)) $ を一緒に考えれば、すべての $ \mathrm{x}(\mathrm{T}-2) $ に対して、第 T-2 段および第 T-1 段の最適制御が得られていることになる。

3） $ t=T-3,\cdots,1 $ として2）と同様な計算を行う。

$$ 4)\ t=0\ とすると $$

$$ \mathrm{V}^{*}{}_{0}(\mathrm{x}(0))=\underset{\mathrm{u}(0)}{\min}\left\{\mathrm{v}(\mathrm{x}(0),\mathrm{u}(0),0)\right\}+\mathrm{V}^{*}{}_{1}(\mathrm{x}(1)) $$

Fig.2.6 動的計画法の手続き

離散システム（多段階システム）

動的計画法による逆向き解法の手続き

となるが、 $ \mathrm{x}(0) = \mathrm{x}_{0} $ が初期条件として与えられているので3)までで求められている $ \mathrm{V}^{*}_{1}(\mathrm{x}(1)) = \mathrm{V}^{*}_{1}(\mathrm{f}(\mathrm{x}_{0}, \mathrm{u}(0), 0)) $ を使えば $ \mathrm{u}^{*}(0) $ は決定される。したがって、 $ \mathrm{x}(1) $ を $ \mathrm{x}(1) = \mathrm{f}(\mathrm{x}_{0}, \mathrm{u}^{*}(0), 0) $ によって計算すれば、3)までの計算過程を逆にたどって行くことにより全段階における最適制御の系列が求められる。

実際の計算においては、各段階における最小化には、通常、非線形計画法におけるさまざまな数値計算手法が用いられる。

このようにして最適制御問題における開ループ最適制御 u*(t) (t=0,1,・・・,T-1) は動的計画法によって求められる。ただし、上に示したようにこの手法は膨大な計算量と記憶を必要とするので、実際の計算では段階数や制御入力、状態量の離散化の程度を考慮しなければならない。また、この手法では全段にわたる開ループ最適制御を求めるために、各段階毎に与えられた初期条件のもとでの最適制御を求めている。そこでこれらをすべて記憶しておけば、実際の制御を行っている間に外乱が加わり状態が変化してしまったとしても、その状態を初期条件とした
場合の最適制御もすでに計算され記憶されているので、ちょうど状態フィードバックを考えた閉ループ制御と同じ効果をもたせることができるという利点もある。

## (2) 非線形計画法 (NLP)

非線形計画法は、制約条件のある静的(static)な最適化問題を解くための一般的な手法である。しかし、動的なシステムの最適化問題も、システムの動的な挙動が明示的にならないように定式化を行うことによって、非線形計画法の手法をそのまま適用することができる。そこで、ここではまず非線形計画法の一般的な定式化に基づいて、最適解の必要条件であるKuhn-Tucker条件を与える。次に、離散時間システムの最適制御問題を静的な最適化問題として定式化して、この問題におけるKuhn-Tucker条件、すなわち最適制御の必要条件を考える。

一般に、非線形計画法が適用される制約条件のある静的な最適化問題（最小化問題）とは、以下のような問題である。

【制約条件付き最小化問題】

$$ \begin{aligned}&x\in\mathbb{R}^{n},v:\mathbb{R}^{n}\rightarrow\mathbb{R}^{1},g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{ng},h:\mathbb{R}^{n}\rightarrow\mathbb{R}^{nh}\\& として \\ \end{aligned} $$

《制約条件》

$ g(x) \leq 0 $ ：不等式制约

$ h(x)=0 $ : 等式制约

を満たし

《目的関数》

v(x)

を最小にする x を求める

この定式化では等式制約条件 $ h(x)=0 $ が含まれているが、これは

$$ \begin{aligned}\mathbf{h}(\mathbf{x})&\leqq0\\ -\mathbf{h}(\mathbf{x})&\leqq0\end{aligned} $$

という２つの不等式に分けて考えれば、不等式制約として扱える。そこで、Kuhn-Tucker 条件の導出は不等式制約条件だけの場合について行う。

まず、Lagrange 関数を次のように定義する。

$$ \mathbf{L}(\mathrm{x}、\lambda\text{ )}=\mathrm{v}(\mathrm{x})+\lambda^{\mathrm{T}}\mathrm{g}(\mathrm{x}) $$

ここで、制約条件を満たす x の集合から境界上の特異点を排除するために、次の仮定をおく。

<束縛資格条件>

$ g(x)=0 $ となるすべての点 x に対して

$$ \frac{\partial\ g(\mathbf{x})}{\partial\ \mathbf{x}}\quad\mathbf{d}\mathbf{x}\leqq0 $$

を満たす任意のベクトル微分 dx は、制約条件 $ g(x) \leq 0 $ を満たす集合内のある弧に接する。

この条件を仮定すると、次の Kuhn-Tucker の定理が成り立つ。

[Kuhn-Tuckerの定理]

$ x^{*} $ が上述の最適化問題の解となるための必要条件は、

$$ \left[\frac{\partial L(\mathbf{x},\lambda)}{\partial\mathbf{x}}\right]_{\mathbf{x}^{*},\lambda^{*}}=0 $$

$$ \left[\frac{\partial L(x,\lambda)}{\partial\lambda}\right]_{x^{*},\lambda^{*}}\leq0 $$

$$ \left[\begin{array}{c}\partial L(\mathbf{x},\lambda)\\ \partial\lambda\end{array}\right]_{\mathbf{x}^{*},\lambda^{*}}\quad\lambda^{*}=0 $$
を満たすλ $ *\geqq0 $ が存在することである。

[証明]

$ x^{*} $ が境界上の点である場合

$$ \left\lfloor\frac{\partial\mathrm{~g~}\left(\mathrm{x}\right)}{\partial\mathrm{~x~}}\right\rfloor\quad\mathrm{d x}\quad\leqq0 $$

を満たすすべてのベクトル微分に対して

$$ \left[\begin{array}{c}\partial\mathrm{v}\quad(\mathrm{x})\\ \partial\mathrm{x}\end{array}\right]_{\mathrm{x}^{*}}\quad\mathrm{d}\mathrm{x}\quad\geq0 $$

が成立しなければならない。すると、Farkasの補助定理によって

$$ \left[\begin{array}{c}\frac{\partial\mathbf{v}(\mathbf{x})}{\partial\mathbf{x}}\\\end{array}\right]_{\mathbf{x}^{*}}^{\mathbf{T}}=\left[\begin{array}{c}\frac{\partial\mathbf{g}(\mathbf{x})}{\partial\mathbf{x}}\\\end{array}\right]_{\mathbf{x}^{*}}^{\mathbf{T}}\boldsymbol{\lambda}* $$

を満たすようなベクトルλ $ *\geqq0 $ が存在する。

すなわち

$$ \left[\begin{array}{c}\partial\mathrm{v}(\mathrm{x})\\ \partial\mathrm{x}\end{array}\right]_{\mathrm{x}^{*}}^{\mathrm{T}}+\left[\begin{array}{c}\partial\mathrm{g}(\mathrm{x})\\ \partial\mathrm{x}\end{array}\right]_{\mathrm{x}^{*}}^{\mathrm{T}}\lambda^{*}=0 $$

$$ \left\lfloor\frac{\partial\mathrm{v}(\mathrm{x})}{\partial\mathrm{x}}\right\rfloor_{\mathrm{x}^{*}}^{+\lambda}\stackrel{*\mathrm{T}}{}\left\lfloor\frac{\partial\mathrm{g}(\mathrm{x})}{\partial\mathrm{x}}\right\rfloor_{\mathrm{x}^{*}}=0 $$

$$ \left\lfloor\frac{\partial L(x,\lambda)}{\partial x}\right\rfloor_{x^{*},\lambda^{*}}=0 $$

を満たすベクトルλ $ *\geqq0 $ が存在する。

また $ x^{*} $ が $ g(x^{*}) < 0 $ となる制約集合の内点である場合には、

$$ \left\lfloor\frac{\partial\mathrm{v}\quad(\mathrm{x})}{\partial\mathrm{x}}\right\rfloor_{\mathrm{x}^{*}}=0 $$

でなければならない。そうすると、

$$ \left[\frac{\partial L(\mathbf{x},\lambda)}{\partial\mathbf{x}}\right]_{\mathbf{x}^{*},\lambda^{*}}=0 $$

がλ $ ^{*}=0 $ に対して成立する。これは

$$ \left[\frac{\partial L(\mathbf{x},\lambda)}{\partial\lambda}\right]_{\mathbf{x}^{*},\lambda^{*}}=\mathbf{g}(\mathbf{x}^{*})\leqq0 $$

から自明である。また、

$$ \lambda^{*\mathrm{T}}\left[\frac{\partial\mathrm{L}(\mathrm{x},\lambda)}{\partial\lambda}\right]_{\mathrm{x}^{*},\lambda}^{*}=\lambda^{*\mathrm{T}}\mathrm{g}(\mathrm{x}^{*}) $$

であり、 $ x^{*} $ が境界上の点のときは $ g(x^{*}) = 0 $ 、内点のときは $ \lambda^{*}=0 $ となるので、いずれにせよ、

$$ \left\lfloor\frac{\partial L(x,\lambda)}{\partial x}\right\rfloor_{x^{*},\lambda^{*}}=0 $$

が成り立つ。(証明終)

この定理の述べる必要条件を Kuhn-Tucker 条件という。また、この条件は、 $ x^{*} $ とそのときの $ \lambda $ $ * $ がすべての x と $ \lambda \geq 0 $ に対して、

$$ L(x^{*},\lambda\text{）}\leqq L(x^{*},\lambda\text{）}\leqq L(x^{*},\lambda\text{）} $$

を満たす点となるための必要条件でもある。このような点は L(x,λ ) の鞍点と呼ばれる。

一般に、上述の最小化問題に対して

<制約条件>

$$ \frac{\partial\mathrm{~L}(\mathrm{x},\lambda)}{\partial\mathrm{~x~}}=0,\lambda\geqq0 $$

のもとで

< 目的関数 >

$$ \mathbf{L}(\mathbf{x},\lambda\mathbf{\Lambda})=\mathbf{V}(\mathbf{x})+\lambda^{\mathrm{T}}\mathbf{g}(\mathbf{x}) $$

を最大にするようなんを求める。

という問題を、もとの問題の双対問題という。