双線形計画問題

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

2種類の変数$\x = (x_1, \ldots, x_n)$,$\y = (y_1, \ldots, y_m)$の一方の値を固定すると線形計画問題になる2次の最適化問題: \[ \begin{array}{lll} \mbox{min.} & \multicolumn{2}{l}{ \c^{\top} \x - \x^{\top} \Q \y + \d^{\top} \y} \\ \mbox{s.t.} & \x \in X, & \y \in Y. \end{array} \] ただし, $\c \in {\bf R}^n$, $\d \in {\bf R}^m$, $Q \in {\bf R}^{n \times m}$で$X \subset {\bf R}^n$, $Y \subset {\bf R}^m$は凸多面体. 2次の凹最小化問題は, 行列$\Q$が正方, 対称正定値な双線形計画問題に等価である.