Mínimos quadrados não lineares com restrições de caixa

10

Quais são as formas recomendadas de fazer mínimos quadrados não lineares, min , com restrições de caixa ? Parece-me (tolos se apressam) que alguém poderia tornar as restrições da caixa quadráticas e minimizar onde é a "função banheira" com o formato \ _ _ _ / / . Isso funciona na teoria, funciona na prática? (Parece haver muitos trabalhos teóricos sobre NLS +, mas meu interesse é prático - casos de teste reais ou realistas me ajudariam a escolher entre os métodos.) $\sum err_i(p)^2$ $lo_j <= p_j <= hi_j$

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$

t u b (x, l o, h i)

$tub( x, lo, hi )$

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$

(Especialistas, adicione tags: "mínimos quadrados"?)

optimization constraints denis
fonte

5

Substituir restrições estritas por funções de penalidade é uma técnica comum na otimização numérica. Parece que o que você está propondo é uma forma específica dessa substituição. Você pode ler tudo sobre técnicas semelhantes, por exemplo, aqui: stanford.edu/~boyd/cvxbook

David Ketcheson

Você pode usar uma parametrização adequada de para satisfazer as restrições da caixa (por exemplo, . Com relação aos solucionadores de NLS, Levenberg-Marquardt é bom o suficiente na maioria das vezes , talvez combinado com um otimizador estocástica global como recozimento simulado Algumas caixas de ferramentas comerciais também parecem métodos região oferecem confiança com base em modelos de superfície resposta adaptativa, que parece uma generalização razoável de Levenberg-Marquardt para mim..

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

Thomas Klimpel

11

Adicionar termos de penalidade ao quadrado para se livrar de restrições é uma abordagem simples, fornecendo uma precisão da ordem apenas 1 / fator de penalidade. Portanto, não é recomendado para alta precisão, a menos que você permita que a penalidade chegue ao infinito durante o cálculo. Mas um alto fator de penalidade torna o Hessiano muito mal condicionado, o que limita a precisão total alcançável sem levar em conta explicitamente as restrições.

Observe que restrições vinculadas são muito mais fáceis de lidar do que restrições gerais, de onde elas praticamente nunca são convertidas em penalidades.

O solucionador L-BFGS-B (usado com uma história de cerca de 5 dimensões) geralmente resolve problemas limitados limitados com muita confiabilidade e rapidez nas duas dimensões altas e baixas. As exceções são inconversas em problemas que podem ficar muito distantes das soluções, onde é fácil ficar preso ao método de descida.

Fizemos muitos experimentos em funções muito diversas em diversas dimensões, com diversos solucionadores disponíveis, pois precisávamos de um solucionador de restrições limitadas muito robusto como parte de nosso software de otimização global. O L-BFGS-B claramente se destaca como método de uso geral, embora, obviamente, em problemas de PME, outros solucionadores tenham um desempenho significativamente melhor. Portanto, eu recomendaria o L-BFGS-B como primeira opção e tentaria técnicas alternativas, caso o L-BFGS-B lide com sua classe de problemas.

Arnold Neumaier
fonte

O L-BFGS está disponível no IPOPT, revisei minha resposta.

Ali

5

Eu simplesmente usaria o IPOPT do solucionador de PNL de uso geral . É o solucionador mais robusto entre aqueles que tentei.

A menos que você tenha alguns requisitos muito especiais, não há motivo para insistir em um solucionador de problemas específico que funcione apenas para o NLS com restrições de caixa.

Uma mudança nos requisitos (por exemplo, adicionar restrições não lineares) causaria uma grande dor de cabeça com um solucionador de problemas específico. Você não terá esses problemas se usar o IPOPT de uso geral.

ATUALIZAÇÃO: Você pode tentar o L-BFGS com IPOPT , veja em Quase-Newton na documentação.

O procedimento da solução pode se tornar mais rápido às custas de estragar a notável robustez do IPOPT. Na minha opinião , use os derivados exatos, se estiverem disponíveis. Eu começaria a mexer com aproximações (como o L-BFGS) somente se tivesse problemas de desempenho comprovados.

Todos
fonte

Não sei o quão bem o IPOPT funciona, mas sua sugestão me lembra declarações semelhantes de advogados do método simplex em declive. Como os mínimos quadrados não lineares são uma classe de problemas comum, rejeitar completamente o uso de um dos solucionadores de NLS existentes me parece um pouco suspeito.

Thomas Klimpel

@ThomasKlimpel Bem, denis deve nos dar mais detalhes, para que possamos ajudá-lo a escolher o solucionador certo. :) Ou ele pode verificar por si mesmo e descobrir qual deles atende melhor às suas necessidades. O IPOPT parece ser um bom solucionador para começar.

Ali

@ Ali, você pode apontar para alguns "casos de teste reais ou realistas", por favor?

Denis

@denis eu poderia, mas não tenho intenção de fazê-lo, isso o tiraria da pista. A única coisa que importa é como o IPOPT lida com o seu problema . A menos que você tenha alguns requisitos muito especiais, ele deve resolvê-lo perfeitamente. O IPOPT possui interfaces para MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Escolha uma interface e teste o que acontece com o seu problema :) Testar um solucionador específico de problemas também não seria mais fácil.

Ali

@ Thomas Klimpel, acho que não fui claro: não estou rejeitando, não perguntando sobre pacotes, mas pedindo insights ou casos de teste: por que esse método trivial pode não funcionar bem?

Denis

1

O pacote R minpack.lm CRAN fornece uma implementação Levenberg-Marquardt com restrições de caixa.

Em geral, Levenberg-Marquardt é muito mais adequado que L-BFGS-B para problemas de mínimos quadrados. Ele convergirá (muito) melhor em problemas desafiadores. Também será muito mais rápido que o IPOPT de uso geral, pois é adaptado para problemas de mínimos quadrados não lineares.

O pacote R escolhe uma abordagem de projeção muito direta para impor as restrições (consulte o código-fonte ). Dependendo da implementação do LM que você está usando, pode ser simples incluir.

Agora, a sugestão nos comentários de usar uma transformação (por exemplo, uma transformação senoidal como em scipy) também é uma alternativa boa e simples para transformar seu algoritmo LM irrestrito em um restrito. Você também precisará incluir a transformação no jacobiano se o jacobiano for analítico.

jherek
fonte

0

(Anos depois) dois solucionadores que lidam com restrições de caixa:

O Scipy least_squares possui 3 métodos, com extenso documento:
1. 'trf': região de confiança reflexiva
2. 'dogbox'
3. 'lm': um wrapper herdado para MINPACK, sem restrições de caixa.
Ceres

denis
fonte

11

O Scipy diz explicitamente que o algoritmo Levenberg-Marquardt não pode lidar com restrições de caixa.

1623 tholy

Mínimos quadrados não lineares com restrições de caixa

Respostas: