Programação quadrática quando a matriz não é positiva definida

8

http://cran.r-project.org/web/packages/quadprog/quadprog.pdf

O pacote R quadprogparece ser capaz de resolver o problema de programação quadrática somente quando a matriz é definida positivamente.D

No entanto, há um caso em que a matriz não é positiva definida. tal comoD

min(x2+y2−6xy)subject tox+y≤1,3x+y≤1.5,x,y≥0.

Como posso resolver esse tipo de problema?

r optimization user67275
fonte
O problema pode estar relacionado ao fato de que, se o quadrático não for definido positivamente, ele não terá um mínimo local. Nesse caso, ainda deve haver um mínimo global, já que a região é limitada.
Glen_b -Reinstala Monica
1
Se não for PSD, o problema não será convexo. Qualquer algoritmo de descida de gradiente o levará a um mínimo local, mais ou menos, dependendo do ponto de partida. Talvez você precise criar uma heurística para decidir quando parar a pesquisa. D
user603
4
Não é tão difícil decidir em qual segmento da fronteira o mínimo se encontra. Então, dada essa restrição, é fácil defini-lo como um problema que tem um mínimo local ... mas a sugestão do @ user603 de usar um algoritmo de minimização padrão como descida em gradiente pode ser bastante útil como uma abordagem geral.
Glen_b -Reinstala Monica

Respostas:

4

Existem rotinas de otimização especificamente para otimização local ou global de problemas de programação quadrática, independentemente de a função objetivo ser convexa.

BARON é um otimizador global de uso geral que pode lidar e tirar proveito de problemas de programação quadrática, convexos ou não.

O CPLEX possui um solucionador de programação quadrática que pode ser chamado com solutiontarget = 2 para encontrar um ótimo local ou = 3 para encontrar um ótimo global. No MATLAB, isso pode ser chamado com cplexqp.

Otimizadores locais de uso geral que podem lidar com restrições lineares também podem ser usados ​​para encontrar um ótimo local. Um exemplo em R é https://cran.r-project.org/web/packages/trust/trust.pdf . Os otimizadores para R estão listados em https://cran.r-project.org/web/views/Optimization.html .

No MATLAB, a função quadprog na caixa de ferramentas de otimização pode ser usada para encontrar um ótimo local.

Em Julia, há uma variedade de otimizadores disponíveis.

O algoritmo de descida de gradiente "Qualquer" pode não levar você a nada, muito menos a lidar com restrições. Use um pacote desenvolvido por alguém que saiba o que está fazendo.

O problema de exemplo fornecido é facilmente resolvido com a otimização global comprovável. Talvez com a passagem de mais de 2 anos não seja mais necessário, ou talvez seja um exemplo que nunca foi, mas, em qualquer caso, o ideal global esteja em x = 0,321429, y = 0,535714

Mark L. Stone
fonte
1
+1. Os métodos multiplicadores de Lagrange para resolver esses problemas são rotineiramente ensinados nas aulas de cálculo do segundo ano. Com eles, obtém-se facilmente e (que é atingido ao longo do limite ). x=9/28y=15/283x+y=3/2
whuber
1

Você pode construir uma solução alternativa usando nearPDdo Matrixpacote assim:
nearPD(D)$mat.

nearPD calcula a matriz definida positiva mais próxima.

vonjd
fonte
2
+1 porque é uma solução aproximada relativamente direta . (não me lembro de ter visto essa pergunta, caso contrário, eu mesma a faria em um comentário.) Dito isso, essencialmente se define os valores próprios negativos como zero ao usar essa técnica e depois reconstrói a matriz original; se os modos de variação correspondentes forem significativos, essa aproximação poderá ser seriamente falha.
usεr11852
3
Concorde com a última frase no comentário anterior. Essa é uma excelente técnica a ser usada, desde que você não se importe nem um pouco se sua resposta está correta, ou mesmo no estádio, cidade ou estado certo. Se a sua matriz "Hessiana" objetiva estiver dentro da "tolerância", longe de ser definida positivamente, essa abordagem pode ser realmente razoável, caso contrário, não.
Mark L. Stone