计算科学 - 找分钟X吨是的minxTAy服从1吨x =1吨是的= 1 , x ≥ 0 , y≥ 01Tx=1Ty=1,x≥0,y≥0 - 吾爱随笔录

找分钟X吨是的minxTAy服从1吨x =1吨是的= 1 , x ≥ 0 , y≥ 01Tx=1Ty=1,x≥0,y≥0

计算科学优化非线性规划约束优化

2021-12-12 23:17:52

在以下问题中，是给定的矩阵：尽管公式很简单，但对我来说并不容易。希望有人可以提供帮助。非常感谢！ $A$ $\mathbb{R}^{m\times n}$

\begin{aligned} minimize & x^{T} A y \\ subject to & 1^{T} x = 1^{T} y = 1, \\ x \geq 0, y \geq 0. \end{aligned}

$\begin{align} \mbox{minimize}\quad & x^TAy \\ \mbox{subject to}\quad & 1^Tx=1^Ty=1, \\ & x\ge 0,y\ge 0. \end{align}$

2个回答

如果没有错误，那比我想象的要容易得多。

我们将证明最小值等于的最小分量，用表示，其中，当和 $A$ $a_{i_0j_0}$ $(i_0,j_0) = \arg\min_{(i,j)} a_{ij}$ $x_{i_0}=y_{j_0}=1$ $x_i=y_i=0\quad\forall i\neq i_0,j\neq j_0.$

事实上，我们有

\begin{aligned} x^{T} A y = \sum_{1 \leq i \leq m} \sum_{1 \leq j \leq n} a_{i j} x_{i} y_{j} \geq \sum_{1 \leq i \leq m} \sum_{1 \leq j \leq n} a_{i_{0} j_{0}} x_{i} y_{j} = a_{i_{0} j_{0}} \sum_{1 \leq i \leq m} \sum_{1 \leq j \leq n} x_{i} y_{j} = a_{i_{0} j_{0}} . \end{aligned}

$\begin{align} x^TAy=\sum_{1\le i\le m}\sum_{1\le j\le n} a_{ij}x_iy_j \ge \sum_{1\le i\le m}\sum_{1\le j\le n} a_{i_0j_0}x_iy_j = a_{i_0j_0}\sum_{1\le i\le m}\sum_{1\le j\le n} x_iy_j = a_{i_0j_0}. \end{align}$

平等很容易检查。

假设和。然后你的问题减少到 $m=n$ $A = I$

\begin{aligned} minimize & \sum_{i = 1}^{n} x_{i} y_{i} \\ subject to & \sum_{i = 1}^{n} x_{i} = \sum_{i = 1}^{n} y_{i} = 1, \\ x \geq 0, y \geq 0. \end{aligned}

$\begin{align} \mbox{minimize}\quad & \sum_{i=1}^{n}x_{i}y_{i} \\ \mbox{subject to}\quad & \sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}=1, \\ & x\ge 0,y\ge 0. \end{align}$

孤立的双线性项通常是非凸的，因此解决该问题具有挑战性，并且通常需要特殊的、昂贵的方法来计算全局最优解。 $\varepsilon$

对于一般，我会期待类似的行为，因为我看不到任何方法可以对双线性项进行分组以实现凸性（例如，通过平方和类型的公式）。 $A$

其它你可能感兴趣的问题

上一篇《维高的祝福……人脸验证》中优化问题的解法下一篇差分进化方法通常需要多少代才能达到全局最优？