带ℓ₁单位球约束的二次优化问题是否存在闭式解？

嘿，这个问题我刚好有研究过，咱们一步步拆解来看～

首先明确你的问题：给定向量$w \in \mathbb R^{M}$和对称半正定矩阵$B \in \mathbb R^{M \times M}$，求解凸优化问题：
$$\begin{array}{ll} \text{minimize} & (x-w)^{T}B(x-w)\ \text{subject to} & |x|_{1} \leq 1\end{array}$$

你提到的“先解无约束二次最小化，再投影到ℓ₁球”的思路，只有在特殊情况下成立，咱们先分析这个思路的局限性，再给出通用的高效解法。

你的初始思路的局限性 #

无约束情况下，目标函数$(x-w)^T B(x-w)$的最小值点：

• 如果$B$是正定矩阵，无约束解就是$x=w$；
• 如果$B$是半正定矩阵，解是$w$加上$B$零空间中的任意向量。

这时候：

• 若$w$本身就在ℓ₁单位球内（$|w|_1 \leq 1$），那无约束解就是原问题的最优解，无需投影；
• 若$w$不在ℓ₁球内，直接把$w$投影到ℓ₁球不一定是最优解——因为目标函数是$B$加权的平方距离，其“等高线”是椭球面而非球面，欧几里得意义下的投影点未必能让加权距离最小。

举个简单例子：假设$B$是对角矩阵，其中一个对角元远大于其他元素，这时候目标函数会对该维度的误差惩罚更重，最优解会优先保证这个维度的$x_i$尽可能接近$w_i$，而不是单纯按ℓ₁投影的规则来缩放元素。

通用高效解法 #

因为原问题是凸优化问题，结合你已经能高效执行ℓ₁球投影的条件，下面两种方法非常适合：

1. 近端梯度法（Proximal Gradient Method） #

把原问题拆分为光滑部分和非光滑约束部分：

• 光滑目标：$f(x) = (x-w)^T B(x-w)$，其梯度为$\nabla f(x) = 2B(x-w)$
• 非光滑约束的指示函数：$g(x) = I_{|x|_1 \leq 1}(x)$（当$x$在ℓ₁球内时为0，否则为无穷大）

近端梯度的迭代步骤很直观：
$$x_{k+1} = \text{prox}_{t_k g}\left(x_k - t_k \nabla f(x_k)\right)$$
其中：

• $\text{prox}_{t_k g}(\cdot)$就是向ℓ₁单位球的投影操作，你已经能高效实现；
• 步长$t_k$可以取$\frac{1}{\lambda_{\text{max}}(B)}$（因为$f$的Lipschitz常数是$2\lambda_{\text{max}}(B)$，$\lambda_{\text{max}}(B)$是$B$的最大特征值），也可以用线搜索来动态调整步长加速收敛。

2. ADMM算法 #

如果$B$的逆矩阵容易计算（比如$B$是对角矩阵、稀疏矩阵），ADMM的效率会很高。我们把问题改写为：
$$\begin{array}{ll} \text{minimize} & (x-w)^T B(x-w) + I_{|z|_1 \leq 1}(z)\ \text{subject to} & x = z\end{array}$$

迭代步骤如下：

1. x-update：求解二次闭式解
   $$x_{k+1} = (B + \rho I)^{-1}\left(Bw + \rho(z_k - u_k)\right)$$
   其中$\rho$是ADMM的惩罚参数，$u_k$是对偶变量。
2. z-update：直接调用你已有的ℓ₁球投影
   $$z_{k+1} = \text{proj}_{|z|1 \leq 1}(x{k+1} + u_k)$$
3. u-update：更新对偶变量
   $$u_{k+1} = u_k + x_{k+1} - z_{k+1}$$

额外提示：ℓ₁球投影的闭式解 #

刚好补充下ℓ₁单位球投影的实现逻辑（如果你还没完全敲定）：
假设输入向量为$v$：

• 如果$|v|_1 \leq 1$，投影结果就是$v$本身；
• 如果$|v|_1 > 1$，需要找到一个阈值$\tau > 0$，对每个元素做软阈值处理：$x_i = \text{sign}(v_i) \max(|v_i| - \tau, 0)$，使得$|x|_1 = 1$。这个阈值可以通过排序$|v_i|$后用线性扫描找到，时间复杂度为$O(M \log M)$。

总结 #

• 当$B=I$（单位矩阵）时，你的初始思路（先取$x=w$再投影）是对的；
• 当$B$是一般对称半正定矩阵时，必须用近端梯度或ADMM这类结合加权二次项和投影的迭代方法，才能得到最优解。

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