3 (pp.13--15)

3 不等式制約下の最大／最小化
max ）／最小化（ min ）を区別して扱う．目的関数は最大化の場合凹関数，最小
化の場合は凸関数とする．
8 max ff(x(x) )を凹関数とするとき，次の定式化を \正準形" と呼ぶ．
<
(P ) : sub. to gi(x) bi (i = 1 2 : : : m) m < n
x 2 Rn x 0
問題 (P) は LP の場合と同様に，スラック変数を用いて次の
(P] ) に書き換えることができる．
8 max
f (x)
<
(P] ) : sub. to gi(x) + si = bi (i = 1 2 : : : m) m < n
x 2 Rn s 2 Rm x s 0
x 2 Rn が (P) または (P]) の最適解であるための必要（十分）条件を考えていく．
本章では最大化（
3.1 準備
max
まず始めに，等式制約が無く非負制約だけの問題
(P )
f (x)
(P ) を考える．
x 2 Rn x 0
x が x 0 における f (x) の制約無し最大点（問題 P の最適解）
sub. to
=)（凹関数の場合は () ）
1 変数の場合
x = 0 ) f 0(x ) 0 0
0
x > 0 ) f 0 (x ) = 0 すなわち x 0，x f (x ) = 0，f (x ) 0．
n 変数の場合
@f (x ) = 0， @f (x ) 0 （ j = 1 2 : : : n ）．
xj 0， xj @x
@x
j
j
3.2 等式条件と非負制約（標準形）
(Q) を考える．
8
f (x)
< max
(Q) : sub. to gi(x) = bi (i = 1 2 : : : m) m < n
x 2 Rn x 0 m
X
問題 (Q) のラグランジュ関数を L(x ~
) = f (x) + i ( bi ; gi (x) )
非負制約のみの場合を基にして，標準形の問題
x
i=1
が問題
と定義する．
(Q) の最適解
=)（ f (x) が凹関数の場合は () ）
x が問題 (Q) に対する Karush-Kuhn-Tucker の条件を満たす．すなわち，
9 ~ such that
@L (x ~ ) = 0， @L (x ~ ) 0 （ j = 1 2 : : : n ）
xj 0， xj @xj
@xj
@L
~
@i (x ) = 0，（ i = 1 2 : : : m ）．
{ 13 {
3.3 正準形の場合
問題
(P] ) に前節の定理を適用して問題 (P) の最適解の必要条件を求める． f (x) が凹関数の場合，
これは必要十分条件となる．
問題
(P) のラグランジュ関数を L(x ~) = f (x) +
x
が問題
m
X
i=1
i ( bi ; gi(x) )
と定義する．
(P) の最適解
=)（ f (x) が凹関数の場合は () ）
x が問題 (P) に対する Karush-Kuhn-Tucker の条件を満たす．すなわち，
9 ~ such that
@L (x ~ ) = 0， @L (x ~ ) 0 （ j = 1 2 : : : n ）
xj 0， xj @xj
@xj
@L
~ ) = 0， @L (x ~ ) 0，（ i = 1 2 : : : m ）．
i 0， i (
x
@i
@i
(証明)
X
(P] ) のラグランジュ関数は K (x s ~) = f (x) + i ( bi ; gi(x) ; si ) である．
i=1
（ si は第 i 制約式の slack 変数）
前節の結果より，x 2 Rn s 2 Rm が最適解となる条件は，ある ~ が存在して
(a) xj 0 （ j = 1 2 : : : n ）
(b) si 0 （ i = 1 2 : : : m ）
@K (x s ~ ) = 0 （ j = 1 2 : : : n ）
(c) xj @x
j
@K
(d) si @s (x s ~ ) = 0 （ i = 1 2 : : : m ）
i
@K
(e) @x (x s ~ ) 0 （ j = 1 2 : : : n ）
j
@K
(f) @s (x s ~ ) 0 （ i = 1 2 : : : m ）
i
@K
(g) @ (x s ~ ) = 0，（ i = 1 2 : : : m ）．
m
問題
i
である．
@L (x ~ ) = 0 と等価．
(d) は i @
i
(f) は i 0 と等価．
@L (x ~ ) 0 と等価．
(b) と (g) は @
i
(c) と (e) のラグランジュ関数 K は L で置き換えても等価．
以上より (a) ∼ (g) は上で示した (P) に対する Karush-Kuhn-Tucker の条件と等価．
{ 14 {
3.4 非負鞍点
(P) に対する Karush-Kuhn-Tucker の条件をみると，x （ 0 ）は L(x ~ ) の最大
点であり，~
（ 0 ）は L(x ~) の最小点であることが想像される．
実際，f (x) が凹関数，gi (x)（ i = 1 2 : : : m ）が凸関数のとき，
L(x ~ ) L(x ~ ) L(x ~)
正準形の問題
が成り立つ．
(x ~ ) は L(x ~) の非負鞍点であるという．
このとき，
~ が存在して，
(x ~
)が
問題 (P) の Lagrangian の非負鞍点
ある
x
は問題
(P) の最適解
,
ある
,
~
Karush-Kuhn-Tucker の条件
が存在して，
xj 0，
@L (x ~ ) = 0，
xj @x
j
@L (x ~ ) 0
@xj
（ for j = 1 2 : : : n ）
；
| i 0，
@L (x ~ ) = 0，
| i @i
@L
~
|
@i (x ) 0
（ for i = 1 2 : : : m ）
；
を満たす．
3.5 線形計画問題への適用
線形計画問題の最適解の必要十分条件を求めてみる．
=)
双対定理，相補スラック条件，シンプレックス基準
{ 15 {

Download Report