第1回輪講 2011.5.10 (火)

慶應義塾大学理工学部
管理工学科４年曹研究室
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,λ, μ) 
ラグランジュ乗数
xX
 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,λ, μ)
xX
双対問題（ラグランジュ双対問題）
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,λ, μ)
xX
 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
が成立することである。
定理：局所的最適性の２次必要条件
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 } は右図のように
２つの直線
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


Download Report