解決使用CGAL二次規劃

Question

超定系統我要解決的形式Ax=b其中A是(m x n)矩陣的超定系統（具有m>n），b是(m)矢量和x是未知的向量。我也想用lb和ub來限制解決方案。

給予下面的程序： （QP）最小化transpose(x).D.x+transpose(c).x+c0受Ax⋛b,l≤x≤u

不知如何計算矩陣d和矢量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 

和矢量c滿足

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

所以你的做法是不正確的，但它是接近！