约束最优性与对偶证书

在约束边界上，最优点的梯度可以不为零。要证明它最优，可以找出一个所有可行点都无法低于的下界，再让候选点恰好达到这个下界。给出下界的拉格朗日乘子，就是这里的“对偶证书”；依据是 Boyd 与 Vandenberghe，第 5 章的拉格朗日下界与最优性条件。

凸优化总览介绍了凸性与 KKT 的基本关系；梯度与多维优化解释梯度和 Hessian。如果还不熟悉怎样确定变量、目标与可行域，可以先看优化建模。下面把这些概念放进同一道题里计算。

目标与可行域

令 $x,y$ 为两个实数变量，求解原问题：

$$\begin{aligned} \text{minimize}\quad & f(x,y)=\frac12\bigl((x-2)^2+(y-1)^2\bigr) \\ \text{subject to}\quad & c_1(x,y)=x+y-2\le0, \\ & c_2(x,y)=-x\le0, \\ & c_3(x,y)=-y\le0. \end{aligned}$$

可行域 $C=\{(x,y):x\ge0,\ y\ge0,\ x+y\le2\}$ 是闭三角形。目标是到点 $(2,1)$ 的平方距离的一半。$C$ 非空且紧，连续目标一定取得最小值；Hessian 为单位矩阵，所以目标严格凸，最优点唯一。

这符合 CVXPY 的二次规划示例所用的形式 $\frac12z^TPz+q^Tz$、$Gz\le h$，其中 $P$ 半正定。本题 $z=(x,y)^T$，$P=I_2$，$q=(-2,-1)^T$，

$$G=\begin{pmatrix}1&1\\-1&0\\0&-1\end{pmatrix},\qquad h=\begin{pmatrix}2\\0\\0\end{pmatrix},\qquad f(z)=\frac12z^Tz+q^Tz+\frac52.$$

常数 $5/2$ 不改变最优点。要得到这里定义的 $f$ 和 $g$ 的值，就必须保留它；若从二者中同时减去 $5/2$，原始–对偶间隙不变。

先算出候选点

无约束最小点 $(2,1)$ 违反 $x+y\le2$。先试边界 $x+y=2$，代入 $y=2-x$：

$$f(x,2-x)=\frac12\bigl((x-2)^2+(1-x)^2\bigr) =\left(x-\frac32\right)^2+\frac14.$$

这条边上的最小点为

$$(x_*,y_*)=\left(\frac32,\frac12\right),\qquad f(x_*,y_*)=\frac14.$$

它确实位于边上，因为两坐标都为正。不过，只在一条边上求出最小值，还没有排除三角形内其他点。后面的对偶下界会补上全局证明。

约束在候选点处取等号时称为活跃约束。这里 $c_1=0$，而 $c_2=-3/2$、$c_3=-1/2$，所以只有总量约束活跃。此时 $\nabla f=(-1/2,-1/2)$：沿负梯度移动会增大 $x+y$，离开可行域。

拉格朗日函数与对偶下界

采用 $c_i\le0$ 的符号约定，分别给三个约束配上非负乘子 $\lambda,\mu,\nu$。按 Boyd 与 Vandenberghe，§§5.1.1–5.1.3，构造

$$L(x,y,\lambda,\mu,\nu) =f(x,y)+\lambda(x+y-2)-\mu x-\nu y.$$

对固定乘子，对偶函数取 $L$ 在变量定义域上的下确界：

$$g(\lambda,\mu,\nu)=\inf_{(x,y)\in\mathbb R^2}L(x,y,\lambda,\mu,\nu).$$

这里要在整个 $\mathbb R^2$ 上取下确界。三个不等式已放进 $L$，不能再把这个计算限制在三角形内。

$L$ 关于 $(x,y)$ 的 Hessian 仍为 $I_2$。因此令偏导为零就能找到它唯一的全局最小点：

$$\partial_x L=x-2+\lambda-\mu=0,\qquad \partial_y L=y-1+\lambda-\nu=0,$$

即 $x_L=2-\lambda+\mu$、$y_L=1-\lambda+\nu$。配方后得到

$$\begin{aligned} L&=\frac12\bigl((x-x_L)^2+(y-y_L)^2\bigr)+g(\lambda,\mu,\nu),\\ g(\lambda,\mu,\nu) &=\lambda-2\mu-\nu-\frac12\bigl((\lambda-\mu)^2+(\lambda-\nu)^2\bigr). \end{aligned}$$

对偶问题是最大化 $g$，约束为 $\lambda,\mu,\nu\ge0$。本题 $g$ 对所有有限乘子都有限。对任意可行 $(x,y)$ 和非负乘子，

$$g(\lambda,\mu,\nu)\le L(x,y,\lambda,\mu,\nu)\le f(x,y).$$

第二个不等式来自“非负乘子 × 非正约束值”。记原问题最优值为 $p_*$、对偶最优值为 $d_*=\sup_{\lambda,\mu,\nu\ge0}g$，便有 $d_*\le p_*$。这叫弱对偶；上述不等式的证明不需要凸性。

算出乘子，检查四项 KKT

互补松弛要求每个乘子与相应约束值的乘积为零。由于候选点的 $x_*,y_*>0$，$\mu_*=\nu_*=0$。再代入驻点方程：

$$-\frac12+\lambda_*=0 \quad\Longrightarrow\quad (\lambda_*,\mu_*,\nu_*)=\left(\frac12,0,0\right).$$

教材 §5.5.3的四项 KKT 条件在本题中逐项如下：

条件	本题的计算	结果
原问题可行	$(c_1,c_2,c_3)=(0,-3/2,-1/2)$	均不大于零
乘子非负	$(\lambda_*,\mu_*,\nu_*)=(1/2,0,0)$	乘子均非负
驻点条件	$\nabla_{x,y}L=(-1/2+1/2,-1/2+1/2)$	$(0,0)$
互补松弛	$(\lambda_*c_1,\mu_*c_2,\nu_*c_3)=(0,0,0)$	全部为零

要给出有限的对偶下界，还须 $g>-\infty$。本题自动满足这一点；但对一般问题，不能仅凭乘子非负就断定下界有限。

正乘子对应的约束一定活跃，非活跃约束的乘子一定为零；活跃约束却可以有零乘子。例如把本题的上限改为 $3$，无约束最小点 $(2,1)$ 就落在 $x+y=3$ 上，而所有乘子都为零。

在可微凸问题中，目标和不等式函数凸、等式约束仿射，满足 KKT 足以证明全局最优。本题还能把证书直接写成数值：

$$g\left(\frac12,0,0\right)=\frac12-\left(\frac12\right)^2=\frac14 =f\left(\frac32,\frac12\right).$$

任何可行点的目标都至少为 $1/4$，候选点恰好达到它，所以 $p_*=d_*=1/4$。平方项也给出同一结论：

$$f(x,y)-\frac14 =\frac12\left(\left(x-\frac32\right)^2+\left(y-\frac12\right)^2\right) +\frac12(2-x-y)\ge0\qquad ((x,y)\in C).$$

等号只在 $(3/2,1/2)$ 处成立。这证明了最优性和唯一性，而不必逐一搜索所有可行点。

用间隙衡量候选解

给定原问题可行点和对偶可行乘子，原始–对偶间隙为 $f(x,y)-g(\lambda,\mu,\nu)$。它给出候选解与最优值之间误差的上界：

$$0\le f(x,y)-p_*\le f(x,y)-g(\lambda,\mu,\nu).$$

下面各行都是可行的原始–对偶组合，但前两行的乘子还不是最优乘子。

$(x,y)$	$(\lambda,\mu,\nu)$	$f$	$g$	$f-g$
$(1,1)$	$(0,0,0)$	$1/2$	$0$	$1/2$
$(1,1)$	$(1/4,0,0)$	$1/2$	$3/16$	$5/16$
$(3/2,1/2)$	$(1/2,0,0)$	$1/4$	$1/4$	$0$

第二行给出 $3/16\le p_*\le1/2$，以及候选解误差至多 $5/16=0.3125$。它的实际误差是 $1/2-1/4=1/4$。某组候选值的正间隙，不等于最优值之间存在正的对偶间隙；本题的最优对偶间隙 $p_*-d_*$ 为零。

正则性与非凸性分别影响什么

凸问题的最优点可能没有 KKT 乘子

教材 §5.2.3 的 Slater 条件要求：凸问题在共同定义域的相对内部存在满足等式约束、且严格满足所有不等式的点。它保证强对偶；若最优值有限，还保证对偶最优值能由有限乘子取得。结合可微性，KKT 就成为最优性的必要且充分条件。对于仿射不等式，教材给出的放宽版本允许不取严格不等号。

本题 $(1/2,1/2)$ 严格满足三个不等式，所以 Slater 条件成立。它保证最优证书存在；已经找到的凸问题 KKT 证书，其充分性本身不需要再假设 Slater。

考虑另一个凸问题：

$$\min_{x\in\mathbb R}x\quad\text{subject to}\quad x^2\le0.$$

唯一可行点为 $x_*=0$，$p_*=0$。不存在 $x^2<0$ 的点，Slater 条件失败。拉格朗日函数 $L=x+\lambda x^2$ 的驻点方程为 $1+2\lambda x=0$；在 $x_*=0$ 处，任何有限乘子都无法使它成立。

当 $\lambda>0$，$L$ 的最小点为 $-1/(2\lambda)$，所以 $g(\lambda)=-1/(4\lambda)$；$\lambda=0$ 时 $g(0)=-\infty$。因此 $d_*=\sup_{\lambda\ge0}g(\lambda)=0=p_*$，却没有取得该上确界的有限乘子。这个例子失败的是乘子存在性和 KKT 必要性；强对偶仍然成立。

非凸问题的 KKT 点可以是最大点

考虑

$$\min_{x\in\mathbb R}-x^2\quad\text{subject to}\quad x-1\le0,\quad -x-1\le0.$$

可行域是 $[-1,1]$，目标不是凸函数。在 $x=0$、两个乘子都为零时，原问题可行、乘子非负、梯度为零、互补松弛也成立，四项 KKT 全部通过。但 $f(0)=0$，而 $f(-1)=f(1)=-1$；这个 KKT 点是可行域上的严格最大点。

原因是 $L=-x^2$ 在零点的驻点并非全局最小点，$\inf_{x\in\mathbb R}L=-\infty$。实际上，任何有限乘子都只能添加仿射项，无法改变向下开口的二次项，所以本题 $d_*=-\infty$。弱对偶仍成立，却给不出有限下界。虽然 $x=0$ 严格满足两个约束，Slater 的凸问题定理也不能用于这个非凸目标。

用 Python 复算

下面只用 Python 标准库的有理数运算。它检查已算出的点和乘子，复算间隙与两个反例；计算证书所需的全局下确界依据是上面的配方推导。

from fractions import Fraction as F


def objective(x, y):
    return F(1, 2) * ((x - 2)**2 + (y - 1)**2)


def dual(lam, mu, nu):
    return lam - 2*mu - nu - F(1, 2)*((lam-mu)**2 + (lam-nu)**2)


def vector(values):
    return '(' + ', '.join(map(str, values)) + ')'


x, y = F(3, 2), F(1, 2)
lam, mu, nu = F(1, 2), F(0), F(0)
constraints = (x+y-2, -x, -y)
multipliers = (lam, mu, nu)
stationarity = (x-2+lam-mu, y-1+lam-nu)
kkt = (
    all(c <= 0 for c in constraints),
    all(m >= 0 for m in multipliers),
    all(s == 0 for s in stationarity),
    all(m*c == 0 for m, c in zip(multipliers, constraints)),
)
assert all(kkt)
print('x=' + vector((x, y)) + ', multipliers=' + vector(multipliers))
print('constraints=' + vector(constraints))
print('stationarity=' + vector(stationarity))
print('KKT=' + vector(kkt))
for label, a, b, l in [('candidate', F(1), F(1), F(1, 4)),
                     ('optimum', x, y, lam)]:
    p, d = objective(a, b), dual(l, F(0), F(0))
    print(f'{label}: f={p}, g={d}, gap={p-d}')
for l in (F(1), F(10), F(100)):
    z = -1/(2*l)
    g = z + l*z*z
    assert g == -1/(4*l)
    print(f'degenerate: lambda={l}, x_min_L={z}, g={g}')
z = F(0)
nonconvex_constraints = (z-1, -z-1)
nonconvex_multipliers = (F(0), F(0))
nonconvex_kkt = (
    all(c <= 0 for c in nonconvex_constraints),
    all(m >= 0 for m in nonconvex_multipliers),
    -2*z + nonconvex_multipliers[0] - nonconvex_multipliers[1] == 0,
    all(m*c == 0 for m, c in zip(nonconvex_multipliers, nonconvex_constraints)),
)
print('nonconvex: KKT=' + vector(nonconvex_kkt)
      + f', f(0)={-z*z}, f(-1)=f(1)={-F(1)**2}')

实际输出：

x=(3/2, 1/2), multipliers=(1/2, 0, 0)
constraints=(0, -3/2, -1/2)
stationarity=(0, 0)
KKT=(True, True, True, True)
candidate: f=1/2, g=3/16, gap=5/16
optimum: f=1/4, g=1/4, gap=0
degenerate: lambda=1, x_min_L=-1/2, g=-1/4
degenerate: lambda=10, x_min_L=-1/20, g=-1/40
degenerate: lambda=100, x_min_L=-1/200, g=-1/400
nonconvex: KKT=(True, True, True, True), f(0)=0, f(-1)=f(1)=-1

若用求解器处理更大的二次规划，CVXPY 示例通过约束对象的 dual_value 读取乘子。要保持约束顺序和符号约定一致，再检查可行性、驻点残差、互补乘积，以及实际对偶函数给出的下界。小的驻点残差本身无法排除上面的非凸最大点。

我的阅读 · 打开过的笔记会记在当前浏览器里。