概率图模型是计算机视觉、模式识别、自然语言处理和生物信息等领域中极为重要的结构化数据建模处理工具,MAP推理是概率图模型中最为关键的瓶颈问题之一,也是概率图模型中的研究热点问题。由于概率图模型MAP推理通常是NP难问题,需要进行松弛求解。在众多松弛方法中,线性规划松弛通常相对其他松弛方法具有更高的精度。本文基于线性规划松弛模型,对概率图模型MAP推理中的模型和方法进行了较为深入的研究,完成的主要成果与创新工作概括如下。(1)现有高阶概率图模型线性规划松弛模型和消息传递框架中,通常存在较多的冗余约束算和冗余运算。针对这两个问题本文:a)在分析比较现有线性规划松弛模型的基础上,针对高阶概率图模型提出一种新的线性规划松弛模型,并基于该模型提出一种冗余约束消除方法,能够有效消除冗余约束;b)基于提出的线性规划松弛模型提出一种新的消息传递框架,该框架通过直接更新重整参数而非消息变量减少了冗余运算。将冗余约束消除方法和消息传递框架相结合,可以提出一系列消息传递方法。在生物信息、图像分割、图像匹配等领域的实验表明,这些方法相对现有方法具有速度较快。(2)图像重建、M-最优求解、二次背包问题等实际问题中需要对作用于随机变量的全局约束条件进行建模,而传统概率图推理模型和方法难以对全局约束条件进行建模。针对这一问题,本文首先建立了一种约束下的概率图模型推理模型,利用该模型可以对机器学习、计算机视觉和组合优化中很多重要的问题进行建模;其次针对该推理模型提出一种约束下的线性规划松弛模型,并利用复杂性理论和对偶优化理论分析得出了该模型在一些特定情形下的误差界。(3)针对通用软件——如CPLEX等对约束下概率图模型求解效率低,求解速度慢的问题,基于对偶分解框架和对偶优化理论提出一种扩展消息传递方法,将复杂的约束下组合优化推理问题分解为简单的消息变量更新问题和约束变量更新子问题,并对消息变量和约束变量进行交替更新,逼近原问题的最优解。在人工随机生成的数据和前景检测、图像重建、M-最优问题和二次背包问题等领域的真实数据验证了方法的有效性,实验表明,所提出方法常常在精度和速度均优于传统方法和CPLEX商业求解软件。(4)特征匹配问题是计算机视觉和机器学习中极为重要的基础性问题,而传统高精度求解方法如基于凹凸松弛过程的因子化图匹配方法以及基于概率图模型的对偶分解方法等求解速度较慢。针对这一问题,提出一种新的二阶特征匹配问题对偶分解框架,将复杂的二阶图匹配问题分解为容易求解的二部图匹配子问题和消息传递子问题,并提出一种“匈牙利-消息传递”方法,利用匈牙利算法和消息传递方法对这两个子问题进行交替优化求解,实现对二阶特征匹配问题的高精度近似求解。理论分析表明:该方法相对传统方法具有更好的时间复杂度,且在一定条件下能够给出图匹配问题的精确解;实验结果表明:该方法相对目前公布的高精度求解方法具有更高的精度和更快的速度。(5)超图匹配相对二阶特征匹配方法能够对更为复杂几何结构进行建模,是计算机视觉中对复杂非刚性形变物体进行匹配的重要方法。传统方法的求解精度通常较低,利用高阶概率图模型可以对超图匹配问题进行较高精度的求解,但求解速度慢,难以满足大规模超图匹配问题的应用需求。针对这一问题,本文提出一种动态规划——二部匹配消息传递方法,将复杂的高阶匹配问题分解为容易求解的二部匹配问题和一些局部非线性匹配问题。利用匈牙利算法对二部匹配问题求解,并提出一种动态规划消息传递方法对局部非线性匹配问题进行求解。通过对两类问题的交替迭代优化,快速得到质量较高的近似解。实验表明,所提出的方法的性能优于当前公布的超图匹配方法。