如何利用Fenchel-Rockafellar对偶推导线性规划对偶问题

嘿，咱们一步步把线性规划套进Fenchel-Rockafellar（简称FR）的原对偶框架里，就能轻松推导出线性规划的对偶问题啦。先从标准线性规划的原问题入手，再对应到FR的各个组件上，最后计算共轭函数代入对偶问题就行。

第一步：写出标准线性规划原问题 #

先明确我们要处理的线性规划原问题（LP-P）：

$$\min_{x \in \mathbb{R}^n} c^T x$$
约束条件：$$Ax = b, \quad x \geq 0$$
这里$A$是$m \times n$的实矩阵，$c \in \mathbb{R}^n$是目标系数向量，$b \in \mathbb{R}^m$是约束右端项。

第二步：将线性规划转化为FR原问题的形式 #

FR的原问题是：
$$\min_{x \in X} f(x) + g(Ax)$$
其中$f$、$g$是凸、下半连续、正常函数，$A$是有界线性算子。我们需要把线性规划的约束和目标拆成$f(x)$和$g(Ax)$：

• 定义$f(x)$：把非负约束$x \geq 0$用指示函数$\delta_{\mathbb{R}+^n}(x)$嵌入，同时加上原目标函数：
  $$f(x) = c^T x + \delta{\mathbb{R}_+^n}(x)$$
  指示函数$\delta_C(x)$的规则是：当$x \in C$时取值为0，否则为$+\infty$。这个$f(x)$完全满足FR对函数的要求（凸、下半连续、正常）。
• 定义$g(y)$：把等式约束$Ax = b$转化为$Ax = b$的指示函数：
  $$g(y) = \delta_{{b}}(y)$$
  也就是当$y = b$时取值0，否则$+\infty$，同样符合FR的函数条件。
• 这里的线性算子$A$就是线性规划里的$m \times n$矩阵（作为从$\mathbb{R}^{n$到$\mathbb{R}}m$的有界线性算子），它的伴随算子$A^{*$就是$A$的转置$A}T$（因为对任意$x \in \mathbb{R}^n$、$y \in \mathbb{R}^m$，有$\langle Ax, y \rangle = x^T A^T y = \langle x, A^T y \rangle$）。

现在，FR原问题$\min_x f(x) + g(Ax)$就和线性规划原问题完全等价：只有当$x \geq 0$且$Ax = b$时，$f(x)+g(Ax)=c^T x$，其他情况都是$+\infty$，最小化这个式子就是求线性规划的最优解。

第三步：计算凸共轭函数$f^*$和$g*$ #

凸共轭的定义是：$h^(z) = \sup_x {\langle z, x \rangle - h(x)}$，咱们分别计算$f^*$和$g$：

1. 计算$f^*(z)$：
   $$
   f^(z) = \sup_x {z^T x - f(x)} = \sup_{x \geq 0} {z^T x - c^T x} = \sup_{x \geq 0} {(z - c)^T x}
   $$
   分析这个上确界：如果存在某个分量$z_i - c_i > 0$，那$x_i$可以取无穷大，上确界为$+\infty$；只有当所有分量$z_i \leq c_i$（即$z \leq c$，逐分量成立）时，上确界为0（当$x=0$时取到）。所以：
   $$
   f^(z) = \delta_{{z \mid z \leq c}}(z)
   $$
2. 计算$g^*(-y)$：
   先算$g^(w)$：
   $$
   g^(w) = \sup_y {w^T y - g(y)} = w^T b
   $$
   因为只有$y=b$时，式子是$w^T b - 0$，其他情况都是$-\infty$，上确界就是$w^T b$。那$g^(-y)$就是：
   $$
   g^(-y) = (-y)^T b = -b^T y
   $$

第四步：代入FR对偶问题得到线性规划对偶 #

FR的对偶问题是：
$$\min_{y \in Y} f^*(A* y) + g^(-y)$$
把$A^ = A^T$、$f(A^T y)$和$g^(-y)$的结果代入：
$$
\min_y \delta_{{A^T y \leq c}}(A^T y) - b^T y
$$
这个式子的含义是：只有当$A^T y \leq c$时，目标函数是$-b^T y$，否则为$+\infty$。而最小化$-b^T y$等价于最大化$b^T y$，所以这个问题就转化为：

$$\max_{y \in \mathbb{R}^m} b^T y$$
约束条件：$$A^T y \leq c$$
这正是线性规划的标准对偶问题！

内容的提问来源于stack exchange，提问作者User32563