二次凸优化问题求解受阻：带线性约束的L2范数平方最小化问题

嗨，我来帮你一步步拆解这个问题，其实这个带单个线性约束的凸二次优化问题，通过KKT条件分情况讨论就能轻松理清啦～

首先先明确你的问题形式：

目标函数：$\min |x|^2$（$x$是$d$维向量）
约束条件：$Mx \leq b$，其中$M$是$d$维向量的转置（也就是$M$是$1 \times d$的行向量），$b$是标量

你写的梯度条件是对的，先回顾完整的KKT条件（因为这是凸优化问题，KKT条件是最优解的充要条件）：

1. 梯度为零：$\nabla_x L = 2x + \lambda M^T = 0$（$L$是拉格朗日函数，$\lambda \geq 0$是拉格朗日乘子）
2. 互补松弛：$\lambda(Mx - b) = 0$
3. 原约束满足：$Mx \leq b$
4. 乘子非负：$\lambda \geq 0$

接下来我们分核心情况讨论：

情况1：$\lambda = 0$ #

代入梯度条件可得$2x = 0$，即$x = 0$。
这时候需要验证是否满足原约束：$M \cdot 0 = 0 \leq b$。

• 如果$b \geq 0$，$x=0$是可行解，而且目标函数值$|x|^2=0$是理论最小值（因为L2范数平方非负），所以**$x=0$就是最优解**。
• 如果$b < 0$，$x=0$不满足约束，这种情况不成立，我们看第二种情况。

情况2：$\lambda > 0$ #

根据互补松弛条件，此时必须满足$Mx = b$（因为$\lambda \neq 0$，所以括号里的项必须为0）。
从梯度条件$2x + \lambda M^T = 0$，我们可以解出$x = -\frac{\lambda}{2} M^T$。
现在把$x$代入约束$Mx = b$：
$$
M \cdot \left(-\frac{\lambda}{2} M^T\right) = b
$$
因为$M$是$1 \times d$行向量，$M M^T = |M|^{2$（$M$的L2范数平方，显然$|M|}2 > 0$，除非$M$是零向量，我们后面单独说），所以上式可以简化为：
$$
-\frac{\lambda}{2} |M|^2 = b \implies \lambda = -\frac{2b}{|M|^2}
$$
因为$\lambda > 0$，所以需要$-\frac{2b}{|M|^2} > 0$，结合$|M|^2 > 0$，可得**$b < 0$**（这也和情况1里$b<0$时$x=0$不可行对应上了）。

把$\lambda$代回$x$的表达式，得到：
$$
x = -\frac{1}{2} \cdot \left(-\frac{2b}{|M|^2}\right) M^T = \frac{b}{|M|^2} M^T
$$
此时验证约束：$Mx = M \cdot \frac{b}{|M|^2} M^T = \frac{b}{|M|^2} \cdot |M|^2 = b$，刚好满足$Mx = b \leq b$，符合约束要求。
这时候的目标函数值是$|x|^2 = \left|\frac{b}{|M|^2} M^T\right|2 = \frac{b^2}{|M|2}$，这是当前可行域内的最小值。

特殊情况：$M = 0$（零行向量） #

这时候约束变成$0 \leq b$：

• 如果$b \geq 0$，所有$x$都可行，最优解还是$x=0$（目标函数最小）；
• 如果$b < 0$，约束$0 \leq b$永远不成立，问题无解。

总结一下：

• 当$b \geq 0$时，最优解是$x=0$；
• 当$b < 0$且$M \neq 0$时，最优解是$x = \frac{b}{|M|^2} M^T$；
• 当$b < 0$且$M = 0$时，问题无解。

备注：内容来源于stack exchange，提问作者Aditi Gupta