制約つき最適化問題

最小化：f(x1,x2)=(x1)^2+(1/3)(x2)^2
制 約：g(x1,x2)=-x1-x2+1<0
という制約条件が1つの問題であれば、ψ=(-x1-x2+1)^2とすることで拡張目的関数が
F(x1,x2,r)=f(x1.x2)+rψ(x1,x2)
=(x1)^2+(1/3)(x2)^2+r(-x1-x2+1)^2 ただし(-x1-x2+1<0である時)
となり、極小解を求めると、制約を満足していない領域においては
dF/dx1=(1+r)x1+rx2-r=0
dF/dx2=3rx1+(1+3r)x2-3r=0
より
x1=r/(4r+1)
x2=3r/(4r+1)
r=∞であるので、x1=1/4 x2=3/4と求まります。
---------------------------------------------------------------

以前に制約が複数個にしたらどうなるのか質問させてもらったんですが、拡張目的関数を編微分するということは理論的にどういうことを意味しているのでしょうか。
単純に目的関数を各変数について編微分すると局所部分がわかるということなのですが、ペナルティ関数項が入った場合も同じようなことがいえるのでしょうか？

No.5 ベストアンサー 回答者： kamiyasiro 回答日時： 2009/06/06 06:40

#1です。

まだ、閉じてみえなかったんですね。

　Penalty Optimization（条件付最適化）は別名罰金法ともいいますが、それは、前にも書いたように、複数の目的関数（y）を逐次最適化していくと次々に説明変数（x）に線形制約がかかり、強い不定解に陥ることによって解が無くなることを防ぐために開発されています。つまり、同時最適化の手段です。
　また、複数の目的関数間に内部従属関係（その著しいのがトレードオフ）があると、両方の目的関数を同時に満たす解がありませんから、その場合も、「yの目標条件を逸脱した場合、逸脱度合いに応じてペナルティ（罰金）を課す」という方法で評価指標を作り、その評価指標の良い解を探します。当然、一部の目的関数を犠牲にした解がでますが、それをパレート解といいます。
　通常は、そのようなペナルティ関数は単峰（たんぽう）ではありませんので、１階の偏微分で極値探索はできません。多峰に応じた探し方が必要になります。

　ですから、解が存在するようなご質問のケースでは、ウェイトで解を限定するような姑息な手段を使っているのです。また、単峰の極値探索ですから偏微分で解が出るのです。

　ペナルティの掛け方には、多くの方法が提案されています。また、最適化ソフトによっても、実装されている関数が違います。その方法を完全に理解するのは困難かと思います。

　ペナルティ法について文献を調べましたが、簡単な解説がありません。Myersらの"Respons Surface Methodology 3rd Edition"の261ページに"desirability function"（満足化関数）について記載があり、ペナルティの掛け方について説明されています。これは、「Derringer and Suich の方法」です。
　この本は洋書で１万円以上します。図書館にあるといいですが・・・。
　あとは、この回答中にある英語のキーワードでググってみてはどうでしょうか。

この回答へのお礼

たくさんの回答ありがとうごがいます。
ご意見を参考にして、理解を深めたいと思います。

皆様の意見はどの参考書よりも分かりやすくて助かりました。

お礼日時：2009/06/22 11:27

No.6 回答者： kamiyasiro 回答日時： 2009/06/06 06:57

#1です。

ついでに・・・

条件付き最適化は、yについて条件を満たすことを考えています。
制約付き最適化は、制約（constraint）を満たしたxの中から解を探し出す方法です。Constrained Optimization と言います。

あなたが参考にされたWEBページのように、区別せず、また混同して使っている方が多いです・・・。
大学教授でさえ、十分に理解していないので、しかたないですが。

No.4 回答者： stomachman 回答日時： 2009/05/02 23:44

　まずは正攻法で解いてみるとどうなるかなとやってみました。

未定乗数法の拡張版であるクルッシュ・クーン・タッカーの定理を使うと、
L(x1,x2,μ) = f(x1,x2)+μg(x1,x2)
とするとき、
---------
(x1,x2)が解になるための必要十分条件は、
∂L/∂x1 = 0
∂L/∂x2 = 0
μg(x1,x2)=0
g(x1,x2)＜0
を全て満たす(μ, x1,x2)が存在すること。
---------
∂L/∂x1 = 2x1-μ=0
∂L/∂x2 = (2/3)x2-μ=0
より
(x1,x2)=(μ/2, (3/2)μ)
です。さらに
μg(x1,x2)=μ(-μ/2-(3/2)μ+1)=μ(1-2μ)=0
より、
μ=0またはμ=1/2
なので、
(x1,x2)=(0, 0) または (x1,x2)=(1/4, 3/4)
のどちらかである。ところがどちらも
g(x1,x2)＜0
という条件を満たさないから、つまり解はない。
　しかし、もしもg(x1,x2)≦0というのが条件であれば、 (x1,x2)=(1/4, 3/4)が解です。ということで、結局これは、fの極小がちょうど境界g(x1,x2)=0上にあって、g(x1,x2)＜0の範囲には最小が（極限としてしか）存在しない例ですね。

　それはさておき、ご質問はペナルティ法の話のようです。だとすると、ご質問にあるψ=(-x1-x2+1)^2というのはなんだか変です。そこで気になるのが、ご質問の文章にある「ただし(-x1-x2+1<0である時)」なる部分が意味不明だということ。もしかすると、
ψ=(-x1-x2+1)^2、ただし-x1-x2+1<0である時はψ=0
という事かなあ。しかしこれでもまだ変なのです。
　というのは、「制約を満足していない領域においては」なんて場合分けをしなくて済むようにするためにこそペナルティを考えるんですから、Fに場合分けがあるんじゃ御利益がない。また、その後にある文章では「制約を満足していない領域」を調べてますが、制約g＜0を満足する解はそこにはないに決まっている。探しどころがおかしい訳で、これもなんだか変ですね。

　ペナルティ関数を入れた目的関数をF(r,x1,x2)とすると、Fは「制約を満足していない領域」かどうかの区別が要らない形であって、しかもr→+∞にしたときに
g(x1,x2)≦0のとき、F(r,x1,x2)→f(x1,x2)
g(x1,x2)＞0のとき、F(r,x1,x2)→間違いなく最小値ではない値（たとえば+∞)
となるように作る。これで「g(x1,x2)≦0を満たすようなx1,x2でなきゃだめ」という条件がFの中に組み込まれた訳で、以後条件のことは忘れて極値問題を解けば良い。その解(rを含む）のr→+∞における極限が首尾良く存在すれば、それが元の問題の解になってる。例えば
F(r,x1,x2)=f(x1,x2)+exp(rg(x1,x2))/r
のようにするのはひとつのやり方です。
　しかしこのアプローチは、境界g(x1,x2)=0上に最小が来ちゃうこの問題では筋が悪い。いや、勉強になります。

No.3 回答者： pspice41 回答日時： 2009/04/29 14:40

#1さんのおっしゃるとおり、方法論をちゃんと理解してから用いることが大切ですが、質問に対して漠然としたイメージをお伝えできたらと思います。

まず、変数が1つしかないときを考えます。例として"y=xの2乗"が最小になるxを考えます。この関数が最小になるxを得るには、この関数の微分”y'=2x”が0になる点を計算すればよいです。（x=0で最小になる）
このように、変数が1の関数が最小になるところは、その微分を用いて算出することができます。
今回の場合、最適化する関数はx1,x2の二つの変数を持ちます。変数が２つある場合はそれぞれの変数について考えてあげなくてはいけないので、偏微分を用いる必要があります。重複しますが、#1さんのおっしゃるとおり、理論をちゃんと理解しないと解けないと思いますが、最小値を求めるイメージは変数が1つの時と変わりません。

No.2 回答者： kamiyasiro 回答日時： 2009/04/29 07:56

#1です。

　前の質問と回答を見ました。この解法は引用なのですね。あなたに問題があるような書き方をして失礼しました。

　前の回答者の方もおっしゃっていますが、解の求め方に問題があります。引用された求め方は、たまたま解が一致しているだけです。

　なお、
・制約が複数になる場合・・・x1～xnという多次元空間であったとしても、線形制約を次々かけていくと、つぎつぎ不定解に陥り、解が無くなります。（設計できません）
・条件が複数になる場合・・・ペナルティつき合成スカラー量の１目的関数の最適化問題なので、必ず解があります。ただし、境界条件から外れた解になることもあります。（必ずしも仕様を満足しません。つまり重量が目標値に入らないとか、燃費が目標値より悪いとか・・・）なお、どれかの条件を犠牲にした解をパレート解といいます。多くは燃費と排ガスのようなトレードオフ特性が該当します。

この回答への補足

丁寧な回答ありがとうございます。
もし、外点ペナルティ関数法（罰金法）に関してよい説明のサイトがあれば教えていただきたいです。
これまでに何度の検索しましたが、理論的なことがはっきり理解できません。

補足日時：2009/04/29 17:55

No.1 回答者： kamiyasiro 回答日時： 2009/04/29 07:27

　ご質問とは視点の違う回答になっていますことをお許し下さい。

前半の解の求め方に一般性がないので、その指摘とからめて回答します。

　分野によって流儀が違うかもしれませんが（というより、本を書いた先生の誤訳により混乱がありますが）、目的関数に条件をつけていますから制約つき最適化ではなく「条件つき最適化」ですね。
　制約つき最適化とは制御因子（設計パラメータ）に線形制約をかけた最適化です。一般には、ネジのように離散的な値しか取れないとか、材料強度のように上限があるとかいう場合に「設計制約がある」という意味で、「制約つき最適化」という言葉が用いられます。方法論的には連立方程式になります。
　ただし、今回のケースもg(x)に条件をつけることによって結果的に制御因子に線形制約がかかっていますので、「制約つき」と言っても間違いではありません。

　さて、今回のケースは、g(x)に境界条件をつけながらf(x)，g(x)両者の合成スカラー量を最小化する式に帰着させていますが、大きな間違いがあります。
　g(x)が境界条件を満たさない外側部分に２乗のペナルティを掛けていますが（たまたま境界が0だからそのままg(x)を２乗しています）、現在の式ですと境界条件を満たす内側部分にも（負の値が大きくなるに従って）ペナルティが掛かります。この式では、もしこの内側部分に最適値があっても発見できません。通常は、境界条件範囲内はペナルティを0にするなどの配慮が必要です。

　最適値の探し方ですが、偏微分で行うことは一般的ではありません。今回のケースでは、x1についても，x2についても下凸で２次関数ですから１階の微分で極値（最小値）探索できるのですが、上凸なら最大値を探すことになりますし、x1が下凸でx2が上凸なら、鞍点，もっと高次の関数なら停留点しか求まりません。通常は、ダウンヒル・シンプレックスや遺伝子アルゴリズムで探索します。

　なお、合成スカラー量にはウェイトw（質問ではr）を掛けていますが、この意味は単位調整です（f(x)が燃費，g(x)がNOxだと単純な合算はできませんから調整します）。今回のようにr=∞というウェイトの掛け方は、制御因子の制約（つまり、ψが0のときしか成立しない）に帰着させる小手先技と思いますが、これも間違いです。前に述べたように、g(x)＝0という境界線上ではなくもっと内側に良い解があっても見つかりません。

　方法論を良く理解して適用されることをお勧めします。