überbestimmung Verwendung CGAL Quadratic Programming

Question

Ich möchte ein überbestimmtes System von der Form zu lösen, wo Ax=bA eine (m x n) Matrix (mit m>n), b ist ein (m)x Vektor und der Vektor der Unbekannten. Ich möchte auch die Lösung mit und ub binden.

Geben Sie das folgende Programm: (QP) minimieren transpose(x).D.x+transpose(c).x+c0 unterliegen Ax⋛b,l≤x≤u

Ich frage mich, wie die Matrix D und den Vektor c zu berechnen. Da die Matrix D symmetrisch sein muss, habe ich sie als D=transpose(A).A und c als c=-transpose(A).b definiert. Meine Frage ist: Ist diese Darstellung korrekt? Wenn nein, wie soll ich D und c definieren?

Answer 1

"Solving" ein überbestimmtes System Ax = b bedeutet in der Regel die Berechnung einer Lösung x, die die euklidische Norm des Fehlers e(x) = ||Ax-b|| minimiert. Wenn Sie l <= x <= u zusätzliche lineare Zwänge der Form haben dann in der Tat erhalten Sie ein quadratisches Programm:

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 } 

unter den linearen Bedingungen

l <= x <= u 

So können Sie die Matrix definieren D sein Hälfte die A'*A (A' Mittel A transposed):

D = 1/2*A'*A 

und Vektor c zu erfüllen

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

Also Ihr Ansatz nicht korrekt ist, aber es war knapp!