线性约束的松弛？

Question

当我们需要在正实半线上优化函数时，我们只有无约束的优化例程，我们使用y = exp(x)或y = x^2来映射到实线，并且仍然在对数或变量的(有符号)平方根上进行优化。

我们能否对线性约束做类似的事情，形式为Ax = b，其中，对于x是d维向量，A是(N,n)-shaped矩阵，b是长度为N的向量，定义约束？

Answer 1

虽然，正如Ervin Kalvelaglan所说，这并不总是一个好主意，但这里有一种方法。假设我们取A的奇异值分解，得到

A = U*S*V'
where if A is n x m
U is nxn orthogonal,
S is nxm, zero off the main diagonal, 
V is mxm orthogonal

计算奇异值分解不是一项微不足道的计算。

我们首先将S的元素清零，我们认为S的元素由于噪声而不为零--这可能是一件稍微微妙的事情。

然后我们可以找到一个解x~ to

A*x = b 

作为

x~ = V*pinv(S)*U'*b

(其中pinv( S )是S的伪逆，即用非零元素的乘法逆替换对角线的非零元素)

注意，x~是约束的最小二乘解，所以我们需要检查它是否足够接近真实的解，即Ax~足够接近b --另一个有点微妙的问题。如果x~不能很好地满足约束，您应该放弃:如果约束没有解决方案，那么优化也没有解决方案。

约束的任何其他解可以写为x= x~ + sum ci*Vi，其中Vi是对应于(现在)为零的S的条目的V的列。这里的ci是任意常量。因此，我们可以将变量更改为在优化过程中使用c[]，约束将自动得到满足。然而，这种变量的改变可能会让人有些厌烦！