内点算法六十年
2018年7月8日到11日，欧洲运筹学年会在西班牙瓦伦西亚举行，来自60多个国家的2000多名运筹学领域的专家学者参加了此次大会。其中，来自美国里海大学工业与系统工程系的Tamas Terlaky讲座教授作了题为“内点算法的60年：从边缘到光荣”的大会报告。Terlaky教授回顾了内点算法在各个阶段的发展以及遇到的问题，并且结合优化与大数据、人工智能等领域，探讨了未来优化的发展。
首先，Terlaky教授举了若干生动有趣的例子，从“蜘蛛抓苍蝇的最短路线”、“水流沿着最速下降方向流动”到“哥尼斯堡七桥问题”，来说明优化问题在生活中随处可见。从17世纪到19世纪，最优化理论开始萌芽和发展。17世纪，Newton给出了线性与非线性方程组的求解算法，接着Lagrange、Gauss、Fourier、Farkas等大数学家在求解带有等式约束的优化问题、消元法、择一性定理等方面做出了杰出的工作。
线性优化
线性优化是最优化理论中非常重要的一类优化问题，在经济管理、金融、军事、交通运输、工业等领域有着广泛的应用，为合理地利用有限的人力、物力、财力等资源作出最优决策提供科学的方法。很多数学家都对线性优化的诞生与发展做出了贡献。自从Farkas（1896）提出有限个线性系统的择一性定理之后，后续很多数学家做了一系列关于线性优化的工作，例如，Pousson（1911）与Motzkin（1934）提出的Fourier-Motzkin消元法、Haar（1932）证明了对于无限个线性系统的择一性定理等等。其中，1938年苏联数学家Kantorovich提出的线性规划模型的经济学概念，一开始并没有受到足够的重视。后来大家发现了其重要性，Kantorovich也因此获得了诺贝尔经济学奖。1947年数学家Dantzig提出了求解线性规划问题的单纯形法，奠定了线性优化这门学科的基础。该算法是公认20世纪10大算法之一。还有不少数学家也在线性优化方面做出了重要工作，例如Karush、Hitchkock、Koopmans等等。
标准形式的线性优化问题如下：
（P）
其中
，且Rank(A)=m，它的对偶问题是
（D）
根据线性规划的原始对偶问题，我们可以得到一些相关的重要结论。
性质：若
是原问题（P）的一个可行解，
是对偶问题（D）的一个可行解，则有
；当且仅当
时，等号成立。
推论：若
是原问题（P）的一个可行解，
是对偶问题（D）的一个可行解，并且
，则和分别是原问题（P）与对偶问题（D）的最优解。
标准线性优化问题（P）的最优性条件可以表示为以下非线性系统的解：
其中
可以替换为
。
单纯形法与内点法
通过上述结果和上图，我们可以进一步了解和掌握单纯形法与内点法求解问题（P）的基本框架与相关关联。
对于大多数线性规划问题而言，单纯形法是一种非常有效的求解方法。然而，众所周知，单纯形法并不是多项式时间算法。事实上，当单纯形法用于求解数学家构造出的极端反例时，可能需要遍历所有顶点才能找到最优解。1979年，前苏联数学家Khachian第一次提出了求解线性规划的多项式时间算法——椭球算法，但椭球算法的效率不高、无法用于求解实际中的问题。1984年，美国贝尔工作室的印度数学家Karmarkar提出了一个实用的多项式时间算法——内点算法。实例测试也表明内点算法求解线性规划问题具有很好的效果，这是真正可用于求解实际中大规模线性规划问题的算法。因此，内点算法得到了社会各界的广泛关注，以及包括美国纽约时报在内的各大媒体的报道。同时该算法还被授予了专利，官方命名为“有效资源分配的方法和装置”，见下图。上世纪80年代，内点算法受到许多研究者的关注，也成为优化领域的前沿研究方向，很多学者都在内点算法方面做出了杰出的工作。
Karmarkar提出的内点算法主要用于求解如下形式的线性规划问题：
s.t.
其中，
是满秩矩阵，
是分量均为1的向量。该算法主要有两个假设：第一，初始点是内点，第二，上述优化问题的最优值是0。该方法主要采用了投影变换技术
并且定义了一个势函数
来探测可行域。
我们常见的原始对偶内点算法用于求解标准线性问题（P）的大体框架如下，主要思想是使用中心路径（central path）：
其中，
表示原始问题（P）的
-center，（
，
）表示对偶问题（D）的
-center，路径
是解析的。因为涉及到求解线性方程组，要使用牛顿法来求解下面的系统：
上述Karmarkar内点算法主要运用了仿射尺度变换与对数障碍罚函数的思想。一个自然的问题是，内点算法最早是由谁提出的？在20世纪50-70年代，单纯形法是求解线性规划问题的主流方法，而其他方法则难以得到关注。事实上，早在1955年，Frisch就提出了用对数障碍函数来求解凸优化问题的思路，这是第一次内点算法思想的提出与应用；1961年，Carrol提出了对数障碍方法的一种变形形式；1967年，Dikin在研究求解线性与二次规划问题的迭代解时，提出了仿射尺度算法；1968年，Fiacco与McCormick进一步丰富并完善了上述思想与方法。
由此可见，内点算法的思想早在20世纪50年代就有学者提出。但是为何直到1984年Karmarkar之后，内点算法才得到重视和关注呢？主要原因有以下几点。首先，70年代时，计算机的设备与性能落后。那个年代最先进的计算机是IBM360，但是内存只有128-256 KB，硬盘的存储空间也只有7.2MB-400MB，人们都使用磁带驱动器作为大容量存储设备，输入的也是穿孔的卡片，操作起来非常不便。其次，计算机无法进行双重精度运算、正则化处理；在缺乏稀疏矩阵的计算方法时，微分运算无法进行。这对于要求大量内存空间、正则化处理病态系统、有技巧地处理稀疏矩阵的内点算法而言，是一道难以逾越的鸿沟。因此，内点算法在当时注定不具有竞争力。
进入80年代后，随着电子计算机的发展与技术的改良，内点算法迎来了大好时机，开始受到研究者的重视。首先，计算机内存容量数量级的增大，保证了足够的存储空间；其次，复杂性理论的建立为控制算法提供了保障；同时，椭球算法的提出，让研究者们对线性规划问题的多项式时间算法充满了信心；再次，计算机逐渐由大型主机发展到工作站再到台式机，使用起来更加便捷；最后，稀疏矩阵理论与软件包以及自动微分算法的成熟，也使得内点算法变得更加有效。
由于内点算法的改革，求解线性规划的软件包也逐渐丰富起来。80年代以前，在大型主机上用于求解线性规划的软件包主要有LPS, MPS, MPSX, MINOS等，经历了内点法的改革以及计算机技术的发展，80年代以后，很多学者陆续开发了在工作站以及台式机上可以运行的CPLEX, OSL, XMP, XPRESS-MP, KORBX, OB1, GuRoBi, XPRESS……等软件包。这些软件包求解线性优化问题的速度较以前提高了
倍，并且一些新的算法的提出还进一步把求解的问题范畴推广到了二次规划等，推动了最优化领域的快速发展。
在报告的最后，Terlaky教授介绍了包括二阶锥优化、半定规划等在内的锥线性优化问题以及内点算法在这类优化问题中的应用，回顾了非线性规划在过去几十年的发展，并且对新世纪最优化的发展方向给出了总结。21世纪以来，最优化理论运用在了社会的各个领域中，变得越来越重要，同时优化问题的规模越来越大，亟需更加有效的算法来求解这些问题，还需要结合数据分类、机器学习、深度学习以及并行计算技术等知识来处理大数据问题。
后记：
本文作者来自河北工业大学优化研究团队，该团队在国内较早开展非线性优化内点方法的研究。他们从2004年起与新加坡国立大学和中国科学院数学与系统科学研究院优化与应用研究中心合作，在《SIAM J. Optim.》和《Math. Program.》等国际刊物发表了多篇非线性优化内点方法的研究论文，目前致力于改进内点方法在求解大规模优化问题中的数值表现。