次のような制約付き最小化問題を考えています。
目的関数は非線形です。
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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり2番目の問題を前問に置き換える。
っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。
これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
一般に制約がf(x)<=0なら、スラック変数y(>=0)を導入して
f(x)+y==0
にできます。
また、負を取りうる変数xについては、非負変数x1(>=0)、x2(>=0)を導入して
x:=x1-x2
によりxをx1、x2に置き換えることができます。
このような置き換えにより、一般論では全ての制約が等号で全ての変数が非負の場合だけ考えれば良くなります。
上記は一般論を簡単にするための便法ですので、個別の問題にそのまま使う必要はありません。質問では不等号制約が偏微分手法と合わないということでしたので、等号制約にする手法を紹介したまでです。
No.2
- 回答日時:
> スラック変数を導入するとうまくいくモノなのでしょうか?
うまくいくかどうかは確認していませんが
> この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。
とありましたので、制約式が初めから等式制約であれば問題は解消されるかもと思った次第です。
あと最適化の一般論は標準形(変数は非負で制約は等式)で行うことが多いので、標準形に直して考える方が扱いやすいかなとも思います。
この回答への補足
標準形=変数は非負で制約は等式 なのでしょうか?
また、私が扱う最適化問題では設計変数(x1、x2)が負になることもあります。
あと、不等式制約を等式制約で扱うためにスラック変数は導入されるのであれば、標準形にするとはスラック変数を導入することなのでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10の-9乗ってどういう意味ですか?
-
「テレホンQ」どこまで?
-
前にも質問したのかもしれないけど
-
確率の問題で、「5人の中から3...
-
曲線の接線
-
log-logの補間式
-
円の接線の方程式
-
二点の座標から直線の方程式を...
-
数学の問題で質問です。 行きは...
-
関数f(x)をx1で微分
-
方程式の解を求める計算機って...
-
原点Oを中心とする単位円周上に...
-
線形代数 線形写像 質問
-
プラスとマイナスが入った比率...
-
3000円が3割なら10割はいくらで...
-
シグマなど文字を含んだままで...
-
ナッシュ交渉解の求め方を教え...
-
ねずみ算?倍々計算の計算の仕方
-
効用関数や生産関数のmin{・}と...
-
増加率、伸び率
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
10の-9乗ってどういう意味ですか?
-
確率の問題で、「5人の中から3...
-
高低差のある支持点で,電線の...
-
数学の問題で質問です。 行きは...
-
数学得意な方!!!!!
-
高校数学Ⅰ・Aです。 2200の正の...
-
再度、4点を通る曲線の方程式
-
連続型確率変数の最大値と最小...
-
log-logの補間式
-
座標平面上での三角形の面積の...
-
チャート例題185について。 解...
-
数学Ⅲです。 楕円楕円x^2/4+y^2...
-
二点の座標から直線の方程式を...
-
高校数学の問題を教えてください
-
ばらつきの掛け算
-
何通りあるか
-
体積の計算(中学生)
-
線型空間の和空間の次元公式
-
外点ペナルティ関数法
-
KKT条件について教えてくだ...
おすすめ情報