前回までの授業で、最適化問題のいろいろな定式化について述べた。
たとえば線形パンツ計画（Liner pantsu programming:LP）、非線形パンツ計画（nonliner pantsu programming）
整（った）数（のぱんつを集める）計画（intenger pantsu is limited）などである。
特にパンツが線形であるか、線形でないかは非常に重要な問題で、もし水玉などを履こうものならその曲線をフィッティングするために多くの労力を割く必要がある。
また、残ったぱんつの分配法である整数計画ではとりうる整数値の組み合わせの問題であるから、その数は膨大となる上にその価値についても多様な評価があるため、一般に解を求めるのは困難とされている。
さて、今回の授業ではすでに定式化された最適化問題の解法について述べる。
この授業は初学者を対象とするため、最も基本的な手法のうちのいくつかを簡単に述べるとしよう。
（１）匂配法(the distribution of smell method)
匂配法の特徴は初期値の選び方によらず、∇f(x) = 0となる解に収束することである。
つまり、アリスがどのようなパンツをはいていたとしても、その匂いを基準として価値を決めるため必ず解に行き着くことができるのである。
この方法の欠点は、悪条件下（ぬぎたてでない、洗濯後、おんなのこの言えない事情）では収束が非常に遅くなるという点である。
注 悪条件とは、収束における悪条件であって、ぱんつそのものの匂いではないことに注意せよ。
さて、では具体的な解の求め方について見ていこう。
xをn次元実数ベクトルとし、f(x)を適当に滑らかな関数（ここでは離散的ではないという程度でよい）とするとき、
f(x) → Min (1)
という問題を考える。この問題に対する解x*を求めるのに
x(k+1)=xk+ αkdk (２）
によって近似解xk+1を改善することを試みる。
探索方向dkをどのように選べば最も効率がよいであろうか。
このことは、アリスがゆっくりと目を閉じた状況によく似ている。
もじもじしながらすこしづつ体を寄せていくようではお互いにはずかしくなってしまって思いを遂げることはできまい。
それはそれで趣もあるものだが、解を収束されるという観点では許容するのは難しいだろう。
もっとも簡単なのはアリスの体を強く抱きしめてむぎゅっとしてしまうことだ。
最初に体をあわせてしまえば、あとはアリスの反応が大きくなる方向にからだをまさぐることで思いを遂げることができるであろう。
このように、できるだけ傾斜の急な方向、つまり過激な方向に進めば解を得ることができる。
これを式にしてあらわすと
-∇f(xk) := (∂f(xk))/∂x1, ……,(∂f(xk))/∂xn) (3)
で与えられる。
この∇の記号は「な、ブラ」と呼ばれるアリスのブラジャーを示す記号である。
過激な方向に進む記号にブラジャーの形を与えた先達には感嘆の意を禁じえない。
(3)はxkを中心とする半径rの円状で関数fが最も小さくなる所を見出すことと同じである。
このような偏微分の使用の仕方はアリス的に最もよく使用される方法なので覚えておいてほしい。
たとえば先ほどあげた水玉パンツカーブのフィッティングにはこの∇を使用することが最も一般的である。
つまり、水玉パンツカーブにフィットするのは水玉ブラということである。
さて、関数fをxkにおいて一時近似すると
目的： f(xk) + ∇f(xk)(x-xk) → Min
と定式化できる。よく知られたシュワルツ不等式により∇f(xk)(x-xk) を最小にするのは
x-xk= -α∇f(xk)
のときである。
シュワルツ不等式は別名コーシー・ノンダラ・パンツガ・シュワルツ不等式と呼ばれるもので、
アリスの部屋における二人の内縁の関係を、コーヒーを飲んだ際の二人のトイレの長さを基準に評価したものである。
今回の授業のレポートは∇f(xk)(x-xk) を最小にするのはx-xk= -α∇f(xk)
であることの証明とする。
さて、探索方向は定まったものの、いまだに式（２）のαの値が定まっていない。
このαの取り方によって解の収束速度が変わるため、その決定は重要である。これを一次探索という。
その方法は、アリスの体の適当な三点を取ってその匂いの強さからαを定める方法や黄金三対比（スリーサイズ）を用いる方法などさまざまな方法が考えられている
（２）ニュートン法
上記の匂配法ではパンツの匂いという一次情報を用いていたのに対し、ニュートン法では２次近似の情報、つまり匂いに起因する周囲の反応まで考慮する。
この方法の欠点は初期値を適切に選択しなければ収束さえ保障できないことである。
諸君も経験があるとおり、ぱんつを前にすると時間がいくらあってもその価値を定めることができないが、ぱんつを前に複数人で議論することでその価値を定める速度が早くなる。これはまさにニュートン法である。しかし、ぱんつの趣味が異なる相手（典型例 母親と恋人、姉と妹、紅魔館の彼女と魔法の森の彼女など）ではその結論がぐだぐだになるのもニュートン法の欠点を如実に表している。
目的関数を二次近似すると、
f(x) = f(xk) + ∇f(xk)(x-xk)+ (1/2)(x-xk)T∇2ｆ（xk）（x-xk）
ここで
∇2 := H
つまり
∇∇ := H
と定義される。アリスのブラジャーを重ねることでHになるとは、なんと美しい式であろうか。
このHはヘシアンと呼ばれる。この式は二次形式であるから、もしもヘシアンが正定であれば、簡単にその最小値は求まり、それをxk+1とすると
xk+1= xk- (∇2f(xk))-1∇f(xk)
を得る。この式によって近似解xkを更新していくのがニュートン法である。
今日の授業には身近なぱんつを用いてできるだけ例を多用した。
しかし最適化問題の解法はぱんつに限るものではなく、応用範囲が広い。
諸君らにおいてはぜひその可能性を探ってほしいものである。
参考文献
システムアリス学
Patchouli Knowledge 著
たとえば線形パンツ計画（Liner pantsu programming:LP）、非線形パンツ計画（nonliner pantsu programming）
整（った）数（のぱんつを集める）計画（intenger pantsu is limited）などである。
特にパンツが線形であるか、線形でないかは非常に重要な問題で、もし水玉などを履こうものならその曲線をフィッティングするために多くの労力を割く必要がある。
また、残ったぱんつの分配法である整数計画ではとりうる整数値の組み合わせの問題であるから、その数は膨大となる上にその価値についても多様な評価があるため、一般に解を求めるのは困難とされている。
さて、今回の授業ではすでに定式化された最適化問題の解法について述べる。
この授業は初学者を対象とするため、最も基本的な手法のうちのいくつかを簡単に述べるとしよう。
（１）匂配法(the distribution of smell method)
匂配法の特徴は初期値の選び方によらず、∇f(x) = 0となる解に収束することである。
つまり、アリスがどのようなパンツをはいていたとしても、その匂いを基準として価値を決めるため必ず解に行き着くことができるのである。
この方法の欠点は、悪条件下（ぬぎたてでない、洗濯後、おんなのこの言えない事情）では収束が非常に遅くなるという点である。
注 悪条件とは、収束における悪条件であって、ぱんつそのものの匂いではないことに注意せよ。
さて、では具体的な解の求め方について見ていこう。
xをn次元実数ベクトルとし、f(x)を適当に滑らかな関数（ここでは離散的ではないという程度でよい）とするとき、
f(x) → Min (1)
という問題を考える。この問題に対する解x*を求めるのに
x(k+1)=xk+ αkdk (２）
によって近似解xk+1を改善することを試みる。
探索方向dkをどのように選べば最も効率がよいであろうか。
このことは、アリスがゆっくりと目を閉じた状況によく似ている。
もじもじしながらすこしづつ体を寄せていくようではお互いにはずかしくなってしまって思いを遂げることはできまい。
それはそれで趣もあるものだが、解を収束されるという観点では許容するのは難しいだろう。
もっとも簡単なのはアリスの体を強く抱きしめてむぎゅっとしてしまうことだ。
最初に体をあわせてしまえば、あとはアリスの反応が大きくなる方向にからだをまさぐることで思いを遂げることができるであろう。
このように、できるだけ傾斜の急な方向、つまり過激な方向に進めば解を得ることができる。
これを式にしてあらわすと
-∇f(xk) := (∂f(xk))/∂x1, ……,(∂f(xk))/∂xn) (3)
で与えられる。
この∇の記号は「な、ブラ」と呼ばれるアリスのブラジャーを示す記号である。
過激な方向に進む記号にブラジャーの形を与えた先達には感嘆の意を禁じえない。
(3)はxkを中心とする半径rの円状で関数fが最も小さくなる所を見出すことと同じである。
このような偏微分の使用の仕方はアリス的に最もよく使用される方法なので覚えておいてほしい。
たとえば先ほどあげた水玉パンツカーブのフィッティングにはこの∇を使用することが最も一般的である。
つまり、水玉パンツカーブにフィットするのは水玉ブラということである。
さて、関数fをxkにおいて一時近似すると
目的： f(xk) + ∇f(xk)(x-xk) → Min
と定式化できる。よく知られたシュワルツ不等式により∇f(xk)(x-xk) を最小にするのは
x-xk= -α∇f(xk)
のときである。
シュワルツ不等式は別名コーシー・ノンダラ・パンツガ・シュワルツ不等式と呼ばれるもので、
アリスの部屋における二人の内縁の関係を、コーヒーを飲んだ際の二人のトイレの長さを基準に評価したものである。
今回の授業のレポートは∇f(xk)(x-xk) を最小にするのはx-xk= -α∇f(xk)
であることの証明とする。
さて、探索方向は定まったものの、いまだに式（２）のαの値が定まっていない。
このαの取り方によって解の収束速度が変わるため、その決定は重要である。これを一次探索という。
その方法は、アリスの体の適当な三点を取ってその匂いの強さからαを定める方法や黄金三対比（スリーサイズ）を用いる方法などさまざまな方法が考えられている
（２）ニュートン法
上記の匂配法ではパンツの匂いという一次情報を用いていたのに対し、ニュートン法では２次近似の情報、つまり匂いに起因する周囲の反応まで考慮する。
この方法の欠点は初期値を適切に選択しなければ収束さえ保障できないことである。
諸君も経験があるとおり、ぱんつを前にすると時間がいくらあってもその価値を定めることができないが、ぱんつを前に複数人で議論することでその価値を定める速度が早くなる。これはまさにニュートン法である。しかし、ぱんつの趣味が異なる相手（典型例 母親と恋人、姉と妹、紅魔館の彼女と魔法の森の彼女など）ではその結論がぐだぐだになるのもニュートン法の欠点を如実に表している。
目的関数を二次近似すると、
f(x) = f(xk) + ∇f(xk)(x-xk)+ (1/2)(x-xk)T∇2ｆ（xk）（x-xk）
ここで
∇2 := H
つまり
∇∇ := H
と定義される。アリスのブラジャーを重ねることでHになるとは、なんと美しい式であろうか。
このHはヘシアンと呼ばれる。この式は二次形式であるから、もしもヘシアンが正定であれば、簡単にその最小値は求まり、それをxk+1とすると
xk+1= xk- (∇2f(xk))-1∇f(xk)
を得る。この式によって近似解xkを更新していくのがニュートン法である。
今日の授業には身近なぱんつを用いてできるだけ例を多用した。
しかし最適化問題の解法はぱんつに限るものではなく、応用範囲が広い。
諸君らにおいてはぜひその可能性を探ってほしいものである。
参考文献
システムアリス学
Patchouli Knowledge 著
ってか著者がパチュリーかいｗ
ところで、ノンダラさんとパンツガさんとは一体どなたなのだろう……？
次はKKT条件や共役勾配法の解説求むｗ
私に数学の本を教えてくれないかい？
そして文系の俺涙目
各自脱がし匂いを嗅ぐことで経験式をつくってみるのも考えてはいかがでしょうか
高卒工学系の限界を感じたわ...orz
でも何となく面白いからＯＫ
今回は最適化問題の解放の導入なので制約条件についてはそれほど詳しく解説していません。
本来目的関数を
f(xk) + ∇f(xk)(x-xk) → Min
で近似する際には
制約 ||x-x^k|| = r
を満たすようなαを満たすように定めなければならないのですが、今回は方向のみを問題として、この制約条件を省略しました。
局所最適解が存在するかどうかは、目的関数が凸であるかどうかが大きな問題になります。
>>8おっしゃるようなKKT（きっときっと凸だって）条件を勉強することでそのあたりのことはわかると思います。
また、>>5のおっしゃる局所最適解に凸が大きな役割を果たすというのは大変興味深いと思います。
凸が局部……。やはり先人はすばらしい表現を残しているものです。
ノンダラさんとパンツガさんではなく、実はノンダラ＝パンツガというお名前です。
ブニャコフスキーというペンネームのほうがよく知られているかもしれません。魂の名前です。
>>9
残念ながらProf.Patchouliの書かれた本はぱんつについて偏執的に執着しているため、教科書にするには適しません。
今回は導入のため皆さんになじみの深い下着を例に出すために参考にしましたが、最も最初に勉強するべき本でしたら
「はじめてのすうがく～これでわたしもさいきょーね～」（大ちゃんが手書きしました。入手困難）がふさわしいでしょう。
難しい概念をやさしいことばで書かれてある名著です。
よいところに気がつきました。
∇がブラジャーを示すことからついつい胸の勾配に気が向いてしまうのですが、魔界語の表現通り、
「smell」です。
>>21
申し訳ありません。しかし自重しません。
>>29
確かに脱がしたパンツからアリスの匂いを性格に計量するのは現実的ではありません。
しかし、このようにシミュレーションの基礎となる匂配法を勉強することで、最適解が「一応」導き出せます。
脱がしあったパンツを用いて最適解におちつくまで分配を繰り返すのもよいのですが、
おそらくみな夢中になることで収束に大変な時間がかかることでしょう。
スプラインとか弄りやすそう（え？
学生時代に出た線形計画法のコーディングが鬼だったのを思い出しました
次はバナッハ空間でのε-アリス-δなんてどうでしょうか。
>>39
三次のスプライン補間には足を向けて寝られません。
いつもお世話になっています。
線形計画法は便利（というかほかの方法が使いにくすぎる）なのですが、自力で組もうとすると……。
>>41
残念ながら、バナッハ空間についての私の知識が足りません。
しかしε-アリス-δについてはすでにアリスがゲームで論法を説明するというページがありました。グーグルさんに聞いてみてください。
なにがなんだか分からないけどアリスは素晴らしいということはわかった