💾 Archived View for tilde.pink › ~sekva › tcc › contexto_historico.gmi captured on 2024-02-05 at 11:00:36. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
Obs: Todas as referencias, exceto quando dito o contrario, são do artigo
do SCP.
A otimização restrita de problemas de mínimo encontrava pouco sucesso na época.
No entanto um pequeno subconjunto desses problemas estava gerando técnicas
muito uteis, e um desses subconjuntos era a minimização de uma função convexa
em um conjunto fechado e convexo, que foi alvo de muito interesse na época.
O motivo de tanto interesse era que, como a função é convexa, todo ponto de
mínimo local é mínimo global.
Nesse contexto, J.E. Kelley, posto como responsavel pela disseminação dos
métodos de corte de plano desenvolve um método de otimização capaz de resolver
problemas convexos de a partir de suposições mais genéricas. O método proposto
por Kelley é iterativo e consiste na resolução de problemas lineares.
Esse método faz parte do crescimento do estudo do problema de ajuste de curvas
de Chebyshev [5, 6, 7]. O problema do ajuste de curvas pode ser resolvido
minimizando a seguinte situação:
σ(ɑ, x) = f(x) - Σⱼ ɑⱼgⱼ(x)
min(ɑ)
Obs: todas as referencias são do artigo [11] do SCP
Outros pesquisadores, como Cheney/Goldstein [1] e Phillip Wolfe [11], das
condições de Wolfe, chegaram independentemente a este método, todos
inspirados pelo trabalho de Remez.
https://mathworld.wolfram.com/RemezAlgorithm.html
https://en.wikipedia.org/wiki/Remez_algorithm#cite_note-1
O método de ajuste de curvas proposto por Remez constrói o polinômio com
melhor aproximação para certas funções sob algumas condições. A forma de
resolução é dada pela resolução de problemas lineares, analise de erro, e
atualização do estado atual baseado em condições sobre o erro. Esses passos
se tornaram base para toda a família de otimizadores pelo fato de gerar
informação sobre direções do ótimo baseado numa analise inteligente do
comportamento da função.
Método responsavel por otimizar um problema da companhia de petróleo Shell.
Trabalhando de forma similar, usando resoluções de subproblemas lineares, o
processo consiste e resolver os subproblemas lineares de forma que a solução
deles venham a convergir para a solução do problema principal.
O método aceita problemas formulados respeitando um certo conjunto de regras,
mas na pratica nem sempre é necessário que sigam todas as funções visto que
a solução dada é boa o suficiente. É dito que as melhores formulações para o
problema necessitam:
Um dos pontos positivos é que a escolha do ponto inicial para dar inicio ao
algoritmo iterativo não afeta tanto o resultado final.
A forma como a convergência das soluções dos subproblemas lineares resolvidos
é mostrada é bastante ingenua, o método sendo iterativo precisa de um ponto
inicial, e tal ponto inicial é o ponto dado como solução do subproblema linear
resolvido anteriormente, e como a região onde esse é resolvido respeita as
restrições do problema principal, então a sequencia de pontos gerados converge
para a solução ótima dentro de polígonos gerados pela linearização das
restrições, e a solução é uma aresta desse polígono.
Em 1977 S.P. Han publicou um artigo no qual demonstrava um método que mudaria
os rumos do estudo de otimização na epoca. Os métodos newtonianos que vinham
sendo desenvolvidos eram de convergencia a um otimo local apenas, até que
S.P.Han mostrou um formato que a convergencia se tornaria a um otimo global.
Esse formato tem como objetivo resolver uma forma quadratica do problema
original, encontrando uma direção de descida, e, ao inves de analisar a
otimização da função original, anailisa-se um função de merito que leva em
consideração propriedades locais da função, tornando o método capaz de
convergir para um otimo global, e mais, de forma superlinear.
Após a publicação desse artigo, uma grande quantidade de publicações foram
feitas usando como base as tecnicas de otimização sequencial quadratica, e até
hoje, uma grande parte dos otimizadores usam de alguma forma tais tecnicas.
Mesmo o SQP sendo um dos métodos mais bem sucedidos para otimização em larga
escala, como com problemas com centenas de variáveis e restrições, existe um
problema, justamente neste caso, o método se torna computacionalmente
ineficiente. Por isso, Bryd, Gould, Nocedal e Waltz, desenvolveram um novo
método onde o problema quadrático não precisa ser resolvido completamente,
em que a resolução de um problema linear limite o que precisa ser avaliado
pelo problema quadrático, reduzindo assim o custo computacional da etapa mais
pesada do método, a resolução de problemas quadráticos. O que os métodos
anteriores vinham fazendo era avaliar as funções de restrição ao mesmo que
tempo que se fazia a computação do atualização do ponto da sequencia naquele
momento. A mudança que este método fez foi separar cada etapa da resolução e
buscar uma melhor forma de resolver cada passo. O primeiro passo, feito por uma
resolução de um problema linear reduz o conjunto de restrições e define uma
direção de minimização. Feito isso é computado um modelo quadrático minimizando
uma função de mérito que faz uso da direção dada pela resolução do problema
linear. Por fim, o problema quadrático é resolvido usando o conjunto de
restrições determinada na primeira etapa.