货运商人小斯每天要把苹果从可行堡运到目标镇，路上必须经过对偶关。关长老关只做一件事：看货估价。奇怪的是，无论老关多老练，他报的估价永远不超过小斯的实际运输成本——用行话说，他永远只摸得到成本的底线，绝无可能高估。小斯做梦都想让老关的估价“一分不差”地等于真实成本，那意味着老关彻底看穿了他，两人之间没有一丝信息差。可老关说了：想让我看穿你？可以，但先拿出一张叫 Slater 的通行证。这张通行证的要求听起来简单却苛刻：你得证明，在可行堡的货仓里，存在一个位置，让你那箱苹果能站在仓库正中央，四周都够不着一面墙。有了这张通行证，对偶这条近路才敢放心走。这篇文章，就从这道海关闸口讲起。

岗位关联

对 AI 工程师来说，Slater 条件是用对偶方法、内点法求解优化问题前的“体检报告”：看一眼是否存在严格可行内点，就能判断强对偶是否成立，避免在隐藏的对偶间隙上浪费算力与时间。

目录
  1. 可视化演示
  2. 对偶间隙之谜
  3. 强对偶：估价命中成本
  4. Slater条件：通行证的样子
  5. 为什么“严格”二字要命
  6. 几何视角：支撑杆与对偶
  7. 哪些问题天生揣着通行证
  8. 失效警示：卡在海关的清单
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示凸优化可行域中严格可行内点的存在性、Slater条件保证零对偶间隙的强对偶证明逻辑，及在LP/SVM/内点法中的实际验证应用。

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

凸优化可行域与严格可行内点 凸不等式约束构成可行域 严格可行内点x*满足g(x*)∃x*: g_i(x*)<0 Slater条件要求存在严格可行内点

对偶间隙之谜

小斯第一次跑货运时还不懂规矩。他拉着一车苹果到对偶关，老关眯着眼扫了扫货单，报出一个价格。小斯心里一喜：这估价比自己的真实成本低了不少，海关这是“看走眼”了？他后来才明白，这根本不是老关眼拙，而是一条铁律——海关的估价，永远只是你真实成本的下界。就像再高明的算命先生，也只能把命运算得更准，不可能算出比你实际寿命更长的“上限”来。

在凸优化里，这条铁律叫弱对偶。任何一个优化问题都自带一正一邪两个“身份”：原问题追求最小化成本 f₀(x)，对偶问题则像个精明的稽查员，在合法范围内追求最大化的“保守估价”。弱对偶定理保证：稽查员能挖出的最高估价 d\，顶多等于你的真实最优成本 p\。两者之间的差，叫对偶间隙。间隙越大，说明海关对你的底细了解得越浅；间隙为零，则意味着估价恰好命中真实成本。

所以小斯每次过关都盼着间隙归零。但老关说了：想让我彻底看穿你？先拿到那张通行证。间隙从何而来、又如何消失，答案都藏在这张通行证里。

d∗≤p∗,gap=p∗−d∗≥0\displaystyle d^* \le p^*, \qquad \mathrm{gap} = p^* - d^* \ge 0
弱对偶说“海关只会低估、不会高估”，所以估价永远是实际成本的下界。
  1. 对偶最优值 $d^*$海关在所有合法估价政策里，能报出的最高数字——这是他能达到的“最好成绩”。
    d∗=sup⁡λ⪰0, νg(λ,ν)\displaystyle d^* = \sup_{\lambda \succeq 0,\ \nu} g(\lambda,\nu)
  2. 原问题最优值 $p^*$你真正能实现的最低运输成本，对应最优的那条送货路线。
    p∗=inf⁡xf0(x)\displaystyle p^* = \inf_x f_0(x)
  3. 不等号方向弱对偶的精华在于"≤"——估价永远不高于成本，这是海关权力的边界。
    d∗≤p∗\displaystyle d^* \le p^*
  4. 间隙 $\mathrm{gap}$实际成本减去海关估价，永远非负。它度量海关与你的“信息差”。
    gap=p∗−d∗\displaystyle \mathrm{gap} = p^* - d^*

强对偶：估价命中成本

小斯忍不住问老关：“到底怎样才能让你估得一分不差？” 老关掸了掸帽檐上的灰：“除非你拿出 Slater 通行证，证明你在可行堡里有一个真正站得住脚、不贴墙的位置。有了它，我的估价就能精确等于你的成本，咱俩之间零间隙。” 小斯半信半疑：一张“站得正”的证明，真能让海关开天眼？

强对偶的定义正是如此简单：对偶最优值等于原问题最优值，d\ = p\，对偶间隙为零。它意味着求解对偶问题与求解原问题完全等价——你把苹果交给海关估价，得到的数字就是你实际要花的钱。许多高效算法（对偶上升法、内点法、ADMM）之所以敢把宝押在对偶问题上，前提都是强对偶成立；否则按照海关报价做的决策，会与真实最优解存在系统性偏差。

关键要记住：强对偶的通行证性质是“充分条件”式的保障。对凸问题，Slater 条件成立 ⇒ 强对偶成立；但有些问题即使不满足 Slater，强对偶依然成立（比如某些退化的线性规划）。通行证不是唯一的路，却是最让人放心的路。小斯点点头：有了它，海关就绝不会让我吃亏。

d∗=p∗,p∗−d∗=0\displaystyle d^* = p^*, \qquad p^* - d^* = 0
强对偶把“估价”和“成本”两个数字焊成同一个数，让对偶方法可以放心代理原问题。
  1. 等号 $d^* = p^*$两个最优值重合，海关估价精确等于你的真实成本。
    d∗=p∗\displaystyle d^* = p^*
  2. 间隙为零信息差消失，估价不再有“折扣”。
    p∗−d∗=0\displaystyle p^* - d^* = 0
  3. 充分非必要Slater 条件成立能推出强对偶，但反过来不成立——没有通行证也可能通关，只是没有保证。

Slater条件：通行证的样子

通行证到底长什么样？老关翻开条例逐条念：货物必须在可行堡内部找到一个“严格可行”的存放点——既要满足所有不等式约束，而且每一项都要严格小于边界，不能刚好压在墙上；仿射（线性）约束是例外，它们像城墙上的标准大门，只要沿门边能放下货物即可。小斯听得一头雾水，老关索性把标准凸优化问题和通行证的格式写给他看。

考虑标准的凸优化问题：最小化凸函数 f₀(x)，受限于一组凸不等式 fᵢ(x) ≤ 0 和一组仿射等式 Ax = b。Slater 条件要求：存在一个点 x，它落在定义域的相对内部 relint D 里，所有非仿射的不等式约束都严格成立 fᵢ(x) < 0，仿射约束只需 fᵢ(x) ≤ 0，等式约束 Ax = b 必须精确满足。

小斯把条例翻译成人话：只要你能在仓库里找一个“离墙还有一拳距离”的地方放苹果箱，通行证就到手了；那些笔直的门洞，贴边放货也不算犯规。

∃ x∈relint D:fi(x)<0  (∀ i 非仿射),fi(x)≤0  (∀ i 仿射),Ax=b\displaystyle \exists\, x \in \mathrm{relint}\,\mathcal{D} :\quad f_i(x) < 0 \;(\forall\, i\ \text{非仿射}),\qquad f_i(x) \le 0 \;(\forall\, i\ \text{仿射}),\qquad Ax = b
Slater 条件说人话就是：存在一个点，它离所有“弯的墙”都有一拳距离，但可以不躲“直的门”。
  1. 存在量词 $\exists\, x$不需要所有点都合格，只要“存在一个”站得住的位置，通行证就有效。
    ∃ x\displaystyle \exists\, x
  2. 相对内部 $\mathrm{relint}\,\mathcal{D}$在可行域张成的低维空间里看“内部”，管的是那条线段中间那些点。
    x∈relint D\displaystyle x \in \mathrm{relint}\,\mathcal{D}
  3. 严格不等式 $f_i(x) < 0$对非仿射约束必须留出余地，这是通行证最重要的钢印。
    fi(x)<0\displaystyle f_i(x) < 0
  4. 仿射豁免 $f_i(x) \le 0$线性约束天生扁平，无需也做不到“严格小于”，只需满足即可。
    fi(x)≤0,Ax=b\displaystyle f_i(x) \le 0,\quad Ax = b

为什么“严格”二字要命

小斯追问：“贴边站和站中间，对海关估价有什么差别？” 老关说：“差别大了。你要是只能贴边站，说明你的可行货仓根本没有'厚度'——它在空间里就是一张纸、一条线，甚至一个点。这种货仓里，我找不到足够的参照物来撑住估价，间隙就冒出来了。”

数学上，Slater 条件的本质是要求可行域有非空的相对内部。当每个可行点都至少有一个非仿射不等式约束取等号时，可行域被“削”成一块没有厚度的薄板。此时问题虽然还是凸的，强对偶却可能失效。换一个角度看：严格可行点意味着，以它为圆心能画出一个半径严格为正的小开球，整个球仍然落在可行域内。这个“开球”就是海关估价的支点——有了支点，撑杆才立得住。

小斯恍然大悟：站在墙角的苹果箱，海关看不真切；站在仓库正中央的苹果箱，每一寸都暴露在灯光下。所谓严格，就是给自己留出被看穿的“余地”。

∃ x∈F, ε>0:{z∣∥z−x∥≤ε}⊆F\displaystyle \exists\, x \in \mathcal{F},\ \varepsilon > 0 :\quad \{z \mid \|z - x\| \le \varepsilon\} \subseteq \mathcal{F}
严格可行等价于“能画出一个不越界的小球”——球的半径 ε 必须严格大于零，这正是“有余地”的数学化身。
  1. 可行点 $x \in \mathcal{F}$x 必须是合法的存放点，满足所有约束。
    x∈F\displaystyle x \in \mathcal{F}
  2. 正半径 $\varepsilon > 0$小球半径必须严格为正，哪怕只有一毫米。
    ε>0\displaystyle \varepsilon > 0
  3. 小球嵌入 $\{z \mid \|z-x\| \le \varepsilon\} \subseteq \mathcal{F}$以 x 为心的整颗小球都在可行域内，说明 x 周围有一圈“安全区”。
    {z∣∥z−x∥≤ε}⊆F\displaystyle \{z \mid \|z-x\| \le \varepsilon\} \subseteq \mathcal{F}

几何视角：支撑杆与对偶

老关把估价的方法摊开在桌上：他从不瞎估，而是给每种货物定一个“单价”（对偶变量），再把所有限制条件折算成税费，最后在全部可能的货单里找最坏的情况。这一套组合拳，数学上叫对偶函数。它把带约束的难题，变成不带约束的“压价游戏”。

对偶变量 λ 给每个不等式约束标了价：约束越紧，单价越高。等式约束则用 ν 记账，可正可负。对偶函数在全部 x 上取下确界——相当于海关假设你“故意配合最坏情况”来压价。几何上，这就像用一根支撑杆从空中压住可行域这座凸山坡：p\* 是谷底，对偶就是在找一根恰好压住谷底的杆子。Slater 条件保证这根杆子不会“竖直插进地里”，总能找到合适的斜率（对偶变量）稳稳压住谷底；如果可行域退化成一堵悬崖，支撑杆就悬空了。

小斯看着图纸，终于读懂了通行证的分量：它不是一张形式文件，而是保证“支撑杆”能落地、斜率能对准谷底的契约。

g(λ,ν)=inf⁡x[f0(x)+∑i=1mλifi(x)+ν⊤(Ax−b)],d∗=sup⁡λ⪰0g(λ,ν)\displaystyle g(\lambda,\nu) = \inf_x \left[ f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^{\top}(Ax - b) \right],\qquad d^* = \sup_{\lambda \succeq 0} g(\lambda,\nu)
对偶函数是“海关压价函数”：把约束当成收费项目，在全部货单里找最吃亏的报价，再挑报价里的最高者。
  1. 单价 $\lambda_i \ge 0$每个不等式约束的“过路费单价”，海关的自由度，必须非负。
    λi≥0\displaystyle \lambda_i \ge 0
  2. 许可证 $\nu$等式约束的“许可证费用”，可正可负，因为它不限制方向。
    ν⊤(Ax−b)\displaystyle \nu^{\top}(Ax - b)
  3. 最坏情况 $\inf_x$对全部可能的货单（含不合格的）取下确界，海关压价压到最狠。
    inf⁡x[f0(x)+∑i=1mλifi(x)+ν⊤(Ax−b)]\displaystyle \inf_x \left[ f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^{\top}(Ax-b) \right]
  4. 上确界 $d^*$海关在合法单价里挑最高报价，得到对偶最优值。
    d∗=sup⁡λ⪰0g(λ,ν)\displaystyle d^* = \sup_{\lambda \succeq 0} g(\lambda,\nu)

哪些问题天生揣着通行证

好消息是：日常工作中遇到的很多问题，Slater 条件天然成立，通行证早就揣在兜里。小斯盘点他常接的三种货运单，发现每一单都自带通行证。他总结出一张“免检名单”，从此过关格外顺当。

第一种是线性规划（LP）。它的约束全是仿射的，Slater 条件退化为“问题可行”——只要货单存在一个可行方案，通行证就在。第二种是二次规划（QP），目标函数是二次的、约束是线性的，只要可行域里有任何一个点满足线性约束（几乎总是成立），Slater 就满足。第三种是半正定规划（SDP），约束形如 X ⪰ 0，这时代数语言变成了矩阵语言：

这条“免检名单”直接解释了内点法的用武之地：内点法恰恰需要从一个严格可行点出发，在可行域内部抄近道走向最优。没有 Slater，内点法连起点都找不到。小斯乐了：原来我接的大多数活，通行证早就揣在兜里。

min⁡X tr(CX)s.t.tr(AiX)=bi,  i=1,…,p,X⪰0\displaystyle \min_{X}\ \mathrm{tr}(CX) \quad \text{s.t.} \quad \mathrm{tr}(A_i X) = b_i,\; i=1,\dots,p,\qquad X \succeq 0
半正定规划的 Slater 要求存在一个严格正定解 X ≻ 0，即所有特征值都严格大于零的“矩阵内点”。
  1. 矩阵变量 $X$优化的对象是一整个对称矩阵，而不是一个数。
    X=X⊤∈Sn\displaystyle X = X^{\top} \in \mathbb{S}^{n}
  2. 迹内积 $\mathrm{tr}(CX)$矩阵版的“点积”，把成本矩阵 C 和决策矩阵 X 逐项相乘再求和。
    tr(CX)\displaystyle \mathrm{tr}(CX)
  3. 半正定 $X \succeq 0$所有特征值非负，对应“贴着墙也能放货”。
    X⪰0\displaystyle X \succeq 0
  4. 严格正定 $X \succ 0$所有特征值严格大于零，这才是“站在仓库正中央”的矩阵版本。
    X≻0\displaystyle X \succ 0

失效警示：卡在海关的清单

通行证不是万能的。小斯有一次接到一个“诡异”的订单：目标函数要求最小化某个负指数成本，而约束把可行方案硬生生压成一条"x = 0"的竖线。他兴冲冲想用对偶方法抄近路，老关却摇头：你的货单里没有任何严格可行的存放点，我的估价给不了你保证。

这类问题的共同特征是可行域的相对内部为空：找不到任何一个点能让你画出一颗不越界的小球。即使问题是凸的，强对偶也可能失效，对偶间隙大于零。经典的例子长这样：最小值 1 藏在 x = 0 这条线上，而海关的对偶估价只能摸到 0，间隙整整差了 1——海关彻底“看不穿”你。

所以动手之前，小斯会掏出贴在驾驶座前的检查清单：第一，问题是不是凸的？非凸问题 Slater 根本不适用。第二，可行域有没有“厚度”？是否存在严格满足所有非仿射不等式的点。第三，若约束全是仿射，问题是否可行？线性规划的 Slater 退化为可行性检查。三关一过，对偶这条近路才敢放心踩油门。

min⁡x e−xs.t.x2y≤0,y>0⟹p∗=1,d∗=0,gap=1\displaystyle \min_x\ e^{-x} \quad \text{s.t.} \quad \frac{x^2}{y} \le 0,\quad y > 0 \qquad \Longrightarrow \qquad p^* = 1,\quad d^* = 0,\quad \mathrm{gap} = 1
这个例子说明：凸问题 + 无严格内点 = 强对偶可能失效，对偶间隙可以实打实地大于零。
  1. 目标函数 $e^{-x}$负指数成本，最小化它在 x 越大时越接近 0，但约束不许 x 乱跑。
    f0(x)=e−x\displaystyle f_0(x) = e^{-x}
  2. 致命约束 $\frac{x^2}{y} \le 0,\ y > 0$y 必须为正，迫使 x² 只能取 0，可行集被压成 x = 0 的竖线。
    x2y≤0,y>0\displaystyle \frac{x^2}{y} \le 0,\quad y > 0
  3. 结果 $p^* = 1,\ d^* = 0$真实成本是 1，海关估价只有 0，间隙为 1。
    p∗−d∗=1>0\displaystyle p^* - d^* = 1 > 0

AI 应用场景

机器学习中的 SVM 对偶求解

阶段：模型训练 / 优化求解

解决的问题：训练支持向量机时，直接求解原问题在高维特征空间里又慢又笨；工程师习惯转成对偶问题再优化。传统做法不敢确认转换是否“等价”，怕对偶间隙偷偷吃掉精度。有了 Slater 条件，只要确认 SVM 的二次规划存在严格可行点，就能保证强对偶成立，对偶解就是原问题解。

具体案例：训练一个线性 SVM 分类器时，优化器用 SMO 算法迭代求解对偶变量 α。由于该 QP 天然满足 Slater，KKT 条件可以直接用于判断哪些样本是支持向量，最终算出的超平面与原问题直接求解完全一致。

大规模线性规划的资源调度

阶段：约束优化 / 运筹决策

解决的问题：物流排产、仓储调拨这类问题常建模为数千变量的线性规划，交给内点法求解。内点法需要从严格可行点起步，而 LP 约束全是仿射，Slater 退化为“模型可行”——工程师只需确认模型存在可行方案，就能放心使用内点法，不必担心对偶方法给出偏离真实最优的答案。

具体案例：某仓库的每日拣货路径规划写成 LP 后，建模工程师先用单纯形法做一次可行性探测，确认有解后直接切到内点法求解大规模实例，收敛稳定且间隙始终为零。

半正定规划松弛的紧度验证

阶段：算法设计 / 理论验证

解决的问题：聚类、最大割等组合优化问题常用 SDP 松弛来逼近，对偶问题则用来验证松弛的紧度。若 SDP 满足 Slater 条件（存在严格正定解），强对偶成立，松弛界可信，近似比证明才站得住脚。

具体案例：研究者在验证某个图聚类 SDP 松弛时，先构造一个扰动矩阵证明严格正定解存在，再放心用对偶问题计算松弛界，最后成功给出近似比上界。

Python 演示

python68 行
import math  def tightest_disk_point():    # 健康问题: min x^2+y^2, 约束 (x-2)^2+y^2 <= 1    # 圆上离原点最近的点是 (1, 0), 最优值 p* = 1    return 1.0  def dual_fn_healthy(lam):    # 对偶函数 g(lam) = inf_x,y [x^2+y^2+lam*((x-2)^2+y^2-1)]    # 解析最小值出现在 x = 2*lam/(1+lam), y = 0    x = 2.0 * lam / (1.0 + lam)    return 3.0 * lam - 4.0 * lam * lam / (1.0 + lam)  def dual_star_healthy():    # 在 lam >= 0 上搜索 g(lam) 的最大值, 得到 d*    best = -1e9    lam = 0.0    while lam <= 5.0:        v = dual_fn_healthy(lam)        if v > best:            best = v        lam += 0.001    return best  def is_strictly_feasible_healthy():    # Slater 检查: (1.5, 0) 是否严格满足不等式 (1.5-2)^2+0 < 1    x, y = 1.5, 0.0    return (x - 2.0) ** 2 + y * y < 1.0  def dual_fn_failing(lam):    # 退化问题: min e^{-x}, 约束 x^2/y <= 0, y > 0    # 固定 x 后, inf_{y>0} lam*x^2/y = 0 (让 y 趋于无穷)    # 所以 g(lam) = inf_x e^{-x} = 0, 与 lam 无关    return 0.0  def dual_star_failing():    # 对偶函数恒为 0, 上确界 d* = 0    return 0.0  def is_strictly_feasible_failing():    # 约束 x^2/y <= 0 且 y > 0 迫使 x = 0, 此时 x^2/y = 0 而非 < 0    # 非仿射约束无法严格成立, Slater 不成立    x, y = 0.0, 1.0    return x * x / y < 0.0   # 恒为 False  def main():    print("== 健康问题: 圆盘约束 ==")    p = tightest_disk_point()    d = dual_star_healthy()    print("严格可行点 (1.5,0) 存在? %s" % is_strictly_feasible_healthy())    print("p* = %.6f, d* = %.6f, 对偶间隙 = %.6f" % (p, d, p - d))     print("== 退化问题: x^2/y <= 0 ==")    d2 = dual_star_failing()    print("存在严格可行点? %s" % is_strictly_feasible_failing())    print("p* = 1.0, d* = %.6f, 对偶间隙 = %.6f" % (d2, 1.0 - d2))  if __name__ == "__main__":    main()
目的：用一个“健康问题”（圆盘约束，Slater 满足）和一个“退化问题”（可行集被压成竖线，Slater 失效）对比演示：前者对偶间隙为零，后者间隙为 1。
  1. return 3.0 * lam - 4.0 * lam * lam / (1.0 + lam)这是把 λ 固定后对 x、y 做无约束最小化得到的对偶函数解析式，省去逐点网格搜索。
  2. x = 2.0 * lam / (1.0 + lam)拉格朗日函数在 x 方向的最优点，随 λ 变化而移动。
  3. while lam <= 5.0:在 λ ≥ 0 的区间上以 0.001 步长枚举，逼近对偶最优值 d\* 的上确界。
  4. return (x - 2.0) ** 2 + y * y < 1.0Slater 检查：验证 (1.5, 0) 严格落在圆盘内部，即存在严格可行内点。
  5. return 0.0退化问题里，对 y 取下确界时可以让 y 趋于无穷，使拉格朗日项归零，因此对偶函数恒为 0。
  6. return x * x / y < 0.0 # 恒为 False唯一可行点 x=0 让非仿射约束恰好取等号，永远找不到严格可行点。
  7. print("p* = %.6f, d* = %.6f, 对偶间隙 = %.6f" % (p, d, p - d))直接输出间隙，健康问题应精确为 0，退化问题应接近 1。

常见误区

误区网上都说 Slater 是强对偶的通行证，那我找不到严格可行点，对偶方法是不是就完全不能用了？对偶间隙肯定大于零吧？

正解Slater 是充分条件，不是必要条件。有些问题即使没有严格内点，强对偶依然成立，比如某些退化的线性规划。通行证是“VIP 通道的保证”，但偶尔有人翻墙也能过去——只是不能保证每次都能过去。正确的表述是：满足 Slater 一定能得到强对偶，不满足时“可能”失效，需要具体分析。

为何常见：因为教材通常只强调“Slater ⇒ 强对偶”这一条正向箭头，初学者容易把充分条件误读成“充要条件”。

误区目标函数和约束都是凸的，那 d\ = p\ 肯定是铁板钉钉的事吧？毕竟凸优化性质那么好。

正解凸性是强对偶的“舞台背景”，但不是“剧本保证”。经典反例中，可行域被约束压成一条竖线，问题依然是凸的，对偶间隙却实打实等于 1。路再直，如果路面窄成一根钢丝，你也无法在上面平稳驾驶。

为何常见：很多课程先讲凸优化再讲对偶，学生容易把“凸”和“易解”划等号，忽略了可行域的拓扑结构同样关键。

误区我找到一个可行点，所有不等式约束都满足 fᵢ(x) ≤ 0，有些还刚好等于 0，这不就是严格可行吗？

正解恰恰相反，取等号是最危险的信号。Slater 要求非仿射约束严格成立 fᵢ(x) < 0，等于 0 意味着点贴在墙上，没有“一拳距离”。等号约束（Ax = b）不需要严格，但不等式必须是“打开”的状态。

为何常见：初学者把“可行”和“严格可行”混为一谈，忽略了“严格”二字背后的几何含义——可画小球、留有余地。

误区我用优化器跑完，所有约束残差都压到 1e-12 了，这不就说明 Slater 条件满足了吗？

正解Slater 是问题本身的存在性性质，与算法输出的残差无关。哪怕残差是 1e-12，如果可行域的拓扑结构没有内部，Slater 依然不成立。判断通行证要看问题结构（有没有严格内点），不是看数值打印。

为何常见：实践者习惯用数值结果反推理论性质，但“算法找到近似可行点”和“问题存在严格内点”是两码事。

面试题

Q1. 弱对偶 d\ ≤ p\ 的正确含义是？

单选题 · easy

  • A.海关估价总高于实际成本
  • B.对偶值是原最优值的下界← 正确答案
  • C.对偶间隙的值可以为负
  • D.弱对偶需 Slater 才成立

答案：B。弱对偶说海关估价永远不高于真实成本，所以 d\ 是 p\ 的下界。A 方向反了；C 错在间隙必然非负；D 错在弱对偶对任何能写出对偶函数的问题都成立，不需要 Slater。

Q2. Slater 条件的核心要求是？

单选题 · easy

  • A.可行域中有一个严格可行点← 正确答案
  • B.目标函数必须是线性函数
  • C.约束必须是线性等式
  • D.最优解必须在边界上

答案：A。Slater 的本质是“存在一个非仿射约束严格小于零的可行点”，即严格内点。它对目标函数没有线性要求，约束也不限于等式，最优解更是常常在边界上——所以 B、C、D 都是干扰项。

Q3. “对偶间隙为零”意味着什么？

单选题 · easy

  • A.d\ 小于 p\，弱对偶成立
  • B.d\ 等于 p\，强对偶成立← 正确答案
  • C.原问题没有任何可行解
  • D.对偶问题一定是无界的

答案：B。间隙为零就是 p\ - d\ = 0，即 d\ = p\，这正是强对偶的定义。A 描述的是间隙大于零的情形；C、D 与间隙定义无关。

Q4. Slater 条件与强对偶的关系是？

单选题 · mid

  • A.Slater 是强对偶的必要条件
  • B.Slater 是强对偶的充分条件← 正确答案
  • C.Slater 与强对偶毫无关系
  • D.Slater 只保证弱对偶成立

答案：B。对凸问题，Slater 成立必然推出强对偶成立，所以是充分条件；但存在不满足 Slater 却依然强对偶成立的例子，所以它不是必要条件。C、D 显然错误。

Q5. 仿射约束在 Slater 条件中如何处理？

单选题 · mid

  • A.必须严格满足小于零
  • B.只需满足小于等于零← 正确答案
  • C.必须与等式约束合并
  • D.无需出现在条件里

答案：B。仿射约束天然“扁平”，无法也无需严格化，Slater 只要求它们满足 fᵢ(x) ≤ 0。B 正确；A 错在把严格性用到仿射约束上；C、D 都没有依据。

Q6. 线性规划通常天然满足 Slater 条件，原因是？

单选题 · mid

  • A.目标函数总是严格凸
  • B.约束全是仿射约束← 正确答案
  • C.可行域一定是无界的
  • D.最优解必然唯一

答案：B。LP 的约束全是仿射的，按 Slater 的仿射豁免规则，条件退化为“问题可行”。B 正确；LP 目标函数不一定凸（线性函数既是凸也是凹），可行域有界无界皆可，最优解也可能不唯一。

Q7. 下列哪个可行域完全没有相对内部？

单选题 · hard

  • A.三维空间中的一条线段← 正确答案
  • B.三维空间中的一个实心球
  • C.三维空间中的一个立方体
  • D.三维空间中的一个椭圆盘

答案：A。相对内部要放进“所在空间内部”看：一条线段在三维空间里没有体积可言，处处都是边界；实心球、立方体、椭圆盘都有真正的内部点。选 A。

Q8. 哪些凸问题通常天然满足 Slater 条件？

多选题 · mid

  • A.可行的线性规划问题← 正确答案
  • B.有严格可行解的二次规划← 正确答案
  • C.存在正定解的半正定规划← 正确答案
  • D.任意非凸整数规划问题

答案：ABC。LP 约束全仿射，可行即满足；QP 只要可行域有内点即可；SDP 需要严格正定解。D 是非凸离散问题，Slater 定理根本不适用。

Q9. 关于严格可行点，下列说法正确的有？

多选题 · mid

  • A.非仿射约束需严格小于零← 正确答案
  • B.仿射约束无需严格化← 正确答案
  • C.等式约束必须留有余量
  • D.严格可行点周围有可行小球← 正确答案

答案：ABD。A、B 正是 Slater 条件对两类约束的差别待遇；D 是“可画开球”的几何等价说法。C 错，等式约束 Ax = b 必须精确满足，没有任何余量可言。

Q10. Slater 条件不成立时，可能出现哪些情况？

多选题 · hard

  • A.强对偶依然成立的结果← 正确答案
  • B.对偶间隙严格大于零← 正确答案
  • C.内点法找不到可行起点← 正确答案
  • D.对偶最优值超过原问题

答案：ABC。Slater 是充分条件，不满足时强对偶“可能”照样成立（A），也可能出现正间隙（B）；内点法需要严格可行起点，无内点则起步困难（C）。D 永远不可能，因为弱对偶 d\ ≤ p\ 对任何问题都成立。