chap0

0.1 Finite Systems of Linear
Inequalities
Definition
•
•
•
•
•
{x1, x2, …, xk} : Rn次元内の点集合
x = Σλk xk (λk ∈R) : xkの一次結合
全てのλkが0以上 ⇒ conical
Σλk x = 1 ⇒ affine
conical かつ affine ⇒ convex
Definition
• xk が linearly independent
Σλk xk = 0 を満たすλがλk= 0のときのみ
• xk が affinely independent
Σλk xk = 0 かつ Σλk = 0 を満たすλが
λk= 0 のときのみ
x 
•  1  が linearly independent
⇒ xk が affinely independent
k
Definition
• 集合 X (⊂ Rn) が(有限の) 左の結合の下で閉じていると
き、Xを右で定義する。
•
•
•
•
linear ⇒ subspace
conical ⇒ cone
affine ⇒ affine set
convex
⇒ convex set
Definition
• 集合 X 内の全ての右の点結合の集合を
左で定義する。
•
•
•
•
linear ⇒ linear span : sp(X)
conical ⇒ conical hull : cone(X)
affine ⇒ affine span : aff(X)
convex
⇒ convex hull : conv(X)
polytope
• Polytope とはある有限集合に対する conv(X) である。7
• Polytope は線形不等式の有限systemの解集合で記述
できる。(Weyl’s Theorem)
１： Elimination method
２： Weyl’s Theorem
Elimination method の例
 2 3 5  x1   2 

   
 0 4 1  x2    1 
  1 1 2  x   4 

 3   
2 x1  3x2  5 x3  2
4 x2  x3  1　 x1  x2  2 x3  4
x1を消去することを
考える。
Elimination method の例
2 x1  3x2  5 x3  2
4 x2  x3  1　 x1  x2  2 x3  4
x1が残っている式を
考える。
2 x1  3x2  5 x3  2
4 x2  x3  1　 2 x1  2 x2  4 x3  8
一番下の式を２倍する
Elimination method の例
2 x1  3x2  5 x3  2
4 x2  x3  1　 2 x1  2 x2  4 x3  8
5 x2  9 x3  10
4 x2  x3  1　一番上と下の式を加えて、
１つの式にする。
Elimination method
次の線形不等式を考える。
n
a x
j 1
ij
j
 bi for　i  1,2,..., m
削除したいxkを選び、aikの符号で式をわける。
S  : {i : aik  0}
S  : {i : aik  0}
S 0 : {i : aik  0}
Elimination method
a11x1  a12 x2      a1n xn  b1
a21 x1  a22 x2      a2 n xn  b2

am1 x1  am 2 x2      amn xn  bm
Elimination method
a11x1  a12 x2      a1n xn  b1
a21 x1  a22 x2      a2 n xn  b2

am1 x1  am 2 x2      amn xn  bm
Elimination method
ai 2  0
a11x1  a12 x2      a1n xn  b1
ai 2  0

a41 x1  a42 x2      a4 n xn  b4
a31x1  a32 x2      a3n xn  b3
a71 x1  a72 x2      a7 n xn  b7
ai 2  0

a11x1  0  x2      a1n xn  b1

Elimination method
S0 : {i : aik  0}
に含まれる式に対してはxkは含まれていないので、
そのままにしておく。
S  : {i : ai k  0}, S  : {i : ai k  0}
に含まれる式に対しては全ての(i+,i-)のペアについて、
以下の操作を行う。
 n

 n

 ai j   ai j x j  bi   ai j   ai j x j  bi 
 j 1

 j 1

Elimination method
•
こうして出来た新しい線形不等式のsystemは以下の性質を満た
す。
① 新しいsystemはxkを含まない。
② 新しいsystem上の各不等式は元のsystemの不等式の非負な線形
結合になっている。
③ (x1, x2,…,xk-1, xk, xk+1,…,xn)が元のsystemの解ならば、
(x1, x2,…,xk-1, xk+1,…,xn)は新しいsystemの解である
④
(x1, x2,…,xk-1, xk+1,…,xn)は新しいsystemの解ならば、
あるxkに対して、(x1, x2,…,xk-1, xk, xk+1,…,xn)が元のsystemの解で
ある。
Weyl’s Theorem(for Polytope)
• Pがpolytopeのとき、あるいくつかの正整数mと
実数aij,bi (1≦i≦m, 1≦j≦n)の選択に対して、
n


n
P   x  R :  aij x j  bi for　i  1,2,..., m
j 1


証明
以下の線形不等式のsystemを考える。xjkは定数。
x j   k x kj  0, for　j  1,2,..., n
kN

k
 1;
k  0, k  N
あとは、先ほどのelimination methodを用いて、
上記の不等式と条件式を用いて全てのλを消去すると、
定理の条件を得ることができる。
Theorem of Alternative for Linear
Inequalities
The system
n
( I )  aij x j  bi , for　i  1,2,..., m
j 1
has a solution if and only if the system
m
ya
i 1
i ij
 0, for　j  1,2,..., n;
( II ) yi  0, for　i  1,2,..., m;
m
yb 0
i 1
i i
has no solution
証明
まず、両方のsystemが解を持つことがないことを示す。
n
m
m
n
m
j 1
i 1
i 1
j 1
i 1
0   x j  yi aij  yi  aij x j   yi bi  0
より、両方のsystemが解をもつことはない。
証明
(I)が解を持たないと仮定する。
(I)において、elimination methodを用いて、
全てのn変数aijを削除する。
そのとき、以下の式が得られる。
n
0 x
j 1
j
 b , for　i  1,2,..., p
'
i
where bk'  0　for some k, 1  k  p.
証明
以下の不等式は、system(I)の不等式の
非負の線形結合となっている。（elimination methodの性質）
n
()  0  x j  bk'
j 1
すなわち、適当なyi ≧ 0 (i=1,2,…,m)が存在し、
(*)は以下のように記述できる。
 n

yi   aij x j  bi 

i 1
 j 1

m
証明
書き換えると、
m
 m

  yi aij  x j  yi bi

j 1  i 1
i 1

n
この係数を(*)の係数と比較すると、(II)の不等式が得られ、
y = (y1, y2, … , ym)は(II)の解になっている。
n
()  0  x j  bk'
j 1
Farkas Lemma
The system
n
 aij x j  bi , for　i  1,2,..., m
j 1
x j  0, for　j  1,2,..., n
has a solution if and only if the system
m
 yi aij  0, for　j  1,2,..., n
i 1
m
 yi bi  0
i 1
has no solution
0.2 Linear-Programming Duality
n
c
max
j1
j
xj
( P ) subject　to :
m
a
i 1
ij
x j  bi for　i  1,2,..., m
m
min
yb　i 1
i
i
( D ) subject　to
m
ya
i 1
i
ij
 c j for　i  1,2,..., n
yi  0 for　i  1,2,..., m
Weak Duality Theorem
•
もし、xがPの実行可能解で、yがDの実行可能
解とすると、 nj1 c j x j  im1 yi bi をみたす。
このとき、
n
m
(1) もし、  j 1 c j x j  i 1 yi bi なら、xとyは最適
解であり、
(2) もし、どちらかのprogramがunboundedなら、も
う一方は実行可能解をもたない。
証明
• xがPの、yがDの実行可能解と仮定する。
m
 n
 m
 m

c j x j     yi aij x j   yi   aij x j    yi bi

j 1
j 1  i 1
i 1

 j 1
 i 1
n
n
Strong Duality Theorem
•
もし、PとDが実行可能解をもつなら、
n
m
c
x

 j 1 j j i1 yibi をみたす最適解x,yをもつ。
もし、実行不能なら、もう一方は実行不能か、
もしくはunboundedである。
証明
次の線形不等式のsystemを考える。
n
 a x j 1
ij
j
 bi for　i  1,2,..., m
m
 y a  c for　j  1,2,..., n
i ij
i 1
i
m
( I )   yi aij  ci for　j  1,2,..., n
i 1
 yi  0　for　i  1,2,..., m
n
m
j 1
i 1
  c j x j   bi yi  0
証明
Weak Duality Theoremより、x,yがそれぞれPとDの
最適解のとき、かつそのときに限り、x,yは(I)を満たす。
n
 a x j 1
ij
j
 bi for　i  1,2,..., m
m
 y a  c for　j  1,2,..., n
i ij
i 1
i
m
( I )   yi aij  ci for　j  1,2,..., n
i 1
 yi  0　for　i  1,2,..., m
n
m
j 1
i 1
  c j x j   bi yi  0
証明
Theorem of the Alternative for Linear Inequalitiesによって、
(I)が解もつのは、(II)が解をもたないときに限る。
m
 ua i 1
n
ij
 c j  0　for　j  1,2,..., n
n
 a v  a v' s  b   0　for　i  1,2,..., m
j 1
ij
j
ij
j 1
j
i
i
ui , si  0　for　i  1,2,..., m
( II ) v j , v' j  0　for　i  1,2,..., n
  0
m
n
n
 b u   c v   c y'
i 1
i i
j 1
j
j
j 1
j
j
0
証明
hj:= v’j-vj for j=1,2,…,n とすると、(II)より(II’)を得る。
 0
m
 u a  c 　for　j  1,2,..., n
i 1
j
i ij
ui  0 for　i  1,2,..., m
n
( II ' )  a h  b 　for　i  1,2,..., m
j 1
ij
j
h j  0 for　i  1,2,..., n
n
m
i
 b u   c h i 1
i i
j 1
j
j
証明
方針としては、
PとDが実行可能であると仮定し、
(I)が実行可能であることを示す。
もし、そうでなければ(II)が実行解をもつ。
場合分けを行う。
① τ> 0
② τ= 0 → subcase a と bに更に場合わけ。
(a) Σuibi < 0
(b) Σcjhj > 0
証明
① τ> 0 のとき。(II’)の解として、xとyを以下のようにおく。
xj 
1

1
h j for　j  1,2,..., n
yi  ui for　i  1,2,..., m

このx,yはそれぞれP,Dの実行可能解になっている。
しかし、この式と(II’)の一番下の式より、
m
n
 b y   c x i 1
i
i
j 1
j
j
しかし、これはWeak Duality Theoremに反する。
証明
② τ= 0 のとき。
subcase (a) Σuibi < 0
Dの実行解となるようなyをとってきて、
y’=y+λuを考える。このy’は全ての非負のλについて、
Dの実行解となっている。
しかし、目的関数が、以下のようになる。
m
min
m
 b y    b u
i 1
i
i
i 1
i i
これでは、λの上昇とともに、目的関数は際限なく減少する。
証明
② τ= 0 のとき。
subcase (ｂ) Σcjhj > 0
Pの実行解となるようなxをとってきて、
x’=x+λhを考える。このx’は全ての非負のλについて、
Pの実行解となっている。
しかし、目的関数が、以下のようになる。
n
n
j 1
j 1
max  c j x j    c j h j
これでは、λの上昇とともに、目的関数は際限なく上昇する。
証明
どちらのsubcaseもWeak Duality Theoremに反している。
これにより、①、②の両方の場合において矛盾を得た。
よって、PとDが実行可能であれば、
(I)は解をもたなければいけない。
次に、Pが実行不可能であることを仮定する。
→目標は、Dが実行不可能かunboundedかを示すこと。
ここでは、Dが実行可能を仮定して、unboundedを示す。
証明
Theorem of Alternative for Linear Inequalitiesより、
Pが実行不能だとすると、次のsystemが解をもつ。
m
 u a  0　for　j  1,2,..., n
i 1
i ij
ui  0 for　i  1,2,..., m
m
 u b  0　i 1
i i
この解のuとDに対する実行解yを用いると、
前述のsubcase(a)と同様の議論ができ、Dがunbounded。
証明
次に、Dが実行不可能であることを仮定する。
→目標は、Pが実行不可能かunboundedかを示すこと。
ここでは、Pが実行可能を仮定して、unboundedを示す。
証明
Theorem of Alternative for Linear Inequalitiesより、
Dが実行不能だとすると、次のsystemが解をもつ。
n
 a h  0　for　i  1,2,..., m
j 1
ij
j
n
 c h  0　j 1
j
j
この解のhとPに対する実行解xを用いると、
前述のsubcase(b)と同様の議論ができ、Pがunbounded。
complementary
Pの実行解xとDの実行解yがcomplementaryであるとは、
以下の条件を満たすときである。
n


  0　for　i  1,2,..., m
yi  bi   aij x j 
j 1


Weak Complementary-Slackness
Theorem
もし、実行解xと実行解yがcomplementaryなら、
そのとき、xとyは最適解である。
証明
xとyを実行可能解と仮定すると、以下の式が得られる。
n
n m
m
n

 m
yi  bi   aij x j    yi bi   yi aij x j   yi bi   c j x j

i 1
j 1
j 1 i 1
i 1
j 1

 i 1
m
xとyがcomplementaryであれば、最左辺が0になる。よって、
m
n
i 1
j 1
0   yi bi   c j x j
Weak Duality Theoremより、xとyは最適解である。
Strong Complementary-Slackness
Theorem
もし、xとyがPとDに対する最適解なら、
そのとき、xとyはcomplementaryである。
証明
xとyを最適解と仮定すると、Strong Duality Theoremより、
以下の式の最右辺が0
n
n m
m
n

 m
yi  bi   aij x j    yi bi   yi aij x j   yi bi   c j x j

i 1
j 1
j 1 i 1
i 1
j 1

 i 1
m
よって、
n


yi  bi   aij x j   0

i 1
j 1


m
また、実行可能性より、
n


yi  bi   aij x j   0
j 1


よって、xとyはcomplementaryでなければならない。
• k = 1, 2, …, pに対して、以下を定義。
n


n
k
k
Pk :  x  R :  aij x j  bi , for　i  1,2,..., m(k )
j 1


次に、以下のlinear programを考える。
p
n

( P) max  c j x j : x   Pk 
k 1
 j 1

次の式を仮定する。
p
c j   c kj
k 1
このようなcの分割をcのweight splittingと呼ぶ。
k=1, 2,…, pに対して、以下のlinear programsを考える。
n k

( Pk ) max  c j x j : x  Pk 
 j 1

Proposition
(Sufficiency of weight splitting)
cのweight splittingが与えられ、
もしxが全てのPkに対して、最適解であるならば、
そのとき、xはPに対しても最適解である。
証明
xが全てのPkに対して、最適解であることを仮定する。
ykをPkの双対式Dkの最適解とする。
m(k)
min

i 1
yik bik ( Dk ) subject　to
m(k )

i 1
yik aijk  c kj for　i  1,2,..., n
yik  0 for　i  1,2,..., m( k )
証明
今、xはPに対しての実行解である。
cのweight splittingを持っているので、
y=( y1, y2,…, yp)がPの双対式Dの実行解になっている。
p
min
m(k)
k k
y
  i bi k 1 i 1
( Dk ) subject　to
p
m( k )
  yik aijk  c j for　i  1,2,..., n
k 1 i 1
yik  0 for　k  1,2,..., p, i  1,2,..., m( k )
証明
Pkに対する、xの最適性とDkに対するykの最適性より、
Strong Duality Theoremより、以下の式が成り立つ。
n
c
j 1
k
j
xj 
m( k )
y b
i 1
k k
i i
cのweight splittingを持っているので、
p m( k )
n
c x    y b
j 1
j
j
k 1 i 1
k k
i i
あとは、PとDに対する、Weak Duality Thoremより、
xがPの最適解であることが証明される。
Proposition
(Necessity of weight splitting)
xがPに対する最適解であるなら、
そのとき、xが全てのPkに対して最適解と
なるような、cのweight splittingが存在する。
0.3 Basic Solutions and the Primal
Simplex Method
n
max
c
j1
j
xj
( P ' ) subject　to :
m
a
i 1
ij
x j  bi for　i  1,2,..., m
x j  0 for　j  1,2,..., n
行列Aをm×n行列で、rank(A)=mとする。
{1, 2,…, n}を基底   ( 1 ,  2 ,...,  m )
と非基底   (1 ,2 ,...,nm ) にわける。
x*1  x*2      x*nm  0
としたときのBasic solution をx* とする。
*
*
*
x1 , x2 ,..., xm
を以下の残りのsystemの唯一の解とする。
m
 a  x
j 1
i
j
j
 bi for　i  1,2,..., m
よって、解x*は、以下のようにかける。
x  0
*
1
x  A b
*
*
もし x
0
なら、解x*はPで実行可能である。
x*がPに対して、実行可能なら、基底βをprimal feasible,
x*がPに対して、最適解なら、基底βをprimal optimal
という。
(P’)の双対は以下の式になる。
m
min
yb
i 1
i
i
( D ' ) subject　to :
m
ya
i 1
i
ij
 c j for　i  1,2,..., m
基底βに関する双対式のbasic solutionは
以下の式の唯一解 y1* , y2* ,..., ym* である。
m
 y a
j 1
i i
j
 c j for　j  1,2,..., n
行列の性質より、y*は以下のようにかける。
y*  c A1
x*
のthe reduced costを以下の式で定義する。
m
c j : c j   yi*ai j
i 1
もし、 c j
0
であれば、y*は双対式D’の実行解となる。
y*がD’に対して、実行可能なら、基底βをdual feasible,
y*がD’に対して、最適解なら、基底βをdual optimal
という。
1
A : A A
Weak Optimal-Basis Theorem
もし、基底βがprimal feasibleかつdual feasibleなら、
そのとき、βはoptimalである。
証明
x*とy*をβに関してbasic solutionとする。
1
cx  c x  c A b  y b
*
*
*
もし、x*とy*がfeasibleなら、Weak Duality Theoremより、
x*とy*はoptimalである。
Symplex Method
Simplex table
x0 x　rhs

1　 c　0
0 A　b
以下の式を表にしたもの。
n
x0   c j x j  0
j 1
n
 aij x j  bi for　i  1,2,..., m
j 1
Symplex Method
basic variableに対して、解くと、以下のSimplex tableを得る。
x0 x x rhs

1　0  c  c A1 A c A1b
0 I　A1 A A1b
書き換えると、
x0 x x rhs

1　0  c c x *
0 x*
I　A Simplex method
• あとは、βがprimal feasibleかつdual feasibleであることだ
けを調べれば、βがoptimal basisかどうかを判定できる。
Symplex method
• まず、基底βからはじめる。
• c  0 であるような、 j を１つ選ぶ。
j
•
*


 x k

i : arg min 
: a k , j  0


 a k , j

を計算する。
• 基底βのi番目の変数と非基底ηのj番目の変数を入れ替
え、新しい基底β’とη’をつくる。このとき、i番目の変数の
値は0として非基底に、j番目の変数の値を上記の値とし
て、基底に入れる。
• それに伴い、目的関数と基底の変数の値を更新する。
Strong Optimal-Basis Theorem
もし、P’とD’が実行可能であれば、そのとき、
Primal feasible かつ dual feasibleである基底βをもつ。
Theorem(Feasible basic solutions
and extreme points)
P’の実行可能基本解の集合は、凸多面体Ｐ’の端点の
集合と等しい。
証明
XがPに対する最適解と仮定する。
明らかにxは全てのPkの実行可能解となっている。
y=( y1, y2,…, yp)をDの最適解とする。
ここで、
c 
k
j
m(k )
y b
i 1
k k
i i
とおく。
ただし、これがcのweight splittingと言っているわけでは
ない。
証明
しかし、 y=( y1, y2,…, yp)がDに対する実行可能解なので、
p
p m( k )
c    y b
k 1
k
j
k 1 i 1
k k
i i
 cj
より、cの「weight covering」にはなっている。
証明
PkとDkにWeak Duality Theoremを用いると、
n
c
j 1
k
j
xj 
m(k )
y b
i 1
k k
i i
これをk=1,…,pまで加えて、x≧0とΣck ≧cを考慮すると、
p
n
 c x   c
j 1
j
j
p m( k )
n
k 1 j 1
k
j
xj    y b
k 1 i 1
k k
i i
証明
PとDにStrong Duality Theoremを用いると、
p m( k )
n
c x    y b
j 1
j
j
k 1 i 1
k k
i i
上式と前述の式より、
n
c
j 1
k
j
xj 
m( k )
y b
i 1
k k
i i
よって、PkとDkに対するWeak Duality Theoremにより、
xはPkに対する最適解で、ykはDkに対する最適解となる。
証明
今、いくつかのjに対して、以下の式を仮定する。
p
c
k 1
k
j
 cj
そのとき、それらのjに対して、
p
k k
y
 j aij  c j
k 1
証明
PkとDkに対して、Weak Complementary-Slackness Theorem
を適用すると、
xj  0
そのとき、それらのjに対して、
p
k k
y
 j aij  c j
k 1

Download Report