Luận án TS: Phương pháp điểm gần trong giải bài toán cân bằng tại Đại học Namur

Institutional Repository - Research Portal Dépôt Institutionnel - Portail de la Recherche researchportal.be University of Namur THESIS / THÈSE DOCTOR OF SCIENCES Towards interior proximal point methods for solving equilibrium problems Author(s) - Auteur(s) : Nguyen, Thi Thu Van Award date: 2008 Awarding institution: University of Namur Supervisor - Co-Supervisor / Promoteur - Co-Promoteur : Link to publication Publication date - Date de publication : Permanent link - Permalien : Rights / License - Licence de droit d’auteur : General rights Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. • Users may download and print one copy of any publication from the public portal for the purpose of private study or research. • You may not further distribute the material or use it for any profit-making activity or commercial gain • You may freely distribute the URL identifying the publication in the public portal ? Take down policy If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately and investigate your claim. Bibliothèque Universitaire Download date: 02.

2024 Moretus Plantin Facultés Universitaires Notre-Dame de la Paix Namur Faculté des Sciences Département de Mathematique Towards Interior Proximal Point Methods for Solving Equilibrium Problems Dissertation présentée par Nguyen Thi Thu Van pour l’obtention du grade de Docteur en Sciences Composition du Jury: Jean-Jacques S TRODIOT (Promoteur) Van Hien N GUYEN (Co-promoteur) L E Dung Muu Michel W ILLEM Joseph W INKIN September 2008 c Presses universitaires de Namur & Nguyen Thi Thu Van Rempart de la Vierge, 13 B-5000 Namur (Belgique) Toute reproduction d’un extrait quelconque de ce livre, hors des limites restrictives prévues par la loi, par quelque procédé que ce soit, et notamment par photocopie ou scanner, est strictement interdite pour tous pays. Imprimé en Belgique ISBN-13 : 978-2-87037-614-0 Dépôt légal: D / 2008 / 1881 / 42 Acknowledgements I am indebted to my PhD supervisor, Professor Jean-Jacques STRODIOT, for his guidance and assistance given during the preparation of this thesis. It is from Prof. STRODIOT that I have not only systematically learned functional analysis, convex analysis, optimization theory and numerical algorithms but also how to conduct research and to write up my findings coherently for publication.

He has even demonstrated how to be a good teacher via teaching me how to write lesson plans and how to present scientific semi- nars. A debt I will not be able to repay but one I am most grateful for. The only thing I can do is to try my best to practice these skills and to pass on my new found knowledge to future students. Secondly, I would like to express my deep gratitude to Professor Van Hien NGUYEN, my co- supervisor, for his guidance, continuing help and encouragement.

I would probably not have had such a fortunate chance to study in Namur without his help. I really appreciate his useful advice on my thesis and especially thank him for the amount of time he spent reading my papers and providing valuable suggestions. It is also from Prof. Hien that I have learned to work in the spirit to willingly share time with others and to be helpful at heart.

I would like to thank my committee members, Professors LE Dung Muu, Michel WILLEM, and Joseph WINKIN for really practical and constructive comments. I would also like to thank CIUF (Conseil Interuniversitaire de la Communauté Française) and CUD (Commission Universitaire pour le Développement) for financial support given during two training place- ments, 3 months in 2001 and 6 months in 2003, at the University of Namur. I further like to address my thanks to the University of Namur for the financial support received for my PhD research, from 2004 until 2008. I also want to thank the Department of Mathematics, especially the Unit of Optimization and Control for the generous help they have provided me.

On this occasion, I want to thank my friends in the Department of Mathematics for their warm support and for their help during my stay in Namur, namely Jehan BOREUX, Delphine LAMBERT, Anne-Sophie LIBERT, Benoît NOYELLES, Simone RIGHI, Caroline SAINVITU, Geneviève SALMON, Stéphane VALK, Emilie WANUFELLE, Melissa WEBER MENDONÇA, and Sebastian XHONNEUX. Last but not least, special thanks are also given to Professor NGUYEN Thanh Long of the University of Natural Sciences - Vietnam National University, Ho Chi Minh City for everything he has done for me. He has not only helped me to do research but also offered me many training courses which allowed me to earn my living. He always listens patiently to me and gives me valuable advice.

His attitude in doing research motivates me to work harder. Xin bày tỏ lòng biết ơn đến các Thầy Cô giáo tại khoa Toán - Tin học, trường Đại học Khoa học Tự Nhiên - Đại học Quốc Gia Thành phố Hồ Chí Minh và các Giáo sư tại Viện Toán học Hà Nội đã quan tâm và giúp đỡ tác giả trong thời gian qua. Xin chân thành cảm ơn các chị, anh, em đang sinh sống, làm việc và học tập tại Bỉ và các bạn bè đồng nghiệp xa gần đã luôn bên cạnh động viên và giúp đỡ tác giả trong suốt quá trình học tập và nghiên cứu tại Bỉ. Luận án này là món quà tinh thần tác giả xin kính tặng đến Gia đình của mình với tất cả lòng biết ơn, yêu thương và trân trọng.

Nguyễn Thị Thu Vân Abstract: This work is devoted to study efficient numerical methods for solving nonsmooth convex equilibrium problems in the sense of Blum and Oettli. First we consider the auxiliary problem principle which is a generalization to equilibrium problems of the classical proximal point method for solving convex minimization problems. This method is based on a fixed point property. To make the algorithm implementable we introduce the concept of µ-approximation and we prove that the convergence of the algorithm is preserved when in the subproblems the nonsmooth convex functions are replaced by µ-approximations.

Then we explain how to con- struct µ-approximations using the bundle concept and we report some numerical results to show the efficiency of the algorithm. In a second part, we suggest to use a barrier function method for solving the subproblems of the previous method. We obtain an interior proximal point al- gorithm that we apply first for solving nonsmooth convex minimization problems and then for solving equilibrium problems. In particular, two interior extragradient algorithms are studied and compared on some test problems.

Résumé: Ce travail est consacré à l’étude de méthodes numériques efficaces pour résoudre des problèmes d’équilibre convexes non différentiables au sens de Blum et Oettli. D’abord nous considérons le principe du problème auxiliaire qui est une généralisation aux problèmes d’équilibre de la méthode du point proximal pour résoudre des problèmes de minimisation con- vexes. Cette méthode est basée sur une propriété de points fixes. Pour rendre l’algorithme implémentable nous introduisons le concept de µ-approximation and nous montrons que la convergence de l’algorithme est préservée lorsque dans les sous problèmes la fonction convexe non différentiable est remplacée par une µ-approximation.

Nous expliquons ensuite comment construire cette approximation en utilisant le concept de faisceaux et nous présentons des ré- sultats numériques pour montrer l’efficacité de l’algorithme. Dans une seconde partie nous suggérons d’utiliser une méthode de type barrière pour résoudre les sous problèmes de la méth- ode précédente. Nous obtenons un algorithme de point proximal intérieur que nous appliquons à la résolution des problèmes de minimisation convexes non différentiables et ensuite à celle des problèmes d’équilibre. En particulier nous étudions deux algorithmes de type extragradient intérieurs que nous comparons sur des problèmes tests.

Contents 1 Introduction 1 2 Proximal Point Methods 7 2.1 Convex Minimization Problems .1 Classical Proximal Point Algorithm .2 Bundle Proximal Point Algorithm .1 Existence and Uniqueness of Solutions .2 Proximal Point Algorithms .3 Auxiliary Problem Principle .4 Gap Function Approach .6 Interior Proximal Point Algorithm. 37 3 Bundle Proximal Methods 41 3.3 Bundle Proximal Algorithm .4 Application to Variational Inequality Problems. 60 4 Interior Proximal Extragradient Methods 67 4.2 Interior Proximal Extragradient Algorithm .3 Interior Proximal Linesearch Extragradient Method. 83 i 5 Bundle Interior Proximal Algorithm for Convex Minimization Problems 87 5.2 Bundle Interior Proximal Algorithm.

98 6 Conclusions and Further Work 103 ii Chapter 1 Introduction Equilibrium can be defined as a state of balance between opposing forces or influences. This concept is usually used in many scientific branches as physics, chemistry, economics and en- gineering. For example, in physics, the equilibrium state for a system, in terms of classical mechanics, means that the impact of all the forces on this system equals zero and that this state can be maintained for an indefinitely long period. In chemistry, it is a state where a forward chemical reaction and its reverse reaction proceed at equal rates.

In economics, the concept of an equilibrium is fundamental. A simple example is given by a market where consumers and producers buy and sell, respectively, a homogeneous commodity, their reaction depending on the current commodity price. More precisely, given a price p, the consumers determine their total demand D(p) and the producers determine their total supply S(p), so that the excess demand of the market is E(p) = D(p) − S(p). If we consider a certain amount of transactions between consumers and producers then there exists the equality between the partial supply and demand at each price level, but the problem is to find the price which implies the equality between the total supply and demand, i.

This is called an equilibrium price model and corresponds to the classical static equilibrium concept, where the impact of all the forces equals zero, i., it is the same as in mechanics. Moreover, this price implies constant clearing of the market and may be maintained for an indefinitely long period. For a detailed study of Equilibrium Models, the reader is referred to the book by Konnov [49]. The equilibrium problem theory has been receiving growing interest by researchers, espe- cially in economics.

Many Nobel Prize winners, such as K. Nash (1994), were awarded for their contributions in this field. Recently the main concepts of optimization problems have also been extended to the field of equilibrium problems. This was motivated by the fact that optimization problems are not an adequate mathematical tool for modeling in situations of decision involving multiple agents as explained by A.

Antipin in [4]: “Optimization problems can be more or less adequate in situations where there is one person making decisions working with an alternative set, but in situations with many agents, each having their personal set and system of preferences on it and each working within the localized constraints of their specific situation, it becomes impossible to use the optimization model to produce an aggregate solution that will satisfy the global constraints that exist for the agents as a whole.” There exists a large number of different concepts of equilibrium models. These models are investigated and applied separately. They require to construct adequate tools both for the theory and for the solution methods. But, in the scope of a mathematical research, it is expected to present a general form which can unify some particular cases.

Such an approach needs certain extensions of the usual concept of equilibrium and a presentation of unifying tools for investi- gating and solving these equilibrium models and meanwhile to drop some details in particular models. For that purpose, in this thesis we intend to consider the following class of equilibrium problem. Let C be a nonempty closed convex subset of IRn and let f : C × C → IR be an equilibrium bifunction, i.