Estudo de Problemas de Otimização Irrestrita via Método do Gradiente

Abstract

Otimização, direta ou indiretamente, é um tema muito presente no dia a dia acadêmico e industrial. Vários campos da ciência fazem uso das ferramentas de otimização com o objetivo de ajudar na tomada de decisão. Dentre eles, pode-se citar, agricultura, finanças, transporte, processos químicos, produtivos, recursos naturais, ambientais e energéticos, entre outros [1], [6]. Nesse processo, o objetivo é minimizar os maximizar certa variável, como o custo ou o lucro em determinado processo. Mais formalmente, pode-se dizer que otimização consiste em encontrar pontos de mínimo ou de máximo de uma função real sobre um conjunto de restrições. Isto pode ser expresso da seguinte forma: min f(x) sujeito a gi(x)  ai, i  1, 2, . . . , p (1) hj(x)  bj , j  1, 2, . . . , n (2) x  0 onde x é um vetor n-dimensional, f(x) é o funcional objetivo, gi(x) são restrições expressas por igualdade, hj(x) são restrições expressas por desigualdades e ai e bj são constantes. Problemas de otimização são classificados conforme a forma de f(x). Nesse contexto, se f(x) não for linear e/ou as restrições forem não lineares, tem-se o caso da programação não linear. Além disso, quando as restrições (1) e (2) são incluídas, tem-se problemas de otimização com restrições, caso contrário, tem-se problemas de otimização sem restrições. Neste trabalho será estudado problemas onde todas as funções usadas para definı-los são continuamente diferenciáveis e, normalmente, não lineares, isto é, o problema de programação não linear (PNL). O caso particular abordado é o problema irrestrito, ou seja, problemas de otimização sem restrições. O problema irrestrito pode ser considerado simples, em comparação aos demais problemas de PNL, e o estudo de suas propriedades, bem como dos métodos que o resolvam, é de fundamental importância em otimização, uma vez que muitos métodos de resolução de PNL fazem uso dos métodos que resolvem o caso irrestrito [2]. Para a obtenção da solução de um problema como o descrito acima, pode-se utilizar uma condição necessária de otimalidade, a qual permite a obtenção de uma candidata à solução analítica para o problema e, portanto, exata. Porém, em muitos casos, se torna difícil e até mesmo impraticável, obter uma candidata a solução analiticamente devido à complexidade das expressões envolvidas. Em casos como bolsista de Iniciação Cientıfica UTFPR †bolsista de Iniciação Cientıfica UTFPR esses, precisa-se utilizar métodos numéricos, com os quais é possível a obtenção de uma solução aproximada. Neste trabalho será estudado algumas situações que garantem a existência de um minimizador e, em seguida, é discutido as condições de otimalidade para o problema de otimização irrestrita. Algumas referências para este assunto são [3], [5], [6] e [7]. Para a resolução numérica do problema de PNL irrestrito será utilizada uma das técnicas mais conhecidas para minimizar uma função, o método clássico do gradiente, também chamado método de Cauchy. O método do gradiente é um processo iterativo que a cada etapa faz uma busca na direção do vetor gradiente da função objetivo no ponto corrente [4] e consiste em procurar o mínimo na direção de maior taxa de decrescimento da função objetivo a partir de uma solução inicial x0. Como o nome implica, os métodos gradientes usam explicitamente informação sobre a derivada para gerar um algoritmo eficiente para localizar o ponto ótimo. Uma das vantagens de métodos do tipo gradiente é que a informação da derivada da função permite alcançar o extremo com menor número de avaliações da função, ou seja, melhor eficiência computacional. Assim, o método gradiente requer como entrada uma solução inicial x0 e um procedimento que calcula o gradiente da função a ser maximizada (ou minimizada). Basicamente, o algoritmo pode ser descrito como um processo iterativo em que novos pontos xk1 são gerados a partir do ponto atual xk: xk1  xk  kf(xk) (3) onde f(xk) é a direção de busca linear, k representa o tamanho do passo a ser dado na direção de busca e k é o número de iterações. O algoritmo foi implementado em linguagem de programação com apoio do software matemático MatLab. No algoritmo implementado, a determinação do tamanho do passo k é deixado em aberto. Para validar os resultados, foram feitas comparações de diversos problemas de PNL da literatura, usando como método de resolução o método do gradiente e o Optimization Toolbox do MatLab, o qual é uma coleção de funções que estendem a capacidade do Matlab em resolver problemas de otimização. Portanto, este trabalho apresenta o desenvolvimento teórico das condições de otimalidade para problemas de otimização, bem como, o estudo de métodos iterativos para obter as soluções numéricas.