数理計画法の最近の発展 — 内点法を中心にして

数理計画法の最近の発展 — 内点法を中心にして —
Recent Development in Mathematical Programming
from the Viewpoint of Interior-Point Methods
小島 政和 （東工大・情報理工）
Masakazu Kojima, Tokyo Institute of Technology
FAX: 03-5734-2752
E-mail: [email protected]
日本学術会議５０周年記念
第４８回理論応用力学講演会
講演論文集掲載（pp 306-309）
Since Karmarkar proposed a new interior-point method for linear programs in 1984,
the interior-point method has made dramatic progress in these fifteen years. Competing with the traditional simplex method, the interior-point method is now known as
the most powerful computational method for solving huge scale linear programs. In
the field of continuous optimization, the interior-point method has been successfully
extended to convex quadratic programs, semidefinite programs, and more general convex programs, while, in the field of discrete optimization, the interior-point method
has bee playing an important role in terms of the semidefinite programming relaxation of 0-1 integer and nonconvex quadratic programs. The purpose of this talk is to
present an overview of recent development of mathematical programming emphasizing
the interior-point method.
1
ル (Euclid ) 空間を表す．また，aij , bi , cj はすべて実数
はじめに
で，線形計画問題のデータとして与えられる．条件 (1) を
内点法 (Interior-Point Method) の歴史をいつまで遡れ
ばよいかはさほど明確ではないが，現在の内点法（[5, 9]
満たす x を 実行可能解，その集まりを P で表す．P は
n 次元ベクトル空間 Rn 内で，有限個の超平面
等）の隆盛の直接のきっかけとなったのは 1984 年に発表
n
X
された線形計画問題の新解法，いわゆる Karmarkar 法 [1]
である．Karmarkar 法が数理計画分野全体に与えた影響
aij xj = bi (1 ≤ ∀i ≤ m)
j=1
は非常に大きく，この 15 年間に数理計画は著しい進歩を
で囲まれた領域（有界とは限らない）になる．P を
遂げている．特に，線形計画 (Linear Programming) の分
実行可能多面体 と呼ぶ．線形計画問題を
野では，内点法は従来の単体法（Simplex Method）では
解けないような超大規模な問題を高速に解く計算手法と
して，その地位を確立している．本講演では，内点法の
Pn
j=1 cj xj → 最小化
条件： x = (x1 , x2 , . . . , xn ) ∈ P
目的：
)
(2)
数理計画分野全体の中での位置づけを通して数理計画全
と記述する．
体の最近の発展を概観する．
線形計画問題 (2) の目的関数は線形であるから，その
Pn
等高面 {x : j=1 cj xj = 定数 } は n 次元ベクトル空間
2
線形計画問題，単体法，双対問題
線形計画問題(Linear Program) は「線形不等式条件
n
X
Rn 内の超平面（n = 2 の場合には ，等高線）となる．等
Pn
高面を目的関数 j=1 cj xj の値が小さくなる方向に，実
行可能多面体 P の境界と接するまでずらすと最小解が得
られる．一般には，最小解の集合が得られるが，その中
aij xj ≤ bi (1 ≤ ∀i ≤ m)
(1)
j=1
n
を満たす x = (x1 , x2 , . . . , xn ) ∈ R で，線形の 目的関数
Pn
∗
j=1 cj xj を最小（または，最大）にする x = x を求
めよ」という問題である．ここで，Rn は n-次元ベクト
に必ず頂点が含まれる．このことより，最小解の候補を
P の有限個の頂点に絞ることができる．
単体法は，線形計画問題の上述の特徴を巧妙に利用し
ている．１つの頂点から出発して隣接する頂点をたどっ
て，目的関数の値を小さくしながら，最小解に到達する
x2
x3
x1
x4
x0
P:
x1
x2
x0
x2
P:
!#"$&%
図 1: 単体法と内点法（概念図）
（図 1 参照）．したがって，単体法の反復回数は最小解に
図 2: 中心パスと主双対内点法（概念図）
到達するまでに生成される頂点の個数に一致し，計算効
率もそれに比例する．一方，線形計画問題のサイズ＝ “
変数の個数 n と線形不等式の個数 m” の増加にともなっ
て，生成される可能性のある P の頂点の個数は爆発的に
3
主双対内点法
増加することが知られている．実社会から生ずる線形計
単体法の特徴は実行可能多面体 P の境界に属する頂点
画問題を解いた経験からは，単体法の反復回数は実行可
をたどって最小解の到達することにある．この特徴は単
能多面体 P を記述するのに用いられる線形不等式の個数
体法が有限回の反復で最小解に到達することを保証して
m の数倍程度であるといわれているが，線形計画問題の
サイズが大きくなると単体法の計算効率が著しく落ちる
可能性を示唆している．
いる．しかしながら，この特徴ゆえに，
「変数の個数 n と
次節で必要となる双対問題，双対定理について簡単に
説明しておく．線形計画問題 (2) の 双対問題 は元の問題
(2) を定義するデータ cj , aij , bi と同じデータを使って
定義されるが，その使い方は異なる．大ざっぱには，元
の問題 (2) の目的関数の最小化，線形目的関数の係数 cj ，
線形不等式条件の係数 aij ，線形不等式条件の定数項 bi
が，“転置” されて，双対問題の目的関数の最大化，線形
不等式条件の定数項 cj ，線形不等式条件の係数 aji （ij
が ji になっていることに注意），線形目的関数の係数 bi
として使われる．ここでは，双対問題を抽象的に以下の
ように書くことにする．
Pm
→ 最大化
条件： y = (y1 , y2 , . . . , ym ) ∈ D
目的：
i=1 bi yi
)
(3)
線形不等式条件の個数 m の増加にともなって頂点が爆
発的に増える」等の実行可能多面体 P の境界の組合せ的
複雑さとまともに対峙することになる．内点法は，実行
可能多面体 P の内部を通って最小解に近づくことで，実
行可能多面体 P の境界の組合せ的複雑さを回避している
（図 1 参照）．ここでは，Karmarkar 法 [1] 以後に提案さ
れた内点法の中で，理論的に最も整備され，かつ，実用
的にも最もよく発展した主双対内点法を紹介する．
主双対内点法は，Renegar による中心パス追跡法に上
述した双対定理を組み入れ，主問題と双対問題の空間で
同時に中心パスを追跡する方法であるといえる．もう少
し詳しく説明するために，主問題 (2) と双対問題 (3) を
合わせた主双対問題を導入する．
)
Pm
Pn
目的：
c
x
−
b
y
→
最小化
i
i
j
j
j=1
i=1
条件： x ∈ P, y ∈ D
(4)
双対定理により，この問題の最小値は 0 である．主双対
問題 (4) の中心パスは，t > 0 をパラメータとする多面体
双対問題 (3) と対比させて，元の問題 (2) を 主問題 と呼
ぶ．主問題 (2) と双対問題 (3) の間には，双対定理 と呼
ばれる以下の関係が成り立つ．
X
G(t) ≡ {(x, y) ∈ P × D :
n
X
j=1
cj xj −
m
X
bi yi ≤ t}
i=1
の解析的中心 (x(t), y(t))（G(t) の内点集合上で定義
bi yi
≤
双対問題の最大値
=
主問題の最小値
n
X
cj xj (∀x ∈ P, ∀y ∈ D)
i=1
≤
j=1
された 対数罰金関数 の最小点）からなる滑らかな曲線
{(x(t), y(t)) : t > 0} として定義される．中心パス
{(x(t), y(t)) : t > 0} は主双対問題の最適解 (x∗ , y ∗ )
に収束する（図 2 参照）．主双対内点法ではこのように
定義された中心パスを，Newton 法を用いて，数値的に追
跡している．内点法，主双対内点法に関してより詳しく
（図 2 参照）．
は，[5, 9] 等を参照されたい．
• S
S
S
S
は有限集合，または，離散的な集合．たとえば，
= {x ∈ Rn : xj = 0 または 1}（有限集合），
= あるグラフの部分グラフの集まり（有限集合），
= {x ∈ Rn : xj = 自然数 }（離散無限集合）．
が仮定される．関数 f, g に連続性（あるいは，微分可能
性）のみを仮定する非線形離散最適化問題のクラスも考
えることができるが，そのような問題は非常に難しく，関
数 f, g が線形（あるいは，高々２次）関数である場合に
限定することが多い．このように限定したとしても，離
散最適化問題には広範な応用がある．離散最適化に属す
る代表的な数理計画問題のクラスとそれらの関係を示す
と図 4 のようになる．
図 3: 連続最適化に属する代表的な数理計画問題
個々の数理計画問題は，それが定式化された元の（現
実）問題と結びつけた名前で呼ばれることも多い．例え
ば，最小費用流問題，最大流問題，行商人問題，グラフ
分割問題等である．また，上記の数理計画問題に関する
分類は厳密ではなく，連続最適化と離散最適化の両方の
特徴を共有する問題（たとえば，施設配置問題，線形混
合整数計画問題）や，それらからはみ出た数理計画問題
も存在する．
単体法，内点法を始めとして，数理計画法の多くのア
ルゴリズムは局所的な改善（目的関数値が減少する，実
行可能領域に近づく，あるいは，その両方）を繰り返す
図 4: 離散最適化に属する代表的な数理計画問題
反復法である．こののような局所的なアルゴリズムでは
局所的に最小な解 を求めるのが精一杯である．局所的に
4
最小な解が常に大域的に最小な解であることがあらかじ
一般の数理計画問題と内点法
め保証されている問題（たとえば，線形計画問題）では
局所的なアルゴリズムで大域的に最小な解まで到達でき
一般の 数理計画問題 は
目的： f (x) → 最小化
る．そのような問題は比較的易しい数理計画問題といっ
)
条件： x ∈ F ≡ {x ∈ S : g(x) ≤ 0}
(5)
と書ける．ここで，S は n 次元ベクトル空間 Rn の部分
集合，f は Rn で定義された実数値関数，g は Rn から m
次元ベクトル空間 Rm への関数である．S は対象とする
数理計画問題を記述するのに用いられる 基礎となる空間
と考えればよい．
基礎となる空間 S, 実行可能領域 F を表現するのに
使われる関数 g : Rn → Rm ，および，目的関数 f に
種々の条件を課した多くのクラスの数理計画問題が研究
されている．数理計画問題は大きく 連続最適化問題 と
離散最適化問題 に分けることができる．
連続最適化問題では，
• S = Rn （より一般的には，S は Rn の開集合）
• 関数 g : Rn → Rm は連続（多くの場合，微分可能）
が仮定される．連続最適化に属する代表的な数理計画問
題のクラスとそれらの関係を示すと図 3 のようになる．
離散最適化問題では，
てよい．この “局所的に最小な解 =⇒ 大域的に最小な解”
という性質は実行可能領域および目的関数の “凸性” と強
く結びついている．凸性は連続最適化の分野で使われて
きたが，近年，“離散凸” なる概念が導入され，離散最適
化問題の解き易さと結びつけて研究されている．[6] 等参
照．これまでに発展した内点法が直接適用できるのは凸
性を満たす連続最適化問題である凸計画問題（[7] 参照）
の範囲までである．
凸性を持たない数理計画問題（たとえば，非凸２次計
画問題，多くの組合せ最適化問題等）での内点法の役割
についてふれておこう．そのような問題を対象とするア
ルゴリズムでは，
(i) より小さい目的関数値 f (x) を達成する実行可能解
x ∈ F を生成する仕組み（[4] 等）
に加えて，
(ii) 未知の大域的最小値を見積もる仕組み
を盛り込むことが望ましい．反復の途中でそれまでに (i)
により得られている最良の実行可能解での目的関数値と，
(ii) により見積もられた真の大域的最小値との差が十分
小さければ，その解を近似大域的最小解として安心して
使える．(ii) のために 緩和 がしばしば使われる．集合 Ŝ
題および凸２次計画問題よりも数学的な記述能力は高く，
が，条件 F ⊂ F̂ を満たすと仮定し，新たな数理計画問題
行列の固有値に関する条件を含む問題を半正定値計画問
目的： fˆ(x) → 最小化； 条件： x ∈ F̂
(6)
を導入する．元の問題 (5) と比較すると，問題 (6) の実行可
能領域 F̂ は広い．したがって，(5) の未知の大域的最小値を
f ∗ ，(6) の大域的最小値を fˆ∗ とすると，f ∗ ≥ fˆ∗ である
ことが分かる．問題 (6) を 緩和問題 と呼ぶ．反復の途中で
求まった問題 (5) の最良解を x̂ とすると，f (x̂) ≥ f ∗ ≥ fˆ∗
が成り立つ．したがって，f (x̂) − fˆ∗ が十分小さいか，許
容範囲にあれば，x̂ を近似大域的最小解として安心して
使える．緩和問題は
• その大域的最小値 fˆ∗ が元の問題の大域的最小値 f ∗
に近いこと，
• 簡単に解けること
半正定値計画問題は凸計画問題の一種で，線形計画問
これらの問題をその特殊な場合として含む．特に，対称
題に定式化できるという特徴を持つ．また，線形計画問
題に対する双対定理および主双対内点法が非常に美しい
形で拡張されている．上述した半正定値計画問題を用い
た離散最適化および非凸２次計画問題の緩和の他，シス
テムと制御分野，建造物の構造最適化分野で研究されて
いる．より詳しくは，[2, 3, 8] を参照されたい．
6
おわりに
Internet を通しても，数理計画法，内点法に関する最新
の様々な情報が得られる．内点法に関しては，S. Wright
が管理・運営する以下のホームページにアクセスし，そ
こから内点法の研究者のホームページをたどるとよい．
http://www.mcs.anl.gov/home/otc/InteriorPoint/
が望ましいが，この２つは矛盾する場合が多い．緩和問
また，数理計画法全般に関しては，東京大学の松井助教
題は，離散最適化問題に対する汎用的な手法である分枝
授の管理・運営するホームページ
限定法と組み合わされて使われている．
従来から，離散最適化問題を線形計画問題で緩和し，緩
http://misojiro.misojiro.t.u-tokyo.ac.jp
/˜tomomi/opt-codeE.html
和された問題に単体法を適用する手法がよく用いられて
いるが，より大規模な緩和問題に対しては内点法が適用
を覗くとよい．
され始めている．さらに，離散最適化および非凸２次計
この原稿は第４８回理論応用力学講演会（１９９９年
画問題を，次節で紹介する半正定値計画問題を用いて，よ
１月２５日（月）∼２７日（水））のパネルディスカッショ
り強力に緩和する研究（[3] 等）も盛んに行われている．
ン『数値解析の新手法 —９０年代の発展 —』での講演
一方では半正定値計画問題を解く内点法のソフトウエア
のために書かれたものである．講演に招待して下さった
も整いつつあるので，今後，内点法が凸性を持たない数
東京大学大学院数理科学研究科山田道夫先生に感謝いた
理計画問題にもますます強く関わっていくことが予想さ
します．
れる．
5
半正定値計画問題 — 最新の話題
半正定値計画問題は，線形計画問題 (2) を対称行列の
空間に拡張した問題といえる．
目的：
条件：
Pn
cj xj
Pj=1
n
j=1 Aj xj
→ 最小化
¹B
)
(7)
ただし，
Ai ∈ S n (1 ≤ ∀j ≤ n), B : m × m 定数対称行列，
cj ∈ R (1 ≤ ∀j ≤ n) : 実定数，
V ¹ U ⇐⇒ m × m 対称行列 U − V が半正定値．
参考文献
[1] N. Karmarkar, “A new polynomial-time algorithm
for linear programming,” Combinatorica 4 (1984)
373–395.
[2] 小島政和，“半正定値計画問題と内点法”，応用数理 6
(1996), pp.270-279.
[3] 小島政和，“半正定値計画とその組合せ最適化への応
用”，離散構造とアルゴリズム ５，近代科学社 (1998),
pp.203-249．
[4] 久保幹雄，“メタヒューリスティックス”，離散構造と
アルゴリズム ４，近代科学社 (1995), pp.171-221．
線形計画問題 (2) における実数に対する不等式 ≤ を，対
[5] 水野真治，“内点法（１）∼（４）
（連載）”，オペレー
称行列に対する “不等式 ¹” に置き換えた問題と考える
ションズ・リサーチ 35 (1995)，pp.321-326, pp.376-
とよい．
381, pp.437-442, pp.508-512.
[6] 室田一雄， “離散凸解析”， 離散構造とアルゴリズム
５, 近代科学社 (1998) 51–100．
[7] Y. Nesterov and A. Nemirovskii, Interior-Point
Polynomial Algorithms in Convex Programming
(SIAM, Philadelphia, 1994).
[8] L. Vandenberghe and S. Boyd, “Semidefinite Programming,” SIAM Review 38 (1996) 49–95.
[9] S. Wright, Primal-Dual Interior-Point Methods,
SIAM, Philadelphia, 1997.