Ji's Blog
线性规划的对偶问题
[ math ]

本篇博客的内容是对偶线性规划（Dual LP），是这学期选修的一门课里的内容（腊月里考试，唉），记下来当作是复习了。

首先，一个线性规划问题包含输入，输出，约束条件以及目标函数这四个部分，它的基本形式是这样的：

Input: $A$, $b$, $c$

Output: $x \in \mathbb{R}$

Constraint: $A \cdot x \geq b$

Objective funtion: $\min(c \cdot x)$

那么它的对偶线性规划为：

Input: $A$, $b$, $c$

Output: $y \in \mathbb{R}$

Constraint: $A^T \cdot y \leq c^T$

Objective funtion: $\max(b^T\cdot y)$

为了方便表示，第一个线性规划问题称为LP1，它的对偶线性规划问题为LP2。同时，LP1也可以看做是LP2的对偶。

LP1和LP2之间有如下的特性：

1. LP1和LP2的目标函数的最优值相同

如下图所示，蓝色是LP2的目标函数值的范围，红色部分是LP1的目标函数值的范围，二者的最优值Opt是相同的。换句话说，如果LP1和LP2的目标函数值相同，那么该值即为最优值。

enter description here

2. 互补松弛性（complementary slackness）

如果LP2的解$y$中的某个变量$y_i$的值大于0，那么其在LP1中对应的约束条件中的符号应为等号，即: $\sum_{j=1}^{n} a_{ij}x_j = b_i$，此时我们称这个约束是紧的。假如$y_i=0$，那么LP1中对应的约束应该取不等号，即：$\sum_{j=1}^{n} a_{ij}x_j > b_i$，此时这个约束是松的。

一道例题

例题来自于课堂的PPT。假设我们有如下图所示的传感器网络，其中圆代表传感器，三角形代表需要检测的目标，一个传感器可以监测所有与其相连的目标。假设每个传感器最多只能使用一个小时，且必须同时监测所有的目标，我们想要最大化监测目标的时间。由图可知，想要同时检测所有的三角形，可选的传感器组合有： $[1,2],[1,3],[2,3],[1,2,3]$。

enter description here

将其转化为一个线性规划问题：

Input: 传感器集合$S$，对于集合中的每个传感器$s_i \in S$，其所能检测到的目标集合 $T_s$。

Output: 每种能够覆盖所有目标的传感器组合$C_1,…,C_p$的使用时间$t_1,…,t_p$。

Constraint: 每个传感器的使用时间不可以超过一个小时，即对于任意一个传感器$s_i$：

\[\sum_{j:i \in C_j} t_j \leq 1\]

Objective Function: $\max(t_1+…+t_p)$

其中，约束条件可以转化为$Ax \leq b$的形式，其中$A$ 中的任一元素$a_{ij}$ 表示传感器$s_i$否属于组合$C_j$，如果属于，$a_{ij}$为1，反之为0；$x=[t_1,t2,…,t_p]^T$, $b = [1,1,…,1]^T$。而目标函数可以写为$\max (c*x)$，其中$c = [1,1,…,1]$。上面这张图中共有3个传感器以及3种可用的组合，求出的最优解为$x=[0.5,0.5,0.5,0]$，目标函数的最优值为1.5。

当传感器以及监测目标的数量变得非常大的时候，方程的数量也会变多。此时我们可以借助它的对偶线性规划来进行求解。即将约束条件和目标函数转换成如下形式：

Constraint: $A^T y \geq c^T$

Objective Function: $\min (b^Ty)$

这样方程的数量就变成了可选组合$C$的数量。我们可以通过一种迭代的方法（Garg-Konemann算法）来求对偶LP的可行解。该算法的步骤如下：

  1. 将$x$中每个元素的初始值设为0，$y$中每个元素的初始值设为$\delta$，$\delta$是一个很小的值。
  2. 找出最小化$a_{1i}y_1+a_{2i}y_2+…+a_{ni}y_n$ 的$i’$。此时，我们可以将第$i’$个约束条件看做是最有问题的约束。
  3. 如果$a_{1i’}y_1+a_{2i’}y_2+…+a_{ni’}y_n \geq 1$ ，那么所有约束条件都满足了（因为其他不等式的左侧只会比它大），此时我们获得了一个可行解，算法结束。
  4. 如果第$i’$个约束没有满足，那么对于所有令$a_{ji’}=1$的$j$，我们令$y_{j} \leftarrow (1+\theta)y_j$。
  5. $x_{i’} \leftarrow x_{i’}+\tau$
  6. 跳转到第二步。

其中$\theta,\delta,\tau$这三个参数需要提前设定。其中$\tau$和$\delta$的设置可以参考以下公式（证明略）：

\[\tau = \frac{\ln(1+\theta)}{\ln{1+\theta}-\ln(\delta)}\] \[\delta = (1+\theta)((1+\theta)n)^{-\frac{1}{\theta}}\]

一般情况下，问题的解只会包含可选组合中的一小部分，因此就算传感器数量较多，也不会迭代太多次数。

以下称原问题为LP1，其对偶线性规划为LP2。

1. 求得最优解

以上的算法可以求出线性规划的一个可行解SOL。如果想要求得最优解OPT，还需要进一步的分析。

我们可以将LP2的约束条件改写为:

\[f(y) = \underset{i}{\mathrm{\ min}}(a_{1i}y_1+a_{2i}y_2+...+a_{ni}y_n) \geq 1\]

如果$f(y)>1$，说明$y$还可以变得更小。因此，最优解对应的$f(y)$值为1。由此，我们可以将LP2的目标函数转换为：$\underset{i}{\mathrm{\ min}} \frac{(z_1+…+z_n)}{f(z)}$。（证明略）

对于给定的$\delta,\theta,\tau$，有如下的两条引理（证明略）：

  1. Garg-Konemann算法的迭代次数 $\geq \ln(\frac{1}{n\delta}) \cdot \frac{OPT}{\theta}$

  2. 对应的LP1的可行解： $SOL \geq \tau \ln(\frac{1}{n\delta}) \cdot \frac{OPT}{\theta}$

将$\tau = \frac{\ln(1+\theta)}{\ln{1+\theta}-\ln(\delta)}$以及$\delta = (1+\theta)((1+\theta)n)^{-\frac{1}{\theta}}$代入可得：

  1. 迭代次数 $\geq \frac{1}{\theta^2}n\ln n$

  2. 可行解： $SOL \geq \frac{1-\theta}{1+\theta}OPT$

由此可知，$\theta$的取值越小，SOL越接近OPT，但是算法所需的迭代次数会增加。如果不限制计算时间的话，理论上我们可以获得最优解OPT。

2. 进一步简化问题？

当传感器数量庞大的时候，Garg-Konemann算法的第2步需要耗费大量的时间。为了节约时间，可以将$f(y)$等价为：

\[f(y) = \underset{i}{\mathrm{\ min}}(a_{1i}y_1+a_{2i}y_2+...+a_{ni}y_n) = \underset{i}{\mathrm{\ min}} \sum_{j\in C_i}y_j\]

因此，G-K算法的第2步就变成了：找到一个传感器集合$C_i’$，令$\sum_{j\in C_i’}y_j$最小。这样的话，求传感器最大监测时间的问题可以被转换为一个目标点覆盖问题(target coverage problem)。该问题存在一个能够保证$SOL \leq (\ln T+1) \cdot OPT$的近似算法，其中$T$是待监测目标的数量。因此，改动之后，LP1的SOL与OPT之间的关系为：$SOL \geq \frac{1-\theta}{1+\theta} \cdot \frac{1}{\ln T + 1} \cdot OPT$。