制約つき非線形最適化

質問

次のような制約つき非線形最適化問題を数値的に解きたいと思っています。
minimize Σ(y_n-f(n,a))^2
subject to G(f(n,a))=0
具体的な関数形は必要なら補足します。

(1)ラグランジュ未定乗数法により解くことを考えます。
ラグランジアンはL=Σ(y_n-f(n,a))^2-λG(f(n,a))
∂L/∂a=0、∂L/∂λ=0を連立してNewton法で解きます。
しかし、Lは複雑な形をしているので、1階微分程度がせいぜいです。
そこでNewton法にでてくるヤコビアンは数値的に求めます。
この考え方でプログラムすると、どうしても収束しません。
どうしたらよいでしょうか？
また、λの初期値はどのように決めたらよいでしょうか？

(2)excelのソルバーに同じ問題をやらせると、
あっさり解を出します。
ソルバーはどのようなアルゴリズムを用いているのでしょうか？

(3)このような問題に適用できる、その他の手法がありましたら、教えてください。

以上、お答えできる問だけで結構ですのでアドバイスをお願いします。

回答No.1

my3027 · ベストアンサー

わかる範囲で助言ですが、

(1)ご存知の通りニュートン法は初期値によって解が収束しません。プログラムと方法が正しければ、エクセルで求めたλ付近の値を入力して収束するか見てみて下さい。収束しなければ、方法かプログラムに問題があると思います。

(2)エクセルのヘルプで「ソルバー」と入力すると以下が出てきました。
Microsoft Excel のソルバー ツールでは、テキサス州オースティンのテキサス大学の Leon Lasdon 氏とクリーヴランド州立大学の Allan Waren 氏が開発した GRG2 (Generalized Reduced Gradient) 非線形最適化コードが使用されています。

線形問題と整数問題では、Frontline Systems, Inc. の John Watson 氏と Dan Fylstra 氏が実装した、束縛変数を用いたシンプレックス法と分枝限定法が使用されています。ソルバーが使用する内部解決プロセスの詳細については、以下の連絡先にお問い合わせください。

Frontline Systems, Inc.
P.O. Box 4288
Incline Village, NV 89450-4288
(775) 831-0300
Web サイト : http://www.frontsys.com
電子メール アドレス : info@frontsys.com

(3)は質問者さんの方法がオーソドックスと思います。他方法としては
・最急降下法
・遺伝的アルゴリズム
があるようです。

お礼

分かりました。問題に見えにくいところに制約条件があったようです。
お付き合いいただきありがとうございました。