攻击jsp网站,互联网网站建设月总结,卡点视频免费制作软件,西安网站开发建设许多组合优化问题可以被转换为集合函数的最小化#xff0c;集合函数是在给定基集合的子集的集合上定义的函数。同样地#xff0c;它们可以被定义为超立方体的顶点上的函数#xff0c;即#xff0c;其中是基集合的基数-它们通常被称为伪布尔函数[27]。在这些集合函数中…许多组合优化问题可以被转换为集合函数的最小化集合函数是在给定基集合的子集的集合上定义的函数。同样地它们可以被定义为超立方体的顶点上的函数即其中是基集合的基数-它们通常被称为伪布尔函数[27]。在这些集合函数中次模函数起着重要的作用类似于向量空间上的凸函数因为在实际问题中出现的许多函数都是次模函数或其轻微的修改的在计算机科学和应用数学的许多领域中有应用例如机器学习[125157117124]计算机视觉[3196]运筹学[98182]电气网络[162]或经济学[203]。由于次模函数可以精确最小化并且在某些保证下近似地最大化因此在多项式时间内它们很容易为它们所应用的所有众多问题带来有效的算法。它们也出现在理论计算机的几个领域中科学如拟阵理论[189]。
然而对次模函数的兴趣并不限于离散优化问题。 事实上次模函数的丰富结构及其通过Lovász扩展与凸分析的联系[135]和各种相关的多面体使它们特别适用于组合优化之外的问题即作为信号处理和机器学习问题中的正则化器[387]。
实际上许多连续优化问题表现出潜在的离散结构例如 基于链、树或更一般的图和次模函数提供了有效和通用的工具来捕获这样的组合结构。
在这本专著中次模函数的理论以一种独立的方式呈现所有结果都是从机器学习中常见的凸分析的第一原理证明的而不是依赖于组合优化和传统的理论计算机科学概念如拟阵或流见例如 [72]有关这些方法的参考书。 此外我们提出的算法是基于传统的凸优化算法如单纯形法线性规划二次规划的有效集方法椭球方法切割平面和条件梯度。 这些将详细介绍特别是在次模函数最小化及其各种连续扩展的背景下。 假设具有良好的凸分析知识见例如 [3028]并在附录A中对重要概念进行了简短的回顾-更多详细信息请见例如 [95第30、28、185页]。
各章大纲。分为几个章节总结如下在目录中第一次阅读时可以跳过的章节用星星标记
(1)定义在第二章中我们给予了次模函数及其相关多面体的不同定义特别是基多面体和次模多面体它们在次模分析中是至关重要的因为许多算法和模型都可以用这些多面体自然地表示。
(2)Lovász扩展在第三章中我们将Lovász扩展定义为从定义在上的函数到定义在上的函数的扩展然后是并给予它的主要性质特别是给出了次模分析中的关键结果Lovász扩展是凸的当且仅当集函数是次模的;此外最小化次模集函数等价于最小化上的Lovász扩展。这意味着次模函数最小化可以在多项式时间内解决。最后通过所谓的“贪婪算法”建立了Lovász扩展和次模多面体之间的联系Lovász扩展是基多面体的支撑函数并且可以以封闭形式计算。
(3)多面体第四章将进一步研究伴随多面体计算线性函数的支撑函数和伴随极大化子我们还详细讨论了这种多面体的面结构这在第五章中与Lovász扩展的稀疏诱导性质相关时将很有用。
(4)次模罚函数的凸松弛虽然次模函数可以直接使用用于集函数的最小化或最大化但我们在第5章中展示了如何使用它们来惩罚向量的支撑集或水平集由此产生的混合组合/连续优化问题可以使用Lovász扩展自然地松弛为凸优化问题。
(5)示例如下在第6章中我们介绍了次模函数的经典例子以及在机器学习中的几个应用特别是割集合覆盖网络流熵谱函数和拟阵。
(6)非光滑凸优化在第七章中我们回顾了经典的迭代算法如次梯度法、椭球法、单纯法、割平面法、有效集法和条件梯度法并特别注意在适用的情况下提供这些算法的原始/对偶解释。
(7)可分离优化-分析在第八章中我们考虑了由Lovász扩展正则化的可分优化问题即形式为的问题并证明了这如何等价于一系列次模函数极小化问题。这是与次模函数相关的组合优化问题和凸优化问题之间的关键理论联系这将在后面的章节中使用。
(8)可分离优化-算法在第9章中我们提出了两套可分离优化问题的算法。 第一个算法是一个精确的算法它依赖于一个有效的次模函数最小化算法的可用性而第二组算法是基于现有的凸优化迭代算法其中一些来与在线和离线的理论保证。 我们考虑有效集方法“最小范数”算法和条件梯度方法。
(9)次模函数最小化在第10章中我们介绍了各种次模函数最小化的方法。 我们简要介绍了精确次模函数最小化的组合算法并专注于更深入地使用特定的凸优化问题可以迭代求解以获得近似或精确解次模函数最小化有时理论保证和近似最优性证书。 我们考虑了次梯度法椭球法单纯形算法和解析中心割平面。 我们还展示了第8章和第9章中的可分离优化问题如何用于次模函数最小化。 第12章将对这些方法进行实证比较。
(10)次模块优化问题在第11章中我们提出了其他组合优化问题可以部分解决使用次模分析如次模函数最大化和次模函数的差异的优化并将这些问题与非凸优化问题的次模多面体。 虽然这些问题通常不能在多项式时间内解决但许多算法都具有基于次模性的近似保证。
(11)实验在第12章中我们提供了前面描述的优化算法的例子用于次模函数最小化以及凸优化问题可分或不可分。 所有这些实验的Matlab代码可以在http://www.di.ens.fr/~fbach/submodular/上找到。
在附录A中我们回顾了凸分析的相关概念如Fenchel对偶、对偶范数、规范函数和极集而在附录B中我们给出了与次模函数相关的几个结果如保持次模性的运算。
已经有几本关于同一主题的书籍和专著文章本专著中提供的材料依赖于这些[72162126]。 然而为了以最简单的方式呈现材料也使用了相关研究论文的思想并更加强调凸分析和优化。
符号。 我们考虑集合其幂集为由的个子集组成。 给定一个向量也表示定义为的模集函数。此外意味着是的子集可能等于。 我们表示为集合的基数并且对于表示集合的指示向量。 若则表示定义为我们称之为弱或强-超水平集。 类似地如果我们记为。
对于我们用表示的-范数定义为其中且。最后我们用表示非负实数集用表示非零实数集用表示严格正实数集。
