C02: 連続と離散の融合による ロバストアルゴリズム構築 杉原厚吉，室田一雄，今井浩，松井知己，岩田覚， 大石泰章，寒野善博，西田徹志，今堀慎治

0-1変数を持つ2次最小化問題の 近似解法の設計 中央大学　松井知己

昨年得られた結果 Y. KUROKI and T. MATSUI, Approximation algorithm for multidimensional assignment problem minimizing the sum of squared errors, 2006. （投稿中） M. Iwasa, H. Saito and Tomomi Matsui, Approximation Algorithms for the Single Allocation Problem in Hub-and-Spoke Networks, 2006. （投稿中）

一般的には, （定数近似比率の）近似解法も難しい MIN ２SAT ： (3/2)近似，1.1037-近似 問題 min. xTQx+cTx s. t. Ax ≧ｂ，　x∈｛0,1｝n 一般性を失うことなく、以下を仮定できる （１）Qは対称行列 （２）Qの対角成分はすべて０ xi∈｛0,1｝より xi2=xiとなり, 　　　各対角項（2乗項）は線形項で表せる 一般的には, （定数近似比率の）近似解法も難しい MIN ２SAT ： (3/2)近似，1.1037-近似 quadratic semi-assignment problem parallel machine scheduling (重みつき終了時刻の総和最小化） ハブネットワーク設計問題 Metric Labeling Problem (多項式時間O(log n)-近似解法)

問題 xi=1 完全グラフ　G＝（V,E）　　V=｛1,2,…,n｝ 頂点iに0－1変数xi を割り当てる 枝｛i,j｝に重み　2qij を割り当てる 頂点i　に重みciを割り当てる 2次項（xTQx）は、1の値をとっている変数からなる頂点で定義されるクリークの重み （クリーク重み＝クリーク中の枝重みの総和） 線形項（cTx）は,変数値が1の頂点の重みの総和

問題 xi=1 完全グラフ　G＝（V,E）　　V=｛1,2,…,n｝ 頂点iに0－1変数xi を割り当てる 枝｛i,j｝に重み　2qij を割り当てる 頂点i　に重みciを割り当てる 2次項（xTQx）は、1の値をとっている変数からなる頂点で定義されるクリークの重み （クリーク重み＝クリーク中の枝重みの総和） 線形項（cTx）は,変数値が1の頂点の重みの総和

min. ∑ｃ=(x∨y) ｗｃ（ｘ＋ｙ－ｘｙ） s. t. x+y=1 (∀{x,y} s.t. x=￢y), x∈{0,1} (∀x). 問題例 1 (x is True) x= 0 (x is False) ＭＩＮ 2ＳＡＴ min. ∑ｃ=(x∨y) ｗｃ（ｘ＋ｙ－ｘｙ） s. t. x+y=1 (∀{x,y} s.t. x=￢y), x∈{0,1} (∀x). quadratic semi-assignment Parallel Machine Scheduling Hub Network Design Problem min. xTQx+cTx s. t. ∑jｘij =1 (∀i), xij∈{0,1} (∀(i,j)) . i j job machine non-hub hub

必要な性質 （定数近似比率を持つ）近似解法が設計できる条件 （１）許容0-1解の凸包が、線形不等式系 Ax ≧ｂ, x ≧0 で記述できている そもそもこれさえ書けてないと話にならない （２）連続緩和した問題が、0-1最適解を持つ 上記の性質が，乱拓解法で証明できる （３）目的関数に、十分大きな線形項がある ２次項しかないと，定数近似比率の近似解法の 構築は殆ど無理 (Metric Labeling: O(log n)-近似解法)

quadratic semi-assignment problem （２）連続緩和した問題が、0-1最適解を持つ 上記の性質が，乱拓解法で証明できる min. xTQx+cTx s. t. ∑jｘij =1 (∀i), xij∈{0,1} (∀(i,j)) xij≧0 (∀(i,j)) ｘ*：上記の連続緩和問題の最適解 確率変数Xij：各iについて独立に，｛xij |∀j ｝の内どれか一つを1にする．ただしPr[Xij=1]=x*ij 元問題の最適値（最小値）≦得られる許容解の期待値 =Ｅ[XTQX＋ｃTX]＝ x*TQx*+cTx* =連続緩和問題の最適値≦元問題の最適値

（１）凸2次計画緩和（SOCP緩和） （２）線形化手法 緩和問題 （１）凸2次計画緩和（SOCP緩和） （２）線形化手法 Second 0rder Cone Programming 2次錐計画

Second 0rder Cone Programming 緩和問題1:凸2次計画緩和(SOCP緩和） Second 0rder Cone Programming 2次錐計画 min. xTQx+　cTx s. t. Ax ≧ｂ，　x∈｛0,1｝n 任意の許容解（0-1解）に対し，以下が成り立つ 　　 xTQx+cTx ＝ xTQx+Σicixi2 関数ｆ（ｘ）＝xTQx+Σicixi2 が凸２次関数になるくらい、線形項の係数ｃiが 正の大きな数 （Ｑが非負行列なら） ＳＯＣＰ緩和 min. z　 s. t. z≧xTQx+Σicixi2 　　　 z≧ cTx Ax ≧ｂ，　x≧0. 凸2次計画緩和　 min. xTQx+Σicixi2 s. t. Ax ≧ｂ，　x≧0.

quadratic semi-assignmentのＳＯＣＰ緩和 min. z　 （Ｑが非負行列） s. t. z≧xTQx+Σicixi2, z≧ cTx, ∑j xij =1 (∀i), xij∈{0,1} (∀(i,j)) xij≧0 (∀(i,j)) (ｘ*,z*)：SOCP緩和問題の最適解 確率変数Xij：各iについて独立に，｛xij |∀j ｝の内どれか一つを1にする．ただしPr[Xij=1]=x*ij 得られる許容解の目的関数の期待値=Ｅ[XTQX＋ｃTX] =x*TQx*+cTx*≦ x*TQx*+Σicix*i2 +cTx* ≦z*+ z*≦2z*≦2(元問題の最適値）

quadratic semi-assignment (parallel machine scheduling) 凸2次計画緩和による近似解法　 quadratic semi-assignment (parallel machine scheduling) M. Skutella, Convex Quadratic and Semidefinite Programming in Scheduling, Journal of ACM, 48(2), 206-242, 2001. 重み付き終了時刻の総和最小化: (3/2)近似解法 k 次元割当問題 Y. KUROKI and T. MATSUI, Approximation algorithm for multidimensional assignment problem minimizing the sum of squared errors'‘, (2006). (多センサー多ターゲットシステムでのターゲット位置同定 最尤推定：「-1×対数尤度」の最小化) Bandelt, Crama & Spieksma 1994: (4-6/k)-近似解法 →Kuroki & Matsui (5/2-3/k)-近似解法

緩和法（２） 線形化手法 （linearization technique)

緩和問題2：線形化手法(linearization technique) yij=xi xj　という変数を導入 目的関数xTQx+cTx は，線形関数になる (線形項が無くても使える手法！） quadratic semi-assignment 目的関数： ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) x(i,j)x(i’,j’) +cTx ⇒ ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) y(i,j)(i’,j’) +cTx 制約： ∑j x(i,j) =1 の両辺に x(i’,j’)をかけると ∑j x(i,j) x(i’,j’) = ∑j y(i,j)(i’,j’) ＝ x(i’,j’)

quadratic semi-assignment min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) x(i,j)x(i’,j’) +cTx s. t. ∑ｊｘ(i,j) =1 (∀i), x(i,j) ∈{0,1} (∀(i,j)). 制約： ∑j x(i,j) =1 の両辺に x(i’,j’)をかけると ∑j x(i,j) x(i’,j’) = ∑j y(i,j)(i’,j’) ＝ x(i’,j’) min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) y(i,j)(i’,j’) +cTx x(i,j) ∈{0,1} (∀(i,j)), ∑j y(i,j)(i’,j’) ＝ x(i’,j’) (∀(i,i’,j’)).

quadratic semi-assignment min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) x(i,j)x(i’,j’) +cTx s. t. ∑ｊｘ(i,j) =1 (∀i), x(i,j) ∈{0,1} (∀(i,j)). min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) y(i,j)(i’,j’) +cTx x(i,j) ∈{0,1} (∀(i,j)), ∑j y(i,j)(i’,j’) ＝ x(i’,j’) (∀(i,i’,j’)). q(i,j)(i’,j’) y(i,j)(i’,j’) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) どれか一つだけが1 どれか一つだけが1

quadratic semi-assignment 連続緩和 min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) y(i,j)(i’,j’) +cTx s. t. ∑ｊｘ(i,j) =1 (∀i), y(i,j)(i’,j’)≧0, x(i,j) ≧0, ∑j y(i,j)(i’,j’) ＝ x(i’,j’) (∀(i,i’,j’)). x(i,j)を需要供給量とした， Hitchcock型輸送問題 （輸送量： y(i,j)(i’,j’) ) q(i,j)(i’,j’) y(i,j)(i’,j’) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) 供給量 需要量

quadratic semi-assignment 連続緩和 min. ∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) y(i,j)(i’,j’) +cTx s. t. ∑ｊｘ(i,j) =1 (∀i), y(i,j)(i’,j’)≧0, x(i,j) ≧0, ∑j y(i,j)(i’,j’) ＝ x(i’,j’) (∀(i,i’,j’)). x(i,j)を需要供給量とした， Hitchcock型輸送問題 （輸送量： y(i,j)(i’,j’) ) q(i,j)(i’,j’) y(i,j)(i’,j’) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) 供給量 需要量

線形化はHub Network 設計問題に適している 輸送問題の費用構造 parallel machine scheduling : Hub Network Design x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) 2つの非ハブを異なるHUB に接続するとHUB間の 輸送費用が発生 ⇒上記の枝の費用のみ0 その他の枝の費用は正 2つの仕事を同じ機械で処理 すると費用が発生 ⇒上記の枝のみ正の費用 その他の枝の費用は0 H1 H3 H2

乱択解法 線形化手法で得られた問題の線形緩和を解く ｘ*(i,j)：緩和問題の最適解 独立丸め法 確率変数X(i,j)：各iについて独立に，｛x(i,j) |∀j ｝の内 どれか一つを1にする．ただしPr[X(i,j)=1]=x*(i,j) 得られる許容解の目的関数の期待値 =Ｅ[∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) X(i,j)X(i’,j’) +cTX] =∑i≠i’∑ｊ≠j’ q(i,j)(i’,j’) x*(i,j)x*(i’,j’) +cTx*

選ばれる確率x*(i,j)x*(i’,j’)と，y*(i,j)(i’,j’) が違い過ぎる 独立丸め法は，線形化手法と相性が悪い 独立丸め法 ：線形化手法での最適解 x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) 緩和問題の最適解に おいて正の値を持つ y*(i,j)(i’,j’)は，全張木 費用q (i,j)(i’,j’) の枝は x*(i,j)x*(i’,j’)の確率で 選ばれる 選ばれる確率x*(i,j)x*(i’,j’)と，y*(i,j)(i’,j’) が違い過ぎる

選ばれる確率x*(i,j)x*(i’,j’)と，y*(i,j)(i’,j’) が違い過ぎる 独立丸め法は，線形化手法と相性が悪い 独立丸め法 ：線形化手法での最適解 x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) 緩和問題の最適解に おいて正の値を持つ y*(i,j)(i’,j’)は，全張木 費用q (i,j)(i’,j’) の枝は x*(i,j)x*(i’,j’)の確率で 選ばれる 選ばれる確率x*(i,j)x*(i’,j’)と，y*(i,j)(i’,j’) が違い過ぎる

従属丸め法の導入（quadratic semi-assignment) 頂点を並べ直して，枝が交わらないようにする x(i,1) x(i’,1) x(i,2) x(i’,2) ： : x(i,j) : : x(i’,j’) : : x(i,m) x(i’,m) x(i,1) x(i’,1) x(i,j) x(i’,j’) ： : x(i,2) : : x(i’,2) : : x(i,m) x(i’,m) 1 x(i,1) x(i’,1) x(i,j) x(i,2) x(i’,j’) x(i’,2) x(i,m) x(i’,m) 右の解(y*(i,j)(i’,j’) )は， 北西隅の規則で得られる基底解 従属丸め法： 一様乱数U∈[0,1]を用いて丸める Pr[X(i,j)X(i’,j’)=1]=y*(i,j)(i’,j’) U

頂点を並べ直して，枝が交わらないようにする 従属丸め法の導入 頂点を並べ直して，枝が交わらないようにする x(i,1) x(i’,1) x(i,j) x(i’,j’) ： : x(i,2) : : x(i’,2) : : x(i,m) x(i’,m) 右の解(y*(i,j)(i’,j’) )は， 北西隅の規則で得られる基底解 従属丸め法： 一様乱数U∈[0,1]を用いて丸める Pr[X(i,j)X(i’,j’)=1]=y*(i,j)(i’,j’) 1 北西隅の規則は， 費用行列がMonge性を 持つときに，最適解となる x(i,1) x(i’,1) x(i,j) x(i,2) x(i’,j’) x(i’,2) x(i,m) x(i’,m) U 元の費用行列をモンジュ行列で 近似できれば，近似比率を算定 できる

Hub Network Design Problem M. Iwasa, H. Saito and Tomomi Matsui, Approximation Algorithms for the Single Allocation Problem in Hub-and-Spoke Networks, 2006. Hub Network Design Problem に対する，初めての（定数近似比率を持つ）近似解法 線形化手法＋独立丸め法：２-近似 線形化手法＋従属丸め法；ハブ数3のとき(5/4)-近似 ハブ数3のときの費用行列Qを，3つのモンジュ行列の凸結合で得られる行列Mで近似した

今後の課題 凸2次緩和 （１）凸2次緩和が使える範囲は？ もともと目的が凸2次関数最小化の0-1問題 正規分布での最尤推定，χ2適合度, 等の確率モデル （２）SOCP緩和の適用範囲は？ 従属丸め法 （１）従属丸め法は，quadratic semi-assignment 以外にどのように拡張できるのか？ （２）独立丸めの巧妙な脱ランダム化として捉える？ （３）元問題を，最適に解けるInstanceの凸結合で近似 することによって，近似解法を設計 quadratic semi-assignment (1)量子情報処理？

END