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

12

Eu preciso resolver

minxAxb22,s.t.ixi=1,xi0,i.

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

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:

11

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,

Axb22=xTATbT,Axb=xTATAxbTAxxTAbbTb

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.xx

xTATAxbT(A+AT)x
David Ketcheson
fonte
4

Em vez do problema que você resolveu, resolva

minxAxb22,s.t.ixi=1,xi0,i.

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