20211225-Primal-Dual原对偶问题

Primal-Dual原始-对偶问题

1. 概述

• Prime-Dual的意义：可以给很多组合优化问题，尤其是网络设计问题提供近似算法。
• 应用：哈密顿回路、最大匹配的经典解法Blossom Algorithm；

2. 拉格朗日函数

• 解决带约束条件的优化问题的一般解法：拉格朗日乘子法，步骤为：
  • 先写出拉格朗日函数；
  • 对$x$求导得到导数为0的点；
  • 将该点代回原函数，其中最大值即为原函数的最大值，最小值即为原函数的最小值。
• 上述凸优化问题的拉式函数为：

$$\begin{equation} L(x, u, v)=f_{0}(x)+\sum_{i=1}^{m} u_{i} f_{i}(x)+\sum_{j=1}^{p} v_{j} h_{j}(x) \end{equation}$$

• 对于固定的$x$而言，$L(x,u,v)$为$u$和$v$的仿射函数。
• 至此，我们就把原来的求解带约束条件的原函数转换为了不带约束条件的拉格朗日函数

3. 拉格朗日对偶函数

• 求解$\min _{x} f_{0}(x)$，等价于求解：$\min _{x} \max _{u, v} L(x, u, v)$；
• 但是上式并不容易求解，由此引入了拉格朗日对偶函数（不是对偶问题），即：

$$\begin{equation} g(u, v)=\inf _{x \in D} L(x, u, v)=\inf _{x \in D}\left[f_{0}(x)+\sum_{i=1}^{m} u_{i} f_{i}(x)+\sum_{j=1}^{p} v_{j} h_{j}(x)\right] \end{equation}$$

• 其中，$\underset{x\in D}{\mathop{\inf }}\,$表示函数逐点对$x$求下确界，即对任意$u$和$v$求出一个使得$L(x,u,v)$最小的$x$；
• 当拉式函数没有下确界的时候，定义下确界为$-\infty$，$D$是可行域。
• 拉格朗日对偶函数是一个凹函数，即它存在一个唯一的极大值点。

4. Set Cover问题举例

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

5. 参考

• https://blog.csdn.net/zuzhiang/article/details/103293545