常用的大规模的优化问题解决方法都有哪些？

Ylisar · 发表于 2023-3-7 05:34

目前的很多凸优化问题都有现成的可靠算法来进行，也有很多库可以直接拿来用。但是对于大规模的运算好像没有找到比较好的解决方法。希望能问一下大家目前这方面的常用方法和思路都有哪些呢？

目前我具体遇到的问题是：正在尝试一个算法，然而最后归出的线性规划问题，约束矩阵过于庞大以至于无法在电脑上生成，也就没有办法求解了。但是我想在实际运用中应该会有不少类似于这样的问题吧？尤其是需要训练大量数据集的情况下。
希望能得到有经验的前辈指点～～谢过！

问题补充：obj func:
min |u|1
st. Au

量子计算9 · 发表于 2023-3-7 05:39

要不试试求解对偶问题？这样就变成变量少但约束多的问题了，再用些启发式的方法。

zifa2003293 · 发表于 2023-3-7 05:47

你好，我也在研究大规模优化问题，能交流下吗

XGundam05 · 发表于 2023-3-7 05:57

硬翻的：https://www.quora.com/How-can-you-solve-a-large-combinatorial-optimization-problem
大型组合优化是一个困难的领域，而您的问题在这个困难的领域中是一个困难的问题。
通常，组合优化有几种方法：
1.贪婪的方法：大多数时候，您都不在乎全局最优解，在这种情况下，贪婪就可以了。在实践中，有许多方法可以设计性能合理的贪婪算法。
2.启发式方法。“更智能”的贪婪算法。如果您具有领域知识，它们将对您有所帮助。
3.放松。组合优化之所以很难，是因为它是非凸的。如果您将其放宽到凸问题，则可以使用大量优化算法在多项式时间内求解它（请参阅《非线性编程》）。
在您遇到的问题中，可行集不是凸集，因为它们是离散的（尽管它们很容易放松）。但是，您选择一个点并将其值设置为c> b，因此该函数本身不是凸的。即使您非常接近P *，也没有知识指导您转向最佳解决方案。据我所知，我没有解决这个问题的好方法。可能有一些大师可以做到这一点。
我的回答：对于您的特定问题，除了蛮力之外，别无其他方法。
为什么要解决这个人为制造的难题？

ainatipen · 发表于 2023-3-7 06:03

你好，起来我也遇到类似的问题，请问后面有进展吗？

johnsoncodehk · 发表于 2023-3-7 06:12

普通算法有列生成算法、分支定价法，他们都有一定的限制条件。现在还有一些启发式算法用得比较多，例如遗传算法等。

		自动登录	找回密码
密码			立即注册