双線形計画問題

出典: ORWiki

【そうせんけいけいかくもんだい (bilinear programming problem)】

2種類の変数\boldsymbol{x} = (x_1, \ldots, x_n) \,,\boldsymbol{y} = (y_1, \ldots, y_m) \,の一方の値を固定すると線形計画問題になる2次の最適化問題:


\begin{array}{lll} \mbox{min.} & \boldsymbol{c}^{\top} \boldsymbol{x} - \boldsymbol{x}^{\top} \mbox{Q} \boldsymbol{y} + \boldsymbol{d}^{\top} \boldsymbol{y} \\ \mbox{s.t.} & \boldsymbol{x} \in X, \, \boldsymbol{y} \in Y. \end{array} \,


ただし, \boldsymbol{c} \in \mathbf{R}^n \,, \boldsymbol{d} \in \mathbf{R}^m \,, Q \in \mathbf{R}^{n \times m} \,でX \subset \mathbf{R}^n \,, Y \subset \mathbf{R}^m \,は凸多面体. 2次の凹最小化問題は, 行列\mbox{Q} \,が正方, 対称正定値な双線形計画問題に等価である.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%8F%8C%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E5%95%8F%E9%A1%8C" より作成