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

Recent Development in Mathematical Programming from the Viewpoint of Interior-Point Methods

小島 政和 （東工大・情報理工） Masakazu Kojima, Tokyo Institute of Technology FAX: 03-5734-2752 E-mail: kojima@is.titech.ac.jp

日本学術会議５０周年記念

第４８回理論応用力学講演会

講演論文集掲載（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 はじめに

内点法 (Interior-Point Method) の歴史をいつまで遡ればよいかはさほど明確ではないが，現在の内点法（[5, 9] 等）の隆盛の直接のきっかけとなったのは 1984 年に発表された線形計画問題の新解法，いわゆる Karmarkar 法 [1] である． Karmarkar 法が数理計画分野全体に与えた影響は非常に大きく，この 15 年間に数理計画は著しい進歩を遂げている．特に，線形計画 (Linear Programming) の分野では，内点法は従来の単体法（Simplex Method）では解けないような超大規模な問題を高速に解く計算手法として，その地位を確立している．本講演では，内点法の数理計画分野全体の中での位置づけを通して数理計画全体の最近の発展を概観する．

2 線形計画問題，単体法，双対問題

\underline{線形計画問題}(Linear Program) は「\underline{線形不等式条件}

∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{i} (1 ≤ ∀i ≤ m)  (1)

を満たす x = (x_{1}, x_{2}, …, x_{n}) ∈ R^{n} で，線形の\underline{目}\underline{的}\underline{関数} ∑_{j=1}^{n} c_{j}x_{j} を最小（または，最大）にする x = x^{∗} を求めよ」という問題である．ここで， R^{n} は n-次元ベクト \begin{matrix}ル (Euclid ) 空間を表す．また， a_{ij}, b_{i}, c_{j} はすべて実数 \\ で，線形計画問題のデータとして与えられる．条件 (1) を \\ 満たす x を\underline{実行可能解}，その集まりを P で表す． P は \\ n 次元ベクトル空間 R^{n} 内で，有限個の超平面 \\ ∑_{j=1}^{n} a_{ij}x_{j} = b_{i} (1 ≤ ∀i ≤ m) \\ で囲まれた領域（有界とは限らない）になる． P を \\ \underline{実行可能多面体}と呼ぶ．線形計画問題を \\ \begin{matrix}目的： & ∑_{j=1}^{n} c_{j}x_{j} → 最小化 \\ 条件： & x = (x_{1}, x_{2}, …, x_{n}) ∈ P \end{matrix} \} & (2) \\ と記述する． \\ 線形計画問題 (2) の目的関数は線形であるから，その \\ 等高面 \{x : ∑_{j=1}^{n} c_{j}x_{j} = 定数\} は n 次元ベクトル空間 \\ R^{n} 内の超平面（n = 2 の場合には，等高線）となる．等 \\ 高面を目的関数 ∑_{j=1}^{n} c_{j}x_{j} の値が小さくなる方向に，実 \\ 行可能多面体 P の境界と接するまでずらすと最小解が得 \\ られる．一般には，最小解の集合が得られるが，その中 \\ に必ず頂点が含まれる．このことより，最小解の候補を \\ P の有限個の頂点に絞ることができる． \\ 単体法は，線形計画問題の上述の特徴を巧妙に利用し \\ ている．１つの頂点から出発して隣接する頂点をたどっ \\ て，目的関数の値を小さくしながら，最小解に到達する \end{matrix}

図 1: 単体法と内点法（概念図）

（図 1 参照）．したがって，単体法の反復回数は最小解に到達するまでに生成される頂点の個数に一致し，計算効率もそれに比例する．一方，線形計画問題のサイズ＝ “ 変数の個数 n と線形不等式の個数 m” の増加にともなって，生成される可能性のある P の頂点の個数は爆発的に増加することが知られている．実社会から生ずる線形計画問題を解いた経験からは，単体法の反復回数は実行可能多面体 P を記述するのに用いられる線形不等式の個数 m の数倍程度であるといわれているが，線形計画問題のサイズが大きくなると単体法の計算効率が著しく落ちる可能性を示唆している．

次節で必要となる双対問題，双対定理について簡単に説明しておく．線形計画問題 (2) の\underline{双対問題}は元の問題 (2) を定義するデータ c_{j}, a_{ij}, b_{i} と同じデータを使って定義されるが，その使い方は異なる．大ざっぱには，元の問題 (2) の目的関数の最小化，線形目的関数の係数 c_{j}，線形不等式条件の係数 a_{ij}，線形不等式条件の定数項 b_{i} が， “転置” されて，双対問題の目的関数の最大化，線形不等式条件の定数項 c_{j}，線形不等式条件の係数 a_{ji} （ij が ji になっていることに注意），線形目的関数の係数 b_{i} として使われる．ここでは，双対問題を抽象的に以下のように書くことにする．

\begin{matrix}目的： & ∑_{i=1}^{m} b_{i}y_{i} → 最大化 \\ 条件： & y = (y_{1}, y_{2}, …, y_{m}) ∈ D \end{matrix} \}  (3)

双対問題 (3) と対比させて，元の問題 (2) を\underline{主問題}と呼ぶ．主問題 (2) と双対問題 (3) の間には，\underline{双対定理}と呼ばれる以下の関係が成り立つ．

∑_{i=1} b_{i}y_{i} ≤ 双対問題の最大値
= 主問題の最小値
≤ ∑_{j=1}^{n} c_{j}x_{j} (∀x ∈ P, ∀y ∈ D)

（図 2 参照）．

図 2: 中心パスと主双対内点法（概念図）

3 主双対内点法

単体法の特徴は実行可能多面体 P の境界に属する頂点をたどって最小解の到達することにある．この特徴は単体法が有限回の反復で最小解に到達することを保証している．しかしながら，この特徴ゆえに，「変数の個数 n と線形不等式条件の個数 m の増加にともなって頂点が爆発的に増える」等の実行可能多面体 P の境界の組合せ的複雑さとまともに対峙することになる．内点法は，実行可能多面体 P の内部を通って最小解に近づくことで，実行可能多面体 P の境界の組合せ的複雑さを回避している（図 1 参照）．ここでは， Karmarkar 法 [1] 以後に提案された内点法の中で，理論的に最も整備され，かつ，実用的にも最もよく発展した主双対内点法を紹介する．

主双対内点法は， Renegar による中心パス追跡法に上述した双対定理を組み入れ，主問題と双対問題の空間で同時に中心パスを追跡する方法であるといえる．もう少し詳しく説明するために，主問題 (2) と双対問題 (3) を合わせた主双対問題を導入する．

\begin{matrix}目的： & ∑_{j=1}^{n} c_{j}x_{j} − ∑_{i=1}^{m} b_{i}y_{i} → 最小化 \\ 条件： & x ∈ P, y ∈ D \end{matrix} \} (4)

双対定理により，この問題の最小値は 0 である．主双対問題 (4) の中心パスは， t > 0 をパラメータとする多面体

G(t) ≡ {(x, y) ∈ P × D : ∑_{j=1}^{n} c_{j}x_{j} − ∑_{i=1}^{m} b_{i}y_{i} ≤ t}

の解析的中心 (x(t), y(t)) （G(t) の内点集合上で定義された\underline{対数罰金関数}の最小点）からなる滑らかな曲線 {(x(t), y(t)) : t > 0} として定義される．中心パス {(x(t), y(t)) : t > 0} は主双対問題の最適解 (x^{∗}, y^{∗}) に収束する（図 2 参照）．主双対内点法ではこのように定義された中心パスを， Newton 法を用いて，数値的に追跡している．内点法，主双対内点法に関してより詳しくは， [5, 9] 等を参照されたい．

\begin{matrix}図 3: 連続最適化に属する代表的な数理計画問題 \\ 図 4: 離散最適化に属する代表的な数理計画問題 \\ 4 一般の数理計画問題と内点法 \\ 一般の\underline{数理計画問題}は \\ \begin{matrix}目的： & f(x) → 最小化 \\ 条件： & x ∈ F ≡ \{x ∈ S : g(x) ≤ 0\} \end{matrix} \} & (5) \\ と書ける．ここで， S は n 次元ベクトル空間 R^{n} の部分 \\ 集合， f は R^{n} で定義された実数値関数， g は R^{n} から m \\ 次元ベクトル空間 R^{m} への関数である． S は対象とする \\ 数理計画問題を記述するのに用いられる\underline{基礎となる空間} \\ と考えればよい． \\ 基礎となる空間 S, \underline{実行可能領域} F を表現するのに \\ 使われる関数 g : R^{n} → R^{m}，および，\underline{目的関数} f に \\ 種々の条件を課した多くのクラスの数理計画問題が研究 \\ されている．数理計画問題は大きく\underline{連続最適化問題}と \\ \underline{離散最適化問題}に分けることができる． \\ 連続最適化問題では， \\ • S = R^{n} （より一般的には， S は R^{n} の開集合） \\ • 関数 g : R^{n} → R^{m} は連続（多くの場合，微分可能） \\ が仮定される．連続最適化に属する代表的な数理計画問 \\ 題のクラスとそれらの関係を示すと図 3 のようになる． \\ 離散最適化問題では， \end{matrix}^{• S は有限集合，または，離散的な集合．たとえば， ; S = \{x ∈ R^{n} : x_{j} = 0 または 1\} （有限集合）， ; S = あるグラフの部分グラフの集まり（有限集合）， ; S = \{x ∈ R^{n} : x_{j} = 自然数\} （離散無限集合）． ; が仮定される．関数 f, g に連続性（あるいは，微分可能 ; 性）のみを仮定する非線形離散最適化問題のクラスも考 ; えることができるが，そのような問題は非常に難しく，関 ; 数 f, g が線形（あるいは，高々２次）関数である場合に ; 限定することが多い．このように限定したとしても，離 ; 散最適化問題には広範な応用がある．離散最適化に属す ; る代表的な数理計画問題のクラスとそれらの関係を示す ; と図 4 のようになる． ; 個々の数理計画問題は，それが定式化された元の（現 ; 実）問題と結びつけた名前で呼ばれることも多い．例え ; ば，最小費用流問題，最大流問題，行商人問題，グラフ ; 分割問題等である．また，上記の数理計画問題に関する ; 分類は厳密ではなく，連続最適化と離散最適化の両方の ; 特徴を共有する問題（たとえば，施設配置問題，線形混 ; 合整数計画問題）や，それらからはみ出た数理計画問題 ; も存在する． ; 単体法，内点法を始めとして，数理計画法の多くのア ; ルゴリズムは局所的な改善（目的関数値が減少する，実 ; 行可能領域に近づく，あるいは，その両方）を繰り返す ; 反復法である．こののような局所的なアルゴリズムでは ; \underline{局所的に最小な解}を求めるのが精一杯である．局所的に ; 最小な解が常に大域的に最小な解であることがあらかじ ; め保証されている問題（たとえば，線形計画問題）では ; 局所的なアルゴリズムで大域的に最小な解まで到達でき ; る．そのような問題は比較的易しい数理計画問題といっ ; てよい．この “局所的に最小な解 ⟹ 大域的に最小な解” ; という性質は実行可能領域および目的関数の “凸性” と強 ; く結びついている．凸性は連続最適化の分野で使われて ; きたが，近年， “離散凸” なる概念が導入され，離散最適 ; 化問題の解き易さと結びつけて研究されている． [6] 等参 ; 照．これまでに発展した内点法が直接適用できるのは凸 ; 性を満たす連続最適化問題である凸計画問題（[7] 参照） ; の範囲までである． ; 凸性を持たない数理計画問題（たとえば，非凸２次計 ; 画問題，多くの組合せ最適化問題等）での内点法の役割 ; についてふれておこう．そのような問題を対象とするア ; ルゴリズムでは， ; (i) より小さい目的関数値 f(x) を達成する実行可能解 ; x ∈ F を生成する仕組み（[4] 等） ; に加えて， ; (ii) 未知の大域的最小値を見積もる仕組み ; を盛り込むことが望ましい．反復の途中でそれまでに (i) ; により得られている最良の実行可能解での目的関数値と，}

\begin{matrix}(ii) により見積もられた真の大域的最小値との差が十分 \\ 小さければ，その解を近似大域的最小解として安心して \\ 使える． (ii) のために\underline{緩和}がしばしば使われる．集合 Ŝ \\ が，条件 F ⊂ F̂ を満たすと仮定し，新たな数理計画問題 \\ 目的： f̂(x) → 最小化；条件： x ∈ F̂ & (6) \\ を導入する．元の問題 (5) と比較すると，問題 (6) の実行可 \\ 能領域 F̂ は広い．したがって， (5) の未知の大域的最小値を \\ f^{∗}， (6) の大域的最小値を f̂^{∗} とすると， f^{∗} ≥ f̂^{∗} である \\ ことが分かる．問題 (6) を\underline{緩和問題}と呼ぶ．反復の途中で \\ 求まった問題 (5) の最良解を x̂ とすると， f(x̂) ≥ f^{∗} ≥ f̂^{∗} \\ が成り立つ．したがって， f(x̂) − f̂^{∗} が十分小さいか，許 \\ 容範囲にあれば， x̂ を近似大域的最小解として安心して \\ 使える．緩和問題は \\ • その大域的最小値 f̂^{∗} が元の問題の大域的最小値 f^{∗} \\ に近いこと， \\ • 簡単に解けること \\ が望ましいが，この２つは矛盾する場合が多い．緩和問 \\ 題は，離散最適化問題に対する汎用的な手法である分枝 \\ 限定法と組み合わされて使われている． \\ 従来から，離散最適化問題を線形計画問題で緩和し，緩 \\ 和された問題に単体法を適用する手法がよく用いられて \\ いるが，より大規模な緩和問題に対しては内点法が適用 \\ され始めている．さらに，離散最適化および非凸２次計 \\ 画問題を，次節で紹介する半正定値計画問題を用いて，よ \\ り強力に緩和する研究（[3] 等）も盛んに行われている． \\ 一方では半正定値計画問題を解く内点法のソフトウエア \\ も整いつつあるので，今後，内点法が凸性を持たない数 \\ 理計画問題にもますます強く関わっていくことが予想さ \\ れる． \\ 5 半正定値計画問題 — 最新の話題 \\ 半正定値計画問題は，線形計画問題 (2) を対称行列の \\ 空間に拡張した問題といえる． \\ \begin{matrix}目的： & ∑_{j=1}^{n} c_{j}x_{j} → 最小化 \\ 条件： & ∑_{j=1}^{n} A_{j}x_{j} ⪯ B \end{matrix} \} & (7) \\ ただし， \\ A_{i} ∈ S^{n} (1 ≤ ∀j ≤ n), B : m × m 定数対称行列， \\ c_{j} ∈ R (1 ≤ ∀j ≤ n) : 実定数， \\ V ⪯ U ⟺ m × m 対称行列U − V が半正定値． \\ 線形計画問題 (2) における実数に対する不等式 ≤ を，対 \\ 称行列に対する “不等式 ⪯” に置き換えた問題と考える \\ とよい． \end{matrix}

半正定値計画問題は凸計画問題の一種で，線形計画問題および凸２次計画問題よりも数学的な記述能力は高く，これらの問題をその特殊な場合として含む．特に，対称行列の固有値に関する条件を含む問題を半正定値計画問題に定式化できるという特徴を持つ．また，線形計画問題に対する双対定理および主双対内点法が非常に美しい形で拡張されている．上述した半正定値計画問題を用いた離散最適化および非凸２次計画問題の緩和の他，システムと制御分野，建造物の構造最適化分野で研究されている．より詳しくは， [2, 3, 8] を参照されたい．

6 おわりに

Internet を通しても，数理計画法，内点法に関する最新の様々な情報が得られる．内点法に関しては， S. Wright が管理・運営する以下のホームページにアクセスし，そこから内点法の研究者のホームページをたどるとよい．

http://www.mcs.anl.gov/home/otc/InteriorPoint/

また，数理計画法全般に関しては，東京大学の松井助教授の管理・運営するホームページ

http://misojiro.misojiro.t.u-tokyo.ac.jp / t̃omomi/opt-codeE.html

を覗くとよい．

この原稿は第４８回理論応用力学講演会（１９９９年１月２５日（月）〜２７日（水））のパネルディスカッション『数値解析の新手法 —９０年代の発展 —』での講演のために書かれたものである．講演に招待して下さった東京大学大学院数理科学研究科山田道夫先生に感謝いたします．

参考文献

[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．

[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.