Resumo

O objetivo deste projeto é a fomulação, análise teórica, desenvolvimento e implementação de algoritmos para os problemas clássicos de otimização: programação linear e não linear, resolução de sistemas de equações lineares e não lineares, problemas de viabilidade convexa (ou seja resolução de sistemas de inequações convexas), problemas de complementaridade linear e não linear e desigualdades variacionais. Outrossim, o núcleo abordará o estudo de técnicas de decomposição de descentralização para problemas estruturados, e o desenvolvimento de ``software" apropriado para este tipo de problemas. Compete também ao núcleo a resolução de problemas práticos usando ferramentas típicas da otimização numérica.

O núcleo reune os pesquisadores da área de otimização do IMPA, do IMECC-UNICAMP, do IME-USP e do departamento de Matemática de UFSC. Participam também dois pesquisadores da PUC-RJ e da Universidade federal do Piauí.

A descrição detalhada dos objetivos do projeto encontra-se na seção ``Estado da arte e objetivos do projeto". Por enquanto, destacamos que o projeto inclui a pesquisa básica e implementação de algoritmos em quase todas as áreas relevantes da otimização continua (i.e., sem incluir a otimização discreta ou combinatórica). Segue a continuação um resumo do conteúdo da seção mencionada acima.

Em programação linear e complementaridade linear, o projeto visa continuar e consolidar os resultados obtidos por C. Gonzaga sobre métodos de pontos interiores, e atacar vários problemas abertos existentes nessa área. Estudaremos a complexidade assintótica dos passos de Newton usados em nestes métodos, a complexidade de algoritmos de pontos interiores não viáveis, o uso de barreiras baseadas em suavizações da penalidade exata e resultados de complexidade baseados em números de condicionamento dos dados. Serão estudados também novos métodos de ponto interior que resultam da extensão da noção de trajetória central a problemas de desigualdades variacionais com barreiras genéricas, assim como métodos de ponto interior do tipo ``ação de linha" apropriados para problemas com matrizes extremamente grandes e esparsas.

Quanto as técnicas específicas para problemas estruturados, que têm sido especialmente estudadas pelos pesquisadores do IME-USP, o objetivo principal é o aproveitamento em algoritmos de otimização de tal estrutura. Podem-se considerar duas linhas básicas:

1- Aproveitamento em termos de decomposição e políticas distribuidas.

2- Aproveitamento em termos computacionais.

Os problemas estruturados de fundamental interesse para o projeto são:

1- Redes de computadores e sistemas de manufatura em decomposição e políticas descentralizadas.

2- Planejamento multi-período em problemas de produção, economia ou finanças.

Na parte de decomposição e descentralização, busca-se obter novos métodos de projeto de redes e contribuições à incipiente teoria dos sistemas compartilhados com disputa por recursos. Problemas típicos ora em estudo são: problemas de projeto de redes de computadores com restrição de equanimidade, caracterização dos vértices de ``multi-commodity flow" para CFA (``capacity and flow assignment") global, ``bounds" para redes de filas e políticas estabilizadoras para controle descentralizado de sistemas de manufatura.

Na parte de métodos computacionais busca-se unir a pesquisa na área de métodos numéricos (em particular para programação estocástica) com a geração de códigos que possam ser utilizados no mínimo como protótipos de ``solvers" em classes de problemas reais. Em termos de pesquisa e desenvolvimento, os tópicos onde a atividade do grupo de otimização contínua do IME-USP está centrada são: métodos para planejamento multiperíodo e determinação e visualisação de superfícies ótimas para problemas de administração de portfólio.

Em otimização diferenciável, área desenvolvida particularmente pelos pesquisadores do IMECC-UNICAMP, o projeto inclui, entre outros aspectos, o desenvolvimento de algoritmos ``semi-factíveis" em que o progresso rumo a factibilidade se sustenta nas restrições originais e não no seu modelo linear. Tenciona-se relacionar estes métodos com os de programação quadrática seqüencial, que também serão objeto de um estudo aprofundado. E também parte do projeto dar continuidade ao desenvolvimento de algoritmos necessários para implementar eficientemente métodos de tipo Lagrangeano aumentado, particularmente algoritmos para minimização em caixas. Os pesquisadores do IMECC-UNICAMP já desenvolveram um ``software" com essa finalidade, chamado BOX-QUACAN, que será aprimorado no decurso do projeto. Outrossim, serão estudadas extensões e melhoramentos dos métodos de programação quadrática recursiva. Quanto aos problemas de desigualdades variacionais, o projeto contempla dar continuidade ao estudo de métodos que os resolvem através da resolução de problemas de otimização relacionados com o problema original. Estes temas também têm sido desenvolvidos pelos pesquisadores do IMECC-UNICAMP, que, além da formulação, implementação, e análise teórica destes métodos, têm produzido aplicações dos novos algoritmos, que continuarão durante a execução do projeto. Os pesquisadores do IMPA e parte dos pesquisadores do IME-USP contribuirão na área de otimização diferenciável com a formulação de novos métodos de ação de linha, baseados numa teoria de dualidade em programação convexa, para problemas de programação positiva semi-definida. Serão estudadas também técnicas alternativas ao ``double dog leg" para a implementação de métodos quase-Newton com regiões de confiança.

Em otimização não diferenciável, as atividades propostas giram entorno de três eixos: novas técnicas de análise para algoritmos de otimização não monótonos (ou seja que não dispõem de nenhuma função de Lyapunov com comportamento monótono), métodos de ponto proximal com distâncias de Bregman e extensão de métodos de otimização convexa que usam a noção de $\varepsilon$-subdiferencial a problemas de desigualdades variacionais (particularmente métodos de feixe). Este último item será desenvolvido a partir de uma nova extensão dos operadores monótonos, que desempenha um papel semelhante ao $\varepsilon$-subdiferencial na optimização convexa. Nesta área, que vem sendo desenvolvida pelos pesquisadores do IMPA, o objetivo principal consiste no desenvolvimento de novas técnicas de análise, formulação de novos algoritmos e estabelecimento das suas propriedades de convergência. Os pesquisadores do IME-USP pretendem contribuir para esta linha de trabalho desenvolvendo novos métodos de separadores.

Finalmente, o projeto inclui atividades de pesquisa em otimização em espaços de dimensão infinita, tópico de várias pesquisas em andamento no IMPA. Três questões serão abordadas: extensão dos métodos de ponto proximal (tanto o ``clássico" quanto os que usam distâncias de Bregman) aos espaços de Banach, métodos de projeções para problemas de viabilidade convexa com infinitas restrições (visando obter um ponto que satisfaz ``quase todas" as restrições, no sentido da teoria da medida) e análise de métodos tipo gradiente e gradiente projetado para otimização não diferenciável em espaços de Hilbert e de Banach.

Além das atividades de pesquisa, o projeto do núcleo inclui ainda a realização de uma reunião internacional do mais alto nível, com a participação dos mais importantes pesquisadores nacionais e estrangeiros da área, em 1998.