はじめに #
非線形システムを対象としたモデル予測制御の最適化問題を解くPANOCというアルゴリスムについてまとめた。 PANOCはProximal Averaged Newton-type method for Optimal Controlの略である。
非線形システムのモデル予測制御 (NMPC, Nonlinear Model Prodictive Control) は非線形計画問題 (NLP, Nonlinear Programming) となる。このような最適化問題は、システムの非線形性により解きづらい (ill-condition) 。また、予測ホライゾンが長いと変数の数も増えてしまう。
PANOCは近接勾配法 (Proximal Gradient Method) と準ニュートン法を組み合わせたアルゴリズムである。 解の初期値から最適解の近傍までは、近接勾配法によって大域的な収束性を保証する。そして、最適解に近づくと、準ニュートン法により高速に収束させる。
PANOCはOpEnというRust製ライブラリに実装されている。インストール方法は以下の記事を参照。
Rust製最適化ライブラリOpEnのインストール – Helve Tech Blog
他手法との比較 #
非線形計画問題を解く手法として、SQP（逐次二次計画法）、近接勾配法 , 準ニュートン法などがある。 SPQは、非線形最適化問題のKKT (Karush-Kuhn-Tucker) 条件を求めるものである。解候補の更新ごとに二次計画問題を解いて探索方向を決定している。 近接勾配法は微分不可能な点を含む凸関数最適化を解く手法である。詳細は以下の記事を参照。
近接勾配法（Proximal Gradient Method） - Qiita
準ニュートン法は、ニュートン法におけるヘッセ行列を近似して解を更新する手法である。
PANOCと比較した各手法の長所・短所は以下の通り。
SQP #
- 長所：主双対内点法と並んで、非線形最適化問題に対する主要な解法である。
- 短所：解の更新 (ouetr loop) ごとに二次計画問題 (inner loop) を解く必要があり、計算負荷が高い。
近接勾配法 #
- 長所：アルゴリズムが単純。
- 短所：1次微分の情報しか用いないため、収束が遅い（1次収束）。
準ニュートン法 #
- 長所：最適解近傍では収束が速い（超1次収束ないし2次収束）。
- 短所：初期点が最適解から離れている場合、収束しづらい（大域的収束性が悪い）。
これらの手法と比較して、PANOCは以下の長所を持つ。
- アルゴリズムが単純
- 解の近傍では収束が早い（超1次収束）
- メモリ消費が少ない
- inner loopやヘッセ行列の計算が不要
PANOCの概要 #
PANOCのアルゴリズムの概要を示す。 まず、解くべきモデル予測制御問題は以下の通り。
$$ \min \ \Sigma_{n=0}^{N-1} l_n(x_n, u_n) + l_N (x_N) \\\ \mathrm{s.t.} \ x_0 = \bar{x}, u_n \in U_n, x_{n+1} = f_n (x_n, u_n) \ (n=0, ..., N-1) $$ここで、\(f_n\)はシステムのダイナミクス、\(x_n\)はシステムの状態、\(u_n\)はシステムへの入力である。また、\(U_n\)は入力制約、\(l_n\)は最適制御のコスト関数、\(N\)は制御ホライゾンである。
式変形は省くが、最適化問題を以下の通り単純に表記する。
$$ \min_{u \in U} \ l(u) $$なお、\(u\)に対する\(l(u)\)の勾配\(\nabla l(u)\)は自動微分により計算される。
PANOCのおおまかなアルゴリズムは以下の通り。
- \(k=0\), 解の初期値\(u^0\)を準備
- 勾配\(\nabla l(u^k)\)を計算
- \(\bar{u}^k = \mathrm{prox}_{\gamma g} (u^k - \gamma \nabla l (u^k))\), \(r^k = (u^k - \bar{u}^k)/\gamma\)を計算
- 準ニュートン法による解の更新方向\(d^k = -H_k r^k\)を計算
- \(u^{k+1} = u^{k} - (1-\tau_k)\gamma r^k +\tau_k d^k\)で解を更新（\(\tau_k\)は直線探索で求める）
- 終了条件を満たせば終了。満たさない場合は7.に進む
- \(k \leftarrow k + 1\)と更新して2.に戻る
上記の3.では近接勾配法による解の候補\(\bar{u}^k\)を求めている。 また、4.の\(H_k\)はヘッセ行列の逆行列に相当し、記憶制限BFGS法などでその近似行列を求める。
5.では近接勾配法の解候補と準ニュートン法の解候補の重みづけ平均を求めている。理想的には、解候補が最適解から遠いとき前者の解候補を重視し(\(\tau = 0\)), 最適解に近づくと後者の解候補を重視する(\(\tau = 1\))。 また、直線探索ではforward-backward envelope (FBE) という緩和関数を用いる。FBEは微分不可能な関数を微分可能に緩和する特性がある。
