Um método de redução para programação semi-infinita não linear baseado numa técnica de penalidade exacta

Abstract

Os problemas de programação semi-infinita (PSI) aparecem nas mais diversas áreas da Engenharia, tais como, no planeamento da trajectória de robôs, no controlo da poluição atmosférica, no planeamento da produção, no desenho óptimo de conjuntos de sinais e desenhos de filtros digitais. Esta tese é dedicada a problemas de PSI não linear na sua forma mais geral. Os problemas considerados são caracterizados por possuírem um número finito de variáveis e um conjunto infinito de restrições. Os métodos numéricos existentes para a resolução de problemas de PSI podem ser divididos em três classes principais: métodos de discretização, métodos das trocas e métodos de redução. Os métodos de redução são os que possuem melhores propriedades teóricas de convergência. São, também, os mais exigentes em termos numéricos uma vez que exigem a resolução de problemas auxiliares, em que se pretende a determinação de todos os óptimos globais e locais (optimização multi-local). Nas últimas décadas foram apresentados vários algoritmos para problemas de PSI. Contudo há pouco software disponível e nenhum fornece uma implementação de um método pertencente à classe de redução. Neste trabalho é proposto um algoritmo de redução local baseado na técnica de penalidade. A função usada considera uma extensão de uma função de penalidade de norma-1 aumentada. A escolha desta função de penalidade para propor a extensão às restrições finitas deve-se à obtenção de melhores resultados numéricos para um conjunto de problemas teste de PSI sem restrições finitas, em comparação com as funções de penalidade baseadas na norma 1, 2 e ∞ da violação das restrições. Fez-se o estudo das propriedades teóricas da função de penalidade estendida. É feita uma implementação do algoritmo de redução local proposto. O solver desenvolvido é designado por SIRedAl (Semi-Infinite Reduction Algorithm). Este solver foi implementado em MATLAB e é capaz de resolver problemas de PSI na forma mais geral com dimensão infinita máxima de 2. O código do solver usa dois algoritmos diferentes na minimização da função de penalidade e dois na resolução dos problemas multi-locais. O solver foi testado com 117 problemas teste da base de dados SIPAMPL e os resultados numéricos confirmaram a potencialidade do algoritmo proposto.

Semi-infinite programming (SIP) problems arise in several engineering areas such as, for example, robotic trajectory planning, production planning, digital filter design and air pollution control. This thesis is devoted to SIP problems in the most general form. These problems are characterized to have a finite number of variables and an infinite set of constraints. The existing numerical methods for solving SIP problems can be divided into three major classes: discretization, exchange and reduction type methods. The reduction type methods are the ones with better theoretical properties, but they are also the most de- manding in computation terms, since they require to solve sub-problems to the local and global optimality (multi-local optimization). In last decades several algorithms were proposed for SIP, but there are not many pu- blicly available software and none provides an implementation of a method belonging to the reduction type class. In this work we propose a reduction type algorithm based on a penalty technique. The penalty function used is an extension of a penalty function of 1-norm, allowing the inclu- sion of finite constraints. In order to define the best penalty function, a numerical study of penalty functions based on the standard 1, 2 and ∞ norms are performed, considering test problems without finite constraints. A theoretical study of the extended penalty function is also performed. The proposed reduction algorithm is implemented in a solver coined as SIRedAl (Semi- Infinite Reduction Algorithm). The solver has been implemented in MATLAB and is capable of solving SIP problems in the most general form with a maximum of two infinite variables. The solver code uses two different algorithms in the minimization of the penalty function and also two different algorithms for solving the multi-local problems. The solver has been tested with 117 test problems from the database SIPAMPL and numerical results confirmed the algorithm potential.