数学优化理论 · 第 9 课
拉格朗日对偶:为什么最小化可以构造下界?强对偶什么时候成立?
2026 年 10 月 28 日|第 2 周·第 2 天|讲授约 18 分钟(自测另计)
今天的问题。 昨天我们学习了 LICQ、MFCQ 与 Slater,知道它们可以帮助保证 KKT 乘子存在。今天反过来问:乘子除了证明最优性,还能不能帮我们求解问题?为什么求解一个新的「最大化」问题,能给原来的「最小化」问题提供可靠下界?
学习目标。 能正确写出 (\mathcal L)、(q)、(p^)、(d^);亲自证明弱对偶和对偶函数凹性;区分「零对偶间隙」与「对偶最优点达到」;推导一个二次规划的原始—对偶解并手算两步对偶上升。
一、定义问题与假设:原问题为何有一个对偶问题?
考虑一般问题
[
\boxed{\begin{aligned}
p^*=\inf_{x\in\mathcal D}\quad &f_0(x)
\text{s.t.}\quad &g_i(x)\le0,\quad i=1,\ldots,m,
&h_j(x)=0,\quad j=1,\ldots,r.
\end{aligned}}\tag{1}
]
这里 (\mathcal D) 是各函数的公共定义域。为便于比较最优值,先假设原问题可行且 (p^*) 是有限实数;弱对偶本身不要求目标或约束凸。
采用约束形式 (g_i\le0),定义
[ \mathcal L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^m\lambda_i g_i(x)+\sum_{j=1}^r\nu_j h_j(x), \qquad \lambda_i\ge0,\ \nu_j\in\mathbb R. \tag{2} ]
对偶函数是在固定乘子时对 全部定义域内的 (x) 取下确界:
[ \boxed{q(\lambda,\nu)=\inf_{x\in\mathcal D}\mathcal L(x,\lambda,\nu).}\tag{3} ]
注意这里的内层 (\inf) 没有再施加原始不等式约束,否则可能得到完全不同的函数。(q) 允许取 (-\infty)。
对偶问题是
[ \boxed{d^*=\sup_{\lambda\ge0,\ \nu\in\mathbb R^r}q(\lambda,\nu).}\tag{4} ]
「原始问题求最小,为什么对偶问题求最大?」答案来自下面的严谨不等式。
二、弱对偶:从两行不等式得到全局下界
任意取一组允许的乘子 (\lambda\ge0,\nu),再取任意原始可行点 (x)。原始可行性意味着 (g_i(x)\le0)、(h_j(x)=0),所以
[ \mathcal L(x,\lambda,\nu) =f_0(x)+\underbrace{\sum_i\lambda_i g_i(x)}{\le0} +\underbrace{\sum_j\nu_j h_j(x)}{=0} \le f_0(x). ]
由下确界的定义:
[ \boxed{q(\lambda,\nu)\le \mathcal L(x,\lambda,\nu)\le f_0(x).}\tag{5} ]
让 (x) 在所有原始可行点中变化,再让乘子在对偶可行域内变化,得到
[ \boxed{d^\le p^.}\tag{6} ]
这叫弱对偶(weak duality),对非凸问题同样成立。对偶问题最大化 (q),是在所有合法的「可靠下界」中寻找尽可能紧的一个。
方向千万别记反: 原问题是 (\min),对偶值是下界;对任意原始可行点,(f_0(x)) 给出上界。于是
[ 0\le f_0(x)-p^*\le f_0(x)-q(\lambda,\nu) ]
当 (x) 可行、((\lambda,\nu)) 对偶可行时成立。右端是可计算的原始—对偶间隙证书;间隙小,代表这个可行解距离最优值不会太远。
三、对偶函数为什么一定是凹的?
固定任意 (x),(\mathcal L(x,\lambda,\nu)) 对乘子是仿射函数。对偶函数是这一族仿射函数的逐点下确界。严格验证:取乘子 (u=(\lambda,\nu))、(v=(\lambda’,\nu’)),(t\in[0,1]),
[
\begin{aligned}
q(tu+(1-t)v)
&=\inf_x\big[t\mathcal L(x,u)+(1-t)\mathcal L(x,v)\big]
&\ge t\inf_x\mathcal L(x,u)+(1-t)\inf_x\mathcal L(x,v)
&=tq(u)+(1-t)q(v).
\end{aligned}\tag{7}
]
中间不等式因为「对所有 (x),两项分别不小于各自下确界」。所以
[ \boxed{q\text{ 对乘子总是凹的,即使原问题非凸。}} ]
但别据此误认为原问题变得容易:计算一次 (q) 要对 (x) 做全局最小化,非凸时内层可能很困难;且对偶通常可能存在严格间隙。
四、贯穿例子:一个约束二次规划的原始解和对偶解
考虑
[ \boxed{\min_{x\in\mathbb R}\ \frac12x^2 \quad\text{s.t.}\quad 1-x\le0.}\tag{8} ]
这是在 (x\ge1) 上寻找离原点最近的点。原始最优解显然 (x^=1),最优值 (p^=\tfrac12)。
4.1 构造并消去原始变量
拉格朗日函数
[ \mathcal L(x,\lambda)=\frac12x^2+\lambda(1-x),\qquad\lambda\ge0. ]
对固定 (\lambda),配方:
[ \mathcal L(x,\lambda) =\frac12(x-\lambda)^2+\lambda-\frac12\lambda^2. ]
因此内层最小点 (x(\lambda)=\lambda),得到
[ \boxed{q(\lambda)=\lambda-\frac12\lambda^2,\qquad \lambda\ge0.}\tag{9} ]
现在对偶问题变成一个容易求解的凹二次函数最大化:
[ \max_{\lambda\ge0}\ \lambda-\frac12\lambda^2. ]
由 (q’(\lambda)=1-\lambda) 得到
[ \lambda^=1,\qquad d^=q(1)=\frac12=p^*. ]
这就是一个强对偶的例子:原始最优值与对偶最优值相等。其原问题为凸优化,且 (x=2) 严格满足 (1-x<0),即满足 Slater 条件。
4.2 用 KKT 同时核对原始解和乘子
[
\begin{cases}
1-x^\le0, &\text{原始可行},
\lambda^\ge0, &\text{对偶可行},
x^-\lambda^=0, &\text{驻点},
\lambda^(1-x^)=0, &\text{互补松弛}.
\end{cases}
]
取 ((x^,\lambda^)=(1,1)) 满足四式。这里唯一的不等式约束是活跃的,乘子为正;但不要推广为「所有活跃约束乘子必正」,前一课已经给过零乘子的反例。
4.3 亲自检查「上界-下界」
若你手中只有原始可行点 (x=1.25),则
[ f_0(1.25)=\frac12(1.25)^2=0.78125 ]
是原始最优值的上界。若对偶只算到 (\lambda=0.5),则
[ q(0.5)=0.5-\frac12(0.5)^2=0.375 ]
是下界。因此无需知道最优点,也可立即保证
[ 0.375\le p^\le0.78125,\qquad 0\le f_0(1.25)-p^\le0.40625. \tag{10} ]
注意 (x(\lambda)=\lambda):当 (\lambda=0.5),内层极小点 (x=0.5) 不满足 (x\ge1)。最小化拉格朗日函数得到的 (x(\lambda)) 并不自动是原始可行解,因此它的函数值不能随意当成原始上界。
五、强对偶、KKT、Slater:三个陈述不要混淆
| 概念 | 精确定义/作用 | 常见误解 |
|---|---|---|
| 弱对偶 | 对偶可行 ((\lambda,\nu)) 总给 (q(\lambda,\nu)\le p^*) | 必须先假设凸 |
| 强对偶 | (d^=p^),只说最优值相等 | 误认为对偶最优乘子必达到 |
| 对偶达到 | 存在有限乘子 ((\lambda^,\nu^)) 使 (q=d^*) | 上确界总能取到 |
| KKT 证书 | 凸问题中原始可行点与乘子满足 KKT,便得到最优性和零间隙 | 没有 Slater 就不能用 KKT 的充分性 |
| Slater | 标准凸优化中存在满足定义域/相对内部条件的严格可行点 | 是所有强对偶实例的必要条件 |
为什么「凸问题中 KKT 足以证明强对偶」?假设 (f_0,g_i) 凸、(h_j) 仿射,(x^) 可行,且存在 (\lambda^\ge0,\nu^) 满足 KKT。对 (x) 而言 (\mathcal L(x,\lambda^,\nu^)) 凸,驻点条件给出它的全局极小点 (x^)。于是
[
\begin{aligned}
q(\lambda^,\nu^)
&=\inf_x\mathcal L(x,\lambda^,\nu^)
&=\mathcal L(x^,\lambda^,\nu^)
&=f_0(x^)\qquad(\text{由互补松弛}).
\end{aligned}\tag{11}
]
再结合弱对偶:
[ d^\ge q(\lambda^,\nu^)=f_0(x^)\ge p^\ge d^. ]
所有不等号必须取等。这样 KKT 同时给出原问题最优、对偶最优达到和零间隙。
Slater 的逻辑方向相反: 在标准凸、仿射等式、适当相对内部/定义域与有限最优值等假设下,它是保证强对偶及对偶乘子存在的重要充分条件。当原始最优解达到时,进而能够使用 KKT 必要性;但 Slater 不是上面「给定 KKT 就能证明最优」所必需的条件。
六、迭代算法:从对偶函数得到投影对偶上升
例 (8) 中:
[ q’(\lambda)=1-\lambda. ]
对约束 (\lambda\ge0) 的凹最大化,可以用投影梯度上升:
[ \boxed{\lambda_{k+1}= \max{0,\lambda_k+\alpha(1-\lambda_k)}.}\tag{12} ]
取 (\alpha=0.5,\lambda_0=0),前几步为
| (k) | (\lambda_k) | (q(\lambda_k)):可靠下界 | 到最优乘子的距离 |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 1 | 0.5 | 0.375 | 0.5 |
| 2 | 0.75 | 0.46875 | 0.25 |
| 3 | 0.875 | 0.4921875 | 0.125 |
| 最优 | 1 | 0.5 | 0 |
因为 (\lambda_k\in[0,1]),投影从未启动,且
[ \lambda_{k+1}-1=(1-\alpha)(\lambda_k-1). ]
因此本例在 (0<\alpha<2) 下,由投影非扩张性可得
[ |\lambda_{k+1}-1| \le |1-\alpha|\,|\lambda_k-1|,\qquad |1-\alpha|<1, \tag{13} ]
即乘子线性收敛。对 (\alpha=0.5),距离每步减半。此结论是这个二次对偶函数的严格结论,并非「所有对偶上升都线性收敛」。
若一般问题的内层最小点 (x(\lambda,\nu)) 唯一且满足适当正则条件,Danskin 定理可给梯度为约束残差,例如 (q’(\lambda)=g(x(\lambda)))。若不能保证可微,但内层下确界由某 (x(\lambda)) 达到,则
[ q(\lambda’)\le q(\lambda)+g(x(\lambda))(\lambda’-\lambda), ]
故约束残差是凹函数的超梯度。超梯度上升通常需要不同的步长与收敛分析,不能套用上面的线性收敛公式。
七、失败反例:零对偶间隙也可能没有有限最优乘子
考虑凸问题
[ \boxed{\min_x (x-1)^2\quad \text{s.t. } x^2\le0.}\tag{14} ]
可行集只有 (x=0),所以 (p^*=1)。约束无法严格满足(Slater 失败),且 (g’(0)=0)。
对偶函数:
[
\begin{aligned}
q(\lambda)
&=\inf_x\big[(x-1)^2+\lambda x^2\big]
&=\inf_x\big[(1+\lambda)x^2-2x+1\big]
&=1-\frac{1}{1+\lambda}
=\frac{\lambda}{1+\lambda},\quad\lambda\ge0.
\end{aligned}
\tag{15}
]
于是
[ \sup_{\lambda\ge0}q(\lambda)=1=p^*. ]
强对偶(零间隙)成立。 但对任意有限的 (\lambda),都有 (q(\lambda)<1),所以对偶最优值不能被有限乘子达到。与此同时,在 (x^*=0) 的 KKT 驻点式为 (-2+\lambda\cdot0=0),根本无解。
这是三个不同事实:①零对偶间隙;②有限对偶最优乘子存在;③原始最优点满足 KKT。它们在缺乏资格条件时不可以混为一谈。反过来,换成 (\min_x x^2) 且仍约束 (x^2\le0),虽无 Slater,却存在有限 KKT 乘子,也能达到对偶最优。因此 Slater 是充分而非必要条件。
另一个失败模式:步长过大。 在例 (8) 的投影对偶上升中,从 (\lambda_0=0) 取 (\alpha=2),则
[ \lambda_1=2,\quad\lambda_2=0,\quad\lambda_3=2,\ldots ]
始终在 (0,2) 之间振荡,并不收敛到 (\lambda^*=1)。所以「问题有强对偶」不意味着「随意采用的求解算法就会收敛」。
八、将概念串起来
flowchart TD
A["原始最小化问题 p*"]
B["L=f+λg+νh,λ≥0"]
C["q(λ,ν)=inf_x L"]
D["弱对偶:q≤d*≤p*"]
E["最大化凹函数 q,得到对偶 d*"]
F["标准凸问题 + Slater/相应资格条件"]
G["对偶乘子存在、零对偶间隙"]
H["原始可行 + KKT 乘子"]
I["凸性下的全局最优证书"]
J["投影对偶上升"]
K["内层可解、步长/曲率等收敛条件"]
A --> B --> C
C --> D
C --> E
F --> G
G --> H
H --> I
E --> J
K --> J
今天必须牢牢记住的一条链:
[ \boxed{ q(\lambda,\nu)\le p^* \quad\text{(始终成立)};\qquad q(\lambda^,\nu^)=p^* \quad\text{(需要附加条件)}. } ]
九、分级自测(100 分;课堂不提供答案)
请先独立提交四题的作答。这里不公布任何标准答案;标准答案、解析和开放题评分要点仅保存在独立测验 JSON 中。
Lv1|弱对偶的必要假设|15 分|预计 2 分钟|单选
设原问题有可行点、最优值有限,约束写为 (g_i(x)\le0)、(h_j(x)=0),拉格朗日函数采用 (+\lambda_i g_i(x)+\nu_jh_j(x))。对任意对偶可行乘子 (\lambda\ge0),以下哪个结论必然成立?
A. 只有原问题是凸问题时,(q(\lambda,\nu)) 才能给出下界。
B. (q(\lambda,\nu)\le p^*),即使原问题不是凸的。
C. 对偶函数 (q) 对乘子一定是凸函数。
D. 只要 (q(\lambda,\nu)) 有有限值,就必然没有对偶间隙。
提示:从 (q\le\mathcal L\le f_0(x)) 出发,注意量词。
Lv2|二次规划的对偶函数计算|20 分|预计 3 分钟|数值
考虑 (\min_{x\in\mathbb R}\tfrac12x^2),约束 (2-x\le0)。定义 (q(\lambda)=\inf_x[\tfrac12x^2+\lambda(2-x)]),且 (\lambda\ge0)。请计算 (q(1.5)),保留三位小数,只填写数字。
提示:先对 (x) 求极小,不要把原始约束带进内层最小化。
Lv3|强对偶不等于任意步长算法收敛|25 分|预计 5 分钟|单选
考虑 (\min_x\tfrac12x^2),约束 (2-x\le0),其对偶函数为 (q(\lambda)=2\lambda-\tfrac12\lambda^2)((\lambda\ge0))。从 (\lambda_0=0) 出发,使用投影对偶梯度上升 [ \lambda_{k+1}=\max{0,\lambda_k+\alpha(2-\lambda_k)} ] 并取常数步长 (\alpha=2)。下面哪一项正确?
A. 第一步直接达到最优乘子,并永久停留在那里。
B. 因为原问题满足 Slater,任意正步长的对偶上升都收敛。
C. 乘子在两个不同值之间反复振荡;即使强对偶成立,迭代也不收敛。
D. 对偶函数是凹的,因此这个算法每一步都严格提高对偶目标值。
提示:显式算出 (\lambda_1,\lambda_2,\lambda_3)。
Lv4|二维原始—对偶构造、KKT 与线性收敛证明|40 分|预计 12 分钟|开放题
考虑 [ \min_{x,y\in\mathbb R} \frac12(x-1)^2+\frac12(y+1)^2 \quad\text{s.t.}\quad 1-x-y\le0. ]
A(10 分) 写出拉格朗日函数,对固定 (\lambda\ge0) 精确消去 (x,y),推导 (q(\lambda));再求对偶最优乘子及对偶最优值。
B(10 分) 求原始最优点,检查原始可行性、对偶可行性、驻点和互补松弛;给出一个 Slater 严格可行点,说明本题强对偶为什么成立。
C(12 分) 不借助本题具体数字,从 (g_i\le0,\lambda_i\ge0,h_j=0) 出发,逐行证明弱对偶;再解释对凸目标、凸不等式及仿射等式问题,为什么存在满足 KKT 的原始—对偶点会构成全局最优性及零间隙证书。
D(8 分) 对 A 得到的 (q),从 (\lambda_0=0) 出发,取步长 (\alpha=\tfrac14) 做两步投影对偶上升;写出 (\lambda_1,\lambda_2),并证明本题此步长下到最优乘子的距离每步至多缩小为上一步的 (1/2)。
提示:消去 (x,y) 可分别令对 (x,y) 的导数为零;证明收敛时结合投影的非扩张性。
十、下一课
第 10 课|2026 年 10 月 29 日:对偶间隙、鞍点与原始—对偶证书。 我们将从 (q(\lambda^)=p^) 进一步理解「为什么拉格朗日鞍点与 KKT 关联」,并通过带等式约束的二次规划比较原始解、对偶乘子、对偶间隙和停止准则。
评分规则保持不变: Lv1 15 分、Lv2 20 分、Lv3 25 分、Lv4 40 分;答卷提交后逐题反馈。80 分及以上继续,60–79 分补充薄弱知识点,低于 60 分复习;日期和课号不因分数改变。