想象你接管了一家糖果工厂的配方车间。车间里摆满了各种原料配比方案，你的任务是在不撞上四面高压电网的前提下，找到利润最高的那种配方。电网就是约束条件——配方比例、温度上限、安全红线，碰一下就全盘皆输。传统的方法像蒙眼狂奔，撞了墙才回头。而内点法给你配了一副特殊的“电子眼”：它让你始终待在车间中央的安全通道上，稳步朝最优配方迈进，每一步都从容不迫，永远不碰电网。 这个“电子眼”的秘密，就是把电网变成一层看不见的“气垫墙”——越靠近边界，推力越强，把你温柔地弹回内部。气垫的松紧由一个旋钮控制，旋钮越拧越紧，安全通道就越来越贴近真正的边界，最终带你抵达那个贴着墙的最优点。这就是内点法：沿着可行域内部走，用对数障碍函数挡住边界，步步逼近最优解。

岗位关联

内点法是现代大规模线性规划和凸优化求解器的核心引擎，掌握它意味着你能看懂并驾驭工业级优化工具，是运筹、机器学习、金融风控等AI岗位的高价值技能。

目录
  1. 可视化演示
  2. 约束优化背景
  3. 对数障碍函数
  4. 中心路径
  5. KKT最优条件
  6. 原对偶内点法
  7. 算法迭代流程
  8. 复杂度分析
  9. 工程应用场景
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示SGD、Momentum、Adam三种优化器在损失曲面上的收敛轨迹、学习率对收敛的影响及收敛速度对比，直观理解优化器选择原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

优化器收敛轨迹 SGD：基础随机梯度下降，震荡大但方向稳定 Momentum：动量加速，利用历史梯度方向减少震荡 θ ← θ - η∇L(θ) 参数更新规则

约束优化背景

糖果工厂的配方车间里，电线杆上贴着告示：“每日生产总量不得超过 3 吨”“温度不得低于 20℃”。这些红线把车间划出了一片“安全活动区”，任何配方都必须落在这片区域里。这片区域，就是最优化世界里的可行域——所有满足约束的点的集合。而你的目标，是在这片区域里找到让利润最大的那个点。这类“有区域限制的寻优问题”，统称为约束优化；当目标和约束都是直线（线性）时，就叫线性规划。

早期的求解思路很直白：沿着边界摸。就像你在车间里贴着电网走，右手扶墙，一路探索。但这种“选边界法”（单纯形法）在多数情况下飞快，可一旦遇到特殊地形，就可能沿着墙体绕来绕去，指数级地慢下去。更麻烦的是，如果起点不在边界上，你甚至不知道往哪儿走才能最快靠近目标。

因此，数学家们换了个思路：不碰墙，走内道。我们把“必须待在车间里”这个要求，变成一种柔性的引导力。你不需要知道墙在哪，只需要感觉到一股无形的推力，越靠近墙越强，永远把你往中央推。顺着这条中央通道走下去，就能抵达最优点——它往往恰恰就靠在墙边。这个“走内道”的思路，就是内点法的灵魂。

车间里的安全通道不会自己出现，它需要一堵“柔软的气垫墙”来引导。下一节，我们就给电网裹上这层气垫。

min⁡x∈Rn  f(x)s.t.gi(x)≤0,i=1,2,…,m\displaystyle \min_{x \in \mathbb{R}^n} \; f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \quad i = 1, 2, \dots, m
这个数学式是约束优化问题的“标准合同”：在满足一系列不等式的前提下，找一个让目标函数最小的点。
  1. 目标函数f(x) 是你想最小化的指标，比如工厂的总成本。
    f(x)\displaystyle f(x)
  2. 决策变量x 属于 n 维实数空间，代表你手中可以调节的所有旋钮。
    x∈Rn\displaystyle x \in \mathbb{R}^n
  3. 不等式约束g_i(x) ≤ 0 共 m 条，是车间的电网围栏。
    gi(x)≤0,i=1,…,m\displaystyle g_i(x) \le 0, \quad i=1,\dots,m

对数障碍函数

想象电网上裹了一层越来越厚的气垫：你离电网越近，气垫的反弹力越大；真要碰到电网，气垫会变成无穷大的弹力，把你狠狠弹回车间中央。这层气垫，就是对数障碍函数。它不改变电网的位置，只改变你对边界的感受——从“硬碰硬”变成“软抵抗”。

技术上，我们把 m 条约束 $g_i(x) \le 0$ 变成目标函数里的惩罚项：每当某个 $g_i(x)$ 接近 0（即逼近边界），$-\ln(-g_i(x))$ 就会急剧飙向正无穷，像是气垫被压缩到极限。于是，任何试图越界的点都会付出天文数字般的代价，优化器只好乖乖待在内部。$\mu$ 是气垫的“松紧旋钮”：$\mu$ 大时气垫厚，内部宽敞但偏离真实最优；$\mu$ 小时气垫薄，贴近边界但接近真实最优。

这样，原本带约束的难题，被改造成一个无约束的光滑问题。我们不断拧小 $\mu$，让气垫慢慢变薄，安全通道也渐渐贴近真正的墙边，最终让迭代点逼近最优解。

气垫墙把迭代点“关”在内部，却还没告诉你该往哪走。答案藏在“车间中央那条安全线”里。

ϕμ(x)=f(x)−μ∑i=1mln⁡ ⁣(−gi(x))\displaystyle \phi_\mu(x) = f(x) - \mu \sum_{i=1}^{m} \ln\!\big(-g_i(x)\big)
这个式子把“必须待在内部”的硬要求，变成目标中一项会发烫的惩罚；$\mu$ 越小，惩罚越轻，越能靠近真实边界。
  1. 惩罚求和对每一条约束取负对数再求和，越靠近边界数值越大。
    ∑i=1mln⁡(−gi(x))\displaystyle \sum_{i=1}^{m} \ln(-g_i(x))
  2. 参数 μ松紧旋钮，乘在惩罚项前，控制气垫的整体厚度。
    −μ∑i=1mln⁡(−gi(x))\displaystyle -\mu \sum_{i=1}^{m} \ln(-g_i(x))
  3. 整体目标原目标加惩罚，构成无约束的新目标函数。
    ϕμ(x)=f(x)−μ∑ln⁡(−gi(x))\displaystyle \phi_\mu(x) = f(x) - \mu \sum \ln(-g_i(x))

中心路径

车间里有一条看不见的“中央安全线”：从车间最宽敞的腹地出发，弯弯曲曲地延伸，最终停靠在最优点旁边。内点法的每一步，都踩在这条线上。这条线叫中心路径。它是由无数个“气垫厚度下的最优位置”连成的：气垫调到某个厚度 $\mu$ 时，车间内会有一个唯一的最舒服的位置（即最小化 $\phi_\mu$ 得到的 $x_\mu^*$）；把 $\mu$ 从大调到小，就得到一串位置，连起来就是一条光滑曲线。

中心路径有一条迷人的性质：它永远不碰墙。因为无论 $\mu$ 多大，惩罚项都把点压在严格内部；无论 $\mu$ 多小，只要还没到零，点就离墙有一丝缝隙。这条“有惊无险”的曲线，让内点法可以放心大胆地沿它走，不用担心撞上约束。

那么，这条安全线通向哪里？当 $\mu \to 0$ 时，惩罚项失去威力，中心路径的终点恰是原问题的最优点。所以内点法的策略很清晰：先站上中心路径，再沿着它把 $\mu$ 一路拧小，终点就是你要的答案。

沿着安全线走，你还需要一张“到此一游”的确认单——当位置真的最优时，必须满足一套签名条件。

C={xμ∗  ∣  μ>0,    xμ∗=arg⁡min⁡xϕμ(x)}\displaystyle \mathcal{C} = \big\{ x_\mu^* \;\big|\; \mu > 0, \;\; x_\mu^* = \arg\min_x \phi_\mu(x) \big\}
中心路径是“气垫厚度参数 μ”从厚到薄时，一系列内部最优解连成的轨迹，内点法就是沿着这条轨迹滑向最终答案。
  1. 集合定义中心路径是所有 $x_\mu^*$ 的集合。
    C={xμ∗∣μ>0}\displaystyle \mathcal{C} = \{ x_\mu^* \mid \mu > 0 \}
  2. 内部最优解$x_\mu^*$ 是在气垫厚度 $\mu$ 下，新目标函数的最小值点。
    xμ∗=arg⁡min⁡xϕμ(x)\displaystyle x_\mu^* = \arg\min_x \phi_\mu(x)
  3. 参数范围$\mu$ 必须大于 0，气垫才不会消失。
    μ>0\displaystyle \mu > 0

KKT最优条件

想象最优配方终于找到了，车间主任拿来一张“验收单”，上面列着几条签名栏：所有内力的合力为零、每个约束的“影子价格”非负、每条电网要么没被碰到要么影子价格为 0。只有全部签名齐全，才证明当前位置真是全局最优。这张验收单，就是 KKT 条件。

第一条签名栏是“驻点条件”：在最优处，目标函数的下降方向必须与约束的“推挡”方向完全抵消，合力为零。这就像你想往东冲，气垫恰好把你往西推，两边僵持。第二条是“对偶变量非负”：每个约束有一个价格标签 $\lambda_i$，松弛的约束价格为零，绷紧的约束价格不能为负。最后是“互补松弛”：约束要么没被激活（$g_i < 0$），此时 $\lambda_i = 0$；要么被激活（$g_i = 0$），此时 $\lambda_i \ge 0$。两者相乘必为零。

KKT 条件不仅用于验收，更是内点法的导航仪表。每次迭代，我们都会计算当前点与 KKT 条件的偏差（残差），然后朝着消零残差的方向走一步。走完所有签名栏，任务就完成了。

有了验收单，还需要一辆“双轮驱动的马车”把每一步精确地带向验收位——这就是原对偶内点法。

∇f(x∗)+∑i=1mλi∗∇gi(x∗)=0,λi∗≥0,λi∗gi(x∗)=0\displaystyle \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla g_i(x^*) = 0, \qquad \lambda_i^* \ge 0, \qquad \lambda_i^* g_i(x^*) = 0
KKT 条件是最优解的“三章验收单”：内力平衡、影子价格非负、互补松弛。满足它，你就能确认当前位置确实是最优。
  1. 驻点条件目标梯度与约束梯度的加权和为零，说明无处可去。
    ∇f(x∗)+∑i=1mλi∗∇gi(x∗)=0\displaystyle \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla g_i(x^*) = 0
  2. 对偶非负每个约束的影子价格 $\lambda_i^*$ 必须不小于零。
    λi∗≥0\displaystyle \lambda_i^* \ge 0
  3. 互补松弛约束余量与影子价格乘积为零，松弛的约束不收费。
    λi∗gi(x∗)=0\displaystyle \lambda_i^* g_i(x^*) = 0

原对偶内点法

车间里的导航车有两个轮子：一个轮子管“配方位置”（原变量 $x$），另一个轮子管“影子价格”（对偶变量 $\lambda$）。两个轮子必须协同转动，车才能沿着中心路径稳稳前行。这就是原对偶内点法的比喻：同时更新原变量和对偶变量，让两条腿交替迈步。

每一步具体怎么做？我们把 KKT 条件的残差看成“偏离验收单的距离”，然后用牛顿法求一个修正方向：把当前的残差函数做一阶线性近似，解一个线性方程组 $J d = -r$，得到修正量 $d$。这个方程组称为牛顿系统。求出方向后，还要控制步长——不能一步跨出车间，所以要把步子限制在气垫范围内，保证 $x + \alpha d$ 仍在可行域内部。

这种“双轮驱动 + 步长刹车”的机制，让原对偶内点法每一步都能大步前进而又不越界，收敛速度远超早期只动一个轮子的方法。它也是现代求解器（如 Gurobi、MOSEK）内部真正使用的引擎。

马车有了方向盘，接下来要制定完整的行车导航图：从哪出发、每站干什么、何时停下。

[∇2f(x)Jg(x)⊤−ΛJg(x)−S][dxdλ]=−[rdualrcent]\displaystyle \begin{bmatrix} \nabla^2 f(x) & J_g(x)^\top \\ -\Lambda J_g(x) & -S \end{bmatrix} \begin{bmatrix} d_x \\ d_\lambda \end{bmatrix} = -\begin{bmatrix} r_{\text{dual}} \\ r_{\text{cent}} \end{bmatrix}
这是原对偶内点法的“方向盘方程”：根据当前偏差（右侧残差）反推左边该转多少角度（$d_x$ 与 $d_\lambda$）。
  1. 残差向量$r_{\text{dual}}$ 是驻点条件的偏差，$r_{\text{cent}}$ 是互补松弛的偏差。
    [rdualrcent]\displaystyle \begin{bmatrix} r_{\text{dual}} \\ r_{\text{cent}} \end{bmatrix}
  2. 系数矩阵由目标二阶导 $\nabla^2 f$、约束雅可比 $J_g$ 与对角阵 $\Lambda, S$ 拼成。
    [∇2f(x)Jg(x)⊤−ΛJg(x)−S]\displaystyle \begin{bmatrix} \nabla^2 f(x) & J_g(x)^\top \\ -\Lambda J_g(x) & -S \end{bmatrix}
  3. 牛顿方向解这个线性方程组得到更新方向 $d_x, d_\lambda$。
    [dxdλ]\displaystyle \begin{bmatrix} d_x \\ d_\lambda \end{bmatrix}

算法迭代流程

把原对偶内点法的行车过程写成一张导航图，你会发现它像极了工厂的标准化作业流程。第一步是初始化：找到车间内部任意一个不碰墙的起点，同时把气垫厚度 $\mu$ 设为一个较大的初值。即使起点离最优很远也没关系，只要在内部，引擎就能启动。

第二步是迭代循环：先看导航仪表（计算残差），如果偏差太大就解牛顿系统求得方向，然后带着刹车走一步，更新位置。走完后，把气垫旋钮拧小一点（通常乘一个 0.1~0.5 的系数，即 $\mu \leftarrow \sigma \mu$），让中心路径向真实边界靠近。如此反复，“走一步、拧一下”。

第三步是收敛判断：当互补间隙（可以理解为“距离验收单还差多少”）小于预设阈值 $\epsilon$ 时，刹车停下，宣布当前位置就是最优解。整个过程像一场精心编排的舞蹈：走步、拧旋钮、看仪表，循环往复，直到钟声响起。

导航图清晰了，你可能会问：这套流程到底多快？它和传统的“摸墙走”相比谁更省时间？

xk+1=xk+αkdk,μk+1=σμk\displaystyle x_{k+1} = x_k + \alpha_k d_k, \qquad \mu_{k+1} = \sigma \mu_k
更新公式是“行进一小步 + 气垫调薄一点”的交替节奏：位置沿方向前进，μ 乘系数缩小。
  1. 位置更新新位置 = 旧位置 + 步长 × 方向。
    xk+1=xk+αkdk\displaystyle x_{k+1} = x_k + \alpha_k d_k
  2. 步长约束$\alpha_k$ 经过刹车限制，保证不越出可行域。
    0<αk≤1\displaystyle 0 < \alpha_k \le 1
  3. μ 更新气垫厚度乘系数 $\sigma$（通常 0.1~0.5）逐渐变薄。
    μk+1=σμk\displaystyle \mu_{k+1} = \sigma \mu_k

复杂度分析

老员工告诉你，以前用“摸墙走”（单纯形法），运气好时几步就到，运气差时可能绕着车间转几百圈。而新来的“内道导航车”则不同：无论车间形状多古怪，它需要的圈数都非常稳定。这就是复杂度分析要回答的问题——算法的迭代次数随问题规模如何增长。

内点法的理论迭代次数约为 $O(\sqrt{m} \ln(1/\varepsilon))$，其中 $m$ 是约束条数，$\varepsilon$ 是要求的精度。这个数字对 $m$ 只开平方根，意味着从 100 条约束涨到 10000 条（100 倍），迭代次数大约只涨 10 倍。更关键的是，它不依赖系数矩阵的特殊结构，属于多项式时间算法——最坏情况也有保证。

对比之下，单纯形法虽然平均表现极佳，但其最坏情况是指数级的，像迷宫中最绕的那条路。因此，在大规模线性规划、金融投资组合、供应链优化等动辄百万变量的场景里，内点法凭借稳定的“圈数上限”成为工业级求解器的主力。复杂度分析给了工程师一颗定心丸：交给内点法，最坏也不会太慢。

理论证明内点法又快又稳，工厂决定全面启用这套“内道导航系统”。让我们一起看看它在真实车间里的部署。

O ⁣(mln⁡(1/ε))\displaystyle O\!\big(\sqrt{m} \ln(1/\varepsilon)\big)
这个式子说：迭代圈数与约束条数的平方根成正比，与精度要求成对数关系，所以规模翻百倍也只多走几圈。
  1. 平方根项$\sqrt{m}$ 来自牛顿法在中心路径附近的局部收敛特性。
    m\displaystyle \sqrt{m}
  2. 对数项$\ln(1/\varepsilon)$ 说明要把精度提高 10 倍，只需多走几步。
    ln⁡(1/ε)\displaystyle \ln(1/\varepsilon)
  3. 大 O 记号表示随规模增长的主趋势，忽略常数倍。
    O(⋅)\displaystyle O(\cdot)

工程应用场景

内点法不是实验室里的花瓶，它已经是现代工业优化软件的“标准发动机”。在航空调度中，每天要排几千架航班的机组与航线，约束条件多达数十万条，用单纯形法可能会卡到天亮，而内点法往往几分钟内给出答案。在金融风控中，投资组合优化要求资产权重在诸多红线（如行业占比、风险上限）内寻找最大收益，原对偶内点法正是标准解法。在生产计划、物流路径、电力调度等运筹场景中，它同样无处不在。

工业界常用的求解器，如 Gurobi、MOSEK、CPLEX，对内点法的实现做了大量工程优化：稀疏矩阵分解、预条件处理、交叉到单纯形做精修。普通开发者也能借助 SciPy 的 linprog(method='highs') 或 CVXPY 轻松调用内点法，像使用家电一样不必深究内部齿轮。这也是学习内点法的价值：你不需要重造车轮，但你需要知道车轮为什么转——当你面对病态模型、收敛失败或求解缓慢时，这份理解就是诊断故障的利器。

用一句话总结：内点法让你在约束的夹缝中从容行走，用“内部视角”绕开边界的险恶，用数学的力量让大规模优化变得可靠而迅捷。 记住这个比喻：你是在糖果车间里贴着安全通道走的人，气垫墙护你周全，中心路径引你前行，KKT 验收单确认终点。

AI 应用场景

大规模线性规划求解引擎

阶段：模型求解与优化

解决的问题：传统单纯形法在最坏情况下需要指数级迭代，面对几十万约束、上百万变量的生产调度或物流规划时会卡死。内点法把迭代次数压到多项式级，让大规模 LP 在可接受时间内求解。

具体案例：某快递公司每天要规划 3 万辆车的配送路线，约束包括车辆容量、时间窗、司机工时等 20 万条。使用基于原对偶内点法的求解器后，求解时间从原来的 3 小时降到 15 分钟，支撑了当日达承诺。

投资组合优化与风控

阶段：决策优化层

解决的问题：资产配置需要在预期收益、风险敞口、行业集中度等多重约束下寻找最优权重，本质是带不等式约束的凸二次规划。手动调仓靠经验，内点法靠数学保证全局最优。

具体案例：某量化基金用 CVXPY（底层调用内点法）每日动态调整 500 只股票的权重，约束包括行业占比上限、单票持仓上限、杠杆率限制，每次优化耗时不到 2 秒，回测年化超额收益提升约 2%。

机器学习超参数与模型校准

阶段：模型训练与调优

解决的问题：支持向量机（SVM）的训练本质是凸二次规划，日志损失并加正则项的模型训练也有约束视角。内点法为这些凸问题提供可靠的高精度解，尤其适合小批量高精度场景。

具体案例：某风控团队用内点法训练 L1 正则逻辑回归替代梯度下降，在特征维度 5 万、样本 200 万的数据上，权重解更稀疏且精度更高，模型 AUC 从 0.87 提升到 0.89，且训练时间稳定可控。

Python 演示

python48 行
import numpy as np  def log_barrier_qp(Q, c, A, b, mu0=1.0, tau=0.5, sigma=0.2, eps=1e-8, max_iter=100):    """用对数障碍内点法求解凸二次规划:        min  0.5 * x^T Q x + c^T x        s.t. A x <= b    """    n = Q.shape[0]    m = len(b)    x = np.zeros(n)    mu = mu0     for k in range(max_iter):        s = b - A @ x        if np.min(s) <= 0:            break         grad = Q @ x + c - mu * (A.T @ (1.0 / s))        H = Q + mu * A.T @ np.diag(1.0 / s**2) @ A        d = np.linalg.solve(H, -grad)         alpha = 1.0        Ad = A @ d        for i in range(m):            if Ad[i] < 0:                alpha = min(alpha, tau * s[i] / (-Ad[i]))         x += alpha * d        mu *= sigma         lam = mu / s        gap = np.dot(s, lam)        if gap < eps:            break     return x  if __name__ == "__main__":    Q = 2 * np.eye(2)    c = -2 * np.array([2.0, 2.0])    A = np.array([[1.0, 1.0], [-1.0, 0.0], [0.0, -1.0]])    b = np.array([3.0, 0.0, 0.0])     x_star = log_barrier_qp(Q, c, A, b)    print("最优解 x =", x_star)    print("目标值  =", 0.5 * x_star @ Q @ x_star + c @ x_star)
目的：用对数障碍内点法求解一个带不等式约束的二次规划问题，并打印最优配方。
  1. grad = Q @ x + c - mu * (A.T @ (1.0 / s))这是目标函数加障碍项后的梯度：原梯度减去“气垫推力”。
  2. H = Q + mu * A.T @ np.diag(1.0 / s**2) @ A障碍项的二阶近似，用来构造牛顿方向。
  3. d = np.linalg.solve(H, -grad)解线性方程组，得到当前步的牛顿方向。
  4. alpha = min(alpha, tau * s[i] / (-Ad[i]))步长刹车：确保不会一步跨出可行域。
  5. x += alpha * d沿方向走一步，更新配方位置。
  6. mu *= sigma把气垫旋钮拧小，让中心路径向真实边界靠拢。
  7. gap = np.dot(s, lam)互补间隙，相当于“离验收单还差多少”。
  8. if gap < eps: break间隙小于阈值就停车，宣布已达最优。

常见误区

误区我听说内点法要沿着边界走，所以初始化时应该选一个靠近约束边界的点，这样收敛快。

正解恰恰相反，内点法的核心优势是始终在内部迭代，起点最好选在可行域深处（比如解析中心），离边界越远越安全。因为障碍函数在边界处数值爆炸，从边界附近出发会在第一步就遇到巨大的惩罚梯度，数值上极不稳定。正确做法是先用 Phase I 或启发式找一个严格内部的点，再启动迭代。

为何常见：很多人把内点法和“碰边界寻优”的单纯形法混淆了，觉得靠近边界才能找到最优解——但内点法靠中心路径逼近最优，而非贴墙行走。

误区障碍函数不就是把约束加个惩罚项吗？那和拉格朗日惩罚法没什么区别。

正解区别很大。拉格朗日惩罚允许点在可行域外，靠惩罚力度拉回来；而对数障碍函数在可行域外根本没有定义——$-\ln(-g_i(x))$ 在 $g_i(x) > 0$ 时无意义。它是一堵“无形墙”，从数学上把迭代点钉在内部，而不是“罚一下再放进来”。这种“硬性内部约束”是内点法名字的由来。

为何常见：初学者看到“惩罚项”三个字，容易联想到通用的罚函数法，忽略了障碍函数定义域的本质限制。

误区内点法是多项式算法，单纯形法是指数算法，所以内点法在所有问题上都更快。

正解复杂度说的是最坏情况的上界。实际工程中，单纯形法在中小规模问题上往往更快，因为它的基矩阵操作更稀疏、更易热启动。内点法在大规模、稠密、无特殊结构的问题上优势明显。现代求解器（如 Gurobi）通常两者都实现，并根据问题特征自动切换，甚至用内点法求解后交叉到单纯形精修。

为何常见：把“最坏情况复杂度”当成“实际运行时间”，忽略了常数因子、稀疏性和热启动等工程因素。

误区既然最优解在 μ→0 时得到，那我把 μ 设成 0 或者极小值，一次迭代不就直接得到答案了吗？

正解μ 太小会让障碍项失去作用，牛顿系统变得病态，迭代点可能直接冲出可行域。内点法的正确策略是从较大的 μ 开始，沿着中心路径逐步缩小，每步只乘一个小系数（如 0.2），让点始终黏在中心路径附近。这个“路径追踪”过程才是收敛性证明的基础。

为何常见：直觉上觉得“参数取极限 = 直接到终点”，忽略了数值稳定性和收敛路径的连续性。

面试题

Q1. 内点法迭代点最本质的特点是？

单选题 · easy

  • A.始终在可行域边界上移动
  • B.始终在可行域内部迭代← 正确答案
  • C.每次迭代跳跃到顶点
  • D.允许短暂越过边界再拉回

答案：B。内点法名字就来自“内部”：通过对数障碍函数把迭代点限制在可行域内部，永不碰边界（除非 μ 恰好趋于 0）。单纯形法才是在顶点间跳跃，罚函数法才允许越界，所以 A、C、D 都是别的算法画像。

Q2. 对数障碍函数在约束边界 $g_i(x) = 0$ 处的取值趋势是？

单选题 · easy

  • A.趋向 0
  • B.趋向某个有限正数
  • C.趋向正无穷← 正确答案
  • D.无定义

答案：C。$-\ln(-g_i(x))$ 中，当 $g_i(x) \to 0^-$ 时 $-g_i(x) \to 0^+$，对数趋向 $-\infty$，加负号后趋向 $+\infty$。这就像气垫在墙边被压缩到极限，反弹力无穷大，所以迭代点被牢牢挡回内部。

Q3. 中心路径是由什么构成的？

单选题 · mid

  • A.一系列可行域顶点
  • B.不同 μ 值下障碍问题的最优解集合← 正确答案
  • C.随机采样的内部点
  • D.目标函数的等值线

答案：B。对每个 μ > 0，最小化 $\phi_\mu(x) = f(x) - \mu\sum\ln(-g_i(x))$ 会得到一个内部最优点 $x_\mu^*$；让 μ 从大变小，这些点连成一条光滑曲线，就是中心路径。当 μ→0 时它通向原问题最优点。顶点是单纯形法的概念，所以 A 错。

Q4. KKT 条件中“互补松弛”的含义是？

单选题 · mid

  • A.对偶变量必须大于零
  • B.约束要么松弛要么影子价格为零← 正确答案
  • C.目标梯度必须为零
  • D.所有约束必须在边界上激活

答案：B。互补松弛即 $\lambda_i g_i(x) = 0$：某条约束没被激活（$g_i < 0$）时其影子价格 $\lambda_i = 0$；被激活（$g_i = 0$）时价格可为正。这像验收单上“松弛的约束不收费”。B 正是这个含义；A、C 是误读，D 是“所有约束都绷紧”的错误极端。

Q5. 原对偶内点法每一步需要做哪些事？

多选题 · mid

  • A.计算 KKT 残差← 正确答案
  • B.求解牛顿系统得到方向← 正确答案
  • C.用最大步长直接跨越边界
  • D.控制步长确保不越出可行域← 正确答案

答案：ABD。原对偶内点法每步先算残差（A），再解牛顿系统 $Jd = -r$ 获取方向（B），然后对步长做刹车限制（D），保证 $x + \alpha d$ 仍在内部。C 恰恰相反——内点法宁可走小步也不越界，直接跨越边界是罚函数的做法。

Q6. μ 在迭代过程中应该怎么变化？

单选题 · mid

  • A.保持恒定
  • B.逐次增大，让惩罚更强
  • C.逐次乘一个小系数（如 0.2）递减← 正确答案
  • D.第一次迭代直接设为 0

答案：C。μ 是气垫的松紧旋钮，应该从大往小调：$\mu_{k+1} = \sigma \mu_k$，σ 通常取 0.1~0.5。这样中心路径逐步贴近真实边界。保持不变（A）则永远找不到精确解；增大（B）反而更偏离；设为 0（D）会让牛顿系统病态，迭代点可能冲出可行域。

Q7. 内点法的迭代复杂度约为多少？

单选题 · hard

  • A.$O(m)$
  • B.$O(\sqrt{m} \ln(1/\varepsilon))$← 正确答案
  • C.$O(2^m)$
  • D.$O(m \ln m)$

答案：B。内点法理论迭代次数为 $O(\sqrt{m} \ln(1/\varepsilon))$，m 是约束条数，ε 是精度。平方根项让它在大规模问题上保持稳健。$O(2^m)$ 是单纯形法的最坏情况复杂度，A、D 不是内点法的标准界。

Q8. 关于内点法与单纯形法的对比，下列说法正确的是？

多选题 · hard

  • A.内点法最坏情况是多项式时间← 正确答案
  • B.单纯形法最坏情况是指数时间← 正确答案
  • C.单纯形法在任何规模下都比内点法快
  • D.现代求解器常根据问题特征自动切换两者← 正确答案

答案：ABD。内点法具有多项式最坏复杂度（A 对），单纯形法最坏是指数（B 对）。但实际工程中单纯形在小规模、稀疏且有热启动的场景下往往更快，所以 C 错。工业求解器如 Gurobi 会智能选择算法甚至交叉精修（D 对）。

Q9. 内点法要求迭代点满足什么条件才能启动？

单选题 · easy

  • A.必须是可行域顶点
  • B.必须在可行域严格内部← 正确答案
  • C.必须在目标函数等值线上
  • D.只需满足部分约束

答案：B。对数障碍函数在可行域外无定义，因此起点必须严格满足所有不等式约束，即 $g_i(x) < 0$ 对全部 i 成立。如果找不到这样的点，需要先用 Phase I 方法寻找“内部起点”。顶点和部分满足约束都无法计算障碍函数。

Q10. 以下哪些问题适合用内点法求解？

多选题 · hard

  • A.百万变量的大规模线性规划← 正确答案
  • B.带不等式约束的凸二次规划← 正确答案
  • C.无约束光滑函数最小值问题
  • D.投资组合权重优化← 正确答案

答案：ABD。内点法专攻带约束的凸优化，大规模 LP（A）和凸二次规划（B）是它的主场；投资组合优化常被建模为带约束的 QP（D）。无约束问题（C）根本不需要约束处理，用梯度下降或拟牛顿法即可，不需要引入障碍函数。