Otimização com restrições de complementaridade: algoritmos e aplicações

Tese de Doutoramento em Engenharia Industrial e de Sistemas (PDEIS)

Nesta tese estuda-se o problema de otimização com restrições de complementaridade, do inglês Mathematical Program with Complementarity Constraints (MPCC). É um problema de otimização não linear com restrições, que para além das habituais restrições, inclui ainda as de complementaridade. O conceito de complementaridade está relacionado com o equilíbrio de um sistema, originando uma grande variedade de aplicações em áreas, tais como a Engenharia e a Economia. O problema MPCC também pode surgir da otimização a dois níveis, do inglês bilevel - quando o problema de otimização de nível inferior pode, sob certas condições, ser substituído pelas respetivas condições de otimalidade de primeira ordem, formula-se um problema MPCC. Uma das formas de resolução do problema MPCC, consiste na sua reformulação num problema NLP (NonLinear Program) equivalente. Todavia, a natureza disjuntiva das restrições de complementaridade, causa problemas de índole teórica e numérica, uma vez que as qualificações de restrição usadas para garantir a convergência dos algoritmos, falham em todos os pontos admissíveis. O problema MPCC é de difícil resolução e tem sido estudado por vários investigadores. Estudos recentes provaram que a estacionaridade forte do MPCC, é equivalente às condições de otimalidade de primeira ordem do problema NLP equivalente. Desta forma, as técnicas normalmente utilizadas nos algoritmos para resolver problemas NLP, têm vindo a ser introduzidas com sucesso nos algoritmos de resolução dos problemas MPCC. Entre elas, realçam-se o método PQS (Programação Quadrática Sequencial) e as técnicas de penalidade. Este trabalho pretende desenvolver e implementar algoritmos para resolução do problema MPCC, bem como a modelação e resolução de dois casos reais. Nos algoritmos desenvolvidos, conjugam-se técnicas da otimização não linear para tratamento das restrições de complementaridade, nomeadamente, estratégias de penalidade, relaxação e suavização. Foram implementadas três estratégias - o método de penalidade hiperbólica, o esquema de relaxação modificado e a função de suavização hiperbólica. Para a implementação destes algoritmos utilizaram-se a linguagem de modelação matemática AMPL e a linguagem de programação MATLAB. São feitos testes computacionais aos algoritmos usando um conjunto de problemas teste em AMPL, da base de problemas MacMPEC. É feita uma análise comparativa de desempenho dos algoritmos, relativamente a algumas métricas. O segundo objetivo do trabalho consiste na modelação e codificação em linguagem AMPL de duas aplicações reais utilizando a formulação MPCC, e a sua resolução pelos algoritmos implementados. São estudados um problema de média dimensão relacionado com uma situação real de congestionamento de tráfego urbano e um problema de posicionamento de um apoio redundante numa viga.

In this thesis the Mathematical Program with Complementarity Constraints (MPCC) is studied. It is a nonlinear constrained optimization problem, which besides the usual nonlinear constraints, also includes the complementarity ones. The complementarity concept is related to the system´s equilibrium, having several applications in areas like Engineering and Economics. The MPCC problem also arises from the bilevel optimization - when the lower level optimization problem can, under some assumptions, be replaced by its first order optimality conditions, an MPCC problem is formulated. One way to solve the MPCC problem is to use its reformulation in an equivalent NLP problem. However, the disjunctive nature of the complementarity constraints, introduces issues of theoretical and numerical indole, since the constraint qualifications used to ensure algorithms convergence, fail into all feasible points. The MPCC problem is difficult to solve and has been studied by many researchers. Recent studies have proven that the strong stationarity of the MPCC problem, is equivalent to the first order optimality conditions of the equivalent NLP problem. Thus, the techniques usually used in the algorithms for solving NLP problems, have been successfully introduced in the specific algorithms to solve MPCC problems. Among them, stand out from the SQP method (Sequential Quadratic Programming) and the penalty techniques. This work aims to develop and implement MPCC solving algorithms, as such two real cases will be modeled and solved. The algorithms join several nonlinear optimization techniques to handle the complementarity constraints, namely penalty, relaxation and smoothing strategies. Three strategies were implemented - the hyperbolic penalty method, the modified relaxation method and the hyperbolic smoothing function. The AMPL modeling and the MATLAB computational languages were used to codify the algorithms. To test them, computational experiments are performed using a set of AMPL test problems, from the MacMPEC database. A performance comparative analysis with respect to some metrics is carried out. The second goal of the work is to model and to codify in AMPL language two real applications using MPCC formulation as well as its resolution by the algorithms developed. A medium size problem related to a real situation of urban traffic congestion and a problem of positioning a redundant support in a beam, are studied.