錐線形計画問題

錐線形計画問題は、凸最適化問題のうち錐最適化問題に属するクラスの問題である。 一見線形計画とあるので扱える問題が狭そうに思えるが、実際は典型的な非線形計画問題を含んでいる：

  • 凸最適化問題 ⊃\supset 錐最適化問題 ⊃\supset 錐線形計画問題 ⊃\supset SDP ⊃\supset SOCP ⊃\supset QCQP ⊃\supset QP ⊃\supset LP

上記SDP～QPにおける非線形な目的関数・制約条件は、錐線形計画問題においては凸錐の制約条件によって表される。

錐は以下のように特徴づけられる集合である： ある錐に属する任意の元 xx と、任意のスカラー λ>0\lambda>0 について、λx\lambda x もまたその錐に含まれる。

主問題

minimizecTxsubject toAx⪯Kb \begin{array}{ll} \mathrm{minimize} & c^Tx \\ \mathrm{subject\ to} & Ax \preceq_\mathcal{K} b \end{array} ここで、

  • 変数 x∈Rnx\in\mathbb{R}^n
  • c∈Rn, A∈Rm×n, b∈Rmc\in\mathbb{R}^n,\ A\in\mathbb{R}^{m\times n},\ b\in\mathbb{R}^m
  • 閉凸錐 K≠∅\mathcal{K}\ne\emptyset

とする。 また ⪯K\preceq_\mathcal{K} の関係は x⪯Ky⟺0⪯Ky−x⟺y−x∈K x\preceq_\mathcal{K}y \Longleftrightarrow 0\preceq_\mathcal{K}y-x \Longleftrightarrow y-x\in\mathcal{K} であり、スラック変数 s∈Rms\in\mathbb{R}^m を導入して主問題は minimizecTxsubject toAx+s=bs∈K \begin{array}{ll} \mathrm{minimize} & c^Tx \\ \mathrm{subject\ to} & Ax + s = b \\ & s \in \mathcal{K} \end{array} と書くことができる。

双対問題

双対変数あるいはラグランジュ乗数を yy とし、 ラグランジアン L(x,s;y)=cTx+yT(Ax+s−b) L(x,s;y) = c^Tx + y^T(Ax+s-b) を導入する。 ここで注意として、x,yx,y の定義域はそれぞれ Rn,Rm\mathbb{R}^n, \mathbb{R}^m だが、 ss の定義域は K\mathcal{K} としている。

ラグランジュ双対をとるために infx,s∈KL\inf_{x,s\in\mathcal{K}} L を評価するにあたり、 L=(c+ATy)Tx+yTs−bTy L = (c + A^Ty)^Tx + y^Ts - b^Ty から、

  • c+ATy≠0c + A^Ty \ne 0 のとき、適当な xx で LL はいくらでも小さくできる
  • ある y,sy,s で yTs<0y^Ts<0 となるとき、 K\mathcal{K} は錐なので任意の λ>0\lambda>0 に対して λs\lambda s も K\mathcal{K} に含まれ、 yTλsy^T\lambda s は（よって LL も）いくらでも小さくできる

ことがわかる。

したがって infx,s∈KL>−∞\inf_{x,s\in\mathcal{K}} L > -\infty のためには

  • c+ATy=0c + A^Ty = 0
  • yTs≥0, ∀s∈Ky^Ts \ge 0,\ \forall s\in\mathcal{K}
    • このような yy からなる集合は双対錐の定義と一致し、y∈K∗y\in\mathcal{K}^* と書く
    • なお K\mathcal{K} は閉集合としたので 0∈K0\in\mathcal{K}、よって yTsy^Ts は必ず 00 を含む

となる必要があり、まとめると infx,s∈KL={−bTy(if c+ATy=0, y∈K∗)−∞(otherwise) \inf_{x,s\in\mathcal{K}} L = \left\lbrace \begin{array}{ll} -b^Ty & (\mathrm{if}\ c + A^Ty = 0,\ y\in\mathcal{K}^*) \\ -\infty & (\mathrm{otherwise}) \end{array} \right.

となる。

結果として g(y)=infx,s∈KLg(y)=\inf_{x,s\in\mathcal{K}} L を最大化するラグランジュ双対問題をとると maximize−bTysubject to−ATy=cy∈K∗ \begin{array}{ll} \mathrm{maximize} & -b^Ty \\ \mathrm{subject\ to} & -A^Ty = c \\ & y \in \mathcal{K}^* \end{array} が得られる。

なお逆に supyL\sup_{y} L（注：yy の定義域 Rm\mathbb{R}^m での sup\sup）の最小化が主問題に戻ることがわかる。

弱双対性

ss の定義域 K\mathcal{K} に注意して L(x,s;y)≥infx,s∈KL=g(y) L(x,s;y) \ge \inf_{x,s\in\mathcal{K}} L = g(y) であるから、 x^,s^,y^\hat x, \hat s, \hat y を主問題・双対問題の実行可能解のひとつとすると、 cTx^=L(x^,s^;y^)≥g(y^)=−bTy^ c^T \hat x = L(\hat x, \hat s; \hat y) \ge g(\hat y) = -b^T \hat y となる。 つまり、実行可能領域において双対問題は主問題の下限を与えている。

さらに最適解 x⋆,s⋆,y⋆x^\star,s^\star,y^\star を代入すれば、最適値を p⋆,d⋆p^\star,d^\star として p⋆=cTx⋆≥−bTy⋆=d⋆ p^\star = c^T x^\star \ge -b^T y^\star = d^\star が成立する。

強双対性

錐線形計画問題は凸最適化問題の一種であり、制約想定（スレーターの条件など）のもとで強双対性が成立し、 双対ギャップがゼロ、つまり主問題と双対問題の最適値が一致する。 p⋆=d⋆ p^\star = d^\star 参考文献[5]を参照。

最適性条件

強双対性の仮定のもと、 Ax+s=b,s∈K,−ATy=c,y∈K∗,cTx=−bTy Ax + s = b,\quad s \in \mathcal{K},\quad -A^Ty = c,\quad y \in \mathcal{K}^*,\quad c^Tx = -b^Ty が最適性の必要十分条件（KKT条件、参考文献[5]を参照）となることがわかる。

results matching ""

    No results matching ""