本文提出了一种用于找到 NP 难问题下离散图像模型 MAP 推理的部分最优解的算法，并通过使用一个线性规划松弛的精确求解器，标记出一些标签作为其最大可能的标签。

Aug, 2015

本文提出了一种新的多项式时间算法来解决最小化无向图模型的能量问题，利用凸松弛方法得到部分最优非松弛积分解，并采用迭代修建策略优化算法，相较之前的方法表现更好。

Oct, 2014

本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

Sep, 2017

使用双重消息传递算法对线性规划进行松弛，通过迭代选择具有保证改进的集群，解决集群选择问题，成功地在蛋白质侧链放置、蛋白质设计和立体化问题中找到了最有可能的 MAP 配置。

Jun, 2012

采用拉格朗日松弛技术，将不可解的估计问题重新定义为更可处理的图上问题，通过相应约束的松弛最大化优化问题，并应用于离散和高斯图模型的 MAP 估计及优化问题中。

Sep, 2007

本研究探讨离散马尔可夫随机场的最大后验概率推断的非凸连续松弛，研究表明该松弛对于任意马尔可夫随机场都是紧密的，并且可以通过简单的块坐标下降算法轻松地达到其离散稳定点。我们进一步研究了使用基于交替方向乘子法 (ADMM) 的多线性分解框架的高效解决方案，该方案在许多现实世界的问题上的实验证明，ADMM 比其他非凸松弛方法表现更好，并且在不同设置中与最先进的 MRF 优化算法比较时表现优异。

Feb, 2018

提出了一种基于松弛的近似推断算法，用于在二元成对马尔可夫随机场中采样接近最大化后验的配置，应用于多个限制波尔兹曼机中的 MAP 推断任务，并使用底层采样器估算了限制波尔兹曼机的对数划分函数，并与其他基于采样的方法进行了比较。

Dec, 2013

研究了一种计算 Markov 随机场上最大后验概率的最优配置的方法，通过将原始分布分解为树形分布的凸组合来得到上限，提出了两种尝试获得紧密上限的方法，并建立了模式搜索问题 LP 松弛和最大乘积（最小和）消息传递算法之间的联系。

Aug, 2005

本文提出了一种新的基于图的方法来进行语义解析，解决了文献中观察到的两个问题：(1) seq2seq 模型无法完成组合泛化任务；(2) 使用短语结构解析器的先前工作无法涵盖树库中观察到的所有语义解析。我们证明了两个优化算法的正确性，用基于约束平滑和条件渐变的方法近似解决这些推断问题。实验证明，我们的方法在 Geoquery、Scan 和 Clevr 上都具有最先进的效果，包括在测试组合泛化的过程中。

Feb, 2023

本文介绍了结构预测在计算机视觉和自然语言处理等领域中的应用，主要是通过最大后验推断或整数线性规划来进行预测，但由于需要复杂的打分函数来获得准确的预测结果，因此学习和推断通常需要使用近似求解器。我们提出了一个理论解释，解释了基于线性规划松弛的近似算法在真实场景中的紧密性，并表明使用 LP 松弛推断进行学习有助于保证训练示例的整整性。

Nov, 2015