Primal-Dual原对偶问题大致介绍

简介

?线性规划技术是多项式时间可解的。通过将整数规划松弛为线性规划后（如将x∈{0,1}x\in\{0,1\}x∈{ 0,1}松弛为$x\ge 0$）,得到一个分数解（fractional），之后再将分数解进行取整得到整数规划的整数解。
?其中primal-dual方法是一种被广泛使用的优化方法，在凸优化和组合优化上有很多应用；其在NP-hard问题的近似算法上也有广泛的使用。下文通过线性规划上的primal-dual方法的应用，进行简单的介绍。
?有一篇关于对偶和拉格朗日对偶问题的描述：优化方法：原问题和拉格朗日对偶问题（primal-dual）。其详细介绍了拉格朗日函数，拉格朗日对偶函数，以及一个通过图片直觉的感受拉格朗日对偶函数为凹函数的一个例子。介绍了 KKT 条件 和 Slater 条件。
?关于仿射函数可以理解为将一个向量x从n维空间映射到m维空间上，具体定义可以参考仿射函数百度百科

线性规划的原对偶（primal-dual）问题

形式化描述：
(Primal):$$min\sum _{i=1}^n{c}_i{x}_i$$
$$s.t.forany1\le j\le m:$$
$$\sum _{i=1}^n{a}_{ij}{x}_i\ge b_j,?1\le i\le n,x_i\ge 0$$
(Dual):$$max\sum _{j=1}^m{b}_j{y}_j$$
$$s.t.forany1\le i\le n:$$
$$\sum _{j=1}^m{a}_{ij}{y}_j\le c_i,?1\le j\le m,y_j\ge 0$$

强对偶、弱对偶

假设原问题得到的可行解为P=$min{\sum }_{i=1}^n{c}_i{x}_i$，最优解为OPT；对偶问题得到的可行解为D=$max{\sum }_{j=1}^m{b}_j{y}_j$。
由对偶的性质可知，其满足：$D\le OPT\le P$
原问题最优解$p^{?}/OPT$和对偶问题最优解$d^{?}$之间的差值称为对偶间隙：$p^{?}?d^{?}$，当对偶间隙为0时，则强对偶性成立；当对偶间隙大于0时，则其为弱对偶性。
大多数情况下， 当原问题是凸优化问题，即原函数和不等式约束为凸函数，而等式约束为仿射函数时，强对偶性成立（但不绝对）这句不太确定，其他博客看到的

互补松弛条件(Complementary Slackness Condition)

P： $x_j>0=>[A^{T}y{]}_j=c_j$
D： $y_i>0=>[A^x{]}_i=b_i$
当互补松弛条件成立时，x,y是P,D的可行解，也是最优解。
它从原问题§的一个可行解出发, 在满足互补松弛条件的前提下, 使得其对偶变量朝着对偶可行解的方向迭代. Primal-Dual的思想是从对偶可行解出发, 在满足互补松弛条件的前提下, 使得原始变量朝着可行解的方向迭代。

松弛的互补松弛条件

P： $x_j>0=>[A^{T}y{]}_j=c_j/\alpha$
D： $y_i>0=>[A^x{]}_i=\beta b_i$
通过松弛的互补松弛条件得到的primal-dual算法迭代计算得到的可行解最大不会超过最优解的$\alpha \beta$倍。

primal-dual方法主要流程（个人理解，不确定一定是对的）

通常将整数优化问题放缩为分数（fractional）形式，然后通过原始对偶方法进行问题最优解的计算，不需要解答线性规划的计算过程（这半句不是很理解，但它是对的）。原始对偶方法从对偶形式下的一个可行解出发，逐渐增加对偶变量值，使得满足互补松弛条件的变量个数增加，改进对偶解的解值，直到无法修正，得到对偶可行解，再通过对偶可行解得到原始的可行解。

set-cover问题举例

?给出一个集合的实例$I$，其对应的最小优化问题也即原始问题（primal）会存在一系列的可行解，定义每个实例$I$对应的最小可行解对应的花费（cost）为$OPT(I)$；同理，在最大化优化问题也即对偶问题（dual）中其对应的最大可行解对应的利润（profit）为$OPT(I)$

之后理解的比较完善了再添加。

参考

算法设计技巧: Primal-Dual