放宽线性约束? [英] Relaxation of linear constraints?

问题描述

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

When we need to optimize a function on the positive real half-line, and we only have non-constraints optimization routines, we use y = exp(x), or y = x^2 to map to the real line and still optimize on the log or the (signed) square root of the variable.

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

Can we do something similar for linear constraints, of the form Ax = b where, for x a d-dimensional vector, A is a (N,n)-shaped matrix and b is a vector of length N, defining the constraints ?

推荐答案

虽然正如 Ervin Kalvelaglan 所说，这并不总是一个好主意，但这里有一种方法可以做到.假设我们取 A 的 SVD，得到

While, as Ervin Kalvelaglan says this is not always a good idea, here is one way to do it. Suppose we take the SVD of A, getting

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

计算 SVD 不是一项简单的计算.

Computing the SVD is not a trivial computation.

我们首先将 S 的元素归零，因为噪声我们认为这些元素不是零——这可能是一件稍微微妙的事情.

We first zero out the elements of S which we think are non-zero just due to noise -- which can be a slightly delicate thing to do.

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

Then we can find one solution x~ to

A*x = b 

作为

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

(其中 pinv(S) 是 S 的伪逆，即将对角线上的非零元素替换为它们的乘法逆)

(where pinv(S) is the pseudo inverse of S, ie replace the non zero elements of the diagonal by their multiplicative inverses)

请注意，x~ 是约束的最小二乘解，因此我们需要检查它是否足够接近成为真正的解，即 Ax~ 是否足够接近 b —— 另一个有点微妙的事情.如果 x~ 没有足够接近地满足约束，你应该放弃:如果约束没有解决方案，优化也没有.

Note that x~ is a least squares solution to the constraints, so we need to check that it is close enough to being a real solution, ie that Ax~ is close enough to b -- another somewhat delicate thing. If x~ doesn't satisfy the constraints closely enough you should give up: if the constraints have no solution neither does the optimisation.

可以写出任何其他约束的解决方案x = x~ + 和 c[i]*V[i]其中 V[i] 是 V 的列，对应于(现在)为零的 S 条目.这里的 c[i] 是任意常数.因此，我们可以在优化中将变量更改为使用 c[]，并且约束将自动满足.然而，这种变量的变化可能有点令人厌烦！

Any other solution to the constraints can be written x = x~ + sum c[i]*V[i] where the V[i] are the columns of V corresponding to entries of S that are (now) zero. Here the c[i] are arbitrary constants. So we can change variables to using the c[] in the optimisation, and the constraints will be automatically satisfied. However this change of variables could be somewhat irksome!

这篇关于放宽线性约束?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！