Minimum-Risk Maximum Clique Problem - todo314 @ ウィキ

Minimum-Risk Maximum Clique Problem

• Maciej Rysz, Pavlo A. Krokhmal, and Eduardo L. Pasiliao
• Dynamics of Information Systems: Algorithmic Approaches 2013

概要

• 最小危険最大クリーク問題
• 各頂点には費用／損失を表す確率変数
  • 同時分布は既知
• 特定の危険尺度で危険最小のクリークを見つけたい
  • 尺度の単調性から最適解は極大クリークになる
• Erdős–Rényiグラフで実験

導入

• 状況: 頂点 が不確かさを持つ

危険回避グラフ理論的問題

• Xi: 頂点iに紐づく確率変数
  • Xiの同時分布は分かる
• 危険尺度ρ
• $$ \min_{S \subseteq V, w} \rho\left( \sum_{i \in S} w_i X_i \right) $$
• $$ s.t. \sum_{i \in S} w_i = 1, w_i \geq 0, S[G] \in {\cal Q}_G $$
  • S: 性質Qを満たす部分集合
    • 今回はクリーク
  • wi: この重みにしたがって頂点を選ぶ

重み？--センサ配置の例

• センサの質: センサの生きている時間
• センサ間リンク: 情報共有→精度向上
• 予算（電力供給）をセンサに配分，これが重み
• 情報をフルに共有して，情報損失を最小化したいお

Coherent危険尺度

Value-at-Risk (VaR)

• 損失分布のα∈(0,1)分位点
• VaR_α(X) = ifn{η | Pr[X≦η]≧α}
• 一般に非凸

Coherent性

• (A1) 単調性 X≦Y⇒ρ(X)≦ρ(Y)
• (A2) 劣加法性 ρ(X+Y)≦ρ(X)+ρ(Y)
• (A3) 正斉次方程式 ∀λ>0 ρ(λX)=λρ(X)
  • positive homogeneity
• (A4) 平衡移動普遍性 ∀α∈ℝ ρ(X+a)=ρ(X)+a
  • translation invariance

• 悲しい: 別に上の性質からρを構成付けるとかではない

• 畳み込み(? convolusion)でρを表現
• φ: X→ℝ
  • (A1)-(A3)を満たす
  • φ(η)>η (η>0)
• ρ(X)=min η+φ(X-η)
  • これはCoherent

Conditional Value-at-Risk (CVaR)

• $$ \mathrm{CVaR}_\alpha(X) = \min_{\eta \in \mathbb{R}} \eta + \frac{1}{1-\alpha} \mathbb{E}[(X-\eta)^+] $$
• $$ = \mathbb{E}[X \mid X \geq \mathrm{VaR}_\alpha(X)] $$

危険回避最大クリーク問題

• 少し目的関数を一般化して
• ρ(X_G(S;w))
• シナリオNがあって，シナリオs∈NでのXiの値がXiみたいな感じ

Isolated Risk Exposures

• X_G(S;w) = Σ_i∈S wi*Xi
  • 簡単にMIPでかける
  • CVaRの表現を変えてもOK

Neighbor-Dependent Risk Exposures

• $$ X_G(S;w) = \sum_{i \in S} \left( w_i X_i + \sum_{j \in S-i} \theta_{ij}w_j X_i \right) $$
  • θ_ij: iからjへのバクロ，適当に1/|V|とかする
  • 少し頑張ってMIP
• 命題
  • Sが大きい方が危険小（単調性）
  • ∴最適解は極大クリークになる

実験…省略

まとめ

• この辺りのはどういう点が評価されるのか分からないですぅ

CVaR 不確実性グラフ 極大クリーク

2015/07/01 13:39