块坐标下降方法：局部最优和收敛消息传递

7559块坐标下降汤姆·马的妻子丹尼尔·普鲁斯·马，汤姆·马的妻子德拉斯克捷克共和国布拉格捷克技术大学电气工程学院{werner，prusapa1，dlaskto2}@ fel.cvut.cz摘要众所周知，对于一般的凸优化问题，块坐标下降可能会陷入局部最优。尽管如此，这种称为收敛消息传递的方法的版本非常成功地解决了图模型中MAP干扰问题的对偶LP松弛。在试图找出为什么这些方法往往实现良好的局部最小图像的原因，我们认为，如果在块坐标下降的最小集在一个可变块有多个元素，应该选择一个元素从这个集合的相对内部。我们表明，这一规则并不比任何其他规则选择块最小。基于这一观察，我们开发了一个理论框架，适用于一般凸问题的块坐标下降。我们说明这个理论的收敛消息传递方法。1. 介绍块坐标下降法（BCD）是一种迭代优化方法，它在每次迭代中在一个变量子集上找到问题的全局最优解，保持其余变量不变。对于某些问题，BCD的不动点和由其生成的序列的聚类点[20]以及其中的参考文献。专注于凸问题，BCD可以非常有效和可扩展，前提是可以保证最优性，如[13，5，1]所示。对于一般的凸问题，BCD固定/聚类点可以是任意差的局部最小图像（其中因此，BCD通常被认为不适合一般的凸问题。一个例外是称为收敛消息传递的一类方法，用于近似解决图形模型[19，7]中MAP推理问题的线性规划（LP）松弛（经常用于对低级计算机视觉任务建模，如去噪，分割或配准）和一些其他组合问题[18]。这些方法将各种形式的BCD应用于各种形式的对偶LP松弛，其中后者归结为无约束的最小值。一个分段仿射（因此不可微）凸函数的作用例子是最大和扩散[11，17，23]，[2019 - 08 - 19 00：00：00][2019 - 08：00][2019 - 01：00][2019 - 01：00][2019 - 01：00]对于许多TRW-S通常比所有竞争方法更快，并且其固定点离全局最小值不远，特别是对于大型稀疏实例[19，7]。这促使我们研究独立于MAP推理的收敛消息传递方法，希望将它们扩展到更广泛的凸问题。人们可能会认为，收敛的消息传递方法是然而，这并不是全部的解释：我们相信这些方法具有允许它们实现良好的局部最优的单一特征。在BCD迭代中，可变块上的极小值不需要是唯一的，因此必须选择单个极小值我们认为，这个极小应选择的相对内部的所有可变块上的极小的集合我们称之为相对内部规则。基于这一观察，我们发展了一个理论框架，适用于一般凸问题的BCD。我们区分三种类型的块坐标局部最小图像：（普通）局部极小、内部局部极小和预内部局部极小。 我们证明了相对内部规则并不比选择变块极小的任何其他规则差，在以下意义上：从任何非预内部局部极小值出发，满足相对内部规则的BCD必然改进目标;从任何预内部局部极小值出发，BCD（不一定满足相对内部规则）从不改进目标。假设一个线性目标函数，我们表明，局部和内部局部极小形成集的可行集，这是封闭的相交下的面。受文[17]证明的启发（在文[16，§8]中重新讨论），我们证明了满足相对内部规则的BCD收敛于预内部局部极小点集。我们如何著名的收敛消息传递方法适合在我们的理论。这里，由相对内部规则诱导的局部极小条件对应于局部一致性，例如弧一致性[23]或弱树一致性[8]。我们还简述了一些新问题的应用。7560n=0n=0n=02. 主要结果假设我们想在闭凸集X <$V上最小化凸函数f：V →R，其中V是R上的有限维向量空间。为此，我们考虑以下块坐标下降的无坐标推广。 为了简洁起见，对于任何Y ∈ V，我们将使用M f（Y）来表示集合Y上f的所有全局极小点的集合。 设I是V的子空间的有限集合，表示允许的搜索方向。 具有最小值的估计xn∈ X，选择下一个估计x n+1，使得xn+1∈Mf （ X<$ （xn+In ） ）（1 ） ， 其 中 1 ∈In∈I. 显 然 ，f （ x n+1） ≤f （ xn）。的点x∈X满足x∈Mf （ X<$ （ x+I ） ）I∈ I（2）具有这样的性质，即f不能通过在X内从X沿着I的任何单个子空间移动而得到改进。我们称这样的点为f在X上关于I的局部极小值。 当I和/或（X，f）从上下文中清楚时，我们将只讨论f在X上的局部最小值或仅仅是局部最小值。注意，我们使用术语坐标下降和块坐标下降是这个公式的特殊情况。在 前 者 中 ， 我 们 有 V=Rd 和 I={span{e1} ， . . . ，span{e d}}其中e ide-记为Rd的第i个标准基向量。在后者中，我们有V=Rd和每个元素的I是一个子集的标准基础的Rd的跨度。[15，4]回忆一下，凸集的相对内部X X的仿射壳是X的拓扑内部。我们用riX表示它。我们建议修改条件（1），使得最小值总是从当前最优集合的相对内部因此，条件（1）变为xn+1∈ ri M f（X <$（xn+ In））.（三）点xn+1总是存在的，因为每个非空凸集的相对内部都是非空的。我们称一个点x∈X满足x∈riMf （ X<$ （ x+I ） ） <$I∈I（4）f在X上关于I的内部局部极小。显然，每个内部局部极小值都是局部极小值。在我们的分析中，另一种类型的局部最小值将出现：预内点局部极小它将在后面定义，现在我们只说它只是有限数量的迭代，（3）远离内部局部最小值。在有限次迭代之后，我们假设序列（In）∞包含I的每个元素无限次。为了简洁起见，我们通常只写（xn）和（In），而不是（xn）∞和（In）∞。下面的事实，证明在续集中，表明满足（3）的方法并不比满足（1）的方法更差，在精确的意义上：• 对于满足（3）的序列（xn），如果x0是内部局部极小值，则xn是对所有n的内部局部极小值（见定理11）.• 对于满足（3）的序列（xn），如果x0是预内部局部极小，则xn是某个n的内部局部极小（见推论14）。• 对于满足（1）的任意序列（xn），如果x0是预内部局部极小，则f（xn）=f（x0）（见定理13）.• 对于满足（3）的序列（xn），如果x0不是预内部局部极小值，则f（xn）f（x0）对于某个n（见定理12）.<作为说明性示例，考虑应用于简单线性规划的坐标下降。设V= R2，X=conv{（1，0），（3，0），（3，1），（0，4）}，f（x）= −e1，x（即，f在垂直方向上是恒定的，向右递减），I={span{e1}，span{e2}}。看图片：）=x5（1， 0）（3， 0）全局最小值的集合是线段[（3，0），（3，1）]，局部最小值的集合是[（3，0），（3，1）]<$[（0，4），（3，1）]，内部局部极小点的集合是{（0，4）}ri[（3，0），（3，1）]，并且预内部局部极小点的集合是{（0，4）} ri [（3，0），（3，1）]。 [（3，0），（3，1）]。 粗线描绘了满足（3）的序列（xn）的前几个点，假设序列（In）在来自I的两个子空间之间交替。当从任意点x0∈X\ {（0，4）}出发时，满足（3）的序列（xn）在有限次迭代后会留下任意非内部局部极小值，而改进的的目标函数。直观地说，这是因为当目标不能通过从I沿着任何单个子空间移动而减少时，条件（3）至少强制点移动到更高维度的X面（如果存在），从而提供（0，4）x0+ I1x0x1x0+ I0X2X3X4（3， 1x7x67561考虑一个序列（x∞n=0 满足（1）相应。（三）、到在未来的迭代中实现目标。 相反，条件（1）允许序列（xn）保持在任何（可能非内部）确保每个搜索方向总是被再次访问1对于x ∈ V和I <$V，我们记x + I ={x + y |y ∈ I}。永远的最小值当从x0=（0，4）开始时，满足（1）的序列将永远留在x0中。n）7562我们证明（定理22），在固定了（3）中极小值的选择之后，在自然的假设下，满足（3）的序列（xn）众所周知，任何凸优化问题都可以用一个线性目标的上图形式来描述：不是在x ∈ X上最小化f（x），而是在（x，t）∈ X×R上最小化t，使f（x）≤ t. 如果我们在两个公式之间传递，不难证明（内部）局部极小值和更新（1）和（3）的概念保持“相同”。 为了说明这一点，考虑X = V = Rd和坐标下降的情况。在每次迭代中，我们最小化f（x1，.- 是的- 是的，xd），而在epigraph形式中，我们最小化t subject to f（x1，. - 是的- 是的，x d）≤ t。显然，这两种形式是等价的。因此，在§3、§4和§5中，我们将假设f是线性的。3. 局部极小值众所周知，闭凸集X上线性函数f的全局极小点集Mf（X）是X的一个（暴露）面。我们展示了当地的反应。内部局部最小值也聚集到X的面。此外，类似的所有面的集合，我们表明，包含本地resp的面的集合事实上，X的唯一面在其相对内部有x。注意，（8c）是从（8a）和（8b）得出的。引理1. 设X∈V是一个凸集。 我们有x∈ ri X当且仅当对任意y∈ X，存在u∈ X使得x∈ri[ y，u].证据“ 唯如果”方向直接来自相对内部的定义。对于“如果”方向，参见，例如，[15，定理6.4]。引理2. 设X，Y∈V是闭凸集，Y 第十章设x ∈ ri Y .然后y ∈Y=⇒y ∈F（ X，x），（9a）y∈ri Y=⇒y∈ri F（ X，x），（9b）y∈rb Y=⇒y∈rb F（ X，x）.（ 9c）证据 对于（9a），设x ∈ri Y，y ∈Y. 因此，根据引理1，有u∈Y使得x∈ri[u，y]。由于x∈F（X，x）和y，u∈X，面的定义产生y∈F（X，x）。从（9 a）和（8）得出（9 b）和（9 c）的引理3. 设y，z，u∈V，x∈ ri[u，y].然后我们有ri[u，z]= ri[x，x + z − y]/=证据 由于x∈ri[u，y]，存在0<α1使得内部局部极小值在相交处是封闭的。x=（1−α）u+αy（注意，如果yu则α是唯一的）。对于x，y∈V，我们表示[x，y]= conv{x，y}={（1 − α）x + y |0≤ α ≤ 1}。（ 五）我们有ri[x，y]={（1−α）x+y|0< α<1}。（6）如果xi=y，则[x，y]是线段并且ri[x，y]=[x，y]\{x，y}。如果x=y，则[x，y]=ri[x，y]={x}。让我们回顾一下关于凸集的面的基本事实[15，4]中。一个凸集X<$V的一个面是一个凸集F<$X，使得从X开始的每个相对内部与F相交的线段都位于F中，即，x ，y∈X ，Fri[x ，y]/==⇒x ， y∈F.（ 七）一个闭凸集的所有面的集合是一个完全格，特别是它在（可能不可数的）相交下是闭的。对于一个点x∈X，设F（X，x）表示X中所有包含x的面（等价地，最小面）的交集。对于每个x，y∈X，y∈F（ X，x）⇐⇒F（ X，y）<$ F（ X，x），（8a）y∈ri F（ X，x）⇐⇒F（ X，y）= F（ X，x），（8b）y∈rb F（ X，⇐⇒F（ X，y）<$ F （8x）（ X，x）， c）其中rbX=X\riX 表示凸集X的相对边界。等价性（8b）表明F（X，x）在7563zx+ z− yv设v =（1 − α）u + αz，则v ∈ ri[u，z]。减去两个方程产生v=（1−α）x+α（x+z−y），因此v∈ ri[x，x + z − y].该图示出了引理3用于一般位置中的点（即，y，z，u不共线）：y x u在本节其余部分的定理中，字母定理4. 设x ∈ M f（X <$（x + I）），y ∈ F（X，x）.则y ∈ Mf（X <$（y + I））.证据 设z ∈ X <$（y + I）. 我们需要证明f（y）≤f（z）。由于y∈F（X，x），根据引理1，存在u∈X使得x∈ri[u，y]。根据引理3，有一点v∈ri[ u，z]<$ri[ x，x+ z− y].由于z，u ∈ X，通过X的凸性，我们有v∈ X。 由于z − y ∈ I，我们有v ∈ x + I。 由于x ∈ M f（X<$（x + I）），我们有f（x）≤ f（v），因此f（x）≤ f（x + z −y）。由于[x，x + z − y]=[y，z]+ x − y ， 通过f的线性，我们有f （ y ）≤ f（z）。7564推论5. 如果x是局部极小值，则F（ X，x）是局部最小值。让我们强调，如果x和y是局部最小值，y∈F（X，x），则我们可以有f（y） f（x）。4. 迭代的效果本文在各种假设下证明了满足条件（1）或（3）的序列（xn）引理6. 设x ∈ ri M f（X <$（x + I）），y ∈ F（X，x）.则M f（X <$（y + I））<$F（X，x）.证据 设z ∈ Mf（X <$（y + I））. 由定理4我们有y∈Mf（X<$（y+I）），因此f（z）=f（y）。 由于y∈F （ X ，x ），根据引理1 ，存在u∈X 使得x∈ri[u，y]。根据引理3，有一点v∈ri[ u，z]<$ri[ x，x+ z− y].由于z，u ∈ X且z − y ∈ I，我们有v ∈ X <$（x +I）。由于[x，x + z − y]=[y，z]+ x − y，通过f的线性我们有f（v）= f（x），因此v ∈ M f（X<$（x + I））。引理2产生v∈F（X，x）。由于z，u∈X，面的定义产生z∈F（X，x）。定理11. 设（xn）是满足（3）的序列，x0是一个内部局部最小值。对于所有的n，以下成立：f（xn）=f（x0），xn∈ riF（X，x0），且xn是内部局部极小值.证据假设对于某个n，xn是内部局部极小值。 考虑（3），通过引理2，我们有xn+1∈riF（X，xn）。根据推论9，xn+1是内部局部极小值。 由于xn，xn+1∈ ri M f（X <$（xn+ In）），我们有f（xn+1）= f（xn）.定理12. 设（xn）是满足（3）的序列，对所有n，f（ xn ） =f （ x0 ） . 则 以 下 成 立 ： xn∈F （ X ，xn+1），xn是某个n的内部局部极小值，x0是预内部局部极小值.引理7. 设x∈M f（X<$（x+I））<$F（X，x）.然后x∈ri Mf（ X<$（ x+ I））.证据 由于f（x n+1个）≤f（xn）=f（x0）对于所有n，我们有证 据 设 u∈Mf （ X<$ （ x+I ） ） . 因 此 f （ u ） =f（x）。此外，根据引理1，存在v∈F（X，x）使得x∈ri[u，v]。 由于u ∈ x + I，我们有v ∈ x + I。通过f的线性，我们有f（v）= f（x），因此v ∈M f（X <$（x + I））。由引理1，x∈ ri M f（X<$（x + I））.定 理 8. 设 Y ≠X 。 设 x ∈ ri M f （ X <$ （ x +I）），f（x n+1）= f（x n）对所有n。将其与（3）结合得到xn∈Mf（X<$（xn+ln））. 因此，对于每个n，有两种可能性：• 若xn∈riM f（X∈（xn+ln）），则根据引理2，我们有一个xn∈riF（X，xn+1）.利用定理8，我们证 明了对所有的I ∈ I，X∈ ri M f （X<$（x n+1+ I）），x n +1∈riM f（X<$（x n+I））.所有x∈ Y。设y∈ri（y + I））。不证据由于G=x∈Y F（X，x）. 则y ∈ ri Mf（X ∈ Mx∈Y F（X，x）是X的一个面，我们有• 若xn∈rbMf（X∈（xn+ln）），则根据引理2，我们有一个xn∈rbF（X，xn+1）.在任一情况下，xn∈F（X，xn+1）。更进一步，如果xn不是一个y∈riG当且仅当G=F（X，y）.根据定理4，我们有y∈Mf （ X<$ （ y+I ） ） 。 利 用 引 理 6 ， Mf（ X<$ （ y+I ） ）<$G. 由引理7 ， y ∈ ri M f （X<$（y + I））.推论9. 设Y ∈ X是一个内部T局部极小点集。则面x∈Y F（X，x）的每个相对内点都是内局部极小点。推论10. 如果x是内部局部极小值，则ri F（X，x）的每一点都是内部局部极小值。本节的结果可归纳如下：• 我们称X的一个面为局部极小面，如果它的所有点都是局部极小点。由于X的面集合在交下是闭的，因此从推论5可以得出X的所有局部极小面集合（假设f和I固定）在交下是闭• 我们称X的一个面为内部局部极小面，如果它的所有相对内部点都是内部局部极小像。推论9表明X的所有内部局部极小面的集合在交下是闭最后，我们定义了另一种类型的局部极小值：点x是预内部局部极小，如果x∈F（X，y），对于某个内部局部极小y。7565内部局部最小值为一些n，然后在一些有限第二种情况发生（回想一下，我们假设（I n）包含I 的 每 个 元 素 无 限 次 ） ， 因 此 xn∈rbF （ X ，xn+m ） 。 但 这意味着dimF（X， xn+m） >dimF（X，xn）。如果xn不是任何n的内部局部极小值，对于某个n，我们会有dimF（X，xn）>dimX，这是不可能的。由于xn∈ F（X，xn+1）对于所有n，面F（X，x0）<$F（X，x1）<$···形成非减链。特别地，x0∈ F（X，xn）对所有n。 由于x n是某个n的内部局部极小，x0是预内部局部极小。定理13. 设（xn）是满足（1）的序列，使得x0是预内部局部极小值，即， x0∈ F（X，x），其中x是内部局部极小值. 则对所有的n，我们有xn∈ F（X，x）和f（xn）= f（x0）.证据 我们将对n使用归纳法。 这个主张在n=0时成立。我们将证明对每个n， xn∈F（X，x）蕴涵xn+1∈ F（X，x）且f（xn+1）= f（xn）.设xn∈F（X，x）.根据引理1，存在u∈X使得x∈ri[xn，u]。根据引理3，有一点v∈ri[u，xn+1]<$ri[x，x+xn+1−xn].7566由于u，xn+1∈ X，我们有v ∈ X。 由于xn+1−xn∈ In，我们有v ∈ x + I n。 由于x ∈ Mf（X <$（x +In）），这意味着f（x）≤f（v）. 由于[x，x+xn+1−xn]=[xn ， xn+1]+x−xn ， 根 据 f 的 线 性 性质，我们有f（xn）≤f（xn+1）. 但从（1）也f（xn+1）≤ f（xn），因此f（xn+1）= f（xn）。这意味着f（v）= f（x）。 由于x ∈ ri M f（X<$（x + I n）），我们有v ∈ M f（X<$（x+In））。 根据引理2，v ∈ F（X，x）.由于u，xn+1∈ X和v ∈ F（X，x），面的定义给出xn+1∈F（X，x）.推论14. 设（xn）是满足（3）的序列，使得x0是预内部局部极小。则存在n设d：X2→R+是X上的度量. 让d（Y，x）=infd（x，y）（14）y∈Y表示点x∈X到集合Y<$X的距离。引理17. 对于每个Y<$X ，函数d （Y ，·）是Lips-chitz。证据对于任意的x，y∈X和z∈Y，我们有d（Y，x）≤d（x，z）≤d（x，y）+d（y，z）。取inf在z∈Y的右边，得到d（Y，x）≤ d（x，y）+d（Y，y）。交换x和y得到|d（Y，x）− d（Y，y）|≤ d（x，y）。使得xn是内部局部最小值。证据首先应用定理13，然后应用定理12。推论15. 对于满足（3）的序列（xn），x0是预内部局部极小值当且仅当f（xn）= f（x0）。证据“如果”方向遵循定理12。The ‘only-if’ directionfollows from Theorem5. 收敛在这里，我们研究序列的收敛性引理18. 一个实数序列是收敛的，如果它是有界的，并且有唯一的聚点。证据 设x是有界序列（xn）的聚点.假设（xn）不收敛于x。 则对于某个n> 0，对于每个m，有n > m，使得|x n−x|>。所以（xn）有一个子序列（yn），使得|yn− x|>所有n。当（yn）有界时，它有一个收敛子序列（zn）。但是（zn）显然不能收敛到x，这是一个矛盾。定理19.如果序列（f（xn））是收敛的，满意（3）。 我们首先给出了一个一般的收敛结果然后将其应用于我们在5.2节中的情况。序列（xn）有界，则limn→∞ d（X_n，x_n）= 0.5.1. 一般收敛结果设p：X→X和f：X→R是连续函数。设（xn）是一个序列，满足证据由于函数d（X，·）是Lipschitz的，序列（xn）是有界的，所以序列（d（X，xn ））是有界的。因此，它有一个收敛的子序列，（d（X，yn）），其中（yn）是（xn）的子序列。通过x n+1= p（x n）<$n = 0，1，. - 是的-是的- 是的（十）引理18，它足以表明，limn→∞ d（X_n，y_n）= 0.让X∈ X={x ∈ X |f（p（x））= f（x）}。（十一）作为（xn）的子序列，序列（yn）是有界的.因此，它有一个收敛的子序列3，（zn）。因此，在本发明中，定理16. 如果序列（f（xn））∞是收敛的，X= lim中文（简体）则每个聚类点2n=0序列（xn）在X中。n→∞证据 设x是序列（xn）的聚类点，即，是（xn）的聚类点。 我们主张对于严格递增序列（kn），我们有0 =d（X，x）=limn→∞d（X，zn）=limn→∞d（X_n，yn）.Limn→∞ x kn = x.（十二）第一个等式由定理16成立。第二将连续映射p应用于（12）得到：等式通过应用连续函数获得.普林Σxkn = lim p（xkn）=limx kn+1=p（x）.（十三）d（X，·）到（15）。 最后一个等式成立，因为∗n→∞n→∞n→∞序列（d（X，yn））是收敛的，因此其子序列我们证明了f（x）= lim f（xkn）= limf（xn）=limf（ xkn+1）7567（d（X，z n））收敛于相同的数。注意，定理19并不意味着（xn）收敛于n→∞=f（p（x））。n→∞n→∞任何一点，它只说（xn）收敛到集合X。通过将连续函数f应用于等式（12）和（13），第一个等式和最后一个等式成立。 第二个和第三个等式成立，因为序列（f（x n））收敛，因此它的每个子序列收敛到相同的数。2.序列的聚点（也称为极限点或聚点）是其收敛子序列的收敛点。它也不意味着映射p有一个不动点。 我们-注：定理19仍然成立，如果函数d（X<$，·）被替换为任何Lipschitz函数e：X→R，使得e（x）=0当且仅当x∈X<$。在[17]中提出了一个这样的函数用于最大和扩散，也参见[16，§8]。3因为（xn）包含在有限维实向量空间V的闭凸子集X中。7568我IJ5.2. 相对内部规则的收敛性为了将这一结果应用于满足相对内部规则的序列，我们通过假设对于每个I∈ I，给出满足以下条件的连续映射pI：X→X来确定（3）中极小值的选择：pI （ x ） ∈riMf （ X<$ （ x+I ） ）（ 16）.我们进一步假设I的元素在（3）中，以（准）循环顺序访问 在一个这样的迭代循环中，I的所有元素都被访问（一些可能不止一次），以由满射映射σ：{1，. - 是的- 是的 ，m} → I，其中m ≥|我|. 迭代循环的动作因此由映射描述由于序列（f（xn））是非增的，如果f在X上有下界，则它是收敛的。简单地说，序列（x n）是有界 的，如 果 集 合X 是 有 界 的 。 但 是 ， 由 于（ f（xn））是非增的，因此有一个较弱的（因此更有用的）充分条件：X0={x ∈ X |f （ x ） ≤ f （ x0 ） }（ 19）是有界的6. MAP推理的应用在这里，我们展示了上述一般结果如何mani-在收敛的消息传递方法中进行MAP推理。图模型（具有成对因子）中的MAP推断导致了以下问题p σ= p σ（1）<$··<$p σ（m）。（十七）最后，我们将§5.1中的映射p定义为：F（ θ）=maxx：V→LΣΣi∈Vθi（xi）+Σ{i，j}∈EΣθij（ xi，xj）（二十）其中（V，E），E。V是无向图，L是p=（pσ）k+1，其中k=dimX （18）2一个标号集，θi：L→R和θij：L2R是重量(i.e.、p是pσ与自身的复合（k+1）次）。在定理12中，假设序列（In）是连续的，对I的每个元素都进行无限次的迭代。但我们的（拟）循环序具有更强的性质：I的每个元素总是在至多m次迭代后再次被访问因此，定理12可以加强如下：定理20. 设x∈X，f（p（x））=f（x）.则p（x）是内部局部极小，x是预内部局部极小。证据 类似于定理12的证明，它认为：• 如果x是内部局部极小值，则x∈函数（采用θ ij（x，y）= θ ji（y，x））。通过替换权重θ来保持（20）的目标其中重新参数化的权重θδ由下式给出：Σθδ（x）=θi（x）−δij（x），（21 a）j∈Niθδ（x，y）=θij（x，y）+δij（x）+δji（y），（21b）其中δ是“消息”δ ij的向量：L → R（i ∈ V，j ∈ Ni），N i = { j ∈V| {i，j}∈E}是顶点i的邻居的集合。特别地，对于所有δ，F（θ）= F（θ δ）。许多基于LP的MAP推理算法在reparam上最小化（20）上的凸分段仿射上界。化。两个这样的界限是riF（X，pσ（x））.• 如果x不是内部局部极小，则x∈rbF（X，pσ（x）），所以dimF（X，pσ（x））>dimF（X，x）.U1（θ）=Σi∈V、maxθi（x）+x∈LΣ{i，j}∈Emaxθij（x，y），x，y∈L、因此，如果f（p（x））=f（x）且p（x）不是内部U2（θ）=maxmax maxθi（x），maxmaxθ ij（x，y）.局部最小值，我们会有dimF（X，p（x））>dimX，这是一个矛盾。由于x∈F（X，p（x）），x是预内部很显然，i∈Vx∈L{i，j}∈Ex，y∈L局部最小值结合定理13和定理20，我们看到集合（11）包含所有的前内部局部极小值，并且只有它们。目标函数f在V上是凸的，因此是连续的。对于由（10）和（18）定义的序列（xn），定理16和19因此意味着以下内容：推论21. 如果序列（f（ xn））是收敛的，则序列（xn）的每个聚点都是预内部局部极小值。推论22. 若序列（xn）有界且序列（f（xn ））收敛，则（xn）收敛于拟内部局部极小点集.7569F（θ）≤U1（θ）≤nU2（θ）其中n=|V|+的|E|.在δ上最小化U1（θδ）或U2（θδ）可以被视为（20）的对偶LP松弛。如果图（V，E）是 连 通 的 ， 在 最 佳 情 况 下 我 们 有 U1 （ θδ ） =nU2（θδ），所以这两个松弛是等价的。对于细节，参见，例如，[23，22]。已知[23]这些问题的坐标方向局部极小值可以由弧一致性来表征。对于权重向量θ，通过以下方式定义布尔向量θ<$：θ<$i（x）=[[θi（x）=maxθi（x′）]]，x′θ<$ij（x，y）=[[θij（x，y）=maxθij（x′，y′）]]。x′，y′7570IJIJ222IJ我i ijj2ii一个布尔向量θ<$是弧相容的，如果_θ<$i（x）=θ<$ij（x，y）（22）y6.2. MPLPMPLP更新[2]选择边{i，j} ∈E并改变变量δij，δji，使得等式4对所有i∈V，j∈Ni，x∈L（其中n表示析取）.δΣδ δΣ我们说θ<$有一个非空弧一致闭包当且仅当它有一个非空弧一致子集（即，有一个非-θi（x）=maxθij（x，y）+θj（y），（25a）yδΣ δ δΣ零弧一致布尔向量θ<$′ ≤θ<$，其中≤表示θj（y）= maxθij（x，y）+θi（x）X（25b）组件方面）。如果θ<$δ是弧相容的，则δ是上述问题的内部局部极小值对所有的x，y∈L都成立。 此更新最小化当θδ（x，y）≤0时，U1（θδ）在变量δij，δji上的分布若θ<$δ有非空弧一致闭包，则δ是预内部局部极小值因此，（预）内局部极小推广了弧一致性.6.1.最大和扩散最大和扩散更新[17，23]选择一个可变的δij（x）并改变其值，使得等式θδ（x）=maxθδ（x，y）（23）（事实上，（25）意味着maxx，yθ δ（x，y）= 0）。与最大和扩散相比，MPLP更新可以在该问题的极小集的相对边界上取一点，则不满足相对内点规则。但请注意，在MPLP不动点（当（25）对所有{i，j}∈E和x，y∈L成立时），我们有θ<$δ（x）=_伊伊伊变得满足。 我们证明了这使U2（θδ）在δij（x）上，满足相对内部规则。的确，U2（θδ）=max{a−δij（x），b+δij（x），c}，（24）`˛¸X `˛¸Xθδ（x）maxθδ（x，y）伊伊日式中a、b、c为常数w.r.t.δ ij（x）。最大和扩散更新通过选择δ ij（x）使得a−δij（x）=b+δij（x）来最小化δ ij（x）上的（24），其具有唯一解δ ij（x）= 1（a-b）。 当（24）在δ ij（x）上的极小集是一个区间（而不是单点）时，该点位于该区间的中间，因此在其相对内部。我们观察到，修改更新使得δ ij（x）在最优范围内的其他地方（而不是中间）选择间隔对算法的影响不大。然而，选择δ ij（x）作为最优区间的端点之一的更新通常会陷入非常差（非预内部）的局部最小值，即使是非常小的实例。推论22假定在扩散过程中的信息向量序列δ虽然这一直被观察到，但证据是未知的。这个技术问题可以解决如下：不是在δ上最小化U2（θδ），而是在θ′∈X上最小化U2（θ′），其中X由所有可能的δ的向量θδ组成。可以看出，这一重新--对任意i∈V，j∈Ni，x∈L. 这意味着，θ<$δ的相容c-y闭包是非空的，因此θδ是预内部局部极小值。可以证明（如果p是MPLP更新的组成，如§5.2所示），（11）仍然是前内部局部极小值的集合，因此定理19适用。6.3. 波茨问题如果θij（x，y）=−[[x=y]]在（20）中，我们讨论Potts问题。在这种情况下，可以简化对偶LP松弛[14]：最小化δ上的U1（θδ），δij（x）+δji（x）=0，（27 a）−1≤δ ij（x）≤1。（27b）尽管忽略这些约束不会改变U1（θδ）的最佳值，但尝试设计一种包括它们的坐标下降方法。 这是一个挑战，因为据我们所知，迄今为止还没有提出用于具有不等式约束的问题（这里，（27 b））的收敛消息传递方法约束（27）意味着对于所有的，max x，y θ δ（x，y）=0{i，j} ∈E，从而可以忽略U1（θδ）在对图（V，E）进行任意定向（使得E<$V2）之后，我们可以通过仅对（i，j）∈E保留变量δij（x）来消除约束（27a），并将（21 a）写为公式保持了相对内部规则。（19）是一种水平集X0={θ′∈X|U2（θ′）≤u0}其中u0是θδ（x）=θi（x）+δij（x）−δ ji（x）。（二十八）上界的初始值。这个集合的边界是一个简单的论点：如果θ δ的某个分量减小（i，j）∈E我们建议更新（j，i）∈E改变δ，那么，通过（21），不可避免地会有一些其他分量增大 因此，推论22适用，表明向量θδ收敛于X上U2的一个准内部局部极小值。δij（x）：=1h（maxθδ（y）−θδ（x）+δijy/=x1δ δ（x））−7571在最大和扩散的任何不动点θδ处（其中（23）全局成立），θ<$δ是弧相容的，因此θδ是内部局部最小值尽管根据经验，向量θδ收敛于一个固定点，但对此的证明是未知的[23]。h（maxθj（y）−θj（x）−δij（x））（29）y/=x4我们以不同于[2]的形式编写MPLP更新。简单的代数表明（见补充材料），（25）意味着如[2，命题1]所述的更新。27572我我我J我其中h（t）=min{1，max{t，-1}}是t的投影，并且（34），F（θ）=max{b，Fi（θ）}其中b不依赖于2 2在区间[-1，1]上。 可以证明，这种更新θ i。因此，我们认为，2 2最小化服从（27 b）的U1（θδ），并满足相对内部规则 我们观察到，在玩具图像分割maxF（θs）= max{max（as+θs），c}S实例（4个标签，20×20像素），更新（29）收敛s∈S 联系我们Fi（θs）全局最优和运行时类似于max-sum dif，其中as和c不依赖于θs。这是我的-融合见补充证明和细节。SI在变量（θi）s∈S上满足（31）+（33）的条件下最小化是很容易证明，如果as+θs6.4. 最大边际平均值si在这里，我们考虑问题（20）的拉格朗日分解框架[6，10]，理解它也包括TRW-S [8]。我们将（20）写成F（θ）= maxθ，φ（x）θ（30）x∈LV其中φ：LV→ {0，1}I是合适的特征映射，I是特征集（标签和标签对）[21]。（30）的上界是通过分解成子问题构造子问题s∈S具有权θs∈RI.假设Σθ=θs（31）s∈S交换（30）中的max和sum，我们得到两个边界. ΣΣΣ对所有s∈Si相同，确定变量（θi）s∈S唯一的，这些变量是一个解决方案，这个问题的最优集合的相对内部。对于这三个子问题，预内部局部极小值对应于[8]中的弱树一致性。对于我们由（31）+（33）给出的可行集，水平集（19）由§6.1中类似的参数限制，因此推论22表明收敛到前内部局部极小值集。7. 加权顶点覆盖的应用一个重要的问题是，我们的理论是否可以导致一些新的凸问题的大规模优化的实用算法作为这个方向的初步步骤，我们提出了一个坐标下降更新的LP松弛的最小顶点覆盖问题。这个LP松弛读F（ θ）= F公司简介F（θ s）≤|S|maxF（θ s）.（三十二）s∈SΣminθi xiS.T.Xi+xj ≥1<${i，j}∈E（35）s∈Ss∈Sx：V→[0，1]i∈V子问题的权重受以下约束：θs=0s∈S，i∈I\Is（33）其中（V，E）是具有节点权重的无向图θ：V→R+。双重问题是我其中每个集合Is∈I使得函数F（θs）易于计算（例如，可以定义（V，E）的子树。Maxy：E→R+.Σ{i，j}∈Eyij+ Σi∈V、min θi− Σj∈Ni，Σyij，0. （三十六）我们希望最小化变量θs服从（31）和（33）的上界（32）之一对于由（20）诱导的I和φ以及在单变量yij≥0，我们建议更新yij=1（max{θi−a−j，0}+ max{θj−a−i，0}）（37）集合Is（如图像的行和列），数字F（θs）对于所有s∈S总是相同2其中a−j我Σ=k∈Ni\{j}伊伊J对于a−i对称。同时保持（31）和（33）。 因此，两个上（32）中的边界在最佳处重合。限制为单个变量的对偶是分段仿射有断点θi−a−j和θj−a−i的函数。展示I j在[8，6]中， 上界由“max”最小化边际平均 函数的最大边际与特征i∈I相关联的<$θ，φ（x）<$是数更新（37）满足相对内部规则，则满足来分析这些断点的迹象的可能情况。该方法对于所有41个最小顶点覆盖实例都达到了对偶LP松弛的全局最优性，Fi（ θ）=maxx：φi（x）=1φθ，φ（x）（三十四）[24]，其中顶点权重被i.i.d.采样。高斯分布的绝对值在所有实例中，更新选择i∈ I和改变变量方法比单纯形算法速度快。 细节可以（θs）s∈S使得最大边际Fi（θs）变得相同可以在补充中找到。我7573对于所有的s∈Si，其中Si={s∈S|i∈I s}。我们表明该更新最小化maxsF（θs）over（θs）s∈S，sat-谢谢。这 项 工作得到了揭示了相对内部规律。我我捷克科学基金会项目19- 09967 S，OP VVV由式（34）可知，Fi（θ）线性地依赖于θi：Fi（θ）=a+θi其中a不依赖于θi。 由（30）项目CZ.02.1.01/0.0/0.0/16 019/0000765和CTU学生补助金SGS 19/170/OHK 3/3 T/13。7574引用[1] JeromeFriedman，Tre