線形計画問題に対する平滑化ニュートン法を用いた解法
田村研究室 内山 寛之
1. はじめに
A を m×n 行列，c を n 次元ベクトル，x を n 次元ベクトル,b を m 次元ベクトルとする．このとき，次の標準形の線形計画問題(LP)を考える．
min c'x
s.t. Ax=b
x≧0
LP に対する解法としては，単体法や内点法などがある．本研究では，平滑化ニュートン法 [1] を用いて LP を解くための方法を提案する．
2. 平滑化ニュートン法の適用
LP(1)の Karush-Kuhn-Tucker 条件は，
Ax-b=0
c-A'λ≧0
x≧0
x'(c-A'λ)=0
とかける．これは区分的に連続的微分可能な方程式
x-max(0, x+A'λ-c)
Ax-b=0
と等価である．ただし，max(*,*)は各要素毎にとる．ここで，max オペレータに対する近似関数φ を考える．ただし，φ は μ>0 のとき連続的に微分可能で
| max(0, a)-φ(μ, a) | ≦ 定数 × μ
を満たすものとする．φ の例として
φ(μ, a)=a+μlog(1+exp(-a/μ))
などがある．また，κ を以下の(1)〜(3)を満たす関数とする．
- μ>0 において連続的に微分可能であり，任意の μ>0 に対して κ'(\mu)>0
- κ(μ)=0 <=> μ=0
- 任意の μ>0 に対して 0 < κ(μ)/κ'(μ) < μ
κ の例として，exp(μ)-1 などがある．このφ，κ を用いて写像 H を
H(μ,x,λ)= ( κ(μ), x-φ(0, x+A'λ-c, Ax-b)'
とおくと，F(x,λ)=0 と H(μ,x,λ)=0 は等価である．この $H$ に対し [1] で提案された平滑化ニュートン法を適用する．ここでは，そのアルゴリズムは省略する．
3. 計算結果
平滑化ニュートン法を用いて LP(1) を解いた結果を示す．全てのプログラムは，C言語で作成し Sun Ultra30 上で倍精度で実行した．
初期点は，(μ,x,λ)=(1,0 ・・・ 0)' とした．以下に結果を示す．
|
m |
m |
ITE |
CPU(秒) |
| Example 1 |
7 |
15 |
7 |
0.01 |
| Example 2 |
10 |
30 |
9 |
0.08 |
| Example 3 |
13 |
48 |
8 |
0.16 |
| Example 4 |
20 |
112 |
8 |
1.39 |
4. まとめ
平滑化ニュートン法を用いた線形計画問題の解法を提案した．今後は，より大規模な問題に対応するプログラムを作成する．さらに，平滑化ニュートン法を用いた非線形計画問題に対する解法を提案していく．
参考文献
[1] 田地宏一，宮本基博，高橋 豊，``滑らかでない方程式に対するスムージングニュートン法と相補性問題への応用,'' 最適化:モデリングとアルゴリズム 12,pp.191-208,1998 年 11 月，統計数理研究所共同研究リポート92