非線形最小二乗法とシンプレックス法

非線形最小二乗法をシンプレックス法を使って解く方法がわかりません。Gauss-Newton法で解いてもいいのですが、この方法は適当な初期値の範囲が狭いという欠点があるようです。
シンプレックス法ならばいいらしいのですが、いろいろ調べてもシンプレックス法は線形問題で扱う場合がほとんどのようで、非線形問題にはでてきません。
シンプレックス法で非線形問題を扱うには、どうすればよいでしょうか？　そもそも非線形問題でシンプレックス法は扱えるのでしょうか？

No.8 ベストアンサー 回答者： grothendieck 回答日時： 2005/06/02 20:06

下記URLの「Rによる統計解析」の「シンプレックス法によるパラメータ推定」にシンプレックス法のソースコードと解説もあります。

例えば(x,y)=(1,3),(2,8),(3,15),(4,35),(5,57),(6,80),(7,92),(8,95),(9,99),(10,100)というデータに
　y = a/(1+b*exp(-c*x))
という関数をあてはめるには次の様にするとできます。
１. Rのホームページ　http://www.R-project.org/
　に入り、Downloadのページ'CRAN'から適当なバイナリをダウンロードする。
2. Rを起動してFileメニューのNew Scriptを選択
3. 「シンプレックス法によるパラメータ推定」からsimplex関数をScriptのウインドウにコピーアンドペーストする。
4. FileメニューのSave asを選択してScriptを保存
5. FileメニューのSource R Codeを選択して保存したScriptを実行
6. Rのコンソール上で次の様に入力してデータを定義
　x <- c(1,2,3,4,5,6,7,8,9,10)
　y <- c(3,8,15,35,57,80,92,95,99,100)
7. あてはめる関数を定義する
　
　model1 <- function(x, p)
　{
　return(p[1]/(1+p[2]*exp(-p[3]*x)))
　}
8. (a,b,c)=(30,20,10)を初期値として実行するには次の様に入力
　simplex(model1, c(30, 20, 10), x, y, plot.flag=TRUE)

参考URL：http://aoki2.si.gunma-u.ac.jp/R/

この回答へのお礼

C++プログラムではありませんが、参考URLにあるソースコードは大いに参考になりそうです。
ありがとうございました。

お礼日時：2005/06/06 13:51

No.9 回答者： noname#21649 回答日時： 2005/06/04 02:40

＞'CRAN'から適当なバイナリをダウンロードする。

今は楽になったのですね。昔は自分でテーブルを紙に書いて(表計算ソフトに1つづつ書きこんで)いたのですが。

ソフトを使う場合には.検算方法(双対定理, 音で覚えているために漢字疑問)だけは理解してから使ってください。なにかしらかの間違いがある場合がありますから。

No.7 回答者： noname#21649 回答日時： 2005/06/02 02:41

5番です。

＞シンプレックス法で数値微分が必要なのか私は疑問に思
「アメーバーほう」は私が知らないので最近の研究成果でしょう。話しの雰囲気ですと計算の簡略化が行われていますから。

数値微分が必要な理由は.ピポットの選択のためです。もっとも変化量が大きい項を選択することで収束を早めます。このために必要です。

No.6 回答者： grothendieck 回答日時： 2005/06/01 23:38

Nelder-Meadのシンプレックス法は変数の数がN個であるとき、N次元空間でのシンプレックスを考えます。

次に各頂点での関数値を求め、以下のような作業を繰り返し、シンプレックスの体積を小さくしていきます。この体積が十分小さくなったら解が求まったことになります。

*関数値最大点を残りの点の重心の反対側に対称移動：（「反射」と言う）
*上記で対称移動した点をさらにその方向に伸ばす：（「膨張」と言う）
*１次元の収縮
*（その時点の）最小点への全次元の収縮

上記のシンプレックスの動きが、伸びたり縮んだりして動くアメーバ（Amoeba）みたいなので、次の本ではアメーバ法と呼ばれています。
William H.Press〔ほか〕著 丹慶勝市〔ほか〕訳
　ニューメリカルレシピ・イン・シー : C言語による数値計算のレシピ 日本語版
東京 技術評論社 1993.
また下記URLの「その他」の項目をダウンロードするとアメーバ法のCソースプログラムがあります。
シンプレックス法で数値微分が必要なのか私は疑問に思います。また私は最小二乗法とシンプレックス法は二者択一されるようなものではなく、
　最小二乗法
→残差を表わす関数を最小にするパラメータを求める
→関数を最小にするパラメータを求める方法としてGauss-Newton法やシンプレックス法がある。
というように理解しております。

参考URL：http://www5.airnet.ne.jp/tomy/cpro/dl/download.htm

この回答へのお礼

参考URLのページを見ました。プログラムが実際書いてあるのは助かります。ご紹介ありがとうございました。

お礼日時：2005/06/05 11:41

No.5 回答者： noname#21649 回答日時： 2005/05/31 02:47

＞ところでカイノス、鞍部とは何でしょうか？

解の巣問題の例としては.
砂場に幼稚園生１０人か２０人集めて穴を掘ってもらいます。もっとも深い穴を掘った園児に賞をあげるとします。
この水平座標の関数としての深さの方程式を最小二乗法で求める場合に.「もっとも深い」かもしれない隣の穴の解を求めてしまい(=穴の深さを最適解として結論付けてしまい)本当に深い隣の穴の深さを測らないことが発声する
というのが.カイノス問題です。


鞍部問題の例としては.
四角い折り紙を適当に2つに折ります。中央付近が持ちあがって.左右が下になるように中央付近の折り目に糸を通して吊ります。
折り紙の紙の中にのみ解が存在し.もっとも低い場所が最適解であるという関数を最小二乗法で求める場合に.中央付近の山の部分よりも低い場所のみ値を求めて.反対側を計算しないという収束を示す場合です。

カイノスは複数の鞍部が存在する場合の鞍部問題と解釈できるでしょう。

それと.「折り紙」とか「幼稚園生が掘った穴」のような不連続店が存在する例をあげたかというと.「共役勾配法」のような方法は方程式に条件がつくのです。この条件は「連続であること」です。不連続な点が存在すると.最適解が求められないのです。
シンプレックス法は不連続点が存在しても(かなり計算が面倒になりますが)それなりの貝が求められます。
だから「悪条件」の場合の初期解として求めて.初期貝の付近の付近の連続性を調べて.最小二乗法の計算をするわけです。
それから数学的に求められている「最小二乗法」ではなくて「絶対値法」も数学的に問題がありますが.使うには便利です。最小二乗法で発散してしまう場合には試す価値があります。これは.通常計算速度の問題から.単精度実数を使っているはずです(倍精度は４倍以上の時間が必要)。まあ.1の近辺に解がある場合に限って求めていれば変な問題が発生しないのですが.１０次元方程式あたりで.解が100とか900とか付近にあるとか0.001とか0.009付近にある場合に.残差二乗和等が計算機eを超えてしまって微分しても同じ値しか帰ってこないのです。
だから.取り扱う数が1の近くになる絶対値法を試す必要が出てくるのです。

この回答へのお礼

わかりやすい例で解説していただきありがとうございます。これからの参考にしたいと思います。

お礼日時：2005/06/01 22:43

No.4 回答者： grothendieck 回答日時： 2005/05/30 19:42

非線形のシンプレックス法に関して

F.H. Walters, L.R. Parker, S.L. Morgan, and S.N. Deming. Sequential Simplex Optimization. CRC Press, Boca Raton, Florida, 1991.

M.H. Wright. Direct search methods: once scorned, now respectable. In D.F. Griffiths and G.A. Watson, editors, Numerical Analysis: Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis, pages 191-208, Harlow, United Kingdom, 1996. Addison-Wesley Longman.

を御覧下さい。ネット上では下記に簡単な解説がありますが、もっと詳しいものもあるかもしれません。

参考URL：http://www.research.ibm.com/infoecon/paps/html/a …

この回答へのお礼

頑張って英語も訳してみようと思います。ありがとうございました！

お礼日時：2005/06/01 22:38

No.3 回答者： tomtom_ 回答日時： 2005/05/30 14:08

シンプレックス法じゃなくて内点法ならば，非線形問題に対しては共役勾配法という手法で確立されていますが，シンプレックス法ですか？

もしくは，シンプレクティック法ではないのですか？

この回答への補足

非線形問題でシンプレックス法が使えるというのを知ったのはここで見たからです。
http://www.akita-noken.go.jp/provide/mc/manual/a …
シンプレティック法とシンプレックス法は全く別物なのでしょうか？

補足日時：2005/05/30 18:49

No.2 回答者： noname#21649 回答日時： 2005/05/30 05:40

＞は扱えるのでしょうか？

取り扱えますが.計算が膨大になるのであまりしません。

＞には、どうすればよいでしょうか？　
まずそれぞれの項(でよかったかな.名称疑問)で解を数値微分して.傾きが最大な項を見つけます。
次に.「ちょっと」(=数値微分の時のdX程度)ずらして...を繰り返して.「極値である.か.他の項の傾きが大きくなる」が項の移動の収束店です。「極値」は刻み幅を変更する必要がある程度の場合です。数値微分に時間がかかるので.局地になるまで「他の項の傾き」を省略する場合が多いでしょう。

ここで最初に戻ります。

線形式では局地まで一回の計算で落とせますが.ひせんけいしきではこれができません。何回も計算する必要があります。

結局.総当りで計算しているのと同じ暗い時間がかかってしまうので....。刻み幅の選択には注意してください。
これを使うときには悪い問題しか取り扱わないので.カイノスとか鞍部にいやってほど苦しみます(収束を早め様と広げると振動してくれる)から。

数値微分の方法と.極値か傾きを取るか.の組み合わせでいくつかの方法があります。数学的に意味がない場合も有ります(カイノスに引っかかった時等)ので.この場合には.最小二乗法の初期値を求める場合になるでしょう。

刻み幅の自動変更には注意してください。場合によっては固定する必要も出てきます。

この回答への補足

回答ありがとうございます。なかなか大変そうな計算ですね。ところでカイノス、鞍部とは何でしょうか？

補足日時：2005/05/30 18:59

No.1 回答者： grothendieck 回答日時： 2005/05/29 22:39

私はこの分野は全く素人なのですが、実際に非線形最小二乗法にシンプレックス法を使っている文献があることから、使えるものと考えられます。

参考URL：http://www.jlc.net/~fperrell/webps03.htm

この回答へのお礼

本当にシンプレックス法が非線形問題で使えるのか不安だったので、安心しました。ありがとうございます。

お礼日時：2005/05/30 18:55