计算科学 - 我该如何解决这个非凸多变量优化问题？ - 吾爱随笔录

我该如何解决这个非凸多变量优化问题？

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

2021-12-14 09:19:49

我想解决以下优化问题：

min_{A, B, X} ‖ Y - A X ‖_{F}^{2} + λ_{1} ‖ Z - B X ‖_{F}^{2} + λ_{2} ‖ B ‖_{F}^{2}

$\min_{A,B,X} \|Y-AX\|_F^2 + \lambda_1 \|Z-BX\|_F^2+ \lambda_2 \|B\|_F^2$

s . t x_{i j} \geq 0

$s.t ~~x_{ij}~ \geq 0$

其中， $Y$ 和 $Z$ 是数据矩阵，分别是 $d \times n$ 和和 $l \times n$ 对应的列是数据样本），是参数矩阵，分别是，和分别。约为 100，约为 20。 $Y$ $Z$ $A,B,X$ $d \times k$ $l \times k$ $k \times n$ $n$ $d,k$

我认为这被称为多元优化问题。我尝试使用像 Matlab 的“fmincon”这样的通用求解器来解决它，它找到了一个很好的最小值。我认为它使用顺序编程算法。

我的问题是我怎样才能以系统的方式解决这个优化问题，以找到一个与 Matlab 求解器发现的相媲美的最佳点？

2个回答

请注意，这是一个非凸问题。因此，期望将问题解决为最佳解决方案可能是不合理的。但是通过一个好的方法和好的初始化，你也许能够收敛到一个好的解，尽管可能很难证明它是最优解。您可以用来解决此类问题的一种方法是使用块坐标下降或替代优化。这方面的论文很多，例如http://www.math.ucla.edu/~wotaoyin/papers/bcu/。

在您的情况下，块将是和。因此，在算法的每次迭代中，您通过直接最小化相对于另一个块的目标来修复一个块并更新另一个块。如果这在计算上难以处理，您始终可以将目标线性化。这相当于只取目标相对于非固定块的梯度并将其投影回可行集。 $X$ $(A,B)$

如果您遇到问题，在次迭代中，您修复，然后通过梯度步骤更新，然后将其投影回非负正交以使其可行。然后，或者，您固定并通过梯度步骤更新进行优化）。您执行此更新直到收敛。请注意，如果您使用梯度，则需要注意每个步骤中的步长，以确保每次更新时始终减少目标。 $X$ $(A,B)$ $X$ $X$ $(A,B)$ $X$

如果您关心寻找全局最优性，最好的办法是使用更高级的 MINLP 求解器，例如 BARON。由于您使用的是 MATLAB，请尝试查看OPTI Toolbox。

其它你可能感兴趣的问题

上一篇为什么有时将两个矩阵与 NumPy 相乘不起作用？下一篇高效高维直方图的数据结构