スレーターの条件

ウィキペディア

スレーターの条件

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 02:22 UTC 版)

数学において、スレーターの条件（スレーターのじょうけん、英: Slater's condition）とは、凸最適化に対して強双対性が成立するための十分条件である。モートン・L・スレーターの名にちなむ^[1]。スレーターの条件では、実行可能領域は必ず内点を持つ（下記の技術的な詳細を参照）ということが述べられている。

スレーターの条件は、制約想定の特別な例の一つである。特に、主問題に対してスレーターの条件が成立するなら、双対性のギャップ（英語版）は 0 であり、双対値が有限であるなら、それは達成される^[2]。

詳細

凸函数 ${\displaystyle f_{0},\ldots ,f_{m}}$ に対する問題

${\displaystyle {\text{Minimize }}\;f_{0}(x)}$

${\displaystyle {\text{subject to: }}\ }$

${\displaystyle f_{i}(x)\leq 0,i=1,\ldots ,m}$

${\displaystyle Ax=b}$

を考える（したがって、凸最適化問題である）。このときスレーターの条件は、ある ${\displaystyle x\in \operatorname {relint} (D)}$ に対して

${\displaystyle f_{i}(x)<0,i=1,\ldots ,m}$ and

${\displaystyle Ax=b.\,}$^[3]

が成立するなら、強双対性が成立することを意味する（ここで、relint は相対的内部であり、${\displaystyle D=\cap _{i=0}^{m}\operatorname {dom} (f_{i})}$ である）。初めの ${\displaystyle k}$ 個の制限 ${\displaystyle f_{1},\ldots ,f_{k}}$ が線型函数であるとき、次を満たす ${\displaystyle x\in \operatorname {relint} (D)}$ が存在するなら、強双対性は成立する。

${\displaystyle f_{i}(x)\leq 0,i=1,\ldots ,k,}$

${\displaystyle f_{i}(x)<0,i=k+1,\ldots ,m,}$ and

${\displaystyle Ax=b.\,}$^[3]

一般化不等式

${\displaystyle f_{0}}$ は凸で、各 ${\displaystyle i}$ に対して ${\displaystyle f_{i}}$ が ${\displaystyle K_{i}}$-凸であるような問題

${\displaystyle {\text{Minimize }}\;f_{0}(x)}$

${\displaystyle {\text{subject to: }}\ }$

${\displaystyle f_{i}(x)\leq _{K_{i}}0,i=1,\ldots ,m}$

${\displaystyle Ax=b}$

を考える。このときスレーターの条件は、次を満たす ${\displaystyle x\in \operatorname {relint} (D)}$ が存在するなら、強双対性が成立することを意味する^[3]：

${\displaystyle f_{i}(x)<_{K_{i}}0,i=1,\ldots ,m}$ and

${\displaystyle Ax=b}$

脚注

[脚注の使い方]

1. ^ Slater, Morton (1950). Lagrange Multipliers Revisited (PDF) (Report). Cowles Commission Discussion Paper No. 403.
2. ^ Borwein, Jonathan; Lewis, Adrian (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples (2 ed.). Springer. ISBN 978-0-387-29570-1 
3. ^ ^{a b c} Boyd, Stephen; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf 2011年10月3日閲覧。