Por que os algoritmos de otimização são definidos em termos de outros problemas de otimização?

Estou pesquisando técnicas de otimização para aprendizado de máquina, mas fico surpreso ao descobrir que um grande número de algoritmos de otimização é definido em termos de outros problemas de otimização. Ilustro alguns exemplos a seguir.

Por exemplo, https://arxiv.org/pdf/1511.05133v1.pdf

Tudo parece bom e bom, mas há esse na atualização .... então qual é o algoritmo que resolve o ? Nós não sabemos, e isso não diz. Então, magicamente, devemos resolver outro problema de otimização, que é encontrar o vetor minimizador para que o produto interno seja no mínimo - como isso pode ser feito?$\text{argmin}_x$$z^{k+1}$$\text{argmin}$

Veja outro exemplo: https://arxiv.org/pdf/1609.05713v1.pdf

Tudo parece bom e bom até você atingir o operador proximal no meio do algoritmo, e qual é a definição desse operador?

Estrondo:

Agora, diga, como podemos resolver esse no operador proximal? Isso não diz. De qualquer forma, esse problema de otimização parece difícil (NP HARD), dependendo do que é.$\text{argmin}_x$$f$

Alguém pode me esclarecer sobre:

1. Por que tantos algoritmos de otimização são definidos em termos de outros problemas de otimização?

(Isso não seria algum problema de galinha e ovo: para resolver o problema 1, você precisa resolver o problema 2, usando o método de solução do problema 3, que depende da solução do problema ...)

2. Como você resolve esses problemas de otimização incorporados nesses algoritmos? Por exemplo, , como encontrar o minimizador no lado direito?$x^{k+1} = \text{argmin}_x \text{really complicated loss function}$

3. Por fim, estou intrigado sobre como esses algoritmos podem ser implementados numericamente. Reconheço que adicionar e multiplicar vetores são operações fáceis em python, mas e quanto a , existe alguma função (script) que magicamente fornece o minimizador de uma função?$\text{argmin}_x$

(Recompensa: alguém pode fazer referência a um artigo para o qual os autores esclarecem o algoritmo do subproblema incorporado no algoritmo de otimização de alto nível?)

Você está olhando para os fluxogramas de algoritmos de nível superior. Algumas das etapas individuais no fluxograma podem merecer seus próprios fluxogramas detalhados. No entanto, em artigos publicados com ênfase na brevidade, muitos detalhes são frequentemente omitidos. Detalhes para problemas padrão de otimização interna, que são considerados "antigos", podem não ser fornecidos.

A idéia geral é que algoritmos de otimização podem exigir a solução de uma série de problemas de otimização geralmente mais fáceis. Não é incomum ter 3 ou até 4 níveis de algoritmos de otimização em um algoritmo de nível superior, embora alguns deles sejam internos aos otimizadores padrão.

Mesmo decidir quando finalizar um algoritmo (em um dos níveis hierárquicos) pode exigir a solução de um problema de otimização lateral. Por exemplo, um problema de mínimos quadrados lineares sem restrição negativa pode ser resolvido para determinar os multiplicadores de Lagrange usados ​​para avaliar a pontuação de otimização KKT usada para decidir quando declarar a otimização.

Se o problema de otimização for estocástico ou dinâmico, pode haver ainda níveis hierárquicos adicionais de otimização.

Aqui está um exemplo. Programação Quadrática Sequencial (SQP). Um problema de otimização inicial é tratado resolvendo iterativamente as condições de otimização de Karush-Kuhn-Tucker, começando de um ponto inicial com um objetivo que é uma aproximação quadrática do Lagrangiano do problema e uma linearização das restrições. O programa quadrático resultante (QP) é resolvido. O QP resolvido possui restrições de região de confiança ou uma pesquisa de linha é conduzida da iteração atual para a solução do QP, que é um problema de otimização, a fim de encontrar a próxima iteração. Se um método Quasi-Newton estiver sendo usado, um problema de otimização deverá ser resolvido para determinar a atualização Quasi-Newton no Hessian do Lagrangiano - normalmente, essa é uma otimização de formulário fechado usando fórmulas de formulário fechado, como BFGS ou SR1, mas poderia ser uma otimização numérica. Em seguida, o novo QP é resolvido etc. Se o QP for sempre inviável, inclusive para iniciar, um problema de otimização será resolvido para encontrar um ponto viável. Enquanto isso, pode haver um ou dois níveis de problemas de otimização interna sendo chamados dentro do solucionador de QP. No final de cada iteração, um problema de mínimos quadrados lineares não negativos pode ser resolvido para determinar a pontuação de otimização. Etc.

Se este for um problema inteiro misto, todo esse shebang poderá ser executado em cada nó de ramificação, como parte de um algoritmo de nível superior. Da mesma forma para um otimizador global - um problema de otimização local é usado para produzir um limite superior para a solução globalmente ótima, então um relaxamento de algumas restrições é feito para produzir um problema de otimização de limite inferior. Milhares ou mesmo milhões de problemas de otimização "fáceis" de ramificação e limite podem ser resolvidos para resolver um problema misto de número inteiro ou otimização global.

Isso deve começar a dar uma idéia.

Edit : Em resposta à pergunta sobre frango e ovo que foi adicionada à pergunta após a minha resposta: Se houver um problema com frango e ovo, não será um algoritmo prático bem definido. Nos exemplos que dei, não há frango e ovo. Etapas de algoritmo de nível superior invocam solucionadores de otimização, que são definidos ou já existem. O SQP chama iterativamente um solucionador de QP para resolver subproblemas, mas o solucionador de QP resolve um problema mais fácil, QP, do que o problema original. Se houver um algoritmo de otimização global de nível ainda mais alto, ele poderá chamar um solucionador SQP para resolver subproblemas de otimização não linear local, e o solucionador SQP, por sua vez, chamará um solucionador QP para resolver subproblemas QP. Sem frango e ovo.

Nota: As oportunidades de otimização estão "em todos os lugares". Especialistas em otimização, como aqueles que desenvolvem algoritmos de otimização, têm mais chances de ver essas oportunidades de otimização e vê-las como tal do que o Joe ou Jane médio. E sendo inclinados algoritmicamente, naturalmente vêem oportunidades para criar algoritmos de otimização a partir de algoritmos de otimização de nível inferior. A formulação e solução de problemas de otimização servem como blocos de construção para outros algoritmos de otimização (de nível superior).

Edit 2 : Em resposta à solicitação de recompensa que acabou de ser adicionada pelo OP. O documento que descreve o otimizador não-linear SQP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf menciona especificamente o solucionador de QP SQOPT, que é documentado separadamente, como sendo usado para resolver subproblemas de QP no SNOPT.

Eu gosto da resposta de Mark, mas gostaria de mencionar o "Simulated Annealing", que basicamente pode ser executado em cima de qualquer algoritmo de otimização. Em um nível alto, funciona assim:

Possui um parâmetro de "temperatura" que começa quente. Enquanto quente, afasta-se frequentemente e (e mais longe) de onde o algoritmo de otimização subordinado aponta. Enquanto esfria, segue o conselho do algoritmo subordinado mais de perto e, em zero, segue-o para o local ideal em que ele acabou.

A intuição é que ele procurará o espaço amplamente no começo, procurando "lugares melhores" para procurar ótimos.

Sabemos que não há uma solução geral real para o problema ótimo local / global. Todo algoritmo terá seus pontos cegos, mas híbridos como esse parecem dar melhores resultados em muitos casos.

Eu acho que uma referência que satisfaça seu desejo está aqui . Vá para a seção 4 - Otimização na computação bayesiana moderna.

TL; DR - discutem métodos proximais. Uma das vantagens de tais métodos é a divisão - você pode encontrar uma solução otimizando subproblemas mais fáceis. Muitas vezes (ou pelo menos algumas vezes) você pode encontrar na literatura um algoritmo especializado para avaliar uma função proximal específica. No exemplo deles, eles fazem denoising de imagem. Uma das etapas é um algoritmo muito bem-sucedido e altamente citado por Chambolle.

Isso é bastante comum em muitos trabalhos de otimização e tem a ver com generalidade. Os autores geralmente escrevem os algoritmos dessa maneira para mostrar que eles tecnicamente trabalham para qualquer função f. No entanto, na prática, eles são úteis apenas para funções muito específicas em que esses subproblemas podem ser resolvidos com eficiência.

Por exemplo, e agora estou falando apenas do segundo algoritmo, sempre que você vê um operador proximal (que, como você observou em outro problema de otimização que pode ser muito difícil de resolver), geralmente está implícito que ele tem uma solução de formulário fechado em ordem para que o algoritmo seja eficiente. Isso é verdade para muitas funções de interesse no aprendizado de máquina, como a norma l1, normas de grupo e assim por diante. Nesses casos, você substituiria os subproblemas pela fórmula explícita do operador proximal, e não há necessidade de um algoritmo para resolver esse problema.

Quanto ao motivo de eles serem escritos dessa maneira, observe que, se você criar outra função e quiser aplicar esse algoritmo, verifique primeiro se o proximal tem uma solução de formulário fechado ou pode ser calculado com eficiência. Nesse caso, basta conectar a fórmula ao algoritmo e pronto. Como mencionado anteriormente, isso garante que o algoritmo seja suficientemente geral para ser aplicado a funções futuras que possam surgir após a primeira publicação do algoritmo, juntamente com suas expressões proximais de algoritmos eficientes para computá-los.

Finalmente, como exemplo, pegue o artigo original do algoritmo FISTA clássico. Eles derivam o algoritmo para duas funções muito específicas, a perda ao quadrado e a norma l1. No entanto, eles observam que não pode ser aplicada nenhuma função desde que atendam a alguns pré-requisitos, sendo um deles que o proximal do regularizado pode ser computado com eficiência. Este não é um requisito teórico, mas prático.

Essa compartimentalização não apenas torna o algoritmo geral, mas também mais fácil de analisar: enquanto existirem algoritmos para os subproblemas que possuem essas propriedades, o algoritmo proposto terá essa taxa de convergência ou qualquer outra coisa.