前回はこの本の第４章、被覆制御について学び、ある一定のエリア内に、所望の諸元でエージェントを分散させる方式について取り扱いました。
第５章は分散最適化です。
最適化問題は、与えられた制約条件を満たしつつ評価関数を最小にする問題です。
最適化制御とかも同じ考えなのでしょうおそらく。
最適化制御ってなんなんだ、最適を目指さない制御なんて存在しないだろうと常日頃から思っていたのですが、評価関数を最小にするというのがポイントなんですかね。
機械工学とかでよく出てくるフィードバック制御も、偏差 = 評価関数と捉えれば、やっぱり全ての制御が最適化制御なんじゃないのという気がしますが・・・
最適化問題を分散系（とでもいうのかな）で解くのが分散最適化問題で、要は各エージェントが制約条件や評価関数の一部しか知らないという場合に、情報交換をしながら最適化を目指すと言ったところか。
分散最適化問題
今まではインデックス1〜nのn個のエージェントからなる系を考えていたが、今回から0〜nのn+1個のエージェントで考える。
エージェントのダイナミクスは離散時間の積分系として、
xi[k+1] = xi[k] + ui[k] --- (1)
ただしui[k]は、k, xi[k]と、xiに隣接する各エージェントの状態変数の関数であるとする。
- ui[k] = ci(k, xi[k], xj1[k], xj2[k], ・・・) （ただしxjはxiの隣接エージェントの集合）
最適化問題とは、ある与えられた集合χに含まれる実ベクトルξの中で、評価関数Jの値であるJ(ξ)を最小にするξを探す問題である。
ここで、任意のξについて
- J(x*) ≦ J(ξ)
が成り立つx*を、上記最適化問題の最適解と呼ぶ。 （x*は複数あるかも知れない、その場合その集合をχ*と表す）
ここで、十分に時間が経過した後（k → ∞）、ある最適解x*に対して、ある定められた実行列B1, B2, ・・・Bnを用いて
- xi[k] = Bi x* （i = 1,2,・・・n）
となるよう、分散制御器 ciを求める問題を分散最適化問題という。
事例１：
総量bの資源をインデックスi:1〜10の10人にξiずつ配分する時、その満足度Ji(ξ)の総和を最大化する問題など。
この時は、Ji(ξ)の総和に-1を乗じたものを最小化する問題として取り扱う。
制約条件は、各人への資源配分量は非負であること、その総和はb以下となること。
事例２：
ある領域に７個の温度センサを配置し、領域合計５４点の温度ξ（54×1ベクトル）を計測したいとする。
各センサは計測範囲を持ち、例えば54個のうちセンサiは近傍12点の計測が可能で、計測値yi（12×1ベクトル）を得られるとする。
これら12点の温度の真値は、12×54のある行列Fiを用いてFi・ξと表せる。（全計測データξから12点のデータを取り出す操作に該当？）
一方、これら12点の計測値は、この真値にノイズwiが加わり、yi = Fi・ξ + wiと表せる。
この設定の下、最良のξの推定を行うとすると、その評価関数は
- J(ξ) = ||F・ξ - y||^2
と表せる。
ただし、FはFiを1〜7まで縦に並べた84×54行列、同じくyは84×1ベクトル。
拘束条件は、ここの条件の範囲だと特になし？
各センサの計測可能点数が異なっても、多分同じ。
事例３：
対象物の2次元上の位置ξ（2×1ベクトル）を、i = 1〜6の6台のカメラネットワークから取得する。カメラは、対象物を視野に収めた時のみ、その位置の計測値yi（2×1ベクトル）を得る。
カメラ１とカメラ2のみが対象物を視野に捉えていれば、y1とy2のみが得られる。
ただし、これらには事例2同様誤差を含むため、計測誤差wiを用いて
- yi = ξ ＋ wi
と表せる。
制約条件は、対象物がカメラ1と2の視野範囲内にあること。
この時、評価関数は
- J(ξ) := ||ξ - y1||^2 + ||ξ - y2||^2
と表わせる。これの最小化を目指せばよい。
この事例を考えると、対象物は動く場合もあるから、制約条件自体も時々刻々変わっていくものと考えられる。結構複雑。
最適化の基礎
前項で導入した最適化問題の式：
- min J(ξ) s.t. ξは制約条件χを満たす ---(2)
を解く方法を劣勾配法という。
ここで、Jは凸関数、χ（N次元）は空でない閉集合かつ凸集合と仮定。
凸集合：
0以上1以下の係数aと任意のχの要素ξ1、ξ2について、
- a*ξ1 + (1-a)*ξ2
もまたχの要素である時、このようなχを凸集合という。
凸関数：
関数Jの実行定義域である dom(J) が凸集合であり、かつ0以上1以下の係数aと任意のdom(J)の要素ξ1、ξ2について、
- J(a*ξ1 + (1-a)*ξ2) ≦ aJ(ξ1) + (1-a)J(ξ2)
を満たす時、Jは凸関数であるという。
等号が成り立つのがξ1 = ξ2である時のみである場合は狭義凸関数という。
なお、Jの-1倍が凸関数の時、Jを凹関数という。狭義の定義も同様。
このJについて、dom(J)に属するある ξ~ を用いて劣勾配という概念を導入する。
劣勾配は一意に定まるとは限らないが、殆どの議論は劣勾配の選び方に依らず共通。
また、Jが微分可能であれば、劣勾配は唯一であり、Jの勾配と一致する。
式（2）の問題の最適解xに収束するx[0], x[1], x[2], ・・・ を生成することを考える。この系は
- x[k+1] = Pχ（x[k] - s[k] + dj(x[k]) ）
という漸化式で表せる。ただしs[k]はステップ幅と呼ばれる正数。
関数Pχは引数ξを閉集合かつ凸集合χへと射影する関数であり、同じくχに属するξ'に対して
- min ||ξ - ξ'||
の最適化問題の唯一の解を返す。
χがN次元（既にxと同じ次元ということ？）の時は
- x[k+1] = x[k] - s[k] + dj(x[k])
と表せる。
この後、双対問題と劣勾配法による解法という小項目があるのだが、日本語でメモを書けるような定性的理解ができなかった。
（というか式も理解していない）
今回は式すらも理解していないから偉そうなことは言えないのだけれど、
個人的には、その物理的な意味や効果を日本語で定性的に説明できない概念は「理解している」とは言えないと考えている。
数学や理学の世界では言葉で説明が難しい数学的操作をする必要があるだろうし、工学の分野でも、数式的な説明でないと厳密な議論はできないというのはあるかもしれなけど・・・
双対分解による分散最適化
インデックス0 ~ nの全エージェントのダイナミクスが式(1)で与えられるMASを考える。
ただし次元は1次元とする。
ここで、エージェント0は1〜n全てのエージェントに隣接し、エージェント1〜nは0にしか隣接しない、0が根で深さ1の有向木からなるグラフで表される構造を考える。
この時、各エージェントへの制御入力 ui は
- u0[k] = c0(k, x0[k], x1[k], x2[k], ・・・xn[k] )
- ui[k] = ci(k, x0[k], xi[k] )
と表現することができる。
このMASが解くべき最適化問題は、式(2)のうち特別なケースとする。
具体的には、ベクトルξの次元はエージェント数n+1より1だけ少ないnとし、その第i要素をξiと表す。
次に評価関数Jは、Ji(ξi)のi = 1~n の総和とする。
制約条件として、以下を設定する。
- ξi は 実数集合Rの部分集合χiに含まれる
- ξiの総和はある実数b以下である
部分集合χi を全て正の実数として、評価関数の正負を反転すれば、これは上記分散最適化問題の事例1と同じとして扱える。
このような問題を分解可能問題という。
この時、全てのi : 1 ~ nに対して、Jiは狭義凸関数、χiは閉集合かつ凸集合と仮定する。
この時、Ji(ξi)の総和である評価関数Jも狭義凸関数となり、χiに属するξiの集合であるχも閉集合かつ凸集合となる。
よってこの問題の最適解x*は唯一となる。以降、x*の要素をxi* (i = 1~n)と表す。
行列Biを、第i要素が1, その他の要素が0の n×1ベクトルとして表すとする。
この時、十分時間が経った（k → ∞）時
- xi[k] = xi*
を目的とする分散最適化問題を考える。
ただし、エージェントiに対する評価関数Ji、その制約条件であるχiの情報はエージェントiにのみ与えられ、それ以外の全エージェントにはその情報を利用できないとする。
先の事例1で挙げた資源配分問題で言うと、各人は他人の満足度がどのような関数で表されるのか、その情報を手に入れられないということを意味する。
このように各エージェントが自分に関する情報しか得られない状態でJi（ξi）を最大とするξiを求めても、その解がxi*になるとは限らない。
ξiの総和がある値b以下であるという制約条件が満たされるとは限らない（資源配分問題で、資源が多いほうが満足度が高い場合、ξiはそれぞれ無限大になる）
この問題では、エージェント0にその制約を満足させる役割を追わせる。（だからインデックスが0始まりになっていた）
ここから書いてあることが理解できなくなってしまったので、一旦読み飛ばします・・・情けない
合意制御による分散最適化
エージェント0は用いない条件に戻る。
各エージェントiのダイナミクスは今までと同じ表記で、状態変数はN次元とする。
MASのネットワーク構造は、連結な無向グラフGによって表現できるものとする。
このMASが解くべき最適化問題であるが、その評価関数Jは、Ji（ξ）の総和（1〜n）で表されるものとする。
また制約条件χは、χiの積集合であるものとする。
ξに添字がついていないことからもわかるとおり、Jiはξの全要素を評価する関数になっていることに注意。同様に、χもξの全要素を制約する。
例えば、分散最適化問題の事例2で挙げた最適化問題を考えると、
- Ji(ξ) = ||Fi・ξ - yi||^2 (i = 1~7)
とおくと
- J(ξ) = ||F・ξ - y||^2 = 総和（i=1~7） : ||Fi・ξ - yi||^2 = 総和（i=1~7） : Ji（ξ）
となる。
事例3についても同様。
対象物を視野に含まない全てのカメラi = 3~6について、Ji（ξ） = 0、χi : 2次元実数ベクトルとすればよい。
ここまでで力尽きました。本の中で何が起こっているのか、ついていけなくなりました。。。
