CSCI3230 L04 · Part 6/6 ESTR3108：Lagrange multipliers and duality

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L04，第 6 部分 / 共 6 部分 · 原件 L04-Support-Vector-Machine-2026T1.pdf（本地课件） p.50–69 定位：把等式约束、弱对偶和 KKT 联系起来，并逐行消去 SVM 的原变量。前后：上一份 Summary

p.50 分节页；p.51 Outline 列拉格朗日/对偶基础及SVM推导。

选读边界：原件p.50明确进入ESTR3108扩展。第一次学CSCI3230，可先完成Part 1–5与八点恢复，再来学习本篇。需要的前置是平方函数求导、向量内积、不等式；每次出现min/max先说清“固定谁、改变谁”，比先记整页公式更重要。

乘子为何能编码约束（p.52–54）【新】

p.52从带约束优化开始：我们想让目标函数小，但只能在满足条件的点中选。没有约束时，导数为零可找驻点；有约束时，一条看起来能下降的方向可能走出可行区域，所以不能直接套无约束规则。

先只考虑等式 $h(w)=0$ 。这里 $w\in\mathbb R^d$ 泛指原未知向量， $f(w)$ 与 $h(w)$ 都输出一个数。p.53引入实数乘子 $\beta$ ，构造 $L(w,\beta)=f(w)+\beta h(w)$ 。 $\beta$ 可以正也可以负，它不是概率。这个构造把约束放进一个函数，以便用导数表达“目标和约束的作用平衡”。

p.54对乘子求导给 $\partial L/\partial\beta=h(w)=0$ ，原等式回来了；对原变量求导给 $\nabla f(w)+\beta\nabla h(w)=0$ 。符号 $\nabla$ 表示收集各坐标偏导的向量，每项长度都为 $d$ 。几何上，在光滑正则的最优点，沿约束面可走的方向已经不能一阶降低目标，因此目标梯度与约束的法向方向有关；这不是说两个函数的值相等。

p.53的一般式有 $l$ 条等式，而不仅一条：

L(w,\beta)=f(w)+\sum_{j=1}^{l}\beta_jh_j(w),\quad \nabla_wL=\nabla f+\sum_j\beta_j\nabla h_j=0,\quad \frac{\partial L}{\partial\beta_j}=h_j(w)=0.

若约束梯度线性无关，切向量 $v$ 满足每个 $\nabla h_j(w^*)^Tv=0$ 。p.54给出的二阶必要检查是这些可行切方向上的 $v^T\nabla^2_{ww}L(w^*,\beta^*)v\ge0$ ；检查的不是任意方向，也不是仅看目标函数某一个偏导。

边界提醒：这些方程一般只筛选候选驻点，可能得到最小、最大或其他驻点。还要检查可行性和最优性条件。也不是对 $w,\beta$ 一起求最小：若 $h(w)\ne0$ ，自由改变 $\beta$ 往往可以使 $L$ 向负无穷走。下面用课件自己的小例子，把方程与实际最小值对上。

原页措辞的适用条件：p.54把“唯一乘子、驻点、约束切方向上Hessian半正定”写成一般局部最小值的双向判据，不能脱离正则性与充分条件照用。补充反例：一维函数 $f(t)=-t^4$ 在0处一阶导数与二阶导数都是0，但附近非零点函数值更小，0反而是局部最大。二阶半正定通常是必要线索，不是一般情形的充分证明；乘子唯一性也需要额外条件。下一节用完成平方直接证明最小，避免误用该页简写。

讲义等式约束算到底（p.55–56）

题面（L04 p.55，公式按原页重排）：最小化 $2x_1^2+x_2^2$ ，满足 $x_1+x_2=1$ 。 $x_1,x_2$ 是两个可选实数；目标用不同代价惩罚它们的平方。没有约束会选全零，但全零的和不是1，不可行。

先将约束移到零的一侧： $h=x_1+x_2-1$ 。构造

L=2x_1^2+x_2^2+\beta(x_1+x_2-1).

对 $x_1$ 求导时 $x_2,\beta$ 暂时当常数，得到 $4x_1+\beta=0$ ；对 $x_2$ 得 $2x_2+\beta=0$ ；对 $\beta$ 得 $x_1+x_2-1=0$ 。前两式都等于同一个 $-\beta$ ，所以 $4x_1=2x_2$ ，即 $x_2=2x_1$ 。代入约束： $3x_1=1$ ，故 $x_1=1/3,x_2=2/3$ 。再代回第一式， $\beta=-4/3$ 。

目标值为 $2(1/3)^2+(2/3)^2=2/9+4/9=2/3$ 。注意分配并不各一半：第一坐标的平方代价更大，最优时给它较小份额。

怎样确认不是最大值？用约束消去 $x_2=1-x_1$ ：

\begin{aligned} 2x_1^2+(1-x_1)^2 &=3x_1^2-2x_1+1\\ &=3(x_1-1/3)^2+2/3. \end{aligned}

平方项永不为负，在 $x_1=1/3$ 时恰为零，因此确是整个可行直线上的最小值。p.56椭圆等高线与直线相切的图表达同一事实：只允许在线上走，能触及的最低等高线停在这个切点。算式给结论，图帮助你理解为什么受限后不能再走向原点。

不等式为何需要非负乘子（p.57–59）【新】

p.57允许两类约束： $g_i(w)\le0$ 是第 $i$ 条不等式， $h_j(w)=0$ 是第 $j$ 条等式。对应乘子分别为 $\alpha_i\ge0$ 和符号自由的 $\beta_j$ 。于是

L(w,\alpha,\beta)=f(w)+\sum_i\alpha_i g_i(w)+\sum_j\beta_j h_j(w).

每个函数值与乘子都是标量，所以所有项可以相加。先固定一个候选 $w$ ，像检查员一样让乘子把 $L$ 尽可能抬高。这个“检查员”是理解先后顺序的类比，数学操作是对乘子取上确界。

若某个不等式被违反，即 $g_i(w)>0$ ，令非负 $\alpha_i$ 越来越大，就把 $L$ 推向正无穷。若等式不满足， $h_j(w)$ 非零，自由选择 $\beta_j$ 的正负也能使乘积为正且无限增大。于是不可行的点付出无限代价。

反过来，若 $w$ 可行，所有不等式项都不正、等式项全为零；把所有 $\alpha_i$ 设零便可达到 $f(w)$ ，其他选择不会更高。因此最大化乘子以后，可行点回到原目标，不可行点被排除。这就是p.58–59把约束编码进目标的原因。

沿原页符号，这个编码函数记为

\theta_P(w)=\sup_{\alpha\ge0,\beta}L(w,\alpha,\beta) =\begin{cases}f(w)&w\text{ 可行},\\+\infty&w\text{ 不可行},\end{cases} \qquad p^*=\inf_w\theta_P(w).

这里用上确界/下确界兼容极值未取到的情形；课件以max/min简写。p.59一行把 $\theta_P(w)$ 与已经最小化的值写在同一等号旁，阅读时应区分“仍依赖 $w$ 的函数”和“对 $w$ 优化后的标量 $p^*$ ”。

补充自取数字：固定 $f=3,g=-2$ ， $L=3-2\alpha$ ，在 $\alpha\ge0$ 中最大值为3（取0）；固定 $g=2$ 则 $L=3+2\alpha$ 没有有限上界。若允许不等式乘子取负，前一个本来可行的点也可能被推向正无穷，所以符号约束不是装饰。

交换先后为何只得到下界（p.60–61）

原问题等价于“先让乘子检查每个点，再在可行点中挑最小值”。p.60把先后换过来：固定乘子，先对原变量取最小，定义对偶函数

q(\alpha,\beta)=\inf_w L(w,\alpha,\beta).

这里的 $\inf$ 是下确界，允许最小值尚未实际取到。对偶再在 $\alpha\ge0$ 上挑最大的下界，记最优值 $d^{\ast}$ ；原问题最优值记 $p^{\ast}$ 。

p.60把同一对偶函数写为 $\theta_D(\alpha,\beta)$ ；因此完整值式是 $d^*=\sup_{\alpha\ge0,\beta}\theta_D(\alpha,\beta)$ 。原页末行的 $\theta_D(w)$ 是变量名简写错误：内层已经对 $w$ 优化，外层改变的是乘子。

为什么只是下界？任取一个可行 $\bar w$ ：第一步 $q\le L(\bar w,\alpha,\beta)$ ，因为对所有 $w$ 取最低不会高于这一点；第二步 $L(\bar w,\alpha,\beta)\le f(\bar w)$ ，因为非负乘子乘非正约束只会减小目标，等式项为零。连起来 $q\le f(\bar w)$ 。这对每个可行点和每个可行乘子都成立，所以最大下界也不会超过最小原目标，即p.61的 $d^{\ast}\le p^{\ast}$ ，称弱对偶。

用p.55的同一个例子实际算下界。固定 $\beta$ 后，无约束最小化 $L$ 给 $x_1=-\beta/4,x_2=-\beta/2$ 。平方两项之和为 $3\beta^2/8$ ；乘子项为 $-3\beta^2/4-\beta$ 。相加得到

q(\beta)=-\frac38\beta^2-\beta.

例如 $\beta=0$ 给下界0； $\beta=-1$ 给 $5/8=0.625$ ，都不超过已知原最小值 $2/3$ 。对这个开口向下的二次函数求最大，导数 $-3\beta/4-1=0$ 给 $\beta=-4/3$ ，此时下界恰达 $2/3$ 。这里两者相等，叫强对偶；一般问题不可以仅因交换符号就假设相等。

补充：用一维约束把弱对偶与零间隙算出来

自编问题为最小化 $x^2$ ，约束 $x\ge1$ ，写成 $g(x)=1-x\le0$ 。拉格朗日函数为 $L(x,\alpha)=x^2+\alpha(1-x)$ ， $\alpha\ge0$ 。固定乘子先对 $x$ 取下确界：配方得

L=(x-\alpha/2)^2+\alpha-\alpha^2/4, \qquad q(\alpha)=\alpha-\alpha^2/4.

当 $\alpha=0$ ，下界为0；当 $\alpha=1$ ，下界为3/4。它们都不超过原问题最优值1，但较紧的下界更有用。对偶最大化这个抛物线，导数 $1-\alpha/2=0$ 得 $\alpha=2$ ，此时 $q=1$ 。原问题在 $x=1$ 达到1，两边相等。

逐项验KKT： $1-x=0$ 可行； $\alpha=2\ge0$ ；驻点 $2x-\alpha=0$ ；互补 $\alpha(1-x)=0$ 。把任何一条删掉都可能接受错误候选。这里通过直接配方算出了相等，不是仅凭把min和max交换就宣布相等；弱对偶只先保证下界关系，强对偶需要成立条件或另外证明。

KKT 是四类条件一起成立（p.62–63）【新】

KKT是一组把候选原变量与候选乘子放在一起检查的条件。先按“排除哪种错误”理解，而不是背五行陌生符号。

p.63特别解释互补：若 $\alpha_i>0$ ，必须 $g_i(w)=0$ （活跃约束）；若 $g_i(w)<0$ ，必须 $\alpha_i=0$ 。约束“活跃”只是恰好碰到边界，不是被删掉。两个零的乘积也是零，所以不能反推“活跃必有正乘子”。

补充自取检查：候选 $g=-2,\alpha=0.5$ 原可行且对偶可行，但乘积−1，不互补；候选 $g=0,\alpha=0$ 则符合互补。每条条件各有工作，只验其中一条不够。

适用前提不能丢：对于可微凸目标、凸不等式与仿射等式，满足KKT的点可以作为全局最优证书；要保证最优点存在乘子并获得强对偶，通常还需要适当约束资格。硬间隔SVM在严格可分时可共同放大参数，让所有不等式严格满足，这支持其凸对偶理论。一般非凸问题的KKT驻点不能自动叫全局最优，p.62的结论应放在相应假设中读。

小检查（补充）：一个训练点功能间隔恰为1、乘子为0，单凭互补能否判为计算错误？

参考答案

不能。约束剩余量为0，乘以0仍为0，互补成立。还需检查整组可行、驻点等条件。退化情况下它可能在支撑面上但不承担非零对偶权重。

补充 · 约束活跃但乘子为零的具体最优点（通识讲解；演示数据不属于原题）。

考虑演示问题：最小化 $x^2$ ，限制 $x\ge0$ ，写成 $g(x)=-x\le0$ 。最优点为 $x=0$ ，限制恰好取等号，是活跃约束。拉格朗日函数为 $L=x^2-\alpha x$ ，驻点条件为 $2x-\alpha=0$ ；代入 $x=0$ 得 $\alpha=0$ 。原可行、对偶可行、驻点和互补都满足。

为什么零乘子并不矛盾？即使去掉这条限制，原目标也在 0 处最小；这条边界恰好碰着最优点，但没有把最优点从更低处挡回来。因此“位于边界”描述位置，“乘子非零”描述约束在当前最优条件中承担的作用，二者不是同一个判断。这也给本篇对课件逆命题的提醒提供了一个可直接重算的反例。

SVM 拉格朗日函数的逐项展开（p.64–66）

p.64回到硬间隔。原变量是 $w\in\mathbb R^d,b\in\mathbb R$ ，每个样本贡献一条不等式 $1-y_i(w^Tx_i+b)\le0$ 。原问题没有等式约束，所以此时不需要 $\beta$ ；后面对偶中的等式是消元后产生的，别把两层问题混在一起。

从定义按分配律展开：

\begin{aligned} L&=\frac12w^Tw+\sum_i\alpha_i[1-y_i(w^Tx_i+b)]\\ &=\frac12w^Tw+\sum_i\alpha_i-\sum_i\alpha_i y_iw^Tx_i-b\sum_i\alpha_i y_i\\ &=\frac12w^Tw+\sum_i\alpha_i-w^T\left(\sum_i\alpha_i y_ix_i\right)-b\sum_i\alpha_i y_i. \end{aligned}

最后一行把与样本编号无关的 $w^T,b$ 提出求和。括号中的和是 $d$ 维向量；它与 $w^T$ 相乘后为标量，维度对得上。

p.66先固定 $\alpha$ ，再对 $w,b$ 最小化。逐坐标看，对 $w_k$ 求导得到 $w_k-\sum_i\alpha_i y_i x_{ik}=0$ ，把 $d$ 条式子合起来就是 $w=\sum_i\alpha_i y_ix_i$ 。对 $b$ 求导则得到 $-\sum_i\alpha_i y_i=0$ 。

后一式不仅是求导技巧，还关系到下界是否有限：若 $\sum_i\alpha_i y_i=c\ne0$ ，函数里有 $-bc$ ，任意改变不受限的 $b$ 就可使它趋向负无穷。因此要得到有用的有限对偶下界，必须限制 $c=0$ 。这也是为什么正负类别的乘子加权和平衡，而非要求两类样本数一样多。

消元、求解、恢复预测（p.67–69）

先临时记 $a=\sum_i\alpha_i y_i x_i$ ，它是 $d$ 维向量。上节给出最小化时 $w=a$ 、 $\sum_i\alpha_i y_i=0$ 。代回展开式：半个平方项为 $a^Ta/2$ ，线性权重项为 $-a^Ta$ ，偏移项为零。因此

q(\alpha)=\sum_i\alpha_i-\frac12a^Ta.

负的半个平方来自“一半减一整份”，不是省略了半批数据。把 $a$ 展开，与自身做内积时左边每一项都要和右边每一项配对：

a^Ta=\sum_i\sum_j\alpha_i\alpha_jy_iy_jx_i^Tx_j.

两个求和索引代表两次独立选择样本。只留 $i=j$ 会漏掉交叉项，变成另一道问题。p.68于是最大化上述 $q$ ，满足 $\alpha_i\ge0$ 和 $\sum_i\alpha_iy_i=0$ ，可用QP/SMO求解。

p.69恢复模型时先合成 $w$ ，再用正乘子支持点求 $b=y_s-w^Tx_s$ 。用p.27–29的三个非零系数，乘子和为1、 $w=(1,0)^T$ ，故 $q=1-1/2=1/2$ ，与原目标相等。原可行、对偶可行、驻点、互补均已在Part 2逐项检查，这比“直线看着不错”更强。

新点的分数可写为 $f(x)=\sum_i\alpha_i y_i x_i^Tx+b$ 。零系数项不贡献，所以保留非零项就足够；在线性核情形也可预先合成一个 $w$ ，预测不必每次访问训练样本。一般核则用 $K(x_i,x)$ 代替内积。这里要区分“支持向量足以预测”和“任何实现必须保存全部支持向量”。

原页p.69把零乘子推成严格在间隔外，退化情况下并不成立；可安全使用的是“正乘子必在面上”“严格在外必为零”。历史分类概念题见附录 A1，属于旧年份练习，不视为本学期必需证明清单。

本讲核心考点

原可行时拉格朗日乘子最大化还原原目标（p.58–59，C 级）。
弱对偶下界，强对偶需条件（p.60–61，C 级）。
KKT 互补不能无条件双向反推（p.62–63，C 级）。
SVM 对偶只需样本内积（p.64–69，A 级：HW02 Q1）。

附录

A1 作业/往年题演练（非讲义内容）：对偶、核与分类损失

题面（ESTR-Final-Exam-2023T1.pdf · Part II Q6 · p.5；扫描件，视觉读取）

p.5 6. What optimization method is used to transform SVM primal problem to a dual problem? If the data points are linearly inseparable, explain why kernel SVM can address the problem and state two commonly used typical SVM kernels. In addition, does kernel SVM belong to supervised learning or unsupervised learning? (7%)

先逐句识别问题，不要用“kernel”一词回答所有小问。第一问是优化方法：拉格朗日乘子把分类约束放入目标，固定乘子后消去 $w,b$ ，再优化乘子。这改变求解变量，不改变训练标签。

第二问是表示能力：核计算某个映射空间的内积，使原坐标中的弯曲边界可以对应新空间超平面。它提供改善可能，不保证任意核都能分开任意数据。举两种常见形式可以用多项式 $K(x,z)=(x^Tz+c)^d$ 与RBF $K(x,z)=\exp(-\gamma\lVert x-z\rVert^2)$ ；需说明参数满足相应有效范围，例如正整数次数、非负常数以及正gamma。

第三问看监督信号从哪里来：SVM训练约束仍有真实标签 $y_i$ ，因此是有监督学习。新空间维度高不等于没有标签。这是2023 ESTR卷的概念练习，不据它推断CSCI3230本学期必考。

题面（同卷 · Part I Q2 · p.2；扫描件，视觉读取）

p.2 2. (3%) For classification methods, which of the following statement is not true?

A. Once a linear SVM classifier is trained, you can only rely on support vectors to make predictions for new samples.

B. Soft-margin SVM aims to deal with noisy samples in training data.

C. Logistic regression uses gradient descent on Hinge loss to train the classification model, because its analytical solution is difficult to obtain.

D. Neural networks can address binary classification by using the softmax activation.

逐项对照所学机制：C把logistic回归与hinge损失配在一起，是概念搭配错误；logistic回归通常使用交叉熵，hinge对应软间隔SVM。这里给的是根据模型定义的解析，不宣称取得官方答案表。

B描述用软间隔容忍噪声的动机；“容忍”是付费违约而非删除样本。D可用两个logits经softmax表达二分类，所以不是因类别数为2就排除softmax。

A的英语“only rely”需要分清两种意思：非零乘子对应的支持样本足以组成预测，零项无贡献；但线性模型可以预先把它们合成 $w$ ，之后直接算 $w^Tx+b$ ，不必每次保存并访问原样本。不要把充分的数学表示误读成唯一软件实现。若按“支持向量足够”理解，A符合课件主题；若按“所有实现必须逐一访问它们”理解，则字面过强。

返回正文

来源与证据

页码按当前本地阅读版 PDF；L04 共69页，未把旧年份讲义当成本学期原件。
原件：L04-Support-Vector-Machine-2026T1.pdf（本地课件），p.50–69；均为当前 PDF 页号。
本次正文逐页核对本讲原件；文末历史题明确标旧年份，只作练习，不据此推断本学期考核要求。
往年卷仅证明相应年份考过；2024 卷及 2025 节选未公开的选择题不作推断。