双線形計画問題

【そうせんけいけいかくもんだい (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}}\,$が正方, 対称正定値な双線形計画問題に等価である.