慶應義塾大学 理工学部 管理工学科4年 曹研究室 60803571 遠藤 健司 非線形計画法 ラグランジュ緩和問題 双対問題 不等式制約のある最適化問題最適性 KKT条件 制約条件のない最適化問題の最適性 最急降下法 「数理計画法の基礎」 坂和正敏 著 森北出版(株)(1999,初版) 「数理計画法」~最適化の手法 森哲夫 著 共立出版(株)(1994,初版) 主問題 主問題の目的関数をラグラン ジュ関数に置き換えることで、 満足すべき制約条件が緩くなり、 解き易くなる。(緩和問題) →ラグランジュ緩和問題 min f (x) s.t. g i (x) 0, i 1,2,...,m h j (x) 0, j 1,2,...,l x Rn ラグランジュ緩和問題 min L(x,λ, μ) ラグランジュ乗数 xX i ( 0) i 1,2,...,m j j 1,2,...,l ラグランジュ乗数と、対応す る主問題の制約関数との積の 和に、目的関数を加える。 →ラグランジュ関数 ラグランジュ関数 m l i 1 j 1 L(x,λ, μ) f (x) i gi (x) j h j (x) m l min f (x) i g i (x) j h j (x) i 1 i 1 s.t. x R n L(x,λ, μ) を x で最適化したもの →双対関数 双対関数 d (λ, μ) min L(x,λ, μ) xX 双対問題(ラグランジュ双対問題) max d (λ, μ ) s.t. λ 0 主問題が与えられた場合、こ れとペアになる問題である、 双対問題が必ず存在する。 しかし、主問題の最適解に対 する最適値と、双対問題の最 適解に対する最適値が等しく なるとは限らない。 →弱双対定理 x : 主問題の最適解 , : 双対問題の最適解 これらの値をラグラン ジュ関数に代入する。 m l L(x , λ , μ ) f (x ) i gi (x ) j h j (x ) i 1 但し、g i (x ) 0, i 1,2,...,m j 1 h j (x ) 0, j 1,2,...,l i 0, i 1,2,...,m L(x , λ , μ ) f (x ) ・・・① また、双対関数の定義より、 d (λ, μ) min L(x,λ, μ) xX d (λ , μ ) L(x , λ , μ ) ・・・② 式①、②より、 f (x ) d (λ , μ ) →弱双対定理 ※ f (x ) d (λ , μ ) の場合、双対 ギャップが存在する。 双対ギャップが存在しない 非線形計画問題 →凸計画問題 凸計画問題 min f (x) →凸関数 s.t. g i (x) 0, i 1,2,...,m →凸関数 h j (x) 0, i 1,2,...,l →一次関数 x R n →凸集合 制約条件のない非線形計画問題 min f (x) s.t. x R n 大域的最適解 x f (x ) f (x) x R n 0 局所的最適解 x N (x 0 , ) {y R n | || y x 0 || } f ( x 0 ) f ( x) 定理:局所的最適性の必要条件 f (x) C1 のとき、 x 0 が制約条件の ない最適化問題の局所的最適解であ 0 るための必要条件は f (x ) 0 が成立することである。 定理:局所的最適性の2次必要条件 f (x) C 2 のとき、x 0 が制約条件の ない最適化問題の局所的最適解であ 0 るための必要条件は f (x ) 0 で、 しかも x 0 におけるヘッセ行列 2 f (x 0 ) が半正定 dT 2 f (x0 )d 0 d R n となることである。 定理:凸関数の最適性の必要十分条件 T 2 f (x0 )d 0, d R n f (x) が R n 上で微分可能な凸関数とするとき、 x dが制約条件のない最適化問 f (x ) 0 が成立することで 題の大域的最適解であるための必要十分条件は、 ある。 不等式条件のある非線形 計画問題 min f (x) s.t. g i (x) 0, i 1,2,...,m 定理:凸計画問題の最適性の条件 不等式条件のある非線形計画問題の 制約集合が凸集合で、目的関数が凸 関数であれば、その局所的最適解は 大域的最適解であり、最適解の集合 は凸集合である。 不等式制約式による制約集合 x X : X i {x R n | g i ( x) 0}, 不等式条件のある非線形問題の実行可 能解 i 1,2,...,m m X Xi i 1 {x R n | g i ( x) 0, i 1,2,...,m} g i (x) が全て凸関数であれば、 X は凸集合となる。 I (x) {i | gi (x) 0} : 活性制約式( gi (x) 0 )の添字集合 定義:線形独立制約想定(正規 条件) 先述の非線形計画問題の制約関 数 g i (x) は全て C 1 級の関数 で、x X とする。このとき、 x X における勾配ベクトル gi (x), i I (x) が線形独立 であれば、制約関数 g i (x)は x X で線形独立制約想定を 満たすという。 →ラグランジュ乗数の存在を 保証する。 f (x), gi (x) : C1 級の関数 x0 X : 局所的最適解 Kuhn-Tucker, KKT 条件 m x L(x , λ ) f (x ) i g i (x 0 ) 0 0 0 0 0 i 1 g i (x 0 ) 0 i 0 g i (x 0 ) 0 →相補条件 i 0 0, i 1,2,...,m 定理:凸計画問題に対する最適性の十分 条件 不等式条件のある非線形計画問題におい て、f (x), gi (x), i 1,...,m が全て凸関 数の時、(つまり、凸計画問題の時) x 0 X において、KKT条件を満たして いれば、x 0 は大域的最適解 x となる。 KKT条件を満たすラグランジュ乗数 i が存在すると仮定した場合、KKT条 件を満たす x 0 はラグランジュ関数 L(x,λ 0 ) の最小値を与える。 →ラグランジュ緩和問題の最適解となる。(凸計画問題の場合) 0 では、非線形計画問題が凸計画問題ではなかった場合は・・・ n ある初期点から出発して、目的関数 f (x) の値を次々と減少させるような R l 1 2 l の点列、f (x ) f (x ) f (x ) となるような点列 {x } を系統的に生成する。 →降下法 x l : 現在の点 x l 1 : 次の新しい点 d l : 方向ベクトル l : ステップ幅 更新公式 xl 1 : xl l dl , l 1,2,... l 方向ベクトルdl はあるステップ幅 a 0 l l l l に対して、f (x d ) f (x ) を満たす必要 がある。( dl :降下方向) またステップ幅 l 0 は一次元探索問題 min ( ) f (x l l d l ) a 0 を解くことで求められる。 降下法のアルゴリズム 目的関数の微分可能性を仮定すると、 l テイラーの定理より、 1. 初期点 x を選び、l : 1とする。 f (xl l dl ) f (x) f (x)d l 2. 現在の点 x において停止基準 であるため、方向ベクトル d は をみたせば終了、そうでない場 f (x)d 0 を満たせば降下方向になる。 合は降下方向 dl をもとめる。 3. 降下方向dl を勾配ベクトル f (xl ) l T l を用いて、d f (x ) とするこ l とにより、xl の近傍で f (x ) を最も 急激に減少させる最急降下方向に 選ぶ手法 →最急降下法 一次元探索問題を解き、ステッ プ幅 l をもとめ、 xl 1 : xl l dl , l : l 1 として、手順2.へ戻る。 ※ 停止基準:|| f (xl ) || 一次元探索問題の最小値が正確に 求められた場合 f (x l l d l )d l l f (x l 1 )d l 0 dl は f (xl 1 ) と直交するので、 新しい方向ベクトル dl 1 T f (xl 1 ) はこれまでに 得られている全ての方向ベク トルと直交する。 等高線が超球(二次元の場合は円)となる関数の場合、一回の探索で最小点に到 達できる。しかし、それ以外の等高線が偏心しているよう一般の関数では、最小 点の近傍での探索でジグザグになり、効率のよい探索方法とは言えない。 1 2 2 f (x) a bT x x TQx 2 x1 x1 x2 2 x2 2 4 1 0 Q , b 0 , a 0 1 4 より、 min ( ) 0 f (x d )d 0 l f (x1 ) 20 f (x) xT Q (4 x1 x2 , x1 4 x2 ) なので、 f (x1 ) (5,10) f (x) bT xT Q l 初期点をx1 (2,3) とする。 l l l {bT (x l l d l )Q}d l 0 (bT xT Q)d l l (d l )T Qd l 0 d1 T f (x1 ) (5,10) 二次関数に対する一次元探索問題 の最適ステップ幅は、 q (x1 )d l 1 T 1 (d ) Qd 1 となるので、αに関する式に変換 すると、最適ステップ幅が解析的 に与えられる。 q(xl )dl l T l , l 1,2,... (d ) Qd l 5 (5,10) 5 10 4 1 5 16 (5,10) 10 1 4 よって、 x 2 x1 1d1 2 5 5 3 16 10 1 7 0.4375 16 2 0.1250 同様にしてx3を求めると、 x 3 x 2 2d 2 1 2 0.0469 128 3 0.0703 となり、点列 {xl } は右図のように 2つの直線 x2 3 7 x1 , x2 x1 2 2 上の値を交互に取りながら、最適 解 x0 (0,0)T に近づいていく。 論文に戻る 「A Paradigm for the Scheduling of a Continuous Walking Beam Reheat Furnace Using a Modified Genetic Algorithm」 Jonathan S. Broughtona, Mahdi Mahfoufb* & Derek A. Linkensb Materials and Manufacturing Processes Volume 22, Issue 5, 2007 An Optimal Scheduling Algorithm for Reheating Furnace in Steel Production NING Shu-shi,WANG Wei,LIU Control and Decision 2006-10
© Copyright 2025 ExpyDoc