内点法 内点法英語Interiorpoint methods也称为障碍法英語barrier methods是解决线性和非线性凸优化问题的一类算法 内点法由前苏联数学家伊伊迪金I I Dikin于年发现并于世纪年代中期在美国重新发明年纳伦德拉卡玛卡Narendra Karmarkar开发了一种称为卡玛卡算法的线性规划方法该算法在可证明的多项式时间内运行并且在实践中也非常高效它能够解决超出单纯形法能力的线性规划问题与单纯形法不同它通过遍历可行区域的内部来达到最佳解该方法可以推广到基于用于编码凸集的自和谐障碍函数的凸规划 通过转换为代码形式任何凸优化问题都可以转化为最小化或最大化凸集上的线性函数安东尼V菲亚科加斯P麦考密克等人在世纪年代初研究了使用屏障对可行集进行编码并设计屏障方法的想法这些想法主要是针对一般非线性规划而开发的但后来由于针对此类问题存在更具竞争力的方法例如顺序二次规划而被放弃 尤里涅斯捷羅夫和阿爾卡迪內米羅夫斯基提出了一类特殊的障碍可用于编码任何凸集它们保证算法的迭代次数受解的维数和精度的多项式限制 尚博勒波克算法于年推出是一种通过最小化非平滑成本函数来有效解决凸优化问题的算法涉及原对偶方法primaldualapproach 卡玛卡的突破重振了内点方法和障碍问题的研究表明可以创建一种以多项式复杂性为特征的线性规划算法而且与单纯形法具有竞争力哈奇延Khachiyan的椭球法已经是一种多项式时间算法然而它太慢了因而没有实际意义