66-理论方法-线性规划内点法

知识点：线性规划内点法

知识点概述

内点法（Interior-Point Method）是求解线性规划（以及更一般的凸优化问题）的一大类主流算法。与在可行域边界上移动的单纯形法不同，内点法通过在可行域的严格内部（内点）进行迭代来逼近最优解。

详细解释

• 核心思想: 将带不等式约束的LP问题（如 $x\ge 0$）通过对数障碍函数转化为一系列无约束（或只有等式约束）的子问题： $\min c^{T}x-\mu {\sum }_i\log (x_i)\text{s.t. }Ax=b$ 其中 $\mu >0$ 是障碍参数。当 $\mu \to 0$ 时，子问题的解会收敛到原始LP问题的解。
• 中心路径 (Central Path): 这一系列子问题的解 $(x^{\ast }(\mu ),{\lambda }^{\ast }(\mu ),s^{\ast }(\mu ))$ 构成了一条“中心路径”，它位于原始问题和对偶问题可行域的严格内部，并最终汇集到最优解。
• 原始-对偶内点法: 现代内点法通常是原始-对偶方法。它们不直接求解带障碍的子问题，而是直接对原始问题和对偶问题的KKT条件应用牛顿法。为了保持迭代点在可行域内部，算法会缩短牛顿步长。

学习要点

• 理解内点法与单纯形法的哲学区别（内部 vs. 边界）。
• 掌握对数障碍函数的思想：用一个光滑的函数来近似边界约束。
• 了解中心路径的概念。
• 知道现代内点法是基于牛顿法求解KKT系统的原始-对偶方法。

实践应用

• 是求解大规模线性规划、二次规划和半定规划问题的标准算法。
• 许多商业和开源优化求解器（如Gurobi, MOSEK）的核心都是内点法。

关联知识点

• 前置知识: 42-核心概念-线性规划, 55-理论方法-带约束凸优化问题最优性条件, 60-理论方法-牛顿法
• 后续知识: 无
• 相关知识: 无