New Trust Region SQP Methods for Continuous and Integer Optimization

Titelangaben

Exler, Oliver:
New Trust Region SQP Methods for Continuous and Integer Optimization.
Bayreuth , 2013 . - VI, 171 S.
( Dissertation, 2013 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

In this thesis new algorithms are presented that address nonlinear optimization problems. The algorithms belong to the class of sequential quadratic programming (SQP) methods. Two problem formulations that arise frequently in real-world applications are considered. Both have in common that functions are nonlinear and the formulations contain equality and inequality constraints. For the one class of problems the domain of all variables is R. These problems are called nonlinear programming (NLP) problems. Many applications also require that some of the featured variables are restricted to the domain Z. Problems with additional integer variables are called mixed-integer nonlinear programs (MINLP) and are also considered here. This work is motivated by the advancement of an algorithm for solving MINLPs that was first discussed by Exler and Schittkowski (2007). The algorithm adapts concepts of SQP methods to mixed-integer nonlinear optimization. The new approach replaces the continuous quadratic problems by mixed-integer quadratic problems. The aim is to profit from the fast local convergence properties of SQP methods at least with respect to the continuous variables when integer variables remain fixed. Two new versions of the underlying algorithm of Exler and Schittkowski are presented. It is well-known that SQP methods might not converge for any arbitrary starting point. To obtain global convergence, techniques of trust region methods are employed by the new algorithms. The first version of an algorithm for MINLPs presented in this thesis employs the Linf-penalty function as merit function. Applying this penalty function might lead to a slow convergence. The so-called Maratos effect requires the reduction of the step length so that fast convergence is lost. Hence, safeguards have to be added. The presented algorithm calculates additional second order correction (SOC) steps. Calculating SOC steps is a frequently used approach to obtain fast local convergence. There also exist other techniques. The SOC steps require additional function evaluations. Frequently, function values of mixed-integer problems arising in the field of engineering are evaluated by running time-consuming simulation tools, where a single function evaluation can take minutes or even hours. Thus, the goal of the development of an efficient method has to be that the number of needed function evaluations is as small as possible. For that reason the investigation of methods that obtain fast local convergence without calculating SOC steps is the key aspect of this thesis. As a fundamental theory is available for NLPs, whereas MINLPs lack in most of these concepts, the main part of this thesis presents and analyzes a new trust region SQP algorithm addressing NLPs. The algorithm proposed here avoids the calculation of SOC steps by using an augmented Lagrangian function as merit function. In trust region methods a differentiable merit function, such as an augmented Lagrangian function, was employed in the past for equality constrained problems. Methods that also treat inequality constraints, transform these constraints into equality constraints. The new algorithm does not reformulate the underlying problem. The proposed algorithm for NLPs is described in detail. The global and local convergence properties of the new algorithm are investigated. Under suitable assumptions it is shown that for any arbitrary starting point the sequence of generated iterates contains at least one accumulation point that is a Karush-Kuhn-Tucker point of the underlying NLP. Under certain conditions fast local convergence is proved, as full SQP steps will be accepted close to a solution. Thus, no additional SOC steps are required. Due to the insight that is gained by the development of the algorithm for NLPs, an additional version of the algorithm for MINLPs can be stated. The second algorithm also enhances the algorithm of Exler and Schittkowski (2007), but does not calculate SOC steps anymore and the extra function evaluations are avoided. All presented algorithms are implemented in FORTRAN and completely documented. The code is evaluated on a set of almost 500 test problems. Numerical results show the good performance of the new algorithms. The numerical tests of the algorithm for NLPs indicate that the theoretical convergence results hold in practice. Moreover, the efficiency of the second algorithm for MINLPs that does not calculate SOC steps has improved compared to the first version with SOC steps

Abstract in weiterer Sprache

Diese Arbeit stellt neue Verfahren zur Lösung restringierter nichtlinearer Optimierungsprobleme vor. Die Algorithmen lassen sich den sequentiellen quadratischen Optimierungsverfahren (SQP) zuordnen. Es werden zwei Arten von Problemstellungen betrachtet. Die Probleme der einen Klasse werden als nichtlineare Optimierungsprobleme (NLP) bezeichnet. Sie zeichnen sich dadurch aus, dass der Wertebereich aller Optimierungsvariablen reell ist. Die zweite Problemklasse umfasst die gemischt-ganzzahligen nichtlinearen Probleme (MINLP). Zusätzlich zu reellen Variablen treten bei MINLPs Variablen auf, deren Wertebereich auf die ganzen Zahlen beschränkt ist. Die betrachteten Probleme beider Klassen weisen Gleichungs- und Ungleichungsnebenbedingungen auf. Motiviert ist die Arbeit durch die Weiterentwicklung eines neuartigen Algorithmus zur Lösung von MINLPs, der erstmals von Exler und Schittkowski (2007) diskutiert wurde. Es handelt sich um eine Erweiterung der SQP Verfahren für die gemischt-ganzzahlige Optimierung. Der Ansatz ersetzt die kontinuierlichen Teilprobleme durch gemischt-ganzzahlige quadratische Probleme. Ziel ist es von den guten Konvergenzeigenschaften der SQP Verfahren bezüglich der kontinuierlichen Variablen zu profitieren. Es werden zwei neue Varianten des ursprünglichen Algorithmus vorgestellt. Es ist bekannt, dass die Konvergenz eines SQP Verfahrens ohne zusätzliche Maßnahmen nicht für jeden beliebigen Startwert garantiert werden kann. Um die globale Konvergenz sicherzustellen, werden Techniken der Trust-Region-Verfahren angewandt. In der ursprünglichen Fassung von Exler und Schittkowski verwendet der Algorithmus zur Lösung von MINLPs die Linf-Penalty Funktion. Ohne spezielle Strategien kann bei Verwendung dieser Funktion die schnelle lokale Konvergenz von SQP Verfahren gestört werden. Das Auftreten des sogenannten Maratos-Effekts führt zu einer unnötigen Verkleinerung der Schrittlänge im Verfahren. Beim ersten hier vorgestellten Algorithmus für MINLPs werden zusätzliche Korrekturschritte zweiter Ordnung berechnet – second order correction (SOC) steps. Die Berechnung von SOC Schritten ist einer von mehreren möglichen Ansätzen, um die schnelle lokale Konvergenz zu bewahren. Diese Schritte erfordern jedoch weitere Funktionsauswertungen. Bei MINLPs aus der Anwendung im Ingenieurwesen geschieht die Bestimmung von Funktionswerten jedoch oftmals durch aufwendige Simulationscodes, so dass eine einzelne Funktionsauswertung bereits Minuten oder sogar Stunden dauern kann. Das Ziel muss es folglich sein, die Anzahl der erforderlichen Funktionsauswertungen möglichst gering zu halten. Aus diesem Grund steht die Untersuchung von Methoden im Vordergrund, die lokal schnell konvergieren und dabei auf die Berechnung von SOC Schritten verzichten können. Da für NLPs fundierte theoretische Grundlagen vorliegen, die für MINLPs teilweise nicht existieren, liegt der Schwerpunkt dieser Arbeit auf der Entwicklung und theoretischen Analyse eines neuen Algorithmus zur Lösung restringierter nichtlinearer Optimierungsprobleme der Problemklasse NLP. Der neue Algorithmus verwendet als Meritfunktion eine erweiterte Lagrange-Funktion. Die schnelle lokale Konvergenz bleibt auch ohne zusätzliche SOC Schritte erhalten. Die Verwendung einer differenzierbaren Meritfunktion, wie der erweiterten Lagrange-Funktion, wurde für SQP Verfahren in Kombination mit Trust-Region-Verfahren für gleichheitsrestringierte Probleme bereits untersucht. Verfahren, die auch Ungleichungen betrachten, überführen die Ungleichungen oftmals durch Schlupfvariablen in Gleichungen. Der Ansatz dieser Arbeit behandelt Ungleichungen ohne eine solche Umformung. Der neue Trust Region SQP Algorithmus für NLPs wird hinsichtlich seiner theoretischen Konvergenzeigenschaften analysiert. Hierbei wird sowohl auf die globale, als auch auf die lokale Konvergenz eingegangen. Es wird gezeigt, dass die von dem Algorithmus erzeugte Folge von Iterationspunkten unter geeigneten Voraussetzungen für jeden beliebigen Startpunkt mindestens einen Häufungspunkt besitzt, welcher die Karush-Kuhn-Tucker Bedingungen des Ausgangsproblems erfüllt. Ist die generierte Folge von Iterationspunkten nahe genug am Optimum, so werden unter geeigneten Voraussetzungen volle SQP Schritte akzeptiert und eine schnelle lokale Konvergenz tritt ein. Teile des kontinuierlichen Algorithmus fließen in eine modifizierte Variante des gemischt-ganzzahligen Algorithmus von Exler und Schittkowski (2007) ein. Es findet keine Berechnung von Korrekturschritten mehr statt, so dass die zusätzlichen Funktionsauswertungen vermieden werden. Alle entwickelten Algorithmen liegen als FORTRAN Implementierungen vor. Die Effizienz der Verfahren und ihrer Implementierungen wird anhand einer Vielzahl von Testproblemen demonstriert.