修士論文 要旨

不確かな目的関数をもつ最適化問題に対する近似アルゴリズム
数理情報学専攻 48096228
指導教員

間野 暢
牧野 和久 准教授
n1 不確かな目的関数をもつ最適化問題

命題 1 (Kasperski and Zieliński [4]). X ⊂ {0, 1} ，W =∏ni=1 [w i , w i ]，w ≥ 0 とする．このとき，w̃ ={ ⊤}不確かさをもつ最適化問題を扱う枠組みは確率最(w + w) /2 として，x̃ を min w̃ x | x ∈ X の最適解

適化 [6] とロバスト最適化 [3] に大きく分けられ，どとする．すると，x̃ は最悪機会損失最小化問題の 2 近似

ちらの枠組みでも盛んに研究されている．本論文では解である．

min {f (x) | x ∈ X ⊆ R } のように記述される最適化n問題の目的関数 f が不確かである場合を扱う．特に目的関数が線形であるときは，ある自然数 n ∈ N とある
重みベクトル w ∈ Rn が存在して f (x) = w⊤ x となる．
このとき，この目的関数が不確かさをもつとは，重みベクトル w が不確かということである．ロバスト最適化の枠組みでは不確かなパラメータが属する集合を仮定する．そこで，不確かな目的関数 f が属する集合を F ，命題 2 (Aissi, Bazgan, and Vanderpooten [1]). X ⊂n{0, 1} ，W = {w1 , . . . , wk }，wi ≥ 0 (i ∈ {1, . . . , k})∑kと す る ．こ の と き ，w̃ =i=1 wi /k と し て ，x̃ を{ ⊤}min w̃ x | x ∈ X の最適解とする．すると，x̃ は最悪値最小化問題の k 近似解である．また，x̃ は最悪機会損失最小化問題の k 近似解である．
命題 1，2 は重みベクトル集合 W から代表点 w̃ を選{}

特に線形の目的関数の場合は不確かな重みベクトル w

び，その重み w̃ での最適化問題 min w̃⊤ x | x ∈ Xが属する集合を W とそれぞれ書くことにする．

最適解が近似解になっている，と主張している．そしこのような状況では実行可能解 x ∈ X を一つ決めのて，どちらの場合も近似解の構成に必要なのは不確かさ{}ても，目的関数 f が不確かなので目的関数値が一意にをもたない問題 min w̃ ⊤ x | x ∈ X

定まらない．そこで，多くの場合，基準を一つ定め，ルゴリズムである．すなわち，近似解を構成するには，その最悪値を最小化しようとする．例えば，最悪の目

重みベクトル w ∈ W を受け取り，そこでの最適化問題

に対する最適化ア的関数値を最小化しようとする最悪値最小化問題は{}min w⊤ x | x ∈ X の最適解を出力するオラクルがあmin {maxf ∈F f (x) | x ∈ X } となる．また，最適解とれば十分であり，X を見る必要はない．そこで，次のよの差，すなわち最善選択との差，機会損失を基準としうな一般化された問題，min-max(L) を考える．て，その最悪値を最小化する最悪機会損失最小化問題はmin {maxf ∈F (f (x) − miny∈X f (y)) | x ∈ X } となる．
不確かな線形の目的関数をもつ個々の最適化問題に対しては様々な研究がなされいる [2, 5]．例えば，不確定義 1 (min-max(L)). 入力は W ⊆ Rn と最適化オラ
クル OP : W → X ．目的は maxw∈W L(w, x) を最小化する x ∈ X を求めること．

かな線形目的関数をもつ最短経路問題，最小全域木問ここで最適化オラクル OP は w ∈ W を受け取り最適

題，割当問題，ナップサック問題に対してロバスト最適実行可能解 argminx∈X w⊤ x を一つ返すオラクルであ化の枠組みを適用し，その計算複雑度，近似可能性を考る．また，L : W × X → R は最適性の基準を表す汎関察するという研究がある [2]．

数である．例えば，L(w, x) = w ⊤ x が最悪値最小化問

2 本論文のねらいと成果

題に，L(f, x) = w⊤ x − miny∈X w⊤ y が最悪機会損失最小化問題にそれぞれ対応する．さらに，min-max(L)

本論文のねらいは不確かな目的関数をもつ最適化問

では X から直接情報を得ることはできず，最適化オラ題に対して 2 つの意味で包括的な近似アルゴリズムをクルを通じて間接的にのみ，X に関する情報を得られ考察することである．1 番目はより一般の目的関数集合ることに注意する．この min-max(L) 問題を考えた際W を扱うことである．2 番目は個々の問題に対するアに，命題 1，2 のようなことが成立するかどうかを明らルゴリズムではなく，一般的な近似アルゴリズムを構成かにするのが本論文のねらいである．

することである．そこで，既存の近似アルゴリズムに関する命題について述べる．

本論文ではこの min-max(L) に関して，5 つの定理を示した．まず，1 番目として L が次の式 (1)，(2) を満たすと仮定し，近似可能性に関する定理 1 を示した．

不確かな目的関数をもつ最適化問題に対する近似アルゴリズム (間野 暢)小点を多項式時間で求めることができる．したがって，∀w ∈ W, ∀x ∈ X , L(w, x) ≥ 0.
⊤(1)

定理 1 より，多項式時間で 1 + λ(W ) 近似解を得ること⊤ができる．さらに，定理 2 より，近似解の近似精度を上∀w ∈ W, ∀x, y ∈ X , L(w, x) − L(w, y) = w x − w y.
(2)
定理 1 (近似可能性と内分可能性). L を式 (1)，(2) を満たす汎関数とする．そして，W は点 w̃ で λ 内分可能から 1 + dim (W ) で抑えることができる．5 番目の定理として，min-max(L) の近似限界が 1 + λ(W ) である
ことを示す次の定理を示した．

であり，x̃ は minx∈X w̃⊤ x の最適解であるとする．す定理 5 (min-max(L) の近似限界). min-max(L) におると，x̃ は min-max(L) の 1 + λ 近似解である．

いて 1 + λ (W ) よりも良い近似比をもつアルゴリズム

定義 2 (内分可能). W ⊆ Rn が点 x ∈ Rn で λ 内分可は存在しない．

能であるとは∀v ∈ W, ∃u ∈ W, µ ∈ [0, λ] , w =この定理 5 でのアルゴリズムとは，多項式時間アルゴv + µu1+µ(3)が成立することとする．
ここで，λ 内分可能とは本論文で導入した概念である．特に W が凸集合であるときには，任意の v ∈ Wに対して，w + (w − v) /λ が W に含まれることが必要十分である．最悪値最小化問題，最悪機会損失最小化問
題の場合は汎関数 L が式 (1)，(2) を満たすことが分かる．そして，この定理 1 と内分比の基本的性質から，先の命題 1，2 を導くことができる．2 番目として，λ 内分可能であるような λ の下限を W の内分比 λ (W ) と定義し，次元との関係を述べた次の定理を示した．
定理 2 (内分比と次元). W を有界閉で凸とする．このとき，λ (W ) ≤ dim (W )．
この定理 2 から，常にある w̃ ∈ W が存在して，Wが w̃ で dim (W ) 内分可能であることが保証できる．これは，定理 1 とあわせれば，うまく w̃ ∈ W を選ぶことができれば，常に 1 + dim (W ) の近似解を得ることができることを示している．そして，3 番目と 4 番目の定理は内分可能性の下限を達成する点，内分比最小点に関する次の定理である．
定 理 3 (内 分 比 最 小 点：凸 包). W ⊂ Rn , W =conv ({w1 , . . . , wk }) とする．このとき，内分比最小点はある線形計画を解くことで得られる．
定理 4 (内分比最小点：線形不等式系). A ∈ Rn×m , b ∈Rm として，W = {f ∈ Rn | Af ≤ b} とする．このとき，内分比最小点はある線形計画を解くことで得られる．
この定理 3，4 より，W の凸包による表現または，線形不等式系による表現が分かっている場合は内分比最リズムのみでなく，指数時間アルゴリズムなどを含む一般のアルゴリズムのことであるに注意する．この定理 5は，内分比による近似の評価が最善であると同時に最適化オラクルのみを使用した解法の限界を示すものでもある．つまり，より良い近似解を求める必要があるならば，オラクルのみを使用するのではなく，問題の構造を利用しなくてはいけない，具体的には X の性質や情報が必要である，ということである．
また，本論文では目的関数が線形でない場合や，最悪相対値や最悪相対機会損失の近似可能性，最大化問題に関する近似可能性，最適化オラクルではなく近似オラクルが与えられた場合についても考察している．

参考文献[1] H. Aissi, C. Bazgan, and D. Vanderpooten, Approximating min-max (regret) versions of some polynomial problems, in Proceedings of the 12th Annual
International Computing and Combinatorics Conference (COCOON 2006), vol. 4112 of Lecture Notes in
Computer Science, Springer Verlag, 2006, pp. 428–438.
, Min-max and min-max regret versions of com[2]binatorial optimization problems: A survey, European
Journal of Operational Research, 197 (2009), pp. 427–438.
[3] A. Ben-Tal, L. E. Ghaoui, and A. Nemirovski,
Robust Optimization, Princeton University Press,2009.
[4] A. Kasperski and P. Zieliński, An approximation
algorithm for interval data minmax regret combinatorial optimization problems, Information Processing
Letters, 97 (2006), pp. 177–180.
[5] P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications, Non-Convex Optimization
and Its Applications, Kluwer Academic Publishers,
1st ed., November 1997.
[6] A. Shapiro, D. Dentcheva, A. Ruszczyński, andA. Ruszczyński, Lectures on stochastic programming: modeling and theory, Society for Industrial andApplied Mathematics, September 2009.