Que considerações devo fazer ao escolher entre BFGS e gradiente conjugado para otimização? A função que estou tentando ajustar com essas variáveis são funções exponenciais; no entanto, a função objetivo real envolve integração, entre outras coisas, e é muito dispendiosa se isso ajudar.
optimization
conjugate-gradient
drjrm3
fonte
fonte
Respostas:
JM está certo sobre o armazenamento. O BFGS requer um Hessian aproximado, mas você pode inicializá-lo com a matriz de identidade e, em seguida, apenas calcular as atualizações de nível dois para o Hessian aproximado à medida que avança, desde que você tenha informações de gradiente disponíveis, preferencialmente analiticamente, e não através de diferenças finitas. O BFGS é um método quase-Newton e convergirá em menos etapas que o CG, e tem uma tendência um pouco menos de "ficar preso" e exigir pequenos ajustes algorítmicos para obter uma descida significativa para cada iteração.
Por outro lado, o CG requer produtos vetoriais de matriz, que podem ser úteis para você, se você puder calcular derivadas direcionais (novamente, analiticamente ou usando diferenças finitas). Um cálculo de diferença finita de uma derivada direcional será muito mais barato que um cálculo de diferença finita de um Hessiano; portanto, se você optar por construir seu algoritmo usando diferenças finitas, basta calcular diretamente a derivada direcional. Essa observação, no entanto, não se aplica realmente ao BFGS, que calculará Hessianos aproximados usando produtos internos de informações de gradiente.
Eu compararia os dois algoritmos em um pequeno problema de teste para seu aplicativo se você souber que o armazenamento não será um problema. Sem conhecer as especificidades específicas do seu problema, meu palpite é que o BFGS será mais rápido, mas você deve realmente testar os dois algoritmos para ter uma idéia melhor de qual funcionará melhor.
Por fim, uma palavra sobre diferenciação automática: tendo alguma experiência com um recurso interno de diferenciação automática (AD) para Fortran ( DAEPACK ), posso dizer que as ferramentas do AD geralmente são exigentes. Eles podem não ser capazes de diferenciar necessariamente o código que eles próprios geram. Existem dois tipos de ferramentas do AD:
As ferramentas fonte a fonte são essencialmente compiladores modificados que pegam o código-fonte que você escreveu, analisam e geram automaticamente um novo código-fonte que calcula o gradiente de funções no seu código-fonte. As ferramentas de sobrecarga do operador do AD exigem que você use os operadores do AD sobrecarregados em seu código-fonte para que as derivadas possam ser calculadas, o que exigiria um esforço adicional de sua parte para calcular derivadas analíticas com o AD.
fonte
Na minha experiência, o BFGS com muitas atualizações armazena informações muito distantes da solução atual para ser realmente útil na aproximação do jacobiano sem atraso, e você pode realmente perder a convergência se armazenar demais. Existem variantes "sem memória" do BFGS que se parecem muito com gradientes conjugados não lineares (consulte a atualização final descrita para um deles) apenas por esses motivos. Portanto, se você deseja fazer L-BFGS em vez de BFGS, os problemas de memória desaparecem e os métodos estão relacionados . Evidências anedóticas apontam para o reinício de ser uma questão complicada, pois algumas vezes é desnecessária e outras muito necessária.
Sua escolha entre os dois também depende muito dos problemas nos quais você está interessado. Se você tiver os recursos, poderá tentar os dois e decidir qual funciona melhor. Por exemplo, eu pessoalmente não faço otimização com esses algoritmos, mas sim me preocupo com a solução de sistemas de equações não lineares. Para estes, descobri que o NCG funciona melhor e é mais fácil executar o pré-condicionamento não linear. BFGS é mais robusto.
fonte
Em baixas dimensões, um método BFGS bem implementado é geralmente mais rápido e mais robusto que o GC, especialmente se a função não estiver muito longe de ser quadrática.
Nem BFGS nem GC precisam de nenhuma suposição sobre convexidade; apenas a aproximação Hessiana inicial (para BFGS) resp. o pré-condicionador (para GC) deve ser definido positivamente. Mas estes sempre podem ser escolhidos para serem a matriz de identidade, em dimensões baixas, sem muito dano. Consulte também /scicomp//a/3213/1117
Na ausência de um gradiente programado, é um grande desperdício de esforço usar gradientes numéricos, especialmente quando os valores das funções são caros. Em vez disso, deve-se usar um algoritmo sem derivadas. Consulte http://archimedes.cheme.cmu.edu/?q=dfocomp para uma pesquisa recente.
fonte