Microsoft Word - 非線形計画法　原稿

Transcription

1 非線形計画法条件付き最適化問題は目的関数と制約条件で示すが この中に一つでも 次式でないものが含まれる問題を総称して非線形計画法いう 非線形計画問題は 多くの分野で研究されているが 複雑性により十分汎用的なものは確立されておらず 限定的なものに限り幾つかの提案がなされている ここでは簡単な解法について紹介する. 制約なし極値問題 単純問題の解法 変数で表される関数 の極値は を解くことによって求められる 例 : 某都市施設を建設することになった 施設の規模を変えると便益 B も建設費用 も変化する 与えられた単位規模当たりの便益と費用をもとに 便益を最大にする規模 S を求める 近似解法複雑な関数であっても ある値 の近傍における近似値として下式のテーラー展開によって求めることができる の場合にはマクローリン展開とも呼ばれる!! 変数の場合のテーラー展開による近似値はどうなるだろうか として. : cs b b とすれば d d d d d d となって 微分演算子も単なる変数記号のように扱うことで分かりやすく表現でき これの高次導関数は以下のように示される 5 6 m S S ds dz B Z S S B

2 r r r r r r d さらに を として をパラメータとする点 との位置関係を示せるように再表現しておき の近似値を求める とすると であり これに を代入すると である このことから m m となって 同様に簡単に表現される ここで のマクローリン展開は! であり であるから 代入して! の値は任意であり 見通し良くするため とすると! となる ここで としてベクトル表現すると

3 ! となって とおくと! と簡潔に表される は のヘッセ行列と呼ばれる の 上付きの は Opme の頭文字 の近傍では次のようになる! が で極値 ここでは局所的最小値としよう となるための条件は である なお は 対称行列であるが これの固有値は実数であり 例えば固有値対角行列を Λ 固有値ベクトルを とすれば 次のようになって より しかないので よってヘッセ行列 は正定値である ニュートン ラプソン法 を においてテーラー展開するととなるが 右辺の近似式を にする を求めるべく これを で偏微分して とおく つまり!! 両辺に をかけて整理すると となる d として d とし 繰り返し計算を行って近似値としての解を求める ステップ : 所期点 を決める ステップ : であればストップ! I X + X

4 ステップ : d を計算する ステップ : d とする ステップ : ならストップ とし ステップ に戻る 例 : m をニュートン法で求めよ 但し 出発点 とし 計算値の差が.5 以下になったら計算作業中止せよ これは式より O で m であることは一目瞭然であるが 近似計算により漸次 であることがわかる * * * * * *.78 *

5 最急降下法 これは探索点における勾配の負の方向を探索方向として用いるほうほうである つまり 作業実施点 からの探索方向として次のベクトルを用いる d これを次のステップを繰り返して行い * になるまで繰り返す ステップ: 所期点 を決める ステップ: であればストップ ステップ: d とする ステップ: αd が最小となる値 α を求める これは簡単に求められないことが多く D α αd として D α より α を求 める方法がある ステップ: α d とする とし ステップに戻る. 制約つき極値問題 ラグランジュの未定乗数法 変数 の間に の関係があるとき の極値を考えよう は の関数であるから は のみの関数である ここで は陰関数であり 両辺を微分して d d d d d d d d となって の極値なので d d d d d d d d d d である よって に極値を与える は の根でなくてはな らない よって これを求め ことができる の符号を調べることによって極大か極小かを判定する ここで なる関係を利用して となり かつ の式は : cs. とおいて 下式 を解くのと等価である 5

6 但し ラグランジュ乗数という の符号は正負どちらでもよい 一般に変数 について m 個の条件 m のもとで関数 の極値を求めるには m : cs. とおいて であるから m の連立方程式で求められる 例 : の条件のもとで を最小にせよ この問題の答えは 目的関数が原点からの距離の 乗に等しいから 原点から に下ろした垂線の交点である 普通に解くには 条件式を変形した を目的関数に代入した を微分して求める つまり d d m ラグランジュの方法を用いれば m 8 8 この方法では に選んでおけば 値が の直線上では をとることを示している また と同じ値 と変形され 値の最小値は 値によって変化す る つまり 値と 及びその座標 は次のようになっている m 6

7 5 6 m m m m m m m これにより m は の直線上を辿りながら原点から と交わるところまで次第に増加し この点を過ぎると次第に減少していることがわかる また がどんな値であっても直線 上の 値は常に一定である m は鞍点となっている 6 = の時の の変化 6 =- の時の Φ の変化 5 5 Φ =6 =6 = Φ= Φ= Φ= m=8 = = Φ m= 例 : 体積 V の円筒形水槽を特殊な板で作ることになった 水槽は底面 側面のみを囲う 構造である このとき 板の面積を最小にする底面の半径 r と高さ の比を求めよ V πr S πr πr r πr m πr V πr πr πr r r πr π πr r r r : r : r 7

8 キュンタッカーの条件制約式は等号で結ばれていれば比較的簡単に求められるが 一つでも不等式が含まれると解は一意に決められないことが多い 非線形計画法は かなり複雑な理論であるので一般的解法は現在でもはっきりせず 一定の条件を満たす問題を解く場合に限られる 問題にある関数を図形に表現した場合 下に凸となるものを凸関数 上に凸となるものを凹関数と呼んでいる のすべてが凸関数であり も凸関数であるとき m m を凸計画法という この中に一つでも凹関数なる場合を非凸計画法という のすべてが凹関数であり も凹関数であるとき m m を凹計画法という 目的関数が凸関数の場合 最小値を求めることは容易であるが最大値を求めることは特定の場合を除き一般に困難であり 凹関数の場合 反対に最大値を求めることは容易であるが最小値については困難である ここでは凸計画法 又は凹計画法に限定して述べる 双対性は A b 主問題 : とすると 双対問題 : c m wa c w wb m である A b wa c これの非対称形は 主問題 : 双対問題: w w である c m wb m A b wa c 又は 主問題 : 双対問題 w c m wb m の組となる 非対称形は通常の双対問題と等価である なぜならスラック s s s とすると A I b c m m s s と表せて この 8

9 非対称性双対問題を書くと m wb c I A w となる これは wi cw wa となり通常形に同じとなるからである よってについて はであり d とし とすると となる また とすると は と示して が存在する ファーカスの定理より なぜなら先の を書き直して ととなるからである ところで のうち l は l は である の場合は双対定理がそのまま使えるが の場合は通常の双対定理 つまりとでなくてはならない よって通常形と非対称形を一緒に扱うため A として調整項 を添えることにする の場合は調整項不要のため l である m A m A m A m A d l d d d d d d d d d d d

10 以上より となる に置き換え 変数を元に戻して 但しなお 境界上でない場合 いわゆる境界内部 では m としておけば m となる これをキュンタッカーの条件という これは グランジュの関数式において簡潔にまとめることができる つまり とするとき が の領域で を最小にするための必要かつ十分条件は であるということである なお は鞍点となっている このことは 次のように説明できる まず 式 は m と等価であり これを用いる まず必要条件は が で最小になるなら は非負領域の中か境界上にあって 領域内では l で 境界上では l である は でも最小値になるから同様のことがいえる つまり で m で l l

11 なので もともと であり 境界内部 境界上 となり いずれにおいても である また十分条件は の両式が成立すると言うことは は において については凸関数であり については凹関数なので よって の近傍 で となるので であり これは が鞍点となっていることを示している Φ

12 例 : 既存市街地内に図に示す矩形の跡地が生じ ここ で区画整理事業を実施する 下記の条件のもとで公共用 住宅地 地 公園 + 多目的用地 を最大にしたい の最適 値を求めよ 地区全体の価値と住宅地と多目的用地とを合わせた m 価値を等しくする なお 地区全体 の地価は 5 万円 / m 従後の地価は住宅地 万円 / m 多目的用地 8 万円 / mとする 従後に住宅地となる土地の南側境界の幅は mを 多目的用地 公園 m 下回ってはならない 多目的用地の南側境界の幅は m を下回ってはならない s.. 6 m Z 8 μ μ 8 μ μ μ & μ μ 5 μ μ 6 μ μ & μ μ 5. 6 μ ; 5.5 Z m μ & μ 6.5 μ 58 6 OK!. μ & μ μ 5 5; μ & μ N Aswer. & ; NO! μ NO! Opme Z m 6