本研究分析了现有的基于不可满足子公式识别的最大可满足性问题（MaxSAT）算法，并提出了几个关键性优化和新的替代算法，这些优化和新算法在实际应用中的 MaxSAT 实例上提供了显着的性能提升。

Dec, 2007

提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法，该算法基于因数分解 X=YY^T，其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何，并得出了二阶优化方法。此外，文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。

Jul, 2008

提出了一个精确算法，决定在时间复杂度 O (m)+2^{O (k^2)} 内，对于每个固定的 r≥2，是否存在一个满足至少 ((2^r-1) m+k)/2^r 个子句的布尔表达式，从而解决 Mahajan 等人未解决的开放问题。该算法基于一个在多项式时间内缩小问题规模的数据约减过程，并介绍了一种新的从参数化问题到另一个参数化问题的生物核化方法，并将其应用于证明所提出的问题具有多项式大小的内核。同时，将定参数可跟踪性和多项式大小内核的结果推广到更广泛的布尔约束满足问题。

Jul, 2009

本文提出了一种低秩坐标下降方法，用于结构半定规划，该方法是极其简单易于实现的，没有自由参数，并且通常比现有技术的优化性能提高一个数量级或更好的性能。我们证明该算法是严格下降的，收敛到一个临界点，并且对于足够秩的情况，所有非最优临界点都是不稳定的。此外，我们证明了通过选择合适的步长，该算法几乎可以在局部线性速率下以随机初始化收敛到半定规划的全局最优解，这是第一个证明在不做任何假设的情况下，在球形流形上达到全局最优的低秩半定规划方法。我们将算法应用于两个相关领域：解决最大割半定松弛和解决最大可满足性松弛（我们还简要考虑了其他应用，如学习单词嵌入）。在所有设置中，我们都在各个方面展示了比现有技术的实质性改进，从而扩大了可以使用半定规划方法解决的问题范围和规模。

Jun, 2017

本文提出了一种新的路线，即通过引入可微（平滑）的最大可满足性（MAXSAT）求解器，将逻辑推理纳入更大的深度学习系统的循环中，从而在端到端学习系统中学习有挑战性的问题的逻辑结构，表现出集成逻辑结构于深度学习的潜力。

May, 2019

本文介绍了解决半定规划在机器学习、控制和机器人领域中可扩展性问题的最近方法，包括利用问题结构（如稀疏性和对称性）、生成低秩近似解决方案、更可扩展算法、以及将可扩展性与保守性相妥协的方法，并提供相应文献入口和实例，最后列出了实现本文所讨论的方法的软件包清单。

Aug, 2019

该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT，用于解决不同类型的布尔可满足性问题，包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数，构建了统一的整数规划表示方法，并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构，在 SAT 问题上应用了蒙特卡罗树搜索（MCTS）方法，证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明，该方法能够剪枝不必要的搜索空间，找到问题的最优布尔赋值，同时为 SAT 问题的监督学习方法提供多样的标签。

Dec, 2023

通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。

Dec, 2013

我们研究了涉及具有凸目标函数（平滑或非平滑）和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题，这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况，在这种情况下，问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果，证明在这些情况下，众所周知的 Extragradient 方法，在在接近最优原始 - 对偶解的位置初始化时，使用低秩奇异值分解（SVD）将收敛到约束优化问题的解，并具有标准收敛速度保证，而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。

Feb, 2024

本文提出了一种新的框架 UpMax，将分割过程与 MaxSAT 解决算法分离，使用户能够根据问题来提出分割方案，证明分割对于基于不可满足性的 MaxSAT 算法的性能有很大的影响。

May, 2023