Algoritmos de otimização paralela para um problema com função objetiva muito cara

15

Estou otimizando uma função de 10 a 20 variáveis. A má notícia é que cada avaliação de função é cara, aproximadamente 30 min de computação em série. A boa notícia é que tenho um cluster com algumas dúzias de nós computacionais à minha disposição.

Assim, a pergunta: existem algoritmos de otimização disponíveis que me permitiriam usar todo esse poder computacional com eficiência?

De um lado do espectro, haveria uma pesquisa exaustiva: subdividir todo o espaço de pesquisa em uma grade fina e calcular a função em cada ponto da grade de forma independente. Este é certamente um cálculo muito paralelo, mas o algoritmo é terrivelmente ineficiente.

Do outro lado do espectro, haveria algoritmos quase-Newton: atualize de forma inteligente a próxima estimativa dos parâmetros com base na história anterior. Este é um algoritmo eficiente, mas não sei como torná-lo paralelo: o conceito de "estimativa dos parâmetros com base no histórico anterior" soa como uma computação serial.

Algoritmos quadráticos parecem estar em algum lugar no meio: pode-se construir o "modelo substituto" inicial computando vários valores em paralelo, mas não sei se as iterações restantes são paralelizáveis.

Alguma sugestão sobre que tipo de métodos de otimização sem gradiente funcionaria bem em um cluster? Além disso, existem implementações paralelas de algoritmos de otimização disponíveis atualmente?

Michael
fonte
11
Você sempre pode calcular o gradiente em paralelo (para métodos quase-Newton usando diferenças finitas) e obter uma aceleração proporcional ao número de parâmetros, ou seja, 10x-20x.
Stali #
@ stali: Você precisa do Hessian para métodos quase-Newton na otimização. Computar o Hessian através de diferenças finitas de avaliações de funções não é realmente uma boa ideia. Calcular aproximações de diferenças finitas do gradiente para otimização também geralmente não é uma boa idéia.
precisa
Muitos métodos quase-Newton, como o BFGS, não exigem o Hessian explicitamente. Eu acho que usando gradientes, em combinação com L-BFGS, o OP pode alcançar rapidamente o que ele deseja.
Stali #
@stali: Eu indiquei por que usar uma aproximação de diferença finita ao gradiente seria uma má ideia na minha resposta. Isso degradará a convergência ao introduzir erros no lado direito da iteração quase-Newton. Além disso, desperdiça avaliações de função porque não há oportunidade para reutilizar avaliações antigas (diferentemente dos métodos substitutos). O uso do BFGS trata apenas metade dos problemas com a abordagem proposta.
Geoff Oxberry
Este é um comentário mais apropriado, não uma resposta. Mas não tenho escolha, pois não tenho representante suficiente para postar um comentário. Michael, tenho um tipo de problema muito semelhante: avaliações de funções caras que envolvem simulações complexas em execução em um cluster. Você já encontrou um código apropriado para executar a otimização quando a avaliação da função envolve uma simulação em um cluster?
MoonMan 24/05

Respostas:

16

Como Paulo afirma, sem mais informações, é difícil dar conselhos sem suposições.

Com 10 a 20 variáveis ​​e avaliações de funções caras, a tendência é recomendar algoritmos de otimização sem derivadas. Discordo totalmente do conselho de Paul: você geralmente precisa de um gradiente de precisão de máquina, a menos que esteja usando algum tipo de método especial (por exemplo, a descida estocástica de gradiente no aprendizado de máquina explorará a forma do objetivo de chegar a uma conclusão razoável. estimativas de gradiente).

Cada etapa quase-Newton terá a forma:

H~(xk)dk=-f(xk),

onde é alguma aproximação da matriz de Hesse, d k é o sentido de pesquisa, x k é o valor das variáveis de decisão na iteração corrente, f é a sua função de objectivo, e f é o gradiente de seu objetivo, eo variáveis ​​de decisão são atualizadas como x k + 1 = x k + α k d k , em que α kH~dkxkffxk+1 1=xk+αkdkαké um tamanho de etapa determinado de alguma forma (como uma pesquisa de linha). Você pode se aproximar do Hessian de determinadas maneiras e suas iterações convergirão, embora se você usar algo como aproximações de diferenças finitas do Hessian por meio de gradientes exatos, poderá sofrer problemas devido a problemas de condicionamento. Normalmente, o Hessian é aproximado usando o gradiente (por exemplo, métodos do tipo BFGS com atualizações de nível 1 no Hessian).

Aproximar o Hessian e o gradiente através de diferenças finitas é uma péssima idéia por várias razões:

  • você terá erro no gradiente, então o método quase-Newton que você está aplicando é semelhante a encontrar a raiz de uma função barulhenta
  • se as avaliações de função forem caras e você estiver tentando avaliar um gradiente em relação a variáveis, isso custará a você N avaliações de função por iteraçãoNN
  • se você tiver erro no gradiente, terá mais erro no seu Hessian, o que é um grande problema em termos do condicionamento do sistema linear
  • ... e custará avaliações de função de por iteraçãoN2

Portanto, para obter uma iteração ruim de quase-Newton, você está fazendo algo como até 420 avaliações de funções a 30 minutos por avaliação, o que significa que você estará esperando um pouco por cada iteração ou vai precisa de um grande cluster apenas para as avaliações de funções. As soluções lineares reais serão de 20 por 20 matrizes (no máximo!), Portanto não há razão para paralelizar essas. Se você pode obter informações de gradiente, por exemplo, resolvendo um problema conjunto, pode valer mais a pena; nesse caso, pode valer a pena olhar para um livro como Nocedal & Wright.

Se você for fazer várias avaliações de funções em paralelo, deve considerar abordagens de modelagem substitutas ou gerar métodos de pesquisa de conjuntos antes de considerar abordagens quase-Newton. Os artigos de revisão clássica são os de Rios e Sahinidis sobre métodos sem derivativos , publicados em 2012 e oferecem uma comparação realmente boa e ampla; o artigo de benchmarking de More e Wild de 2009; o livro de 2009 "Introdução à otimização sem derivativos", de Conn, Scheinberg e Vicente; e o artigo de revisão sobre geração de métodos de pesquisa de conjuntos de Kolda, Lewis e Torczon de 2003.

Conforme vinculado acima, o pacote de software DAKOTA implementará alguns desses métodos, assim como o NLOPT , que implementa o DIRECT, e alguns dos métodos de modelagem substitutos de Powell. Você também pode dar uma olhada no MCS ; está escrito em MATLAB, mas talvez você possa portar a implementação do MATLAB para o idioma de sua escolha. O DAKOTA é essencialmente uma coleção de scripts que você pode usar para executar sua simulação cara e coletar dados para algoritmos de otimização, e o NLOPT possui interfaces em um grande número de linguagens; portanto, a escolha da linguagem de programação não deve ser um grande problema no uso de nenhum pacote de software; O DAKOTA demora um pouco para aprender, e possui uma enorme quantidade de documentação para filtrar.

Geoff Oxberry
fonte
2
É um prazer para mim estar completamente errado e aprender algo novo e útil no processo :).
Paul
Obrigado! Apenas mais um esclarecimento: quais desses algoritmos são capazes de realizar avaliações de funções em paralelo? Por exemplo, na grade k-way executando as iterações n + 1, ..., n + k com base apenas nas informações obtidas nas iterações 1, ..., n?
Michael
k
3

Talvez algoritmos de otimização baseados em substitutos sejam o que você está procurando. Esses algoritmos usam modelos substitutos para substituir os modelos computacionalmente caros reais durante o processo de otimização e tentam obter uma solução adequada usando o mínimo possível de avaliações dos modelos computacionalmente caros.

Eu acho que o método Modo de Prosseguir Amostragem pode ser usado para resolver seu problema. Esse algoritmo usa o modelo substituto do RBF para aproximar a função objetiva cara e pode lidar com restrições não lineares. Mais importante, ele seleciona vários candidatos para fazer as avaliações de funções caras, para que você possa distribuir esses candidatos para computação paralela para acelerar ainda mais o processo de pesquisa. O código é de código aberto e escrito em MATLAB.

Referência

Wang, L., Shan, S. e Wang, GG (2004). Método de amostragem para otimização global em funções caras de caixa preta. Engineering Optimization, 36 (4), 419-438.

Zhan Dawei
fonte
2

Não tenho certeza se um algoritmo paralelo é realmente o que você está procurando. Suas avaliações de funções são muito caras. O que você quer fazer é paralelizar a própria função, não necessariamente o algoritmo de otimização.

Se você não pode fazer isso, existe um meio termo entre a pesquisa exaustiva e o algoritmo de Newton, são os métodos de Monte Carlo. Você pode, em vários núcleos / nós diferentes, iniciar o mesmo algoritmo que pode cair nos ótimos locais (por exemplo, algoritmos quasi-Newton), mas todos com condições iniciais aleatórias. Seu melhor palpite para o verdadeiro ótimo é o mínimo dos mínimos. Isso é trivial para paralelizar e pode ser usado para estender qualquer método. Embora não seja perfeitamente eficiente, se você tiver poder de computação suficiente à sua disposição, pode vencer definitivamente a produtividade de programação versus o desempenho do algoritmo (se você tiver muito poder de computação, isso poderá terminar antes que você termine de criar um algoritmo mais sofisticado).

Chris Rackauckas
fonte
0

A escolha do algoritmo de otimização (e, portanto, sua paralelização) depende muito das propriedades da função objetivo e das restrições. Sem saber mais sobre o problema, é difícil dar qualquer tipo de conselho significativo.

Mas, pelas suas considerações sobre os métodos newton, deduzo que sua função objetivo é diferenciável. Se possível, seu problema se beneficiaria muito ao paralelizar a avaliação da função. Se não for possível, você também pode considerar um método newton inexato que substitui os gradientes / hessianos exatos por aproximações de diferenças finitas. Em seguida, você pode usar todos esses processadores à sua disposição para calcular cada elemento diferente de zero do jacobiano, como sugere @stali.

Para obter mais informações, leia Otimização numérica de Nocedal & Wright, capítulo 7 . Existem muitos pacotes de software de otimização que implementam isso em paralelo. Entre o freeware mais utilizado, está o pacote de software DAKOTA (Sandia National Labs) .

Paulo
fonte
5
N
-2

Aqui está uma solução para o seu problema.

A descrição de um método matemático é fornecida neste documento .

Paulo
fonte
3
Bem-vindo ao SciComp.SE. Você pode fornecer detalhes sobre a abordagem descrita no documento e implementada no software? Qual é o método usado? Por que isso é bom? O que é fornecido nessa abordagem que as outras respostas não cobrem?
nicoguaro
2
Além disso, parece que este é seu próprio trabalho. Se isso for verdade, indique isso explicitamente em sua resposta.
Nicoguaro
@nicoguaro: obrigado, mas eu sei como clicar nos links.
Michael
2
@ Michael, não é para você. A filosofia deste site é ser uma coleção de respostas. Você está obtendo sua resposta hoje, mas no futuro alguém poderá precisar da mesma ajuda. É por isso que existem padrões de fato sobre o que é uma boa resposta.
nicoguaro