Variantes implementáveis dos métodos de decomposição VU para funções compostas

Resumo

A otimização não diferenciável surge naturalmente ao modelar problemas de energia, finanças, processamento de sinais, mecânica geométrica. Além disso, problemas suaves às vezes levam ao uso de métodos de otimização não diferenciável, para tornar o processo de solução tratável em termos de porte ou estrutura (por exemplo, por meio da decomposição Lagrangeana ou de Benders).Também pode acontecer que um problema seja analiticamente suave, mas rígido ("stiff") e, portanto, do ponto de vista numérico, parece que não é diferenciável. Essas considerações mostram a importância de desenvolver ferramentas teóricas e computacionais que permitam manipular eficientemente problemas não diferenciáveis de otimização matemática. O programa de pesquisa considera uma classe especial de métodos para funções convexas não diferenciáveis, com base na chamada decomposição VU. A estrutura de tipo U corresponde a um sub-espaço onde, pelo menos localmente, a função aparece como sendo suave, e um passo de Newton pode ser feito ao longo de direções em U. Desta forma, a velocidade superlinear torna-se possível, mesmo para funções sem derivadas de primeira ordem. A abordagem teórica, introduzida por Lemarechal e Sagastizábal, depende da capacidade de fazer cálculos proximais exatos e de identificar adequadamente os subespaços (ortogonais) V e U. Usando uma abordagem semelhante a um método de feixes para aproximar esses cálculos, Mifflin e Sagastizábal desenvolveram um algoritmo VU para o qual uma (sub)sequência converge a uma solução com velocidade superlinear. O problema de como identificar corretamente, de modo sistemático, as estruturas V e U ao longo do algoritmo ficou em aberto. Esta pesquisa pretende responder a essa questão para uma importante subclasse de funções convexas, chamadas de tipo composto. Especificamente, as funções consideradas são o resultado de compor uma função convexa sublinear e fechada com um mapeamento suave. A identificação adequada dos subespaços V e U equivale a um processo semelhante aoo que na programação não-linear é feito para encontrar quais restrições de desigualdade são ativas num iterado. O conceito extendido, denominado de variedade de atividade, foi introduzido por Lewis ao estudar funções ditas parcialmente suaves. O subespaço U é tangente a essa variedade de atividade. A pesquisa focará em como caracterizar vários conceitos relacionados à suavidade parcial para funções compostas. Em particular, estudaremos uma decomposição espacial relaxada, dependendo de certos subespaços V-epsilon e U-epsilon, que convergem continuamente para as contrapartes V e U quando epsilon tende a zero. Estudaremos também a relação da nova decomposição epsilon-VU com um conjunto de epsilon atividade que contém a variedade onde a função é parcialmente suave (o conjunto relaxado correspondoria, grosso modo, a encontrar desigualdades que são ativas até epsilon em programação não-linear). Este projeto e uma continuacao natural de trabalhos começados em colaboração com C. Sagastizabal e M. Solodov. Graças a supervisão do J. M. Martinez nesta segunda fase do projeto, o candidato se beneficiara da ampla expertise em otimização numérica do pesquisador responsável, e poderá assim implementar variantes eficazes dos métodos desenvolvidos. (AU)