Rozwiązywanie problemu najmniejszych kwadratów z ograniczeniami liniowymi w Pythonie

Muszę rozwiązać

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^2_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

Myślę , że to kwadratowy problem, który powinien być rozwiązany za pomocą CVXOPT , ale nie potrafię zrozumieć, jak to zrobić.

— tillsten
źródło

Mam nadzieję, że to pytanie nie jest zbyt szczegółowe dla compsci.

— tillsten

Geoff Oxberry: Ciekawostka, ale dlaczego edytowałeś część liniową? Myślę, że jest to dość bezsilna część opisu problemu, rozwiązanie byłoby zupełnie inne w przypadku nieliniowej optymalizacji metodą najmniejszych kwadratów.

— tillsten

Przy okazji, inne zmiany są świetne!

— tillsten

Możesz to łatwo rozwiązać za pomocą własnego kodu w bardzo wydajny sposób. Nie ma potrzeby CVXOPT.

— Royi,

Odpowiedzi:

Napisałem pełną odpowiedź (poniżej linii) przed odkryciem CVXPY , który (podobnie jak CVX dla MATLAB) robi dla ciebie wszystkie trudne rzeczy i ma bardzo krótki przykład prawie identyczny z twoim tutaj . Trzeba tylko zastąpić odpowiednią linię

 p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)])

Moja stara odpowiedź: robić to trudniej z CVXOPT:

Podążając za sugestią Geoffa, aby wyrównać, daje się funkcja celu

‖ A x - b ‖_{2}^{2} = ⟨ x^{T} A^{T} - b^{T}, A x - b ⟩ = x^{T} A^{T} A x - b^{T} A x - x^{T} A b - b^{T} b

$\|Ax-b\|^2_2 = \langle x^TA^T - b^T,Ax-b\rangle = x^TA^TAx - b^TAx - x^TAb - b^Tb$

Oczywiście wszystkie terminy są skalarne, więc możesz transponować trzeci i upuścić ostatni (ponieważ nie zależy to od a zatem nie zmieni się, co daje ci minimum, chociaż będziesz musiał go dodać z powrotem in po rozwiązaniu w celu uzyskania prawidłowej wartości celu), aby uzyskać To (wraz z ograniczeniami) ma postać programu kwadratowego, jak podano w dokumentacja CVXOPT tutaj , w której znajduje się również przykładowy kod do rozwiązania takiego problemu. $x$ $x$

x^{T} A^{T} A x - b^{T} (A + A^{T}) x

$x^TA^TAx - b^T(A + A^T)x$

— David Ketcheson
źródło

Zamiast problemu, który rozwiązałeś, rozwiąż

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^{2}_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

Ten problem jest rozróżnialnym, wypukłym, nieliniowym problemem optymalizacji, który można rozwiązać w CVXOPT, IPOPT lub dowolnym innym wypukłym rozwiązaniu optymalizacyjnym.

— Geoff Oxberry
źródło