Complementaridade linear e aplicação em optimização global

Abstract

O Problema Linear Complementar (LCP) consiste em determinar vectores tais que Este problema tem um elevado número de aplicações em vários ramos da ciência, engenharia e economia e tem recebido grande interesse nos últimos anos. o LCP é em geral um problema NP-completo. Contudo o LCP pode ser resolvido em tempo polinomial quando a sua matriz satisfaz determinadas propriedades e existem vários algoritmos para o resolver nestes casos. Esta tese debruça-se sobre a resolução do LCP sem hipóteses restritivas na classe da matriz M. Além disso são consideradas duas extensões do LCP (BLCP e GLCP) e estudadas as aplicações de todos estes problemas complementares na resolução de alguns problemas de optimização global. Nesta tese é proposto um algoritmo enumerativo híbrido para a resolução dos LCP e GLCP e sua implementação para problemas de media e grande dimensões e estrutura esparsa. E também desenvolvido um algoritmo Sequencial LCP (SLCP) para a resolução de um problema linear complementar com uma função linear para minimizar (MLCP). Nesse processo, uma solução óptima do MLCP e determinada a partir da resolução de urna sucessão de LCPs ou GLCPs. Este algoritmo é usado para determinar mínimos globais de alguns problemas importantes de optimização global, nomeadamente problemas bilineares, quadráticos não convexos e problemas de dois níveis. Neste trabalho são ainda propostas duas extensões dos algoritmos de Keller e de Lemke para o BLCP e dois novos métodos polinomiais para a resolução de casos especiais dos LCP e BLCP côncavos, conjuntamente com as suas implementações para problemas de grandes dimensões. 0 programa quadrático côncavo (CQP) com apenas limites nos valores das variáveis tem merecido muito interesse nos ültimos anos. Este problema e também tratado nesta tese, apresentando-se um algoritmo que facilita a pesquisa de um mínirno global. E também descrita urna implementação eficiente para CQPs de grandes dimensões. Este trabalho inclui ainda urna vasta experiência computacional com todos os processos referidos que atestam a validade das nossas propostas.