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

Question

我想求解 Ax=b 形式的超定系统，其中 A 是一个 (m x n) 矩阵(带有 m>n)，b 是一个(m) vector ，x 是未知数的 vector 。我还想用 lb 和 ub 绑定(bind)解决方案。

给出以下程序:(QP)最小化 transpose(x).D.x+transpose(c).x+c0 subject to Ax⋛b,l≤x≤u

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

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'*A 的一半 ( A' 表示 A transposed ):

D = 1/2*A'*A

和 vector c满足

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

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