Métodos baseados em Newton na otimização vs. sistemas de resolução de equações não lineares

Pedi esclarecimentos sobre uma pergunta recente sobre o minpack e recebi o seguinte comentário:

Qualquer sistema de equações é equivalente a um problema de otimização, e é por isso que os métodos baseados em Newton na otimização se parecem muito com os métodos baseados em Newton para resolver sistemas de equações não lineares.

O que me confunde sobre esse comentário (e opiniões negativas relacionadas sobre solucionadores de mínimos quadrados não-lineares especializados como minpack) pode ser melhor explicado no exemplo do método do gradiente conjugado . Este método é aplicável aos sistemas $Ax=b$ com um simétrica definida positiva matriz $A$ . Também poderia ser usado para resolver o problema geral dos mínimos quadrados $\operatorname{min}_x||Ax-b||^2$ para uma matriz arbitrária $A$ , mas não é recomendado. Uma explicação por que não devemos fazer isso é que o número de condição do sistema aumentaria significativamente.

Mas se transformar um sistema de equações em um problema de otimização é considerado problemático mesmo para o caso linear, por que deveria ser menos problemático para o caso geral? Parece estar de alguma forma relacionado ao uso de um algoritmo de otimização de ponta, em vez de usar um solucionador de mínimos quadrados não-linear ligeiramente envelhecido. Mas os problemas relacionados ao descarte de informações e ao aumento do número de condições do sistema são relativamente independentes do algoritmo de otimização realmente usado?

optimization least-squares Thomas Klimpel
fonte

Respostas:

Como uma das minhas respostas foi citada, tentarei esclarecer por que sugeri o uso do IPOPT em vez do MINPACK.

Minhas objeções ao uso do MINPACK não têm nada a ver com os algoritmos que o MINPACK usa e tudo a ver com sua implementação. Minha principal objeção é que o software remonta a 1980 e foi atualizado pela última vez em 1999. Jorge Moré está aposentado; Duvido que ele ou qualquer um dos outros autores do software mantenha o controle sobre ele, e não há nenhuma equipe de pessoas que o apóie ativamente. A única documentação que posso encontrar no software é o relatório técnico original de Argonne de 1980, escrito por Jorge Moré e os outros autores do MINPACK. (Os capítulos 1-3 podem ser encontrados aqui e o capítulo 4 pode ser encontrado aqui.) Depois de pesquisar o código-fonte do MINPACK e ler a documentação (os PDFs são imagens digitalizadas e não podem ser pesquisadas), não vejo opções para acomodar restrições. Como o pôster original do problema de quadrados mínimos não lineares queria resolver um problema de quadrados mínimos não lineares restrito, o MINPACK nem sequer resolveria esse problema.

Se você olhar para a lista de discussão IPOPT, alguns usuários indicam que o desempenho do pacote em problemas de mínimos quadrados não lineares (NLS) é misto em relação aos algoritmos de Levenberg-Marquardt e algoritmos NLS mais especializados (veja aqui , aqui e aqui ). O desempenho do IPOPT em relação aos algoritmos NLS depende, é claro, do problema. Dado o feedback do usuário, o IPOPT parece ser uma recomendação razoável em relação aos algoritmos NLS.

No entanto, você enfatiza que os algoritmos NLS devem ser investigados. Concordo. Eu apenas acho que um pacote mais moderno que o MINPACK deve ser usado porque acredito que ele terá um desempenho melhor, será mais utilizável e terá suporte. Ceres parece ser um pacote candidato interessante, mas não pode lidar com problemas restritos no momento. TAOfuncionaria em problemas de mínimos quadrados com restrição de caixa, embora não implemente o clássico Levenberg-Marquardt, mas implemente um algoritmo sem derivadas. Um algoritmo livre de derivado provavelmente funcionaria bem para problemas de grande escala, mas eu não o usaria para problemas de pequena escala. Não consegui encontrar outros pacotes que inspirassem muita confiança em sua engenharia de software. Por exemplo, o GALAHAD parece não usar controle de versão ou qualquer teste automatizado, à primeira vista. O MINPACK também não parece fazer essas coisas. Se você tem experiência com o MINPACK ou recomendações sobre um software melhor, eu sou todo ouvidos.

Com tudo isso em mente, voltando à citação do meu comentário:

Qualquer sistema de equações é equivalente a um problema de otimização, e é por isso que os métodos baseados em Newton na otimização se parecem muito com os métodos baseados em Newton para resolver sistemas de equações não lineares.

Um comentário melhor provavelmente é algo para o efeito de:

$n$ $n$ $g(x) = 0$

Esta afirmação vale mesmo para resolver sistemas de equações sob restrições. Não conheço nenhum algoritmo que seja considerado "solucionador de equações" para o caso em que existem restrições nas variáveis. A abordagem comum que conheço, talvez com icterícia por vários semestres de cursos de otimização e pesquisa em um laboratório de otimização, é incorporar as restrições no sistema de equações em uma formulação de otimização. Se você tentasse usar as restrições em um esquema semelhante a Newton-Raphson para resolver equações, provavelmente terminaria com um gradiente projetado ou um método de região de confiança projetada, como os métodos usados na otimização restrita.

Geoff Oxberry
fonte

Eu tenho experiência com o MINPACK. É bom o suficiente como método local. Gosto que os critérios de parada funcionem bem sem ajustes. Eu sei que a coisa com as restrições pode ser irritante, especialmente porque não seria uma grande mudança no próprio algoritmo. Eu até conheço implementações LM que oferecem limites para variáveis e restrições lineares gerais, mas essas implementações não são muito mais novas que o próprio MINPACK e não me preocupei em avaliá-las.

Thomas Klimpel

g (x) = 0

$g(x)=0$

‖ g (x) ‖^{2}

$\lVert g(x) \rVert^2$

@JedBrown: Eu deveria mudar o idioma. Na minha opinião, a otimização sem derivativos (DFO) é preferível apenas quando as avaliações de funções são muito caras. Por alguma razão, o caso seminal que vem à mente é quando o objetivo envolve resolver um PDE, e foi por isso que eu disse "em larga escala" (é claro, para mim, em otimização, "PDE em larga escala" significa algo diferente de para você, que resolve PDEs em paralelo regularmente). Quando penso em "resolver equações com restrições", o problema que tenho em mente é . (continuação)

g (x) = 0, x \in S, S \subset R^{n}, S \neq R^{n}

$g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$

Geoff Oxberry

@JedBrown: Uma maneira padrão de resolver esse problema é resolver . Pode haver outras maneiras, mas não conheço nenhuma. Não estou sugerindo que se descarte ; mínimos com valores de função objetivo diferentes de zero claramente não resolvem o sistema de equações que está sendo resolvido. No caso não-convexo, são necessários métodos de otimização global para certificar a existência ou inexistência de soluções. Eu não tenho muita experiência com desigualdades variacionais, então não está claro imediatamente para onde os VIs entram em cena aqui, especialmente porque não é necessariamente um cone.

min_{x \in S} ‖ g (x) ‖^{2}

$\min_{x \in S} \|g(x)\|^2$

g (x) = 0

$g(x) = 0$

S

$S$

Geoff Oxberry

Então, você ainda precisa ser capaz de definir com precisão o que entende por uma solução que encontra-se no limite do . VIs, muitas vezes escritos como uma formulação de complementaridade, fazem exatamente isso. Eu tenho a opinião oposta sobre livre de derivativos, especialmente quando o espaço de design é grande. Se o objetivo envolve uma solução dispendiosa de PDE, considero isso um requisito que tenhamos um anexo para que possamos usar gradientes para explorar o espaço do design. Um adjunto PDE custa apenas um pequeno múltiplo de uma resolução direta, independentemente da dimensão do espaço. Isso impõe requisitos extras à suavidade do modelo.

S

$S$

Jed Brown

Se um determinado sistema não linear é a condição de otimização de primeira ordem para um problema de otimização, geralmente podemos produzir um algoritmo mais robusto usando essas informações. Por exemplo, considere a equação

f (x) = x^{2} - \exp (- 4 (x - 2)^{2}) [click for Wolfram Alpha]

$f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$

Trama do objetivo original

Isso claramente tem um mínimo único e esperamos que nosso método de otimização o encontre independentemente do ponto de partida. Mas se olharmos apenas para as condições de otimização de primeira ordem, estaremos procurando uma solução de [Wolfram Alpha] $x$ $\nabla f(x) = 0$

gradiente

que tem uma solução exclusiva, mas muitos métodos de busca de raiz podem ficar presos no mínimo local.

Se reformularmos um novo problema de otimização para minimizar a norma do gradiente ao quadrado, estamos procurando um mínimo global de [Wolfram Alpha] que possui vários mínimos locais. $x$ $\lVert\nabla f(x)\rVert^2$

insira a descrição da imagem aqui

Para resumir, começamos com um problema de otimização que possuía uma solução única que poderíamos garantir que um método encontraria. Nós reformulamos como um problema de busca não linear de raiz que tinha uma solução única que poderíamos identificar localmente, mas um método de busca de raiz (como Newton) pode estagnar antes de alcançá-lo. Em seguida, reformulamos o problema de localização raiz como um problema de otimização que tinha várias soluções locais (nenhuma medida local pode ser usada para identificar que não estamos no mínimo global).

Em geral, sempre que convertemos um problema de otimização em busca de raiz ou vice-versa, tornamos os métodos disponíveis e as garantias de convergência associadas mais fracos. A mecânica real dos métodos geralmente é muito semelhante, portanto é possível reutilizar muito código entre solucionadores não lineares e otimização.

Jed Brown
fonte

Jed, esses links WA não vão exatamente para o que você diz que eles fazem. Os parênteses estão sendo ignorados ou transmitidos incorretamente no URL.

Bill Barth

Estranho, os links funcionam para mim. Poderia depender do navegador da web? Alguma sugestão para uma maneira alternativa de apresentar isso?

precisa

Não tenho certeza. Cortar e colar o link reformatado de uma guia para a próxima faz com que ele estrague WA e estrague tudo por conta própria!

Bill Barth

Alguém mais está tendo problemas com os links? Eu tentei em vários navegadores e funciona bem em todos os casos.

Jed Brown

Esta é uma boa resposta. No entanto, decidi aceitar a resposta de Geoff Oxberry, porque parte do que eu estava tentando entender são os problemas do "mundo real" relacionados à pergunta. Isso inclui que pessoas como eu usem e recomendem o MINPACK, apesar de conhecer suas deficiências, e que outras pessoas solicitem conselhos sobre como resolver sistemas não lineares "trivialmente pequenos", mas que não consigam testar nem um único solucionador ao longo de três meses prazo.

Thomas Klimpel