c++ - 使用 cgal 二次规划求解超定系统

Question

我想解决一个超定系统，Ax=b其中A是一个(m x n)矩阵（带有m>n），b是一个(m)向量并且x是未知数的向量。我还想用lband绑定解决方案ub。

给出以下程序： (QP)minimize transpose(x).D.x+transpose(c).x+c0subject to Ax⋛b,l≤x≤u

我想知道如何计算矩阵 D 和向量 c。因为矩阵 D 必须是对称的，所以我将其定义为D=transpose(A).A和。我的问题是：这种表示是否正确？如果不是，我应该如何定义 D 和 c？cc=-transpose(A).b

Answer 1

“解决”一个超定系统Ax = b通常意味着计算一个x使误差的欧几里得范数最小化的解决方案e(x) = ||Ax-b||。如果您有其他形式的线性约束，l <= x <= u那么您确实会得到一个二次程序：

min { 0.5*e(x)^2 } <=> min { 0.5*(Ax-b)'*(Ax-b) } 
               <=> min { 0.5*x'*A'*A*x -b'Ax + 0.5*b'b) }
               <=> min { 0.5*x'*A'*A*x -b'Ax }

受线性约束

l <= x <= u

因此，您可以将矩阵定义D为（均值）的一半：A'*AA'A transposed

D = 1/2*A'*A

和向量c来满足

c' = -b'*A => c = -A'*b

所以你的方法不正确，但它很接近！