线性化技巧：绝对值变量的线性化

1. 问题

以方述诚老师课件中的案例为例：
$$\begin{gathered} max3x_1-2x_2-4|x_3| \\ s.t.-x_1+2x_2\le -5 \\ 3x_2-x_3\ge 6 \\ 2x_1+x_3=12 \\ {x}_1,x_2\ge 0 \end{gathered}$$

$x_3$是一个自由变量，且在目标函数中它是以绝对值的形式存在，如果我们要将该模型转化成标准型，首先要做的就是将$x_3$线性化。

2. 线性化

对于每一个数字$x$，我们都可以将它拆成正的个数$x^{+}$和负的个数$x^{-}$，并将其表示为$x^{+}-x^{-}$（正的个数 - 负的个数），举个例子：

• 5：正的个数是5，负的个数是0，5-0=5；
• -5：正的个数是0，负的个数是5，0-5=-5。

直觉上十分合理对吧（intuition是方老师第一节课反复强调的重点），我们用数学表达式来表达上述思想。

$x_i\in R$

$$x_i^{+}=\{\begin{array}{l}{x}_i,if{x}_i\ge 0\\ 0,otherwise\end{array}$$

$$x_i^{-}=\{\begin{array}{l}0,if{x}_i\ge 0\\ -x_i,otherwise\end{array}$$

$x_i=x_i^{+}-x_i^{-}$
$x_i^{+}\times x_i^{-}=0$

（很多教材和文章里直接省去了这个约束，其实是不对的，待会儿后面讲。）

$x_i^{+},x_i^{-}\ge 0$

3. 缺少$x_i^{+}\times x_i^{-}=0$ 有什么问题

$x_i^{+}\times x_i^{-}=0$ 该约束本质保证的是$x_i^{+}$ 和$x_i^{-}$ 至少有一个为0，如果没有该约束，5除了表示为5-0以外，还可以表示为6-1、7-2等等。也就是会使得原来只有一个解的问题，变成具有很多个新的解的问题。

4. 延伸思考

上述问题中的$|x|$是一个“V”字型的凸函数，它可以求极小值。如果要求$max|x|$ 那就unbounded了。

5. 参考文献

1. Linear Programming