Por que o SQP é melhor que o Augranged Lagrangian para programação não-linear?

No relatório técnico sobre Galahad [1], os autores declaram, no contexto de problemas gerais de programação não linear,

Em nossa opinião, nunca houve muita dúvida de que os métodos SQP [programação quadrática sequencial] seriam mais bem-sucedidos [do que os métodos Lagrangeanos Aumentados] a longo prazo ...

Qual poderia ser a base para essa crença? Ou seja, existem resultados teóricos que sugerem que os métodos SQP devam ser mais rápidos / confiáveis do que os métodos Lagrangianos Aumentados?

[1] Galahad, uma biblioteca de pacotes Fortran 90 seguros para threads para otimização não linear em larga escala, por Gould, Orban e Toint

nonlinear-programming cjordan1
fonte

Respostas:

Os métodos SQP exigem que o objetivo seja diferenciável duas vezes (cf https://en.m.wikipedia.org/wiki/Sequential_quadratic_programming ), enquanto os Lagrangianos aumentados funcionam mesmo quando o objetivo não é diferenciável (daí o seu ressurgimento recente na comunidade de processamento de imagens, cf ftp: //arachne.math.ucla.edu/pub/camreport/cam09-05.pdf )

Não conheço o software galahad, mas se supostamente resolver problemas de otimização diferenciáveis, provavelmente será muito melhor usando um método que permita diferenciar a função objetivo.

dranxo
fonte

Não é verdade que o SQP exija duas funções objetivas diferenciáveis. Você pode simplesmente obter um método que tenha uma menor taxa de convergência se a função objetivo tiver menos diferenciabilidade, mas isso é exatamente o mesmo que nos métodos Lagrangianos aumentados.

Wolfgang Bangerth

Em termos de iterações externas, o SQP deve vencer porque inclui informações de segunda derivada, enquanto métodos lagrangianos aumentados, como o ADMM, não.

No entanto, lembre-se de que cada iteração desses métodos envolve a solução de um sistema linear; portanto, para fazer uma comparação justa, é necessário levar em consideração a facilidade com que esses sistemas são resolvidos.

Para métodos lagrangianos aumentados (alternados), a cada iteração que você está resolvendo algo como, onde é um operador direto direto da função objetivo que é conhecida e geralmente mais fácil de lidar ou pré-condição , e é o parâmetro de penalidade. (por exemplo, seu problema é

(A^{T} A + ρ I) x = b,

$(A^TA + \rho I)x = b,$

A

$A$

ρ

$\rho$

min_{x} | | A x - b | |^{2}

$\min_x ||Ax-b||^2$ sujeito a algumas regularizações e restrições).

Para métodos SQP, você está resolvendo algo como que

H x = g,

$Hx = g,$

H

$H$ é o hessiano (ou aproximação do mesmo) que geralmente só está disponível implicitamente em termos de ação em vetores

é o gradiente. O Hessian contém não apenas

g

$g$

A

$A$ , mas também uma combinação de outras matrizes e inversos de matrizes provenientes da linearização das restrições e da regularização.

Pré-condicionar Hessianos é um negócio bastante complicado e é muito menos estudado do que pré-condicionar problemas futuros. Um método padrão é aproximar o inverso de Hessian com L-BFGS, mas isso é de eficácia limitada quando o inverso de Hessian é alto. Outro método popular é aproximar o Hessian como uma soma de uma matriz de baixo escalão mais uma matriz fácil de inverter, mas isso também tem eficácia limitada para problemas difíceis. Outras técnicas populares de estimativa hessiana são baseadas em aproximações esparsas, mas os problemas de continuum geralmente têm hessianos que têm aproximações esparsas ruins.

Nick Alger
fonte

+1, embora eu queira advertir contra declarações gerais (com as quais não quero dizer especificamente esta resposta). Por exemplo, na otimização restrita ao PDE, a aplicação de

geralmente envolve a resolução de um PDE não linear, enquanto

pode ser aplicado resolvendo dois PDEs lineares - que podem ser significativamente mais baratos (e mais fáceis de pré-condicionar) se o PDE original for desagradável.

A

$A$

H

$H$

Christian Clason

Portanto,

pode ser aplicado resolvendo dois PDEs, mas para aplicar o

você precisa resolver 2 PDEs por iteração kryolv no seu solucionador. Por outro lado,

é um operador de encaminhamento, por isso geralmente não envolve nenhuma solução de PDE. Normalmente, na verdade, se conhece a matriz

explicitamente, por exemplo, um estêncil de diferença finita de 5 pontos em uma malha. Precondicionadores para

pode ser usado para precondicionadores compilação para

, mas é mais difícil usá-los para pré-condição

H

$H$

H^{- 1}

$H^{-1}$

A

$A$

A

$A$

A

$A$

A^{T} A + ρ I

$A^TA + \rho I$

H

$H$

Nick Alger

A

$A$

A

$A$

A^{T}

$A^T$

min_{q, u} \frac{1}{2} | | C u - y | |^{2} + \frac{α}{2} | | R q | |^{2}

$\min_{q,u} \frac{1}{2}||Cu - y||^2 + \frac{\alpha}{2}||Rq||^2$

A u = q

$Au=q$

H = A^{- T} C^{T} C A^{- 1} + α R^{T} R

$H = A^{-T}C^TCA^{-1} + \alpha R^T R$

H

$H$

H^{- 1}

$H^{-1}$

S (q) = u

$S(q) = u$

S

$S$

q

$q$

u

$u$

- \nabla \cdot (q \nabla u) = f

$-\nabla\cdot(q\nabla u) = f$