Implementation and Performance Analysis of Interior-Point Methods for Solving Mathematical Programs with Complementarity Constraints

Abstract

Denne avhandlinga tar for seg implementering og evaluering av løysningsmetodar for matematiske program med komplementaritetsavgrensingar, også kjent som MPCC. Desse løysningsmetodane baserer seg på ein bestemt optimaliseringsmetode nærmare kjent som indrepunktmetoden. MPCC er eit kraftig rammeverk for å modellere system der komplementaritetsrelasjonar er til stades. Desse relasjonane er funne i kombinasjon med mange reelle problem, slik at effektive løysningsstrategiar er avgjerande. MPCC er svært utfordrande å løyse ettersom dei er ikkje-konvekse optimaliseringsproblem, som bryt med fundamentale konsept innanfor optimalisering. For å handtere desse problema, har det blitt foreslått to ulike løysningsstrategiar i litteraturen, nærmare kjent som den klassiske og dynamiske metoden. Implementeringa av desse metodane har i denne avhandlinga basert seg på eksisterande optimaliseringsløysara som brukar indrepunktmetoden. Den dynamiske framgangsmåten skil seg frå den klassiske ved at den tilet hyppigare justeringar av straffeparameteren. Denne parameteren er i kostnadsfunksjonen og bestemmer vektinga av tilfredsstillinga til komplementaritetsavgrensingane. For å samanlikne metodane blei ein internt utvikla løysar brukt som grunnlag for implementeringa, og metodane blei anvendt på mindre komplekse problem. Resultat frå denne undersøkinga demonstrerte at begge metodane presterte generelt bra, men at den dynamiske metoden overgjekk den klassiske metoden i spesifikke tilfelle. IPOPT blei vidare brukt som grunnlag for implementeringane, ettersom ein velutvikla løyser var nødvendig for å undersøke metodane ytterlegare. Det var i midlertidig utfordrande å inkorporera algoritmane med denne løysaren, ettersom løysaren og grensesnittet forbaud brukaren tilgang til visse trinn i løysaren. Til tross for dette blei implementeringa av den klassiske algoritmen tilstrekkeleg og vidare brukt for å simulera ein multikomponent flashtank med faseendringar. Den stasjonære simuleringa blei vellykka gjennomført, medan den dynamiske simuleringa bydde på fleire utfordringar. Fleire justeringar var nødvendig for å oppnå ei simulering som var i tråd med dei fysiske forventingane. Vidare forsking bør i midlertidig fokusera på å forbetra integrasjonen med dei eksisterande løysarane, slik at ei betre implementering av algoritmane kan bli oppnådd. Det er også forbetringspotensial i flashtankmodellen, da problema som oppstod kan skyldast ei dårleg, ikkje-unik modellformulering. Til tross for problema som oppstod undervegs, viser den klassiske og den dynamiske algoritmen eit lovande potensial. Ytterlegare eksperimentering er uansett nødvendig for å trekke ein endeleg konklusjon om metodane.

The aim of this thesis is to implement and evaluate interior-point methods for mathematical programs with complementarity constraints, MPCC. MPCC has become a powerful framework for modelling systems with complementarity relationships. These relationships are present in many practical problems, such that effective solving strategies are crucial. However, complementarity constraints present specific difficulties due to their inherent nonconvex nature and violation of essential constraint qualifications. In order to tackle these challenges, two potential solution strategies have been proposed in the literature, the Classic and Dynamic approaches. These approaches are based on a penalty reformulation and were, in this thesis, implemented as extensions of existing interior-point-based algorithms for nonlinear optimisation. However, the Dynamic approach differs from the Classic by allowing greater flexibility in adjusting the penalty parameter. In order to evaluate their performance, an in-house developed solver was used as the foundation for their implementations. After conducting a small-scale problem investigation, it was observed that both algorithms performed well overall, but the Dynamic algorithm outperformed the Classic when unbounded penalty problems were confronted. To further investigate the methods, IPOPT was used as the basis as a more advanced solver was required for this purpose. However, it was challenging to incorporate the additional features as this solver prohibits access to specific steps. Despite this, the integration of the Classic implementation was deemed sufficient and applied to a multi-component flash tank where phase changes were modelled through complementarity constraints. The steady-state simulations were successfully conducted, while the dynamic simulation presented a significant challenge and needed multiple adjustments. Despite this, a successful simulation which agreed with the physical expectations was eventually obtained. Further research should, however, focus on improving the integration with the existing solvers to obtain a better implementation of the algorithms. Additional model modifications may also be necessary, as poorly posed, and non-unique model formulations may be the blame for the problems encountered. Despite the difficulties faced, the Classic and Dynamic methods appeared promising, but further investigations are necessary before a definitive conclusion can be drawn.