二次錐計画問題
確率的線形計画問題とは次のような不等式制約を含む線形核問題を指す。
minimize c T x {\displaystyle \ c^{T}x\ }
subject to P ( a i T ( x ) ≥ b i ) ≥ p , i = 1 , ... , m {\displaystyle P(a_{i}^{T}(x)\geq b_{i})\geq p,\quad i=1,\dots ,m}
この式において a i {\displaystyle a_{i}} は平均 a ̄ i {\displaystyle {\bar {a}}_{i}} 、共分散 Σ i {\displaystyle \Sigma _{i}} の正規乱数を要素とするベクトルであり、 p ≥ 0.5 {\displaystyle p\geq 0.5} である。この問題は次の二次錐計画問題と同値とみなすことができる。
minimize c T x {\displaystyle \ c^{T}x\ }
subject to a ̄ i T ( x ) + Φ − 1 ( 1 − p ) ‖ Σ i 1 / 2 x ‖ 2 ≥ b i , i = 1 , ... , m {\displaystyle {\bar {a}}_{i}^{T}(x)+\Phi ^{-1}(1-p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\geq b_{i},\quad i=1,\dots ,m}
ただし Φ − 1 {\displaystyle \Phi ^{-1}} は誤差関数の逆関数を表す。