非線形計画法主-双対問題

締切済

質問者：guugle
質問日時：2009/12/08 10:37
回答数：3件

次のような制約付き最小化問題を考えています。
目的関数は非線形です。
min x1^2+x2^2
s.t. -x1-x2+4<=0
x1>=0
x2>=0

この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。
次に次式のような双対問題を考えます。
g(x)=-x1-x2+4とおき
双対関数
φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0}
=inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u

上記においてもしu>=0であれば、x1=x2=(u/2). （なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。）
u<0であるならばx1=x2-0であることに注目しますと。
φ(u)=-(1/2)*u^2+4*u for u>=0
=4u for u<0
となります．
双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。

次に主問題を次のように制約を増やした最小化問題を考えます。
min x1^2+x2^2
s.t. -x1-x2+4<=0
-2*x1-3*x2<=0
x1>=0
x2>=0
これの最適解は上記の問題と同じにならないといけないのですが、
例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると（λ：ラグランジュ乗数）、
F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2)
最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。
この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。
偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。
しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。
っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。

これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

最新から表示
回答順に表示

No.3

回答者： rinkun
回答日時：2009/12/15 09:09

一般に制約がf(x)<=0なら、スラック変数y(>=0)を導入して

　f(x)+y==0
にできます。
また、負を取りうる変数xについては、非負変数x1(>=0)、x2(>=0)を導入して
　x:=x1-x2
によりxをx1、x2に置き換えることができます。
このような置き換えにより、一般論では全ての制約が等号で全ての変数が非負の場合だけ考えれば良くなります。

上記は一般論を簡単にするための便法ですので、個別の問題にそのまま使う必要はありません。質問では不等号制約が偏微分手法と合わないということでしたので、等号制約にする手法を紹介したまでです。

- 1
- 件

通報する

No.2

回答者： rinkun
回答日時：2009/12/09 11:41

> スラック変数を導入するとうまくいくモノなのでしょうか？

うまくいくかどうかは確認していませんが

> この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。

とありましたので、制約式が初めから等式制約であれば問題は解消されるかもと思った次第です。

あと最適化の一般論は標準形(変数は非負で制約は等式)で行うことが多いので、標準形に直して考える方が扱いやすいかなとも思います。