非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。
目的関数は非線形です。
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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。
っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。
これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
お礼
お返事どうもありがとうございました。 早速この本を探すことができて、 Brent法を学ぶことができそうです。