Aplicações, métodos e ferramentas para programação semi-infinita não linear

Abstract

Esta tese dedica-se à modelação e resolução de problemas de programação semi-infinita (PSI) não linear. Estes problemas são caracterizados por possuírem um número finito de variáveis e um conjunto infinito de restrições. A partir de uma compilação de problemas existentes na literatura da especialidade e com base na linguagem de modelação AMPL foi construída uma base de dados que contém actualmente cento e quarenta e quatro problemas. Adicionalmente foram integrados no pacote de software designado por SIPAMPL, uma interface que permite a ligação de um software de resolução à base de dados e um conjunto de ferramentas. Problemas de optimização de trajectórias de robôs e de desenho óptimo de conjuntos de sinais foram formulados como problemas de PSI e resolvidos por um método de discretização. Foi desenvolvida uma extensão da técnica de programação quadrática sequencial para a resolução de problemas de PSI, a qual se baseia numa parametrização linear das variáveis duais para obter a solução do problema quadrático dual. Através de uma estratégia de transcrição das restrições infinitas em restrições finitas que envolvem o uso de integrais, foram ainda desenvolvidos um método de penalidade e um método primal-dual de pontos interiores não admissível que requerem, pela natureza do problema finito definido, a utilização de fórmulas numéricas adaptativas para o cálculo de integrais. Para a implementação destes métodos e aproveitando as potencialidades do pacote SIPAMPL, foi criado o software NSIPS para a resolução de problemas de PSI. Este software permite que o utilizador altere de uma forma simples e eficaz os parâmetros dos métodos implementados, afinando-os para os problemas que pretende resolver. Os pacotes de software SIPAMPL e NSIPS encontram-se disponíveis ao público em geral e em conjunto suportam a PST desde a modelação de um problema até a sua resolução.

This thesis is devoted to modeling and solving nonlinear semi-infinite programming (SIP) problems. These problems have a finite number of variables and an infinite set of constraints. By collecting a set of problems from the SIP literature and using the AMPL modeling language, a database of problems was developed containing at present one hundred and forty four problems. Additionally an interface that connects a solver to the database and a set of tools were integrated in the software package ca SIPAMPL. Robot trajectory planning and optimal signals set problems were formulated as SIP problems and solved by a discretization method. An extension of the sequential quadratic programming technique for solving SIP problems was developed which is based on a linear parametrization of the dual variables to obtain the solution of the quadratic dual problem. Using a transcription of the infinite constraints into finite constraints involving integrals, we also developed a penalty method and an infeasible primal-dual interior point method that require, due to the defined finite problem, the use of adaptative numerical formulae for integral computations. To implement these methods and using the SIPAMPL facilities, a package called NSJPS was created for solving SIP problems. This software allows parameter modifications in a simple and powerful way to suit problems request. The software packages SIPAMPL and NSIPS are freely available and together they support SIP from problem modeling to its resolution.