凸优化（6）——对偶性：案例分析，强弱对偶性及理解，再看KKT条件

2021-08-09 17:30:37 浏览数 (3)

上一节笔记：凸优化（5）——近端梯度法：性质，延伸与案例分析；对偶性：引入与理解

————————————————————————————————————

大家好！

上一节我们简单提到了对偶问题的构造方法和对偶性的两种理解，这一节我们还会继续讨论对偶性相关的概念。我们会先介绍两个有趣的线性规划对偶问题的实际例子（本来不想花篇幅写例子的，但我觉得它们真的太有意思了！），再将对偶性推广到更加一般的优化问题进行讨论。

那么我们开始吧。

目录

  • 线性规划对偶问题综合案例
  • 一般问题的强，弱对偶性与对偶问题性质
  • 对偶性的其他理解
  • 对偶性框架下的KKT条件

Source

  • CMU 10-725: Convex Optimization
  • USTC: 最优化原理
  • Boyd, Vandenberghe, Convex Optimization
  • R. T. Rockafellar (1970), Convex Analysis

线性规划对偶问题综合案例

我们上一节提到了两种对偶问题的构造方法：直接构造法和拉格朗日函数法，并且用线性规划问题做了方法的示范。这里我们先用一个具体的例子开始这一节，顺便帮助大家理解如何使用这些方法求解对偶问题的形式。

Example 1: Max flow and min cut （Source：CMU） 证明最大流问题与最小割问题的潜在对偶关系

最大流问题和最小割问题都是图论和运筹学中的经典问题，我们先来看看它们的定义。考虑下面的这张图

（

s

和

t

都画的太偏了……凑合着看吧233）

在这张图里，

V

表示结点集合，

E

表示边的集合，且这是一个有向图。

f_{ij}

表示

(i, j)

方向的流量（flow），

c_{ij}

表示

(i,j

)方向的最大流量，那么我们的目标就是从源头（s）出发，到目标点（t），能够运输尽可能大的流量。在现实生活中这也非常常见，在盘根错节的水流管道中，我们肯定要考虑一次最多能运输多大流量的水，并且要保证每一处管道的运输量都在管道的最大运输范围内。这一个问题在计算机科学中也有成熟的解法，一般被称为网络流（netflow）问题，学过《算法设计与分析》的同学应该了解它。

把上述问题描述成一个数学问题，就是

max_{f in mathbb R^{|E|}} sum_{(s, j)in E}f_{sj}\s.t. 0 le f_{ij} le c_{ij}, forall (i,j) in E \ sum_{(i, k) in E}f_{ik} = sum_{(k, j) in E}f_{kj},forall k in V backslash {s, t}

这里目标函数其实就是表示从起点往外输送的流量，在上面的那张图中，从

s

出发的那三条边的流量和就是我们的目标函数。最后一个等式约束就是要求每一个中间节点的入流等于出流，这也是很显然的要求。注意这个问题是一个极大值问题，所以我们的对偶问题，其实是在解原问题的最优值的上界。

那么按照我们上面的思路，可以假设一些常数

a_{ij}, b_{ij} ge 0, (i, j ) in E

和

x_k, k in V backslash {s, t}

，但是没有要求。那么可以得到下面的式子

sum_{(i, j) in E}(-a_{ij}f_{ij} b_{ij}(f_{ij} - c_{ij})) sum_{k in V backslash {s, t}} x_k (sum_{(i, k) in E} f_{ik} - sum_{(k, j) in E}f_{kj}) le 0

注意到我们希望得到

sum f_{sj}

这样的东西，所以我们要把与

f_{ij}

相关的内容都移到一边。这样的话就可以得到

sum_{(i, j) in E}M_{ij} (a,b, x)f_{ij} le sum_{(i, j) in E}b_{ij}c_{ij}

这个地方的关键就是在于，我们只要

sum f_{sj}

，换句话说对于一条边来说，如果它的起点不在源头，那对应的系数

M_{ij}(a,b ,x)

就应该是0，否则是1。所以我们可以把要求划归为

begin{cases}M_{sj} = b_{sj} - a_{sj} x_j = 1 \ M_{it} = b_{it} - a_{it} - x_i = 0 \ M_{ij} = b_{ij} - a_{ij} x_j - x_i = 0end{cases}

当然这三行就对应了边的三种情况：起点在源头，终点在目标点，和中间的边。

在很多问题中，我们可以通过自己额外的赋值，弥补一些特殊的情况。比如说这里，我们完全没有必要单独讨论边的起点或终点在哪里，因为只要额外设

x_s = 1, x_t = 0

即可。这样的话就变成了一个条件，也即为

M_{ij} = b_{ij} - a_{ij} x_j - x_i = 0

但是注意这里，除了

(i,j) in E

以外，没有其它额外的要求了。这样的话，会发现根据

a_{ij} ge 0

，就可以消去这个变量，得到

b_{ij} x_j - x_i ge 0

，所以最终，我们得到的它的对偶问题就是

min_{b in mathbb{R}^{|E|}, x in mathbb R^{|V|}} sum_{(i, j) in E}b_{ij}c_{ij} \ s.t. quad b_{ij} x_j - x_i ge 0, forall (i,j ) in E \ b ge 0, x_s = 1, x_t = 0

简单分析一下，看似这个对于

x_i

没有额外的限制，但其实你会发现，因为我们有

x_s = 1

，所以实际上这就规定了每一个点

x_i in [0, 1]

（想想为什么？），也会间接的影响到

b

的取值范围。所以我们的约束条件除了

b_{ij} ge x_i - x_j

以外，还可以推出

b_{ij} , x_i , x_j in [0, 1]

这就是我们最终的对偶问题。

可是这个和最小割问题有什么联系吗？我们先看一下什么是最小割问题。最小割问题其实就是把条件

b_{ij} , x_i , x_j in [0, 1]

给收紧，也就是变成了

b_{ij} , x_i , x_j in {0, 1}

。结合

b_{ij} x_j - x_i ge 0

，我们可以推出，如果

b_{ij} = 1

，那么对应的是

x_i = 1, x_j = 0

，其他情况其实都对应了

b_{ij} = 0

（换句话说，只要我们要求

x_i, x_j in {0, 1}

，就能够满足

b_{ij} in {0, 1 }

）。如果我们假设

A = {i : x_i = 1}

，

B = {i: x_i = 0}

，那么就会有

i in A, j in B

。我们看一下下面的这张图，事实上可以人工的将图的节点分为两个部分

A, B

，那么可以看出，优化目标的意思其实就是从

A

到

B

所能够流过的最小流量。所以事实上我们会发现，最大流问题的对偶问题是最小割问题经过线性松弛得到的结果。而学过运筹学的同学会知道，最大流与最小割所得到的最优解是一致的。这一方面是因为线性规划问题的最优值都在顶点取到（不然单纯形法就没有理论基础了，不过这个slides上没有，是我猜的，有错请指出！），另一方面则是因为强对偶性（strong duality），这个概念我们后面再解释。

Example 2: Mixed strategies for matrix games 考虑博弈论中的混合策略博弈与信息不对称问题。

（给小白科普一下：game在这里是博弈的意思）

这是一个很有趣的问题，简单来说就是假设有两个人

J, R

，它们有一个收益矩阵

这里我们假设行的是

J

的决策，列是

R

的决策，也就是说

J

有

m

个决策，

R

有

n

个决策。假如说

J

选择了第

i

个决策，

R

选择了第

j

个决策，那么对应的

J

就要给

R
P_{ij}

这么多的奖励（当然了这个奖励不一定是正数，可以认为它是金钱，或者硬币，或者点赞，或者收藏，或是喜欢，etc...）。混合策略博弈中的“混合”的含义就是博弈者不知道自己要选择哪一个策略。所以假设它们的选择服从一个概率分布，也即设

x_i

表示

J

选择第

i

个决策的概率，

y_j

表示

R

选择第

j

个决策的概率。那么我们希望研究的对象，就是在这个框架下的期望收益

sum_{i = 1}^m sum_{j = 1}^n x_i y _j P_{ij } = x^T P y

当然了这里就是

R

的最大收益。

现在我们考虑两种情况

Case 1:

R

知道

J

的策略，但

J

不知道

R

的策略。

我们把它翻译成数学语言，就是说，对于

R

来说，

x

是已知的，那么其实这个优化问题就是

max x^T P y \ s.t. quad y ge 0, 1 ^T y = 1

这个约束条件其实就是因为

{y_i}

是一个离散的概率分布。

这个优化问题是可解的，我们设

c = P^T x

，那么我们会有

max {x^T P y mid y ge 0, 1 ^T y = 1 } = max {c^T y mid y ge 0, 1 ^T y = 1} = max_i c_i

最后一个等式怎么来？我们在《凸优化》第1节（凸优化（1）——引入，优化实例分析，凸集举例与相关性质）单纯性那个部分用到过这个技巧，这个部分留给读者思考。

这个就是

R

的决策，那么对于

J

来说，他肯定希望期望收益越小越好（因为这是他要付给

R

的奖励），所以对于

J

来说，这个优化问题就是

min_{x} max_{i = 1, ldots, n}(P^T x )_i \ s.t. quad x ge 0, 1^T x = 1

那么现在，我们来考虑第二种情况

Case 2:

J

知道

R

的策略，但

R

不知道

J

的策略

同样的推导方式，我们可以得到

max_{y} min_{j = 1, ldots, m}(P y )_j \ s.t. quad y ge 0, 1^T y = 1

所以根据这两个情况，我们可以看出，会得到不同的策略，不同的优化问题。而且很明显，两种方案中很明显在Case 1中，

R

是更占优的，因为他知道的信息更多。但答案其实可能会让很多人感到失望，就是其实二者的最优值是相同的。也就是说其实两种情况对应的

R

的最大收益是完全一样的，Amazing啊！

要解释这个其实还是需要利用强对偶性。假如说你已经知道了这一个性质，那么其实只用说明一个问题为另一个问题的对偶问题就行了。

我们考虑Case 1的优化问题。注意到其实问题可以转为

min_{x, t} t \ s.t. quad x ge 0, 1^T x = 1, P^T x le t

我们写出它的拉格朗日函数

L(x, t, u, v, y) = t - u^T x v(1 - 1^T x) y^T(P^T x - t 1)

所以我们会有

g(u, v, y) = min_{x , t} L(x, t, u, v, y) = begin{cases}v & 1 -1 ^T y = 0, Py - u - v1 = 0 \ - infty & othersend{cases}

并且我们有

u, v ,y ge 0

，那么其实这里我们可以把

u

消掉，这样这个问题就可以变成

max_{y, v} v \ s.t. quad y ge 0, 1^T y = 1 , Py ge v

这就是我们的Case 2的优化问题，这里要注意

Py ge v

和

min_{j = 1, ldots, m}(P y )_j ge v

是等价的。

这个问题告诉了我们一个人生哲理，即占有绝对优势的人往往并不能通过精致利己达到效率的最大化hhh。另外我们在进入下一个部分之前还需要强调一遍，第二种理解对偶性的方式是更常见也更容易推广的，但第一种推导对偶问题的方式可以更好的帮助我们理解对偶性提出的动机。

进一段广告！

广告结束！

一般问题的强，弱对偶性与对偶问题性质

我们说的一般的问题，其实就是形式

min_x f(x) \ s.t. quad h_i(x) le 0 , i =1 ,ldots, m \ l_j(x) = 0 , j = 1, ldots, r

对应的拉格朗日函数为

L(x, u, v) = f(x) sum_{i = 1}^m u_i h_i(x) sum_{j = 1}^r v_j l_j(x)

其中

u ge 0

，

v

没有限制。那么

g(u, v) = min_x L(x, u ,v )

就是我们的对偶问题，我们希望最大化这个

g(u, v)

来给出一个好的原始优化问题的下界。

下面是某个函数对应的原问题和对偶函数（注意这里它的对偶变量只有一个

lambda

，而我们上面说的对偶变量其实有2个向量，为

u, v

）的图像，可以看出对偶函数永远在原问题极小值（就是虚线的那个位置）的下方。

所以我们会发现拉格朗日函数其实是一个凹函数，这是为什么呢？

Theorem 1: 证明拉格朗日函数是一个凹函数。

这个证明不是很难，因为注意到我们有

g(u, v) = min _x {f(x) sum_{i = 1}^m u_i h_i(x) sum_{j = 1}^r v_j l_j(x)} = - max_x {- f(x) - sum_{i = 1}^m u_i h_i(x) - sum_{j = 1}^r v_j l_j(x)}

那么注意到函数

max_x {- f(x) - sum_{i = 1}^m u_i h_i(x) - sum_{j = 1}^r v_j l_j(x)}

相当于在对一个凸函数求极大值，所以它依然是一个凸函数（注意这个函数是关于

u, v

的，而关于

u, v

它们是仿射函数，自然是凸函数）。那么求了一个负号，它就变成凹函数了，这就证明了结论。

因为是凹函数，所以注意我们后面对它求极大化的时候，这个问题本身依然会变成一个凸问题，因为极大化一个凹函数和极小化一个凸函数是一个意思。这也是对偶问题被青睐的一个很重要的原因。

接下来我们来说一下强弱对偶性的定义。

Definition 1: Weak Duality, Strong Duality 设原问题的最优值是

f(x^*)

，对偶问题的最优值是

g(u^*, v^*)

，那么如果

g(u^*, v^*)le f(x^*)

，则称问题满足弱对偶性，如果

g(u^*, v^*)= f(x^*)

，则称问题满足强对偶性。

很明显强对偶性的意义要重要得多，因为有些时候，对偶问题的求解会比原问题要容易，如果问题同时具备强对偶性，那么求解对偶问题就能够达到优化的目的。所以在很多运筹学的问题中，研究者都会花很多时候去寻找问题的对偶问题，也是出于这个考虑。

到此很多人自然会有个疑问：我怎么知道问题具备强对偶性？一个最为常用的东西就是斯莱特 (Slater) 条件。

Proposition 1: Modified Slater's Condition 若原问题是一个凸优化问题，且存在一个严格可行点，即所有的等式约束满足，所有的非仿射的不等式约束不取等，则问题具备强对偶性。

因为涉及到挺多分析的内容，我们不证明这个条件。感兴趣的可以去Boyd的Convex Optimization中找到相关的内容。

这个条件是非常好用的。对于一开始提到的Example 1，所有的约束都是线性约束，那么自然它们都是仿射约束，Slater条件告诉我们这个问题直接具备强对偶性。对于Example 2也是一样的，这也就解决了我们之前在那两个例子中留下的“为什么原问题和对偶问题的最优解一致”这样的问题。

关于对偶性的性质，我们最后再提一个对偶间隔（duality gap）的概念。

Definition 2: Duality Gap 对任意的原问题的一组可行解

x

和一组对偶问题的可行解

u, v

（注意它们都是向量），定义

f(x) - g(u, v)

为对偶间隔。

它的主要作用体现在不等式

f(x) - f(x^*) le f(x) - g(u, v)

上，因为这不等式约束，很多涉及到对偶问题的优化算法就可以使用对偶间隔来判断优化算法是否已经收敛。

对偶性的其他理解

关于强对偶性中得到的原问题与对偶问题解一致的结论，其实有很多种更加形象的解释。我们这里提供两种视角：几何视角与鞍点视角。

几何视角是什么呢？其实就是考虑把问题改一下形式。为了方便讨论我们来简化一下原始问题，也即

min f_0(x) \ s.t. quad f_1(x) le 0

也就是说只有一个约束和一个目标函数，这样的话就可以把它们写成一个平面上的点。具体说就是设

G = {(f_1(x) , f_0(x)) mid x in D}

这无非就是把问题具像化描述了。那么我们会有下面两个等式

f_0(x^*) = inf {t mid (u, t ) in G, u le 0}
g(lambda) = inf {lambda u t mid (u, t ) in G}

这个并不难理解，因为第一个式子其实含义就是在

f_1(x) le 0

的情况下，对应

f_0(x)

的最小值，这也就是原始优化问题，得到的也就是原始优化问题的最优解

f_0(x^*)

。对于

g(lambda)

，注意到内部的表达式其实就是拉格朗日函数就可以了，因为我们只有一个约束，所以对偶函数只有一个自变量

lambda ge 0

。

那么我们画一下两个图，分别对应强对偶性和弱对偶性，来看一下它们几何上的含义。

这里的绿线与

y

轴（更严格地说应该是

t

轴，就是竖轴啦）的交点表示的是原问题的最优值，而红线的交点则表示的是对偶问题的最优值。可以看出对于第一张图，红线与区域的两个边界相切。这个函数的取值比较不规整，区域画的乱七八糟，所以它并不具备强对偶性。但是对于第二张图，它对应的两个最优值相同，那么也就说明这种情况下是具备强对偶性的。

第一张图为什么两个最优值对应的情况是那样，其实不仔细想不一定能想明白，这里尽力解释一下。对于原问题的最优值没什么好说的，它本质上就是一条与

x

轴（更严格地说应该是

u

轴，就是横轴啦）平行的直线，结合

u le 0

就很容易画出来。但对偶问题那个怎么画呢？首先注意到

lambda ge 0

，也就是说一定是一条斜率非正的直线。其次注意到我们这个集合的含义是，对于每一个

(u,t) in G

，我们的

g(lambda)

是过

(u,t)

的直线绕了一圈之后，与

y

轴的交点的最小值，所以很多情况下其实这个值都是

-infty

，这也符合我们的认知。

但是为什么一定要是两边相切的时候呢？事实上可以先想着固定

lambda

，固定之后，直线的斜率固定了，所以可以将直线“向上推”，推到与区域的某个地方相切为止。那么寻找这个最优值，其实就是再进一步的改变

lambda

的过程，可以看出如果不是两边相切，如果是只切了一边，与另一边没切到呢（对应蓝色的线）？它可能是最优值吗？那么我们完全可以上移这一条直线，所以这样得到的对偶函数的值会更大，因此不可能是最优值。反过来，如果与一边相交呢（对应紫色的线）？那么注意，我们可以不改变

lambda

，把线向下移，依然可以满足它与区域相交（注意与区域相交是集合的一个条件）。所以这个情况不可能是某一个

g(lambda)

，因为

g(lambda)

要求一个最小的。所以红线为什么那么画，其实真要解释，还是需要费一番口舌的233。

当然了，上面的分析也只是针对那一个情况做的。但这种几何的分析思想是通用的。这也便是第一种解释，虽然可能在实际的操作中没啥辅助的作用，但也算是分析问题结构的一种工具。

接下来我们来看一下鞍点视角。鞍点我们在《数值优化》第1节（数值优化（1）——引入，线搜索：步长选取条件）中提过，它是梯度为0的点，但是却不是极值。不过我们下面有一个鞍点的更为形象的定义。

Definition 3: saddle point 对函数

L(x, lambda)

，如果满足

inf_{x in D} sup_{lambda ge 0} L(x, lambda) = sup_{lambda ge 0} inf_{x in D} L(x, lambda)

，且取到极值的点

(x^*, lambda^*)

相同，则称这个点为鞍点。

这个定义和之前说的好像完全没什么关系？理解它关键要看到底什么是马鞍面。我们找一张马鞍面的图。

可以看出，在三维的马鞍面中，从一个方向走过去（比方说从前到后），这个点对应的就是这个方向函数的极大值。但是如果换了一个方向（比方说从左到右），这个点就对应了这个方向函数的极小值。所以我们会发现鞍点对应的梯度为0（因为从各个方向来看，它都达到了极值），但是你无法确定这个点究竟是极大值还是极小值。

那么在我们的定义中，我们会发现，右边的式子

sup_{lambda ge 0} inf_{x in D} L(x, lambda)

就是

d^*

，因为从右往左看，先求了一个极小，这会得到对偶函数

g(lambda)

，然后再取了一个极大，这就是对偶函数的推导过程。但是左边的式子是什么意思呢？简单来说，如果

x not in D

，那么在这个问题中就是

f_1(x) > 0

，那么这个时候其实左边的式子一定是

infty

，这个显然不可能作为极小值存在（因为我们一般情况下

D ne emptyset

），所以只能有

x in D

，那么左边其实就是原问题，因此得到的解就是

p^*

。

这个结论得到之后，我们其实就会发现，强对偶性如果要满足，一定要拉格朗日函数存在鞍点，而这个鞍点就对应了原问题与对偶问题的解。因此研究拉格朗日函数的性质，也是一个不错的发现对偶性的方案。

那么关于对偶性的理解，我们就说到这里，之前专栏收录了一篇讲对偶性的更加简洁的文章，这里也把链接贴上，感兴趣的可以去看一看

https://zhuanlan.zhihu.com/p/52544386

再进一段广告！

广告结束！

对偶性框架下的KKT条件

说“再看”的原因是，我们在《数值优化》第9节（数值优化（9）——非线性规划中的极值性质，KKT条件）已经花了大篇幅去引入KKT条件并给出了证明。但是我们这里给出的KKT条件其实视角有些不同，我们没有对问题施加“光滑”这样的约束，而这个KKT条件的提出也不完全是因为一阶最优性条件。

还是一样，考虑一个优化问题

min_x f(x) \ s.t. quad h_i(x) le 0, i = 1, ldots, m \ l_j(x) = 0, j = 1, ldots, r

那么KKT条件其实就是下面这些式子

Definition 4: KKT Conditions 定义KKT条件为

0 in partial_x (f(x) sum_{i=1}^m u_i h_i(x) sum_{j = 1}^r v_j l_j(x))

（稳定性条件）

u_i h_i(x) = 0, forall i

（互补松弛条件）

h_i(x) le 0, l_j(x) = 0, forall i, j

（原问题可行条件）

u_i ge 0, forall i

（对偶问题可行条件）

其实和之前我们推导的一样有五个条件，我们在对偶性框架下又给这些条件起了不同的名字，我们后面会使用这些名字来描述每个条件。稍微有所不同的就是第一个条件。这里我们没有光滑的条件，因此我们只能够求拉格朗日函数的次梯度。这样的话一定程度上，相比较之前做了一个推广，因为随便一想就知道，如果

f(x)

不是凸函数，那么这个求次梯度得到的结果，和我们之前求梯度得到的结果就不等价了。

那么KKT条件和对偶性有什么关系呢？一个很重要的地方在于，如果对偶性足够好，KKT条件可以帮助我们发现最优值的一些性质，而不需要诉诸于求解原问题或对偶问题。所以为了推导出KKT条件与对偶性的关系，我们要做一些工作。

首先呢我们要说明的是下面这个结论。

Proposition 2: 如果强对偶性满足，那么原问题的最优解

x^*

和对偶问题的最优解

u^*, v^*

满足KKT条件。

这个其实挺容易的，首先根据强对偶性我们有

f(x^*) = g(u^*, v^*) = min_{x} f(x) sum_{i= 1}^m u_i^*h_i(x) sum_{j = 1}^nv_j^* l_j(x) \ le f(x^*) sum_{i= 1}^m u_i^*h_i(x^*) sum_{j = 1}^nv_j^* l_j(x^*)le f(x^*)

所以可以发现所有不等式其实都应该取等号。这说明什么？注意到

h_i(x)

都是不等式约束，均非正，而等号恰好告诉我们

sum_{i= 1}^m u_i^* h_i(x) = 0

，所以这就说明了

h_i(x) = 0

都是成立的，这就能推出互补松弛条件。

继续探索，倒数第二个不等号也应该取等号，说明

x^*

是一个极小值点，因此必然会有稳定性条件满足。剩下的两个条件不用证明，因为如果点不满足可行性条件，这个优化问题也没有讨论下去的必要了……所以我们就证明好了这个结论。

现在我们把条件和结论反过来说，稍微改一下，看看下面这个结论。

Proposition 3: 如果原问题的变量

x^*

和对偶问题的变量

u^*, v^*

满足KKT条件，则

x^*

为原问题的最优解，

u^*, v^*

为对偶问题的最优解。

我们证明一下这个结论。也不难，因为假如说

u^*, v^*

为解，那么就会有

g(u^*, v^*) = f(x^*) sum_{i = 1}^m u_i^* h_i(x^*) sum_{j = 1}^n v_j^* l_j(x^*) = f(x^*)

第一个等式是根据稳定性条件得到的（我跳了一步，想想为什么？），第二个等式是根据互补松弛条件得到的。这个式子就是告诉我们对偶间隔为0。这说明什么？根据上面的不等式，这说明一方面原问题取到了最优解，另一方面说明强对偶性满足，也即对偶问题也取到了最优解。

所以我们把Proposition 2和3结合一下，得到的结论就是：如果强对偶性满足，那么解KKT条件就能够得到原问题和对偶问题的最优解。但反过来，如果强对偶性不满足，那么即使有了最优性，也不能使用KKT条件，因为等价关系不成立。

好的，我们先用一个简单而常用的例子来结束这一节。剩下的关于对偶性的部分则下一节再说。

Example 3: 研究问题

min_x f(x) quad s.t. h(x) le t

与

min_x f(x) lambda h(x)

的等价性。

这两个问题最经典的例子就是对范数性质的研究。这个具体的可以看《回归分析》的第13节（https://zhuanlan.zhihu.com/p/53764089），在那里我们分析

l_1

和

l_2

范数的性质的时候，说可以把加了罚项的式子（拉格朗日式）通过对偶性转换为一个带约束的优化问题。在这里我们可以把这个问题看得更透彻一些。

假如说

x^*

是左边的带约束优化问题，并且这个问题存在解是使得不等式取不到等号的（严格定义说是严格可行的解（strictly feasible）），那么强对偶性就满足，那么这个解

x^*

也是

min_x f(x) lambda (h(x) - t)

的解。这就说明了

x^*

也是右边那个优化问题的解（因为

t

是与自变量无关的）。

反过来，假如说

x^*

是右边问题的解，那么这个时候，设

t = h(x^*)

，我们就会发现

x^*

满足KKT条件（只需要把几个条件都check一下即可）。我们之前说过，如果KKT条件满足，那么

x^*

就是原问题的解，所以这一个方向也推出来了。

虽然看似证明了一个等价性，但是这个等价性是有条件的。如果说原问题上不存在一个严格可行的解，那么等价性是推不过来的。不过这种情况不是特别多见，比方说在这里，其实就是要对应

t = 0

的时候，但应该不太会有人做这样的假设吧233。

所以有了这个结论，我们就可以理解为什么我们可以通过一个等价转换，来解释

l_1

，

l_2

范数的性质了。

好的，那么这一节就说这么多。关于对偶性其实还是有很多可以聊的，我们在下一节会继续说。不过我想下一节就可以把对偶性给结束掉了，所以大家也不必太担忧困在理论里面太久，我们毕竟还是算法导向的系列笔记啊hh。

小结

本节从例子开始，介绍了强对偶性的理解和作用，并从不同的方面带着大家深入的理解了优化问题的对偶性概念。之后我们又花时间解释了在对偶性框架下的KKT条件，并利用它来解释了一个常见的拉格朗日函数和带约束优化问题的不完全等价性（example 3）。不过对偶性的内容真的很多又很重要，似乎这一整节还不够说。下一节我们会继续介绍这一部分内容，介绍完之后就会重新回到算法的部分，应该是可以介绍完的吧？希望如此吧。

definition optimization 优化

0 人点赞