L1範數優化的線性化方法如何證明？

01-21

公式3中的EMR和EXT只是論文前文的一些矩陣乘積，請主要關註上一個公式的證明。另外根據公式3的理解，min y+z應該是指最小化y+z這個矩陣的所有元素之和。

對L1 norm如何線性化的理解最主要的是要想明白為什麼對單一元素的最小化，即 $min |x|$ 等價於

以下的線性規劃問題。

$egin{eqnarray} min y+z\ y-z=x\ y,zgeq 0 end{eqnarray}$

現在假設以上的線性規劃問題的最優解是 $y_0,z_0$ ,並且 $y_0>0,z_0>0$ ,這個時候，總可以找到一個很小的正數 $alpha$ 使得 $y_1=y_0-alpha geq 0, z_1=z_0-alpha geq 0$ 。而對於 $y_1,z_1$ 它們滿足以上線性規劃的所有約束，比如 $y_1-z_1=y_0-alpha-(z_0-alpha)=y_0-z_0=x$ ，但這組可行解卻具有比 $y_0,z_0$ 更小的目標函數值，即 $y_0+z_0-2alpha$ 。這就證明了 $y_0,z_0$ 並不是最優解，從而導出矛盾。所以這一段的結論就是對於以上的線性規劃問題，其最優解必須滿足要嗎y=0, 要嗎z=0，從而其最優目標值要嗎是x，要嗎是-x，即|x|。