POSTS

计算LLM需要多少GPU内存的公式和工具

对偶问题

对偶方式

• 拉格朗日对偶
• 共轭对偶（非线性优化中用得比较多）

拉格朗日对偶

对原问题的每个约束引入对偶变量（对偶变量也可以称作影子价格，表示满足该约束成立的cost），然后进行线性组合。

线性规划的对偶模型

1. 原始模型->对偶模型

   • 原始约束->对偶变量
   • 原始变量->对偶约束

   因此，一个模型是因为约束很多而很难处理时，就可以转变对偶，变成一个约束少变量多的对偶模型。

   对于约束很多的模型可以用行生成的方式来处理；对变量很多的模型可以采用列生成的思路来处理。

2. 例

   线性规划中一个经典问题的描述如下：

   • 某工厂有两种原料A、B，而且能用其生产两种产品： 1、生产第一种产品需要2个A和4个B，能够获利6；
     2、生产第二种产品需要3个A和2个B，能够获利4； 此时共有100个A和120个B，问该工厂最多获利多少？ 设变量为$(x_1,x_2)$，表示生产两种产品的数量。将上面的问题用数学表达式描述如下：

   $\text{max} \; 6x_1 + 4x_2 \\ s.t. \\ 2x_1 + 3x_2 \leq 100 \\ 4x_1 + 2x_2 \leq 120$

   • 工厂除了拿原料生产成产品卖掉这条出路外，还有一种方法是直接将原料卖掉。当然，不管是怎么做都要利益最大！也就是说，把原料卖掉赚的钱比生产成产品赚的钱多，才去会这样做。那么最低可以接受多少的价格呢？假设资源A和B的单价分别为：$y_1$和$y_2$，那么可以用数学表达式描述如下：

   $\text{min} \; 100y_1 + 120y_2 \\ s.t. \\ 2y_1 + 4y_2 \geq 6 \\ 3y_1 + 2y_2 \geq 4$

   这两个问题互为对偶问题,分别称之为原问题（P）和对偶问题（D）

3. 更一般的情况

   • 原问题

     $\text{min} \; c^T x \\ s.t. \\ Ax \geq b, \; x \geq 0$

     其中， $x \in \mathbb{R}^n$ 为决策变量， $A \in \mathbb{R}^{m \times n}$ 为约束系数矩阵， $c \in \mathbb{R}^n$ 为目标函数系数向量， $b \in \mathbb{R}^m$ 为约束右项。

   • 对原问题的主约束引入对偶变量，构造拉格朗日松弛函数（引入拉格朗日乘子），将约束条件“松开”或者引入到目标函数中，以便将问题转化为更易处理的形式。

     $\mathcal{L}(x,\mu)=c^Tx + \mu ^ T(b-Ax) = (c^T-\mu ^T A)x + \mu ^T b$

   • 该函数要求原问题的松弛，引入对偶变量 $\mu \geq 0$ ，这个拉格朗日函数将原问题的目标函数和约束结合在一起。

   • 为了求解原问题的松弛版本，我们需要最小化这个拉格朗日函数，这意味着我们要找到合适的 $x$ 使得 $\mathcal{L}$ 尽可能小。同时为了避免其趋于负无穷，要求 $(c^T-\mu ^T A) \geq 0$ ，显然 $x = 0$ 时使得拉格朗日函数最小化。

   • 由此函数只剩$\mu ^T b$，即对偶问题的目标函数，约束为$(c^T-\mu ^T A) \geq 0$，且$\mu \geq 0$。注意上述过程只对主约束引入对偶变量，而$x \geq 0$属于变量范围，不需要引入对偶变量。

   • 对偶问题

     $\text{max} \; b^Ty \\ s.t. \\ A^Ty \leq c, \; y \geq 0$