**Desenvolvimento de "Software" em Otimização Não-Linear para Problemas Restritos, Esparsos e de Grande Porte**

RESUMO

Este artigo tem como objetivo informar as tendências do desenvolvimento de novos "software" para resolver problemas de otimização não linear de grande porte restritos e esparsos. Aqui abordaremos alguns aspectos importantes do desenvolvimento destes "software". As principais partes dos mesmos são:

o programa principal, geralmente baseado em Programação Quadrática Sequencial (SQP);
a formação da matriz Hessiana, ou sua aproximada;
obtenção das primeiras e/ou segundas derivadas das funções objetivo e das restrições;
e a resolução dos sistemas lineares esparsos envolvidos.

Descreveremos também alguns "software" já existentes no mercado.

INTRODUÇÃO

Existem vários "software" para resolver problemas restritos de otimização não-linear esparsos de grande porte. Estes "software" estão sendo constantemente melhorados tanto no método como na técnica de implementação. Isto significa que todos estes "software" estão sujeitos a ser constantemente superados por outros. Exemplos destes tipos de "software" são: LANCELOT [Conn et al. 1992] ^[1] e [Conn et al. 1993] ^[2] desenvolvido em conjunto pelos seguintes três instituições: IBM-Watson Research Centre nos EUA, Rutherford Appleton Laboratory na Inglaterra e Facultés Universitaires de Namur na Bélgica; MINOS baseado no Simplex [Murtagh & Saunders 1995] ^[3] e [Murtagh & Saunders 1976] ^[4] desenvolvido pelo Department of Operational Research of Stanford University nos EUA; BOX [ Friedlander et al. (1994) ] ^[5] para resolver problemas com restrições caixas (isto é problemas com variáveis restritas) o qual foi desenvolvido pelo DMA-IMECC- UNICAMP, Campinas-SP, Brasil; e finalmente o OPTIMA [Bartholomew-Biggs 1989] ^[6] desenvolvido pelo Numerical Optimisation Center, University of Hertfordshire. Um dos programas do OPTIMA, o OPALQP foi melhorado e adaptado para resolver problemas de grande porte esparso durante o desenvolvimento da tese [Hernández 1995] ^[8]e outros "software" estão descritos em [Moré & Wright 1993]. ^[9]

Recentemente o Optimization Technology Center do Argonne National Laboratory e a Northwestern University, USA [Fourer et al. (1996) ] ^[7] , vêm desenvolvendo o NEOS, um "software" para resolver problemas de otimização através da INTERNET ou E-MAIL.

Para que seja possível o desenvolvimento de "software" competitivo, faz-se necessário uma pesquisa intensa na análise dos métodos, na implementação computacional, nos tipos de testes e nas comparações com os melhores já existentes.

Os problemas resolvidos por estes "software" podem ser colocados na forma

Minimize F(x)
sujeito a g_i(x)=0 para i = 1,...,m' onde m' ^>=0 m' 0
h_j(x) ^>= 0 para j = m'+1,...m onde m ^>= m' ,

onde F é uma função escalar de várias variáveis x (x é um vetor), chamada de função objetivo e g e h são funções escalares também de x, as quais são as restrições. Para que este problema seja de Otimização não Linear, F deve ser não linear, as outras funções podendo ser lineares ou não.

Métodos iterativos são os mais apropriados para resolver este tipo de problemas. Os mais usados são do tipo Programação Quadrática Sequencial (SQP), nos quais para cada iteração se forma e resolve um subproblema de otimização quadrática. A sequência de cálculos efetuados em cada iteração na maioria dos métodos são as seguintes:

Determinar o conjunto ativo que contenha todas as restrições de igualdade e as de desigualdade que satisfaçam a uma determinada condição.
Formar o Lagrangeano que é a função objetivo menos o somatório das funções restrições pertencentes ao conjunto ativo multiplicadas pelos seus respectivos multiplicadores de Lagrange estimados.
Supondo que todas as funções são duas vezes diferenciáveis, determinar o gradiente (primeira derivada da função em cada variável) da função objetivo, o Jacobiano (cada linha é o gradiente de uma função) das restrições pertencentes ao conjunto ativo e também a Hessiana (matriz derivada de segunda ordem) do Lagrangeano, para formar o subproblema quadrático. Em alguns métodos usam-se estimativas da Hessiana.
Da Hessiana e do Jacobiano, formar um sistema linear, cuja matriz é a matriz K-K-T; daí calcular a direção de busca e os novos multiplicadores de Lagrange estimados.
Atualizar os valores das variáveis e verificar as condições de convergência. Se as condições de convergência são satisfeitas, terminar o processo; se não, voltar ao passo 1.

Para mais detalhes, ver [Fletcher 1987] ^[11] e [Gill et al. 1982] ^[12]. Os passos 3 e 4 são os mais caros computacionalmente, tanto em tempo de execução como no armazenamento dos dados. As pesquisas atuais neste campo visam reduzir estes custos mantendo ou aumentando a precisão dos cálculos. Para isso, se fazem necessário os seguintes requisitos:

O número de iterações deve ser o menor possível.

As derivadas devem ser calculadas com eficiência, tanto na rapidez como na precisão.

Se usar a estimativa da Hessiana, esta deve ser o mais aproximada possível da Hessiana exata, de maneira que ao calcular a direção de busca esta deve ser a mais adequada possível. A estimativa da Hessiana é iniciada com uma matriz positiva ou negativa (dependendo do problema) definida e vai se atualizando a cada iteração conservando a positividade ou negatividade definida para obtermos uma direção de busca razoavelmente adequada.

Se usar a Hessiana exata e se é previsto que a direção de busca pode não ser adequada, a perturbação da Hessiana deve ser mínima possível para se obter uma boa direção de busca.

Aproveitar o máximo possível da esparsidade das matrizes K-K-T.

Ter eficiência na resolução do sistema linear levando em conta rapidez, esparsidade (se é o caso) e precisão.

ALGUNS TÓPICOS DE PESQUISA

Levando em conta os requisitos ditos acima os tópicos são os seguintes:

Diferenciação Autoámtica (Também chamada de diferenciação aritmética)

É um método para calcular computacionalmente gradientes e Hessianas de funções. Diferenciação automática é mais preciso e rápido do que os métodos numéricos comuns de derivação e também até mais rápido do que as derivadas feitas manualmente e fornecidas para o programa.

Este tópico tem despertado bastante interesse devido às vantagens e às suas inúmeras aplicações, sendo uma delas a resolução de problemas de otimização. Ver por exemplo [Griewank 1988] ^[13]e [Dixon 1993] ^[14].

Existem alguns "software" de diferenciação automática já disponíveis no mercado (www, ftp ou e-mail) para ser incorporado a "software" de otimização. O Laboratório Argonne [Fourer et al. (1996)] ^[7a] tem desenvolvido dois; o ADIFOR, implementado em FORTRAN 77 e que fornece as primeiras derivadas, e o ADOL-C desenvolvido em C/C++ e que fornece as derivadas de ordem arbitrária. O Rutherford Appleton Laboratory [Duff 1995] ^[15]desenvolveu o HSL_AD01 o qual fornece as primeiras e segundas derivadas.

Memória Limitada

A Hessiana estimada é iniciada como uma diagonal ou tridiagonal a qual é armazenada em vetores e as atualizações também são armazenadas em vetores. Durante o processo iterativo somente as últimas atualizações são armazenadas. As vantagens deste método são a economia no armazenamento na memória e também no número de operações, visto que nos métodos tradicionais quasi-Newton, as Hessianas estimadas são não-esparsas. Ver por exemplo [BYRD et al. 1994] ^[16]e [Hernández 1995] ^[8a].

Estimativa da Hessiana Esparsa

Atualiza-se a Hessiana levando-se em conta a esparsidade da matriz Hessiana usando métodos quasi-Newton. A vantagem destes métodos é de se obter a estimativa da Hessiana conservando-se a esparsidade. Este método não foi bem sucedido, até quando Fletcher [Flecher 1992] ^[17]reformulou o trabalho de Toint [Toint 1977] ^[18], dando um novo impulso a esta linha de pesquisa.

Outra linha de pesquisa é o uso do método Quasi-Newton particionado. Se as funções objetivo e restrições podem ser separadas em grupos parciais ("group partial separability") no processo de atualização da Hessiana estimada, consideram-se separadamente as Hessianas de cada grupo parcial de funções. Estas Hessianas normalmente são pequenas fazendo com que a Hessiana estimada a partir do Lagrangeano seja esparsa. Este método foi implementado em LANCELOTE ver [Conn et al. 1992] ^[1a].

Modificação da Matriz K-K-T durante a Fatorização

Seja H A^T
K-K- T =
A D

onde H é a Hessiana do Lagrangeano, A é a matriz jacobiana e D pode ser matriz diagonal ou nula dependendo do método usado. Nos métodos tradicionais, normalmente antes de formar a matriz K-K-T, verifica-se se H é positiva definida, se não adicionam-se valores na diagonal de H forçando-a a ser positiva definida como em [Hernandez 1995] ^[8b] e [Schnabel & Eskow 1988] ^[26]. Neste caso, como a Hessiana (ou sua aproximação) é positiva definida, obtém-se uma direção de busca adequada. Quando a Hessiana (ou sua aproximação) é positiva definida, isto garante a positividade definida da Hessiana reduzida. Por outro lado, para se obter uma direção de busca adequada basta que a Hessiana reduzida (ou sua aproximação) seja positiva definida e não a Hessiana (ou sua aproximação). Recentemente (ver [Fosgren & Murray 1993] ^[19], [Arioli et al. 1992] ^[20]e [Hernández 1995] ^[8c]) têm-se desenvolvido técnicas baseadas no esquema: durante a fatorização da matriz K-K-T, identifica-se se a Hessiana reduzida é ou não positiva definida; se não, no processo de fatorização, adicionam-se valores na submatriz que ainda tem de ser fatorada, usando-se uma determinada regra para que a Hessiana reduzida (ou sua aproximação) se torne positiva definida e continue a fatorização. Estas últimas técnicas são uma tentativa de reduzir a perturbação introduzida na matriz K-K-T ou H.

MÉTODOS DE BUSCA LINEAR E MÉTODOS DE REGIÃO DE CONFIANÇA

Os métodos podem ser divididos em dois tipos Região de Confiança e Busca Linear. Os métodos de região de confiança demandam que o passo esteja dentro de um raio de confiança e os de busca linear demandam que a busca seja ao longo de uma direção de descida para a F(x) (função objetivo).

Atualmente se inverte tanto no métodos de região de confiança como no de busca linear. Exemplo de "software" que usam métodos de região de confiança são LANCELOTE e BOX e que usam método de busca linear são OPALQP e MINOS .

Problemas com "Simple Bounds" (variáveis restritas)

Quando o problema possui variáveis restritas, podemos usar funções penalidade ou "Barriers". Os valores destas funções são adicionados somente na diagonal da Hessiana, evitando a adição de elementos não-zeros (fill-in's ) fora da diagonal, ver [Conn et al. 1992] ^[1b].

Outros métodos que podem ser usado são o de região de confiança como em BOX e o de Ponto de Cauchy Generalizado ("Generalized Cauchy Point") como em LANCELOT.

Método de Ponto Interior

Recentemente tem surgido a tentativa de usar métodos de ponto interior para problemas não lineares gerais de otimização como foi apresentado por [Sargent (1996)] ^[21] e [Forsgren et al. (1996)] ^[10]os quais tem obtidos bons resultados. Na versão futura ou segunda versão do LANCELOT [Conn et al. (1996) ] ^[22]os autores estão se concentrando em métodos de ponto interior para suprir algumas deficiências da versão atual (primeira versão).

Método de Resolução de Sistemas Lineares Simétricos Esparsos Indefinido

Como as matrizes K-K-T sempre são simétricas indefinidas em problemas restritos, faz-se necessário o uso de "software" robustos e eficientes para resolver sistemas lineares com estas características. Podem-se usar métodos iterativos mas [Conn et al. 1993] ^[2a] recomenda usar métodos diretos baseados em técnicas especiais para resolver estes tipos de sistemas, como em [Duff et al.. 1991] ^[23]. Um dos melhores "software" no mercado no momento com este fim é o MA47, a versão mais recente do MA27 (subrotina da Harwell Library) desenvolvida pelo Rutherford Appleton Laboratory, ver [Duff & Reid 1982] ^[24] e [Duff & Reid 1995] ^[27]. Destes "software" já existentes devem-se extrair os conhecimentos e construir um exclusivo de melhor qualidade.