Resolvendo um problema de mínimos quadrados com restrições lineares em Python

Eu preciso resolver

\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}$

Eu acho que é um problema quadrático que deve ser solucionado com o CVXOPT , mas não sei como.

optimization python convex-optimization least-squares quadratic-programming tillsten
fonte

Espero que esta pergunta não seja muito específica para o compsci.

tillsten

Geoff Oxberry: Apenas uma curiosidade, mas por que você editou a parte linear? Eu acho que é uma parte bastante impotente da descrição do problema, a solução seria bem diferente para uma otimização de mínimos quadrados não lineares.

tillsten

Aliás, as outras edições são ótimas!

tillsten

Você pode resolver isso facilmente com seu próprio código de maneira muito eficiente. Não há necessidade de CVXOPT.

Royi 9/07/19

Respostas:

Eu escrevi uma resposta completa (abaixo da linha) antes de descobrir o CVXPY , que (como o CVX para MATLAB) faz todo o trabalho duro para você e tem um exemplo muito curto quase idêntico ao seu aqui . Você só precisa substituir a linha relevante por

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

Minha resposta antiga, fazendo da maneira mais difícil com o CVXOPT:

Seguindo a sugestão de Geoff de enquadrar sua função objetiva,

‖ 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$

Obviamente, todos os termos são escalares, então você pode transpor o terceiro e largar o último (como ele não depende de e, portanto, não muda, qual fornece um mínimo, embora seja necessário adicioná-lo novamente depois de resolver para obter o valor correto do seu objetivo) para obter Isso (incluindo suas restrições) tem a forma de um programa quadrático, conforme indicado em a documentação do CVXOPT aqui , onde também há código de exemplo para resolver esse problema. $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
fonte

Em vez do problema que você resolveu, resolva

\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}$

Esse problema é um problema de otimização diferenciável, convexo e não linear que pode ser resolvido no CVXOPT, IPOPT ou em qualquer outro solucionador de otimização convexo.

Geoff Oxberry
fonte