Sobre condições sequenciais de otimalidade associadas ao esquema algorítmico de Lagrangiano aumentado

Autor(es)

Renan William Prado

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2023-03-27

Membros da banca

Sandra Augusta Santos; Maria Laura Schuverdt; Leonardo Delarmelina Secchin; Gabriel Haeser; Roberto Andreani

• Orientador: Lucas Eduardo Azevedo Simões; Sandra Augusta Santos

Resumo

O método de Lagrangiano aumentado salvaguardado (SALM, do inglês safeguarded augmented Lagrangian method) é muito utilizado na resolução de problemas gerais de programação não linear. Devido à sua capacidade de calcular pontos aproximadamente Karush-Kuhn-Tucker (KKT), o método é conhecido por convergir a pontos verdadeiramente KKT sob condições de qualificação extremamente fracas. O que explica tal sucesso são as condições sequenciais de otimalidade. Elas são condições concretamente estabelecidas que, quando asseguradas pela sequência gerada pelo algoritmo, fornecem uma análise de convergência mais próxima do comportamento real do método, refletindo com tanta precisão quanto possível as qualidades do algoritmo. Assim, uma forma de garantir novas propriedades para um algoritmo é fazer uma análise detalhada de sua convergência global por meio das condições sequenciais de otimalidade. Pensando nisso, e visando melhorar a teoria de convergência global do SALM, é interessante esclarecer como as condições de otimalidade que o método já garante se relacionam entre si e assegurar quais condições geradas por outros algoritmos também são asseguradas pelo SALM, indicando que tal método, possivelmente, garante melhores candidatos a minimizadores que os demais algoritmos abordados na análise. Pensando em tais questões, este trabalho teve dois objetivos: o primeiro foi mostrar que duas novas condições sequenciais de otimalidade estão associadas ao SALM, uma previamente estabelecida para o contexto não suave, chamada ?-Approximate Smooth Optimality Condition (?-ASOC), e outra derivada para o método de penalidade quadrática, chamada Strong AKKT (SAKKT); o segundo foi esclarecer a relação de força entre as novas condições garantidas para o método com as principais já estudadas na literatura. Para garantir que o segundo objetivo fosse cumprido, mostrou-se que a condição strong approximate gradient projection (SAGP) é garantida pelas condições ?-ASOC, que a condição positive approximate KKT (PAKKT) não se relaciona com a condição ?-ASOC e que, sob hipóteses fracas, SAGP é equivalente às condições complementary approximate KKT (CAKKT). Melhorando ainda mais os resultados anteriormente obtidos na literatura, neste trabalho é demonstrado, sob hipóteses fracas, que uma pequena modificação das condições SAKKT, ainda garantida pelo SALM, é mais forte do que outras condições sequenciais de otimalidade conhecidas, nomeadamente, CAKKT, PAKKT e ?-ASOC. Em suma, os resultados de convergência global do SALM foram melhor esclarecidos e uma relação mais completa entre as condições sequenciais de otimalidade garantidas pelo método foi apresentada (AU)

• Processo FAPESP: 19/18859-4 - Um método de otimização contínua com critério de parada baseado em uma nova condição sequencial de otimalidade
• Beneficiário: Renan Willian Prado
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto