优化问题(P')向(P)的归约证明及解的关系推导咨询
嘿，你用正负变量分解的思路完全找对方向了！咱们一步步把这个归约过程落地，同时理清两个问题解的对应关系：
首先先明确两个问题的形式：
原问题定义
- 问题(P)：
$$
\min _{\substack{x \geq 0 \ \sum_i x_i \leq 1}} \frac{1}{2} \lVert x-a \rVert^2
$$ - 问题(P')：
$$
\min _{\lVert x\rVert_1 \leq 1} \frac{1}{2} \lVert x-a \rVert^2
$$
第一步：变量替换与可行域的对应
对于问题(P')中的任意可行解 $x \in \mathbb{R}^n$，我们把每个分量拆成正部和负部：
$$x_i = x_i^+ - x_i^-, \quad 其中\ x_i^+ = \max(x_i,0),\ x_i^- = \max(-x_i,0)$$
显然 $x_i^+ \geq 0$，$x_i^- \geq 0$，且 $x_i^+ x_i^- = 0$（同一分量的正负部不会同时为正）。
现在构造一个2n维的新向量 $w$：
$$w = (x_1^+, x_2^+, ..., x_n^+, x_1^-, x_2^-, ..., x_n^-)$$
此时 $w$ 满足：
- $w \geq 0$（所有分量非负）；
- $\sum_{j=1}^{2n} w_j = \sum_{i=1}^n (x_i^+ + x_i^-) = \sum_{i=1}^n |x_i| = \lVert x \rVert_1 \leq 1$。
这正好符合问题(P)的约束条件！反过来，任意满足 $w \geq 0$ 且 $\sum w_j \leq 1$ 的2n维向量 $w$，对应 $x_i = w_i - w_{n+i}$（前n个分量是正部，后n个是负部），显然 $\lVert x \rVert_1 = \sum |w_i - w_{n+i}| \leq \sum (w_i + w_{n+i}) \leq 1$，是(P')的可行解。
第二步：目标函数的等价性
接下来看目标函数，我们先展开原问题(P')的目标：
$$
\lVert x - a \rVert^2 = \sum_{i=1}^n (x_i - a_i)^2 = \sum_{i=1}^n (x_i^+ - x_i^- - a_i)^2
$$
现在构造2n维向量 $b$：
$$b = (a_1, a_2, ..., a_n, -a_1, -a_2, ..., -a_n)$$
计算 $\lVert w - b \rVert^2$：
$$
\lVert w - b \rVert^2 = \sum_{i=1}^n (w_i - a_i)^2 + \sum_{i=1}^n (w_{n+i} + a_i)^2
$$
展开后对比原目标函数的展开式：
$$
\sum_{i=1}^n (x_i^+ - x_i^- - a_i)^2 = \lVert w - b \rVert^2 - 2\sum_{i=1}^n w_i w_{n+i} - \sum_{i=1}^n a_i^2
$$
这里的关键结论是：在最优解中，$w_i$ 和 $w_{n+i}$ 不会同时为正。原因很简单：如果某个分量 $w_i > 0$ 且 $w_{n+i} > 0$，我们可以同时减去一个小正数 $t$（不超过两者的最小值），得到新的 $w'$，此时 $\sum w'j$ 更小（仍满足约束），且目标函数值会下降（具体推导可以看下面的补充）。因此最优解中 $w_i w{n+i} = 0$，这时候原目标函数就变成：
$$
\frac{1}{2}\lVert x - a \rVert^2 = \frac{1}{2}\left(\lVert w - b \rVert^2 - \sum_{i=1}^n a_i^2\right)
$$
其中 $\sum a_i^2$ 是常数，不影响最小值的位置。因此最小化(P')的目标等价于最小化2n维版本的(P)目标。
第三步：解的对应关系
- 若 $w^$ 是2n维问题(P)（对应向量 $b$）的最优解，则原问题(P')的最优解 $x^$ 满足：
$$x^_i = w^i - w^*{n+i}, \quad i=1,2,...,n$$ - 反过来，若 $x^$ 是(P')的最优解，则对应的 $w^ = (x^{+}_1, ..., x^{+}_n, x^{-}_1, ..., x^{-}_n)$ 是2n维问题(P)的最优解。
补充：最优解中无同时正的正负部
假设存在某个 $i$ 使得 $w_i > 0$ 且 $w_{n+i} > 0$，取 $t = \min(w_i, w_{n+i})$，令 $w'i = w_i - t$，$w'{n+i} = w_{n+i} - t$，其他分量不变。此时：
- $\sum w'_j = \sum w_j - 2t \leq 1$，仍满足约束；
- 原目标函数的变化量为：
$$
\frac{1}{2}\left[(w'i - w'{n+i} - a_i)^2 - (w_i - w_{n+i} - a_i)^2\right] = 0
$$
但 $\lVert w' - b \rVert^2$ 的变化量为负（具体展开后可验证），结合目标函数的等价性，说明原 $w$ 不是最优解，矛盾。因此最优解中必然不存在同时为正的 $w_i$ 和 $w_{n+i}$。
备注：内容来源于stack exchange，提问作者Pipnap
