Biblioteca C ++ para minimização restrita não linear

Atualmente, estou tentando resolver um problema de minimização com restrições não-lineares, conforme implementado na função matlab "fmincon". Minhas expectativas são: minimizar (fun1, x0, uB, lB, fun2) onde x0 é o estado inicial, fun1 é uma função que precisa ser minimizada, uB são limites superiores, lB são limites inferiores e lB são limites inferiores e fun2 é uma função que fornece vetores de igualdade não linear / desigualdades, conforme descrito em http://www.mathworks.com/help/optim/ug/fmincon.htmlcomo função nonlcon. Esses vetores também estão mudando através de iterações (eles são não linearmente dependentes de x_n, n-ésima iteração do vetor de solução). Na implementação do matlab, eles estão no formato c (x) <= 0. Este é o último pedaço de código que precisa ser portado do matlab para c ++ e tenho lutado bastante ao tentar encontrar a biblioteca c ++ apropriada que contenha esse algoritmo. É por isso que estou procurando ajuda aqui e gostaria muito que você pudesse fornecer seus conhecimentos.

Um bom exemplo do que eu quero fazer é o primeiro desta página http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b A única diferença é que eu precisa de limites também ...

Desde já, obrigado.

Pedro

c++ nonlinear-programming Peter Kottas
fonte

Existe a possibilidade de usar NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference, mas eu precisaria calcular diferenças finitas usando várias chamadas para avaliar a função "minimizada" da função objetivo e fui gentil de esperar que isso fosse resolvido pelo algoritmo para melhorar o desempenho. Minha função minimizada é realmente cara de calcular. Apenas para esclarecer, a função minimizada é a probabilidade logarítmica do modelo estimado com dados originais na estimativa do modelo de comutação de markov de séries temporais.

Peter Kottas

Você já viu as respostas para esta pergunta ? Se seus requisitos não forem suficientemente atendidos, edite sua pergunta para indicá-los, a fim de obter recomendações úteis.

Christian Clason

Obrigado, existem algumas informações úteis lá. Atualmente, eu estou disposto a usar os cotovelos na biblioteca NLOPT desde que descobri que ele também pode se adequar ao meu problema. Manterei este tópico publicado e fornecerá uma solução quando surgir um. Qualquer ajuda que possa tornar o processo mais rápido ainda é apreciada. Implementação real, por exemplo, etc.

Peter Kottas

Várias perguntas: 1. Seu problema é convexo? 2. O objetivo e as restrições são diferenciáveis? Se sim, quantas vezes? Uma vez? Duas vezes? 3. Você pode calcular facilmente esses derivados, se existirem? As aproximações de diferenças finitas seriam fáceis de calcular se você não tiver esses derivados prontamente disponíveis? 4. Quantas variáveis de decisão você possui? (ou seja, sobre quantas variáveis você está tentando minimizar?) Uma estimativa aproximada seria suficiente. 5. As avaliações de funções são caras? Seria útil ter todas essas informações para obter uma resposta melhor.

precisa

Oi! Primeiro de tudo, obrigado pela resposta. 1. Difícil dizer, mas provavelmente não, porque a função minimizada é a probabilidade logarítmica entre a estimativa do modelo de comutação markov de séries temporais na aplicação financeira e, pela natureza, presumo uma saída ruidosa. 2. não 3. apenas usando diferenças finitas 4. o vetor de solução consiste em n variáveis em que n depende dos parâmetros de modelos desejados, em geral de 12 a digamos 30 5. a probabilidade de log entre o modelo e os dados originais é cara, desigualdades não-lineares adicionais são cheep para calcular

Peter Kottas

Respostas:

Se sua função não for diferenciável, você deve ter cuidado com o uso de diferenças finitas. Se você deseja usar informações derivadas, sua melhor aposta é provavelmente algum tipo de método semântico de tipo Newton. Um conjunto de notas descrevendo esses métodos pode ser encontrado aqui .

Doze a trinta variáveis provavelmente estão na extremidade superior do que é possível com os métodos de pesquisa de padrões (também chamados de pesquisa direta). Um artigo de revisão recente de Rios e Sahinidis no Journal of Global Optimization sobre métodos de otimização sem derivativos (como métodos de pesquisa de padrões) pode ser encontrado aqui , juntamente com uma página da web complementar . Um artigo de revisão menos recente sobre esses métodos de Kolda, Lewis e Torczon no SIAM Review pode ser encontrado aqui . Esses métodos funcionam razoavelmente bem com avaliações de funções caras e não exigem necessariamente diferenciabilidade ou informações derivadas.

Muitos desses métodos requerem algum tipo de convexidade para garantir a convergência para o ideal global; portanto, se você resolver seu problema rigorosamente, poderá ser necessário associar esses métodos acima com uma estratégia de ramificação e limite. No entanto, se você não se importa com o rigor, uma abordagem como a do MATLAB fminconpode funcionar bem o suficiente (não há mais garantias). As diferenças finitas provavelmente fornecerão a você um membro do subdiferencial de sua função não diferenciável, o que pode ser suficiente para a instância do problema e dados de entrada específicos para retornar um resultado suficientemente preciso para seus propósitos. Nesse caso, você provavelmente deve olhar para as bibliotecas mencionadas nas respostas à pergunta que Christian vinculou em seu comentário.

Geoff Oxberry
fonte

Se tudo o que você precisa é de uma biblioteca C ++ para resolver problemas de otimização não linear, você pode usar o RobOptim . Embora o RobOptim tenha sido desenvolvido inicialmente com os problemas de otimização da robótica em mente, ele é adequado para qualquer problema de otimização não linear. Ele fornece uma interface C ++ simples com plug-ins para vários solucionadores não-lineares ( Ipopt , NAG , etc.). O uso desse tipo de invólucro facilita o uso de outro solucionador de PNL. Se você não pode fornecer gradientes, o cálculo de diferenças finitas pode ser feito automaticamente.

É de código aberto para que você possa conferir o código-fonte no GitHub: https://github.com/roboptim/

A análise feita por Geoff Oxberry é essencial para a escolha do solucionador não-linear que será chamado pelo RobOptim. Observe que, ao lidar com esse tipo de solução, o ajuste de parâmetros pode ter um enorme impacto no desempenho e você ainda pode ficar preso em mínimas locais (isso realmente depende do tipo de problema com o qual está lidando).

Nota: Eu sou um dos desenvolvedores deste projeto.

BenC
fonte