条件付き線形最小化問題を解くには？

質問

ある関数がある制約条件下でどのような最小値をとるかを数値的に計算したいと考えています。
わかりにくいのですが、式を混ぜて書くと以下のような感じになります。

（１）実数W_kについてΣW_k * F_kを最小化したい
（２）F_kは実数(or複素)定数で、与えられている
（３）制約条件はΣW_k=1とW_k>=0

最小二乗法のように、||ΣW_k * F_k||を最小化することはできます。
ΣW_k=1という拘束条件を入れることもできました（LAPACKのZGELSSを使用しました)。
しかし、W_k>=0を入れた場合LAPACKのルーチンの中では該当するものが見当たりませんでした。

Mathematicaの実装ノートをみると改良Simplex法を使っているとか書いてありましたので、Simplex法を自分で実装しようかなとも思いましたが、もし既存の数値計算ライブラリで、上記のような最小化問題を解くことができるのならば、その方がいいと考えています。

何かご存知の方はいませんでしょうか？

またSimplex法に関して、詳しい実装に関するWebサイト、論文、書籍等ご存知の方がいましたら、教えてもらえないでしょうか？

よろしくお願いします

回答No.1

kts2371148 · ベストアンサー

もし、

F_k は実数定数
最小化: ΣW_k * F_k
制約条件: W_k は実数,ΣW_k=1,W_k≧0

であれば、線形計画法になり、
端点は「W_k のどれか一つが１で他のすべてが０」以外に存在しませんので、
そのうちのどれかが解になるはずです。

どこか問題に間違いはありませんでしょうか？

お礼

回答ありがとうございます。

> 端点は「W_k のどれか一つが１で他のすべてが０」以外に存在しない

なるほど、言われてみればF_kが実数の範囲においては、確かにそうですね。気がつきませんでした。
とすると、F_kが実数であるという仮定は強すぎる仮定のようです。

F_kは一般に複素数でRe(ΣW_k * F_k)を最小化し
Im(ΣW_k * F_k)の絶対値(二乗)を最小化

という問題に訂正します。

回答No.2

Tacosan

一般的には
「Re Σ W_k F_k の最小化」と「|Im (Σ W_k F_k)| の最小化」は両立しないような気がするんですけど, その場合にはどうすればいいんでしょうか?

お礼

回答ありがとうございます。
たしかに両立しない場合が考えられますね。
何で気がつかなかったのか…。

「Re Σ W_k F_k の最小化」である様な{W_k}の中で「|Im (Σ W_k F_k)| の最小化」と考えると、kts2371148さんのおっしゃられたように自明な解一つになってしまいますし。

Σ W_k F_kにおいてW_kも複素数でΣ W_k=1という条件下で||Σ W_k F_k||を最小化だとすると、一般には最小値が存在しなくなってしまいますし。

うーん、手詰まりです。少なくとも、こういう種類の最小化問題では、「自明な解」か「一般には最小値は存在しない」ということが答えのようですね。もう一度問題設定を考え直すことにします。ありがとうございました。