最近在看支持向量机，对对偶问题不甚了解。就花了一些时间看了一下知乎上的解释和Andrew Ng的解释。以下是关于这个issue的总结。
假设我们有如下优化问题（原问题）
Problem
1
:
min
f
(
x
)
\min f(x)
min
f
(
x
)
$s.t. g(x) \leq 0, $
为描述方便起见，我们假设只有一个不等式约束，多个不等式约束可以做简单的扩展。等式约束则可以转化为不等式约束。令
L
(
x
,
λ
)
=
f
(
x
)
+
λ
g
(
x
)
L(x, \lambda) = f(x) + \lambda g(x)
L
(
x
,
λ
)
=
f
(
x
)
+
λ
g
(
x
)
，
很显然，如果
Problem
2
:
f
(
x
)
<
v
f(x) < v
f
(
x
)
<
v
s
.
t
.
g
(
x
)
≤
0
,
s.t. g(x) \leq 0,
s
.
t
.
g
(
x
)
≤
0
,
无解，我们称
v
v
v
是Problem 1的一个
下界
。如果Problem 2有解，那么对于任意的
λ
≥
0
\lambda \geq 0
λ
≥
0
,
Problem
3
:
L
(
x
,
λ
)
<
v
,
L(x, \lambda) < v,
L
(
x
,
λ
)
<
v
,
有解（略微思索便知）。
显然地，根据逆否命题：
如果Problem 3无解，那么Problem 2无解
。
Problem 3无解的充分必要条件是
Problem
4
:
v
≤
min
x
L
(
x
,
λ
)
v \leq \min_x L(x, \lambda)
v
≤
min
x
L
(
x
,
λ
)
.
因此，如果Problem 4成立，则Problem 2无解，那么v是Problem 1的一个下界。
因为我们要找到一个最大下界，所以
v
∗
=
max
λ
min
x
L
(
x
,
λ
)
v^* = \max_\lambda \min_x L(x, \lambda)
v
∗
=
max
λ
min
x
L
(
x
,
λ
)
.
因此，也就引入了Dual problem.
说到这里，我们再来看一下原问题，
很显然，我们有如下公式
max
λ
L
(
x
,
λ
)
=
f
(
x
)
,
if
g
(
x
)
≤
0
;
e
l
s
e
+
∞
\max_\lambda L(x, \lambda)= f(x), \text{ if } g(x) \leq 0; else \text{ } +\infty
λ
max
L
(
x
,
λ
)
=
f
(
x
)
,
if
g
(
x
)
≤
0
;
e
l
s
e
+
∞
所以原问题即
Problem
5
:
p
∗
=
min
x
max
λ
L
(
x
,
λ
)
p^* = \min_x \max_\lambda L(x, \lambda)
p
∗
=
min
x
max
λ
L
(
x
,
λ
)
.
我们看到，原问题与对偶问题实际上就是前面极小极大符号的交换。
针对该解释，我给出的直观的理解是：对偶问题是直接求解原问题转化成求原问题的最大下界的问题
原问题与对偶问题满足如下不等式关系,
v
∗
=
max
λ
min
x
L
(
x
,
λ
)
≤
min
x
max
λ
L
(
x
,
λ
)
=
p
∗
v^* = \max_\lambda \min_x L(x, \lambda) \leq \min_x \max_\lambda L(x, \lambda) = p^*
v
∗
=
max
λ
min
x
L
(
x
,
λ
)
≤
min
x
max
λ
L
(
x
,
λ
)
=
p
∗
.
当f(x)与g(x)都是convex的时候，我们有
v
∗
=
p
∗
v^* = p^*
v
∗
=
p
∗
，原问题等价于对偶问题。这是因为当f(x)与g(x)是convex的时候，原问题与对偶问题的解都是独立于
λ
\lambda
λ
的，具体地可以参见：
https://wenku.baidu.com/view/3d94c60f172ded630a1cb63d.html
补充：看西瓜书上对对偶问题的解释，觉得很透彻，现在复述一遍。
对于原始问题
m
i
n
f
(
x
)
min \text{ } f(x)
m
i
n
f
(
x
)
s
.
t
.
h
i
(
x
)
=
0
,
i
=
1
,
…
,
m
s.t. h_i(x) = 0, i = 1, \dots, m
s
.
t
.
h
i
(
x
)
=
0
,
i
=
1
,
…
,
m
g
j
(
x
)
≤
0
,
j
=
1
,
…
,
n
g_j(x) \leq 0, j = 1, \dots, n
g
j
(
x
)
≤
0
,
j
=
1
,
…
,
n
.
构建Lagrange函数如下：
L
(
x
,
α
,
β
)
=
f
(
x
)
+
α
T
g
(
x
)
+
β
T
h
(
x
)
L(x, \alpha, \beta) = f(x) + \alpha^Tg(x) + \beta^Th(x)
L
(
x
,
α
,
β
)
=
f
(
x
)
+
α
T
g
(
x
)
+
β
T
h
(
x
)
其中
α
⪰
0
\alpha \succeq \mathbf{0}
α
⪰
0
，表示
α
\alpha
α
中每个分量都是大于0的。
其Lagrange对偶函数如下，其中
D
D
D
表示可行域：
Γ
(
α
,
β
)
=
i
n
f
x
∈
D
L
(
x
,
α
,
β
)
\Gamma(\alpha, \beta) = inf_{x \in D} \text{ } L(x, \alpha, \beta)
Γ
(
α
,
β
)
=
i
n
f
x
∈
D
L
(
x
,
α
,
β
)
=
i
n
f
x
∈
D
[
f
(
x
)
+
α
T
g
(
x
)
+
β
T
h
(
x
)
]
= inf_{x \in D} [f(x) + \alpha^Tg(x) + \beta^Th(x)]
=
i
n
f
x
∈
D
[
f
(
x
)
+
α
T
g
(
x
)
+
β
T
h
(
x
)
]
很显然，x在可行域范围之内，满足
g
(
x
)
≤
0
g(x) \leq 0
g
(
x
)
≤
0
以及
h
(
x
)
=
0
h(x) = 0
h
(
x
)
=
0
那么
α
T
g
(
x
)
+
β
T
h
(
x
)
≤
0
\alpha^Tg(x) + \beta^Th(x) \leq 0
α
T
g
(
x
)
+
β
T
h
(
x
)
≤
0
是成立的，因此：
假设
x
∗
x^*
x
∗
是无约束函数
f
(
x
)
f(x)
f
(
x
)
的最优解，那么有
Γ
(
α
,
β
)
=
i
n
f
x
∈
D
L
(
x
,
α
,
β
)
≤
L
(
x
∗
,
α
,
β
)
≤
f
(
x
∗
)
\Gamma(\alpha, \beta) = inf_{x \in D} L(x, \alpha, \beta) \leq L(x^*, \alpha, \beta) \leq f(x^*)
Γ
(
α
,
β
)
=
i
n
f
x
∈
D
L
(
x
,
α
,
β
)
≤
L
(
x
∗
,
α
,
β
)
≤
f
(
x
∗
)
。
令
f
(
x
∗
)
=
p
∗
f(x^*) = p^*
f
(
x
∗
)
=
p
∗
为最优值, 那么
Γ
(
α
,
β
)
≤
p
∗
\Gamma(\alpha, \beta) \leq p^*
Γ
(
α
,
β
)
≤
p
∗
显然，这个下界取决于
α
,
β
\alpha, \beta
α
,
β
这两个变量，找到一个最好的下界便成为一个很自然的问题，因此引入对偶问题：
m
a
x
α
,
β
Γ
(
α
,
β
)
max_{\alpha, \beta} \Gamma(\alpha, \beta)
m
a
x
α
,
β
Γ
(
α
,
β
)
s
.
t
.
α
⪰
0
s.t. \alpha \succeq \mathbf{0}
s
.
t
.
α
⪰
0
当
f
(
x
)
,
g
(
x
)
f(x), g(x)
f
(
x
)
,
g
(
x
)
为凸函数，
h
(
x
)
h(x)
h
(
x
)
为仿射函数的时候，有
m
a
x
Γ
(
α
,
β
)
=
p
∗
max\text{ } \Gamma(\alpha, \beta) = p^*
m
a
x
Γ
(
α
,
β
)
=
p
∗
。