带边界约束的最小二乘问题最优性条件及求解技术问询

嘿，我来帮你梳理带边界约束的最小二乘问题的相关细节——先从基础的带线性约束的情况说起，再延伸到边界约束的场景：

首先看带线性等式约束的最小二乘问题，我们的目标是：
$$
\min_x ||Ax-b||^2
$$
$$
s.t.;;Cx=d
$$
用拉格朗日乘数法推导最优性条件后，会得到如下的分块线性方程组（也就是KKT系统）：
$$
\left[ \begin{array}{cc}
2A^TA & C^T \
C & 0 \end{array} \right]
\left[\begin{array}{c}
x\
z\end{array} \right]=
\left[\begin{array}{c}
2A^Tb\
d\end{array} \right],
$$
这里的$z$是对应线性等式约束的拉格朗日乘子向量。

要顺利解出这个系统，必须满足两个核心前提条件：

• 定义堆叠矩阵 $\bar{A}=
  \left[\begin{array}{c}
  A\
  C\end{array} \right]$，$\bar{A}$ 必须列满秩（也就是它的列向量线性无关）
• 约束矩阵$C$必须行满秩（也就是它的行向量线性无关）

现在如果给变量$x$加上上下界边界约束（比如 $l_i \leq x_i \leq u_i$，$i=1,2,...,n$），问题就变成了带边界约束的最小二乘问题，这时候的最优性条件就得考虑每个变量是否触碰到边界的情况，也就是完整的KKT条件：
对于每个变量分量$x_i$，需要同时满足梯度条件和互补松弛条件：

1. 梯度条件：$2A^T(Ax - b) + C^T z + \mu - \lambda = 0$
   其中$\mu$是对应下界约束$x \geq l$的拉格朗日乘子向量，$\lambda$是对应上界约束$x \leq u$的拉格朗日乘子向量
2. 互补松弛条件：
   • 若$x_i = l_i$，则$\mu_i \geq 0$ 且$\lambda_i = 0$
   • 若$x_i = u_i$，则$\lambda_i \geq 0$ 且$\mu_i = 0$
   • 若$l_i < x_i < u_i$，则$\mu_i = \lambda_i = 0$

针对这类问题，常用的求解方法有几种：

• 投影梯度法：每次迭代先计算无约束最小二乘的梯度下降步，然后将迭代点投影到边界约束和线性等式约束的可行域内，实现简单，适合大规模问题
• 活动集法：先猜测当前哪些边界约束是激活的（变量触碰到边界），把这些激活的边界转化为等式约束，求解带等式约束的最小二乘问题，再验证解是否满足最优性条件，不满足就更新活动集，循环迭代
• 内点法：通过引入对数障碍函数，把边界约束转化为目标函数的惩罚项，逐步减小障碍参数，求解一系列近似的无约束最小二乘问题，收敛速度快，适合中小规模的高精度求解

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