问题是
其中 ,和
我们可以看到是的形式，是一个凸函数。
还可以证明 f(.) 有界。
这是具有线性约束的凸最小化问题。
用于解决此类问题的标准算法有哪些？
使用问题的特定性质，是否可以使用任何标准优化软件/包来解决它？
使用线性约束最大化凸函数（最小化凹函数）
计算科学
优化
2021-12-14 05:56:02
4个回答
您可以利用问题的结构，尽管我知道没有预先打包的求解器可以为您这样做。
本质上，您正在寻找的是最小化凸多面体（或凸多面体）上的凹函数。快速搜索了一些相关资源（我依稀记得四年前我参加非线性规划课程时提到过其中一个）：
Falk、JE 和 Hoffman，KL凹面最小化通过折叠多面体，运筹学，1986 年，卷。34, No. 6, p. 919-929。
Hoffman, KL一种在凸集上全局最小化凸函数的方法，数学规划，1981 年，卷。20 页。22-31。
Benson, HP多面体上凹最小化的有限算法，海军研究物流，1985 年，卷。32, No. 1, p. 165-177。
Christophe Meyer 网站上的大量参考资料。
如果您谷歌“最小化多面体上的凹函数”（或将“多面体”替换为“多面体”），则会有更多来源。
几年前我参加了一个关于优化的讲座。那时我们将 Matlab 与 YALMIP 结合使用。
这个问题可以看作是凸函数（DC）编程问题的差异。有大量关于 DC 编程的文献，您可以在那里搜索相关研究。最著名的方法之一是 DCA 方法，例如参见：http: //lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf
最近另一篇在某种程度上调查 DC 文献并且可能很方便的论文是： https ://arxiv.org/pdf/1511.01796.pdf
对于非平滑问题，您还可以使用一些更通用的方法，例如：http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf 中给出的基于代理的 方法
我会提供Frank Wolfe 算法和相关方法供您考虑。基本上，您将目标函数线性化并在每次迭代中求解得到的 LP。但是，我确实认为您需要在上添加界限以使这种方法有效。