简介
线性规划技术是多项式时间可解的。通过将整数规划松弛为线性规划后（如将
x
∈
{
0
,
1
}
x\in\{0,1\}
x∈{0,1}松弛为
x
≥
0
x\geq0
x≥0）,得到一个分数解（fractional），之后再将分数解进行取整得到整数规划的整数解。
其中primal-dual方法是一种被广泛使用的优化方法，在凸优化和组合优化上有很多应用；其在NP-hard问题的近似算法上也有广泛的使用。下文通过线性规划上的primal-dual方法的应用，进行简单的介绍。
有一篇关于对偶和拉格朗日对偶问题的描述：优化方法：原问题和拉格朗日对偶问题（primal-dual）。其详细介绍了拉格朗日函数，拉格朗日对偶函数，以及一个通过图片直觉的感受拉格朗日对偶函数为凹函数的一个例子。介绍了 KKT 条件 和 Slater 条件。
关于仿射函数可以理解为将一个向量x从n维空间映射到m维空间上，具体定义可以参考仿射函数百度百科
线性规划的原对偶（primal-dual）问题
形式化描述：
(Primal):
m
i
n
∑
i
=
1
n
c
i
x
i
min\sum_{i=1}^nc_ix_i
mini=1∑ncixi
s
.
t
.
f
o
r
a
n
y
1
≤
j
≤
m
:
s.t.\ \ for \ \ any \ \ \ 1\leq j\leq m:
s.t. for any 1≤j≤m:
∑
i
=
1
n
a
i
j
x
i
≥
b
j
,
∀
1
≤
i
≤
n
,
x
i
≥
0
\sum_{i=1}^na_{ij}x_i\geq b_j, \ \ \forall \ 1\leq i\leq n, \ x_i\geq 0
i=1∑naijxi≥bj, ∀ 1≤i≤n, xi≥0
(Dual):
m
a
x
∑
j
=
1
m
b
j
y
j
max\sum_{j=1}^mb_jy_j
maxj=1∑mbjyj
s
.
t
.
f
o
r
a
n
y
1
≤
i
≤
n
:
s.t. \ \ for \ \ any \ \ 1\leq i\leq n:
s.t. for any 1≤i≤n:
∑
j
=
1
m
a
i
j
y
j
≤
c
i
,
∀
1
≤
j
≤
m
,
y
j
≥
0
\sum_{j=1}^ma_{ij}y_j\leq c_i,\ \ \forall 1\leq j \leq m,\ \ y_j\geq 0
j=1∑maijyj≤ci, ∀1≤j≤m, yj≥0
强对偶、弱对偶
假设原问题得到的可行解为P=
m
i
n
∑
i
=
1
n
c
i
x
i
min\sum_{i=1}^nc_ix_i
min∑i=1ncixi，最优解为OPT；对偶问题得到的可行解为D=
m
a
x
∑
j
=
1
m
b
j
y
j
max\sum_{j=1}^mb_jy_j
max∑j=1mbjyj。
由对偶的性质可知，其满足：
D
≤
O
P
T
≤
P
D\leq OPT \leq P
D≤OPT≤P
原问题最优解
p
∗
/
O
P
T
p^*/OPT
p∗/OPT和对偶问题最优解
d
∗
d^*
d∗之间的差值称为对偶间隙：
p
∗
−
d
∗
p^*-d^*
p∗−d∗，当对偶间隙为0时，则强对偶性成立；当对偶间隙大于0时，则其为弱对偶性