We introduce basic ideas of a nonsmooth Newton’s method and its application in solving semidefinite optimization (SDO) problems. In particular, the method can be used to solve both linear and nonlinear semidefinite complementarity problems. We also survey recent theoretical results in matrix functions and stability of SDO that are stemed from the research on the matrix form of the nonsmooth Newton’s method. / Singapore-MIT Alliance (SMA)

Cette thèse étudie l’évolution des marchés du gaz naturel en Europe jusqu’en 2035 en utilisant les outils de la modélisation. Le modèle proposé, intitulé GaMMES, repose sur une description oligopolistique des marchés et ses principaux avantages sont les suivants : un niveau de détail important de la structure économique de la chaîne gazière et une prise en compte endogène des contrats de long-terme en amont ainsi que de la substitution avec les produits pétroliers et le charbon, au niveau de la demande. Dans un premier temps, nous étudions la question de la sécurité d’approvisionnement en gaz en Europe et les conditions favorables à la régulation des marchés vulnérables au risque de rupture d’approvisionnement, notamment de la part de la Russie. Trois études de cas sont proposées selon le degré de dépendance et la nature de régulation en place : le marché allemand des années 1980 et les marchés actuels de la Bulgarie et de l’Espagne. Nous étudions en particulier l’évolution des caractéristiques des marchés en fonction du risque de rupture et le type de régulation à mettre en place afin d’assurer l’optimalité du bien-être social. Ensuite, nous proposons un modèle de type systèmes dynamiques afin de prendre en compte la substitution énergétique entre le charbon, le pétrole et le gaz naturel. Notre approche permet d’estimer une nouvelle forme fonctionnelle de la fonction de demande pour le gaz naturel, qui englobe à la fois la substitution énergétique et les inerties de consommation dues aux investissements des usagers finaux. Dans un troisième temps, nous utilisons cette fonction de demande dans un modèle d’équilibre partiel des marchés du gaz naturel en Europe. Le modèle GaMMES, écrit sous forme de problème de complémentarité, représente les principaux acteurs de l’industrie du gaz naturel en considérant leurs interactions stratégiques et les pouvoirs de marchés. Il a été appliqué au marché du gaz naturel en Europe du nord-est afin d’étudier l’évolution, jusqu’en 2035, de la consommation, des prix spot, des prix et volumes long-terme, de la production et de la dépendance par rapport aux imports étrangers. Finalement, nous proposons une extension stochastique du modèle GaMMES afin d’analyser l’impact de la forte fluctuation du prix du Brent sur les marchés gaziers. Une étude économétrique a été menée afin de calculer la loi de probabilité du prix du pétrole, lorsqu’il est modélisé en tant que variable aléatoire, dans le but de construire et pondérer l’arbre des scénarii. Les résultats permettent de comprendre comment l’aléa modifie les comportements stratégiques des acteurs, notamment au niveau des contrats de long-terme. Enfin, la valeur de la solution stochastique est calculée afin de quantifier l’importance de la prise en compte des fluctuations du prix du pétrole pour chaque acteur de la chaîne. / This thesis studies the evolution of the natural gas markets in Europe, until 2035, using optimization theory tools. The model we develop, named GaMMES, is based on an oligopolistic description of the markets. Its main advantages are the following: we consider an important level of detail in the economic structure of the gas chain and we endogenously take into account long-term contracts in the upstream as well as energy substitution between gas, oil, and coal in the demand. In the first part of this thesis, we study the issue of security of supply in Europe and the conditions under which it is necessary to regulate the gas markets that are strongly dependent on foreign imports. Three case studies are then presented, regarding the level of dependence and the markets' specificities: the German gas trade of the 1980s and the current Spanish and Bulgarian markets. We study in particular the evolution of the markets' outcome as a function of the supply disruption probability and the kind of regulation to implement in order to maximize the social welfare. In the second part, we develop a system dynamics model in order to capture fuel substitution between oil, coal, and natural gas. Our approach allows one to calculate a new functional form of the demand function for natural gas that contains energy substitution and consumption inertia effects due to end-users' investments. In the third part, we take advantage of our demand function and use it in a partial equilibrium model of natural gas markets in Europe. The GaMMES model, when written as a complementarity problem, describes the principal gas chain actors as well as their strategic interactions and market power. It was applied to the northwestern European gas trade to analyze the evolution of consumption, spot and long-term contract prices and volumes, production, and natural gas dependence, until 2035. In the last part, we present a stochastic extension of the GaMMES model in order to study the impact of the strong Brent price fluctuation on the gas markets. An econometric analysis allowed us to calculate the probability law of the oil price, when taken as a random variable, in order to construct the scenario tree and estimate its weights. Our results show how uncertainty changes the strategic behavior, in particular for the long-term contracting activity. Finally, the value of the stochastic solution is calculated to quantify the importance of taking into account randomness in the optimization programs of the gas chain actors.

In dieser Arbeit präsentieren wir eine neue Art von Newton-Verfahren mit Liniensuche, basierend auf Interpolation im Bildbereich nach Wedin et al. [LW84]. Von dem resultierenden stabilisierten Newton-Algorithmus wird theoretisch und praktisch gezeigt, dass er effizient ist im Falle von nichtsingulären Lösungen. Darüber hinaus wird beobachtet, dass er eine superlineare Rate von Konvergenz bei einfachen Singularitäten erhält. Hingegen ist vom Newton-Verfahren ohne Liniensuche bekannt, dass es nur linear von fast allen Punkten in der Nähe einer singulären Lösung konvergiert. In Hinsicht auf Anwendungen auf Komplementaritätsprobleme betrachten wir auch Systeme, deren Jacobimatrix nicht differenzierbar sondern nur semismooth ist. Auch hier erreicht unser stabilisiertes und beschleunigtes Newton- Verfahren Superlinearität bei einfachen Singularitäten. / In this thesis we present a new type of line-search for Newton’s method, based on range space interpolation as suggested by Wedin et al. [LW84]. The resulting stabilized Newton algorithm is theoretically and practically shown to be efficient in the case of nonsingular roots. Moreover it is observed that it maintains a superlinear rate of convergence at simple singularities. Whereas Newton’s method without line-search is known to converge only linearly from almost all points near the singular root. In view of applications to complementarity problems we also consider systems, whose Jacobian is not differentiable but only semismooth. Again, our stabilized and accelerated Newton’s method achieves superlinearity at simple singularities.

<p><span style="left: 81.5833px; top: 720.322px; font-size: 17.5px; font-family: serif; transform: scaleX(1.07268);">U doktorskoj disertaciji razmatrani su iterativni postupci za re&scaron;avanje nelinearnih komplementarnih problema (NCP). Problemi ovakvog tipa javljaju se u teoriji optimizacije, inženjerstvu i ekonomiji. Matematički modeli mnogih prirodnih, dru&scaron;tvenih i tehničkih procesa svode se takođe na ove probleme. Zbog izuzetno velike zastupljenosti NCP problema, njihovo re&scaron;avanje je veoma aktuelno. Među mnogobrojnim numeričkim postupcima koji se koriste u tu svrhu, u ovoj disertaciji posebna pažnja posvećena je<br />generalizovanim postupcima Njutnovog tipa i iterativnim postupcima sa re-gularizacijom matrice jakobijana. Definisani su novi postupci za re&scaron;avanje NCP i dokazana je njihova lokalna ili globalna konvergencija. Dobijeni teorijski rezultati testirani su na relevantnim numeričkim primerima. </span></p> / <p>Iterative methods for nonlinear complementarity problems (NCP) are con-sidered in this doctoral dissertation. NCP problems appear in many math-ematical models from economy, engineering and optimization theory. Solv-ing NCP is very atractive in recent years. Among many numerical methods for NCP, we are interested in generalized Newton-type methods and Jaco-bian smoothing methođs. Several new methods for NCP are defined in this dissertation and their local or global convergence is proved. Theoretical results are tested on relevant numerical examples.</p>