aiwiki.page
中文
数学 / 应用与计算数学 / strong-duality

强对偶性

强对偶性指优化问题与其对偶问题的最优值相等,可据此获得精确界和最优性证书。

24 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
数学优化拉格朗日对偶目标函数可行集拉格朗日乘数线性规划多面体凸优化强对偶性

强对偶性是数学优化中一对问题所具有的性质,指两者的最优目标值相等。在拉格朗日对偶中,一个最小化问题(原问题)对应一个最大化问题(对偶问题),后者为原问题的最优值提供下界。强对偶性意味着这些下界可以任意逼近原问题的最优值。但仅有强对偶性,并不意味着任一问题都能取到其最优值。对于可行且有界的有限维线性规划,以及满足适当正则条件的许多凸优化问题,强对偶性成立;但对任意非线性问题,则没有这样的保证。

数学表述

考虑原问题

p⋆=inf⁡x∈Df0(x)subject tofi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,r,\begin{aligned} p^\star=\inf_{x\in D}\quad & f_0(x)\\ \text{subject to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\\ & h_j(x)=0,\qquad j=1,\ldots,r, \end{aligned}

其中,D⊆RnD\subseteq\mathbb R^n 是给定的定义域,f0f_0 是目标函数。其可行集由 DD 中满足全部约束的点组成。

拉格朗日函数为

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1rνjhj(x),L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x) +\sum_{j=1}^{r}\nu_j h_j(x),

其中,λi≥0\lambda_i\geq0,而等式约束的乘子 νj\nu_j 不受符号限制。这些变量称为拉格朗日乘子。

对偶函数为

g(λ,ν)=inf⁡x∈DL(x,λ,ν),g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu),

对偶问题为

d⋆=sup⁡λ≥0, νg(λ,ν).d^\star=\sup_{\lambda\geq0,\ \nu}g(\lambda,\nu).

即使原问题是非凸的,对偶函数仍然是凹函数,因为它是关于乘子的仿射函数族的逐点下确界。因此,按照在凸域上最大化凹函数这一通常意义,对偶问题是一个凸优化问题。

弱对偶性与强对偶性

对于每个原问题可行点 xx 以及每个 λ≥0\lambda\geq0,都有

g(λ,ν)≤L(x,λ,ν)≤f0(x).g(\lambda,\nu) \leq L(x,\lambda,\nu) \leq f_0(x).

对乘子取上确界,对可行的 xx 取下确界,即得弱对偶性:

d⋆≤p⋆.d^\star\leq p^\star.

当

d⋆=p⋆.d^\star=p^\star.

时,强对偶性成立。若这两个值均有限,则其差

p⋆−d⋆p^\star-d^\star

称为最优对偶间隙。因此,强对偶性也称为零对偶间隙。

这一等式涉及的是最优值,而不一定涉及最优解。“原问题最优值可达”和“对偶问题最优值可达”分别指存在取到相应下确界和上确界的点。

保证强对偶性成立的条件

线性规划

对于有限维线性规划,如果原问题可行且最优值有限,则其对偶问题也存在最优解,并且两者的最优值相等。

例如,标准形式的问题对

minimizecTxsubject toAx=b,x≥0\begin{aligned} \text{minimize}\quad & c^{\mathsf T}x\\ \text{subject to}\quad & Ax=b,\qquad x\geq0 \end{aligned}

与

maximizebTysubject toATy≤c\begin{aligned} \text{maximize}\quad & b^{\mathsf T}y\\ \text{subject to}\quad & A^{\mathsf T}y\leq c \end{aligned}

只要原问题可行且目标值有下界,两者的最优值就相等,且均能取到最优值。

线性规划的多面体结构提供了比一般非线性优化更强的保证。尤其是,它不要求严格可行性。

凸优化与斯莱特条件

在凸优化问题中,目标函数和不等式约束函数都是凸函数,定义域是凸集,等式约束是仿射的。然而,仅有凸性并不能保证强对偶性成立。

一个广泛使用的充分条件是斯莱特条件。在标准的有限维表述中,该条件要求公共定义域的相对内部存在一点,满足

fi(x)<0for every inequality constraint,hj(x)=0for every equality constraint.f_i(x)<0\quad\text{for every inequality constraint}, \qquad h_j(x)=0\quad\text{for every equality constraint}.

相对内部是指在包含该定义域的最小仿射空间中取的内部。

在斯莱特条件下,强对偶性成立。如果原问题的最优值有限,则对偶问题也能取到最优值。该条件的一个精化版本允许仿射不等式约束以非严格的形式得到满足。

斯莱特条件是充分条件,而非必要条件。不满足该条件并不意味着对偶间隙为正;即使不存在严格可行点,强对偶性仍可能成立。

其他正则条件

其他强对偶定理利用适当集合的闭性、扰动后最优值的连续性,或额外的约束品性。在无限维优化中,拓扑和对偶变量空间的选择也很重要。有限维情形下的结果通常不能原封不动地推广到泛函分析中的问题。

几何解释与扰动解释

对偶性可以通过可实现的目标值与约束值的几何结构来理解。适当的分离超平面或支撑超平面可以给出乘子,使相应的对偶值等于原问题的最优值。正则性假设可以排除那些妨碍此类支撑超平面存在或导致间隙的几何退化情形。

另一种相关解释使用扰动价值函数

v(u,w)=inf⁡{f0(x):x∈D, fi(x)≤ui, hj(x)=wj}.v(u,w)= \inf\left\{ f_0(x): x\in D,\ f_i(x)\leq u_i,\ h_j(x)=w_j \right\}.

这里,v(0,0)=p⋆v(0,0)=p^\star。

每一组对偶可行的乘子都会给出一个仿射下界:

v(u,w)≥g(λ,ν)−λTu−νTw.v(u,w) \geq g(\lambda,\nu)-\lambda^{\mathsf T}u-\nu^{\mathsf T}w.

如果强对偶性成立,且 (λ⋆,ν⋆)(\lambda^\star,\nu^\star) 取到对偶最优值,则上式变为

v(u,w)≥p⋆−(λ⋆)Tu−(ν⋆)Tw.v(u,w) \geq p^\star-(\lambda^\star)^{\mathsf T}u -(\nu^\star)^{\mathsf T}w.

该下界在未受扰动的问题处是精确的。这为在敏感性分析中将最优乘子解释为影子价格提供了依据。当价值函数在原点可微时,它对这些扰动的偏导数等于相应最优乘子的相反数。

最优性条件与鞍点

假设原问题和对偶问题均能取到最优值,且它们共同的最优值有限。那么,最优点满足

g(λ⋆,ν⋆)=L(x⋆,λ⋆,ν⋆)=f0(x⋆).g(\lambda^\star,\nu^\star) = L(x^\star,\lambda^\star,\nu^\star) = f_0(x^\star).

由这一等式可得互补松弛条件:

λi⋆fi(x⋆)=0for every i.\lambda_i^\star f_i(x^\star)=0 \qquad\text{for every }i.

因此,严格不活跃的不等式约束所对应的乘子必为零。

如果各函数可微,且拉格朗日函数是在 Rn\mathbb R^n 上无约束最小化的,则最优性还给出驻点条件:

∇f0(x⋆)+∑iλi⋆∇fi(x⋆)+∑jνj⋆∇hj(x⋆)=0,\nabla f_0(x^\star) +\sum_i\lambda_i^\star\nabla f_i(x^\star) +\sum_j\nu_j^\star\nabla h_j(x^\star)=0,

其中,∇\nabla 表示梯度。若定义域受限,则驻点条件还必须将该定义域的限制考虑在内。

原问题可行性、对偶可行性、互补松弛和驻点条件共同构成卡鲁什—库恩—塔克条件。对于等式约束为仿射的可微凸问题,这些条件是全局最优性的充分条件。在适当的正则条件下,它们也是必要条件。在非凸优化中,仅有驻点条件并不够:它未必能确定拉格朗日函数的全局极小点。

同一关系也可以表述为鞍点:

L(x⋆,λ,ν)≤L(x⋆,λ⋆,ν⋆)≤L(x,λ⋆,ν⋆)L(x^\star,\lambda,\nu) \leq L(x^\star,\lambda^\star,\nu^\star) \leq L(x,\lambda^\star,\nu^\star)

对所有 x∈Dx\in D 以及所有允许的乘子均成立。存在这样的鞍点,等价于强对偶性成立且两个有限的最优值都能取到。

示例与局限

两个最优值均可达的强对偶情形

考虑

min⁡x∈Rx2subject tox≥1.\min_{x\in\mathbb R}x^2 \quad\text{subject to}\quad x\geq1.

将约束写为 1−x≤01-x\leq0,则

L(x,λ)=x2+λ(1−x),λ≥0.L(x,\lambda)=x^2+\lambda(1-x), \qquad \lambda\geq0.

对 xx 最小化,得到

g(λ)=λ−λ24.g(\lambda)=\lambda-\frac{\lambda^2}{4}.

对偶问题在 λ⋆=2\lambda^\star=2 处取到最大值 11。原问题在 x⋆=1x^\star=1 处取到最小值,同样为 11。

对偶最优值不可达的强对偶情形

考虑

min⁡x∈Rxsubject tox2≤0.\min_{x\in\mathbb R}x \quad\text{subject to}\quad x^2\leq0.

唯一的可行点是 x=0x=0,因此 p⋆=0p^\star=0。其对偶函数为

g(λ)={−14λ,λ>0,−∞,λ=0.g(\lambda)= \begin{cases} -\dfrac{1}{4\lambda},&\lambda>0,\\ -\infty,&\lambda=0. \end{cases}

因此,

d⋆=sup⁡λ≥0g(λ)=0,d^\star=\sup_{\lambda\geq0}g(\lambda)=0,

但没有任何有限的乘子能取到这一值。尽管不满足严格可行性,强对偶性仍然成立,但对偶最优值不可达。

具有正对偶间隙的凸问题

考虑凸问题

min⁡x,y e−xsubject tox2y≤0,y>0,\min_{x,y}\ e^{-x} \quad\text{subject to}\quad \frac{x^2}{y}\leq0,\qquad y>0,

其中,y>0y>0 是定义域的一部分。约束函数 x2/yx^2/y 在该定义域上是凸的。可行性迫使 x=0x=0,因此 p⋆=1p^\star=1。

对每个 λ≥0\lambda\geq0,都有

g(λ)=inf⁡x∈R, y>0(e−x+λx2y)=0.g(\lambda)= \inf_{x\in\mathbb R,\ y>0} \left(e^{-x}+\lambda\frac{x^2}{y}\right)=0.

该表达式非负,且只要令 xx 足够大,并使 yy 相对于 x2x^2 足够大,就能使其趋于零。因此 d⋆=0d^\star=0,对偶间隙为 11。

这个例子说明,必须区分凸性与强对偶定理所使用的正则条件。

应用

强对偶性提供了精确的最优性证书:如果一个原问题可行点与一个对偶可行点的目标值相等,那么两者都是最优解。更一般地,两者目标值之差给出了原问题可行点与最优值之间差距的上界。这是优化算法的一项核心停止准则。

在运筹学中,对偶变量描述受约束资源的边际价值。在机器学习中,对偶表述可以揭示约束模型和正则化模型中的有用结构。它与博弈论的联系源于拉格朗日函数所表示的最小化与最大化之间的相互作用;适当的极小极大定理可以在优化次序可交换时确立两者相等。

对于非凸问题和整数规划,对偶问题可能只能提供下界。即使强对偶性不成立,这些界在分支定界法等方法中仍然有用。