优化问题之子模问题
什么是子模函数?
维基百科

核心:这涉及到一个边际效应递减,边际效应递减指的是当集合中元素较少或没有时加入一个元素会带来巨大的效益,当集合中已经有许多元素时,加入一个新的元素会带来的收益较微小。
注:
- 一个非负的子模函数也是次模加性函数,次模加性函数指两个集合并集的函数值最大可以取到两个集合各自函数值的和。
- 上述三个不等式,当且仅当集合是无穷的时候成立。
2. 有哪些常见的子模函数?
-
单调的

-
非单调的

子模函数的连续性拓展。

子模函数的优化方法
子模函数的优化主要分成三个子模最小化,子模最大化和相关性优化问题。
- 无约束的子模最小化一般来说是线性可解的,如求图的最小割,但是加上约束,常常就变成了NPhard的问题。
- 子模最大化一般是NPhard的问题,只有近似算法:


最后
以上就是害怕芝麻最近收集整理的关于优化问题之子模问题的全部内容,更多相关优化问题之子模问题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复