概要

非線形最適制御の勉強を始めた。 実は去年授業で単位は取得したのだけれど、ほとんど覚えていないも同然なので、はじめからやり直すことにする。 教科書はE. Brysdn, Jr. Yu-Chi Ho, “Applied Optimal Control”, CRC Press, 1975を用いた。 式番号は教科書に倣った。 今回はとりあえず、ダイナミクスなしの最適化問題について、ざっと復習する。

制約なし最小化問題

問題

決定変数$u=[u_1 \ \cdots \ u_m]^T\in R^m$を決めることで、評価関数 $$L(u):R^m\rightarrow R$$ を最小化したい。

必要条件

$L$が$C^2$級の関数であるとき、$u$が最小値であるのための必要条件は $$\frac{\partial L}{\partial u} = 0 \tag{1.1.3}$$ 及び $$\frac{\partial^2 L}{\partial u^2} \succeq 0$$ が成り立つことである。 $(1.1.3)$を満たす$u$を停留点という。

十分条件

$u$が局所最小であるための十分条件は$(1.1.3)$及び $$\frac{\partial^2 L}{\partial u^2} \succ 0$$ が成り立つことである。

数値計算法

勾配法 (gradient decent) 、ニュートン法 (newton method) を始め、様々な数値計算法が用いられる。

等式制約付き最小化問題

問題

決定変数$u\in R^m$を決めることで等式制約 $$ f(x,u)=0 \tag{1.2.2} $$ のもと、評価関数 $$L(x,u): R^n\times R^m\rightarrow R$$ を最小化したい。ここで$x=[x_1 \ \cdots \ x_n]^T\in R^n, \ f=[f_1 \ \cdots \ f_n]^T:R^n\times R^m\rightarrow R^n$とおいた。

必要条件

ラグランジュ乗数$\lambda=[\lambda_1 \ \cdots \ \lambda_n]^T\in R^n$を導入する。 ハミルトニアン $$H(x,u,\lambda):=L(x,u)+\lambda^Tf(x,u)$$ に対して、 $$\frac{\partial H}{\partial x} = \frac{\partial H}{\partial u} = \frac{\partial H}{\partial \lambda} = 0 \tag{1.2.8 - 1.2.10}$$ が成り立つことが、$u$が停留点であることの必要条件であることが知られている。

さらに計算を進めていくと

$$ \left( \frac{\partial^2 L}{\partial u^2} \right)_{f=0} = H_{uu} - H_{ux}f_x^{-1}f_u - f_u^T(f_x^T)^{-1}H_{xu} + f_u^T(f_x^T)^{-1}H_{xx}f_x^{-1}f_u \succeq 0 \tag{1.3.7} $$

もまた必要条件であることが確かめられる。 ここで例えば$f_x=\frac{\partial f}{\partial x}, \ H_{xx}=\frac{\partial^2 H}{\partial x^2}$などとおいた。

まとめると、$u$が最小となるための必要条件は$(1.2.8 - 1.2.10)$及び$(1.3.7)$が成り立つことである。

$(1.2.8-1.2.10)$の導出

任意に与えられた$u$を$du$だけ変化させたときの$H$の変化量$dH$を計算すると $$dH = \frac{\partial H}{\partial x}dx + \frac{\partial H}{\partial u}du$$ となる。 ここで、$u$が最小値であるためには、$(1.2.2)$を通じて得られる$x$の微小変化$dx$に対して、$dH$が不変であることが必要なので $$\lambda^T=-\frac{\partial L}{\partial x}\left( \frac{\partial f}{\partial x} \right)^{-1}$$ と選ぶことにより、 $$\frac{\partial H}{\partial x} = 0 \tag{1.2.8}$$ 及び $$dH = \frac{\partial H}{\partial u}du$$ を得る。 さらに、与えられた$u$が最小値であるためには、任意の変化$du$に対して$dH=0$が成り立つ必要があるので $$\frac{\partial H}{\partial u} = 0 \tag{1.2.10}$$ が必要条件となる。 こうして$(1.2.8-1.2.9)$が得られた ($(1.2.10)$は$(1.2.2)$そのものである) 。

十分条件

$u$が局所最小であるための十分条件は$(1.2.8 - 1.2.10)$及び $$ \left( \frac{\partial^2 L}{\partial u^2} \right)_{f=0} = H_{uu} - H_{ux}f_x^{-1}f_u - f_u^T(f_x^T)^{-1}H_{xu} + f_u^T(f_x^T)^{-1}H_{xx}f_x^{-1}f_u \succ 0 $$ が成り立つことである。

数値計算法

等式制約付き最小化問題を解析的に解くのは、一般には難しいので、数値計算が用いられる。 最も単純な方法として、つぎの勾配法 (gradient decent) がある。

  1. $u$の初期値を与える。
  2. $f(x,u)=0$から$x$を求める。
  3. $\lambda^T=-\frac{\partial L}{\partial x}\left( \frac{\partial f}{\partial x} \right)^{-1}$より$\lambda$を求める。
  4. $\frac{\partial H}{\partial u} = \frac{\partial L}{\partial u} + \lambda^T\frac{\partial f}{\partial u}$より求める。
  5. 整数$K$に対して$\Delta u = -K \frac{\partial H}{\partial u}$を定め、$u \leftarrow u+\Delta u$と更新する。
  6. 1-5までを$\Delta J = -K\frac{\partial H}{\partial u}\frac{\partial H}{\partial u}^T$が十分小さくなるまで繰り返す。

勾配法は収束が遅いため、しばしばつぎの二階の勾配法 (second order gradient decent) が用いられる。

  1. $x,u,\lambda$の初期値として$x^0,u^0,\lambda^0$を与える。
  2. つぎの値を求める。 $$H_x^0 := H_x(x^0,u^0,\lambda^0),\ H_u^0 := H_u(x^0,u^0,\lambda^0),\ f^0:=f(x^0,u^0)$$ $$H_{xx}^0 := H_{xx}(x^0,u^0,\lambda^0),\ H_{xu}^0 := H_{xu}(x^0,u^0,\lambda^0),\ H_{ux}^0 := H_{ux}(x^0,u^0,\lambda^0),\ H_{uu}^0 := H_{uu}(x^0,u^0,\lambda^0)$$ $$f_x^0:=f_x(x^0,u^0),\ f_u^0:=f_u(x^0,u^0)$$
  3. つぎの連立方程式を$dx,du,d\lambda$について解く。 $$H_x^0 + H_{xx}^0dx + H_{xu}^0du + (f_x^0)^Td\lambda = 0$$ $$H_u^0 + H_{ux}^0dx + H_{uu}^0du + (f_u^0)^Td\lambda = 0$$ $$f^0 + f_x^0dx + f_u^0du = 0$$
  4. $x^1=x^0+dx,\ u^1=u^0+du,\ \lambda^1=\lambda^0+d\lambda$と更新していく。

不等式制約付き最小化問題

おまけとして、制約が不等式の場合の最小化問題と、その解についての必要条件を紹介。

問題

決定変数$y:=[x^T \ u^T]^T$を決めることで制約 $$f(y) = 0, \ h(y) \le 0$$ のもと、評価関数 $$L(y)$$ を最小化したい。

必要条件

ハミルトニアン $$H(y,\lambda,\mu) := L(y) + \lambda f(y) + \mu h(y)$$ に対して、 $$\frac{\partial H}{\partial y} = 0, \ \frac{\partial H}{\partial \lambda} = 0, \ \frac{\partial H}{\partial \mu} \le 0, $$ $$\mu \left\{ \begin{array}{cc} \ge 0 & h(y) = 0 \newline = 0 & h(y) < 0 \end{array} \right. $$ が成り立つことが、$y$が最小値であるための必要条件であることが知られている。 この条件はKKT条件という名前で知られている。

数値計算法

射影勾配法 (gradient projection method) 、ペナルティ関数法 (penalty function method) 、乗数法 (multiplier method) 、逐次二次計画法 (sequential quadratic programming method) 、内点法 (interior point method) などが知られている。