• search hit 1 of 4
Back to Result List

## Extension of the Proximal Auxiliary Problem Method using Logarithmic-quadratic Distances - Convergence Theory and Numerical Investigations

### Erweiterung der Proximal Auxiliary Problem Methode auf logarithmisch-quadratische Distanzen - Konvergenztheorie und numerische Untersuchungen

• Variational inequality problems constitute a common basis to investigate the theory and algorithms for many problems in mathematical physics, in economy as well as in natural and technical sciences. They appear in a variety of mathematical applications like convex programming, game theory and economic equilibrium problems, but also in fluid mechanics, physics of solid bodies and others. Many variational inequalities arising from applications are ill-posed. This means, for example, that the solution is not unique, or that small deviations in the data can cause large deviations in the solution. In such a situation, standard solution methods converge very slowly or even fail. In this case, so-called regularization methods are the methods of choice. They have the advantage that an ill-posed original problem is replaced by a sequence of well-posed auxiliary problems, which have better properties (like, e.g., a unique solution and a better conditionality). Moreover, a suitable choice of the regularization term can lead to unconstrained auxiliary problems that are even equivalent to optimization problems. The development and improvement of such methods are a focus of current research, in which we take part with this thesis. We suggest and investigate a logarithmic-quadratic proximal auxiliary problem (LQPAP) method that combines the advantages of the well-known proximal-point algorithm and the so-called auxiliary problem principle. Its exploration and convergence analysis is one of the main results in this work. The LQPAP method continues the recent developments of regularization methods. It includes different techniques presented in literature to improve the numerical stability: The logarithmic-quadratic distance function constitutes an interior point effect which allows to treat the auxiliary problems as unconstrained ones. Furthermore, outer operator approximations are considered. This simplifies the numerical solution of variational inequalities with multi-valued operators since, for example, bundle-techniques can be applied. With respect to the numerical practicability, inexact solutions of the auxiliary problems are allowed using a summable-error criterion that is easy to implement. As a further advantage of the logarithmic-quadratic distance we verify that it is self-concordant (in the sense of Nesterov/Nemirovskii). This motivates to apply the Newton method for the solution of the auxiliary problems. In the numerical part of the thesis the LQPAP method is applied to linearly constrained, differentiable and nondifferentiable convex optimization problems, as well as to nonsymmetric variational inequalities with co-coercive operators. It can often be observed that the sequence of iterates reaches the boundary of the feasible set before being close to an optimal solution. Against this background, we present the strategy of under-relaxation, which robustifies the LQPAP method. Furthermore, we compare the results with an appropriate method based on Bregman distances (BrPAP method). For differentiable, convex optimization problems we describe the implementation of the Newton method to solve the auxiliary problems and carry out different numerical experiments. For example, an adaptive choice of the initial regularization parameter and a combination of an Armijo and a self-concordance step size are evaluated. Test examples for nonsymmetric variational inequalities are hardly available in literature. Therefore, we present a geometric and an analytic approach to generate test examples with known solution(s). To solve the auxiliary problems in the case of nondifferentiable, convex optimization problems we apply the well-known bundle technique. The implementation is described in detail and the involved functions and sequences of parameters are discussed. As far as possible, our analysis is substantiated by new theoretical results. Furthermore, it is explained in detail how the bundle auxiliary problems are solved with a primal-dual interior point method. Such investigations have by now only been published for Bregman distances. The LQPAP bundle method is again applied to several test examples from literature. Thus, this thesis builds a bridge between theoretical and numerical investigations of solution methods for variational inequalities.
• Variationsungleichungen bilden eine gemeinsame Grundlage, um die Theorie und Algorithmen zum Lösen verschiedener Probleme der mathematischen Physik, der Ökonomie und der Naturwissenschaften zu untersuchen. Als Problemklasse beinhalten sie nicht nur klassische nichtlineare Optimierungsprobleme, sondern auch Gleichgewichtsprobleme, Komplementaritätsprobleme, nichtlineare Gleichungssysteme und andere. Die aus Anwendungen stammenden Variationsungleichungen sind in den meisten Fällen schlecht gestellt. Beispielsweise führen kleine Störungen in den Eingangsdaten zu großen Abweichungen in der Lösung, oder es liegen nicht-eindeutige Lösungen vor. In diesen Fällen können Standard-Lösungsverfahren scheitern. Aus diesem Grund gewinnen Regularisierungsverfahren an Bedeutung, da sie das Ausgangsproblem in eine Folge von gut gestellten Hilfsproblemen überführen, welche beispielsweise eine eindeutige Lösung und eine bessere Kondition besitzen. Ferner kann durch eine geeignete Wahl des Regularisierungsterms erreicht werden, dass die Hilfsprobleme unrestringiert sind und sogar zu Optimierungsproblemen äquivalent sind. Die Fortentwicklung solcher Verfahren ist Gegenstand aktueller Forschung, an der wir uns mit dieser Arbeit beteiligen. So schlagen wir einen neuen, auf logarithmisch-quadratischer Regularisierung basierenden Algorithmus (LQPAP-Methode) vor, der die Vorteile des bekannten Proximal-Punkt Verfahrens mit dem sogenannten Auxiliary Problem Principle verbindet. Seine Untersuchung und Konvergenzanalyse ist eines der Hauptresultate der vorliegenden Dissertation. Die LQPAP-Methode knüpft dabei an den aktuellen Entwicklungsstand von Regularisierungsverfahren zum Lösen von Variationsungleichungen an, indem sie verschiedene in der Literatur vorgestellte Techniken zur Verbesserung der numerischen Stabilität der Verfahren aufgreift. So entsteht durch die Verwendung einer logarithmisch-quadratischen Distanzfunktion ein Innerer-Punkt-Effekt, der es erlaubt, die Hilfsprobleme als unrestringiert zu betrachten. Ferner arbeiten wir mit äußeren Operatorapproximationen, was für die numerische Lösung von Variationsungleichungen mit mengenwertigen Operatoren von Wichtigkeit ist. Außerdem werden inexakte Lösungen der Hilfsprobleme betrachtet und entsprechende Fehlerbedingungen verwendet. Als weiteren Vorteil der logarithmisch-quadratischen Distanz verifizieren wir, dass sie self-concordant ist (im Sinne von Nesterov/Nemirovskii), was die Anwendung der Newton Methode zum Lösen der Hilfsprobleme motiviert. Im numerischen Teil der Arbeit wird die LQPAP-Methode auf linear restringierte, differenzierbare und nicht differenzierbare, konvexe Optimierungsprobleme, sowie auf nicht symmetrische Variationsungleichungen mit co-koerziven Operatoren angewendet. Es kann häufig beobachtet werden, dass die Folge der Iterierten den Rand der zulässigen Menge erreicht, bevor sie in der Nähe einer Optimallösung ist. Vor diesem Hintergrund stellen wir die Strategie der Unter-Relaxierung vor, mit deren Hilfe die LQPAP-Methode robustifiziert wird. Ferner vergleichen wir die Ergebnisse mit einer entsprechenden Bregman-Distanz basierten Methode (BrPAP-Methode). Die Hilfsprobleme, die bei Anwenden der LQPAP-Methode auf differenzierbare, konvexe Optimierungsprobleme entstehen, werden mit der Newton Methode gelöst. Mit Testbeispielen werden verschiedene Experimente durchgeführt und ausgewertet, wie zum Beispiel eine adaptive Wahl des Start-Regularisierungsparameters und eine Kombination der Armijo- und Self-Concordanz-Schrittweite. Testbeispiele für nicht-symmetrische Variationsungleichungsprobleme sind in der Literatur kaum zu finden. Daher präsentieren wir einen geometrischen und analytischen Zugang, um Testbeispiele mit bekannter Lösung oder sogar einer bekannten Lösungsmenge zu generieren. Zur Lösung der Hilfsprobleme bei nicht-differenzierbaren, konvexen Optimierungsproblemen wird die bekannte Bundle-Technik angewendet. Dabei beschreiben wir detailliert die Vorgehensweise und gehen auf die Wahl der beteiligten Funktionen und Parameterfolgen ein. Solche Untersuchungen wurden bisher nur in Verbindung mit Bregman-Distanzen veröffentlicht. Die Effektivität dieses LQPAP-Bundle Verfahrens wird wiederum an akademischen Beispielen aus der Literatur getestet. Unsere Arbeit schlägt somit eine Brücke zwischen theoretischen und numerischen Untersuchungen von Lösungsverfahren für Variationsungleichungen.