Mathematical program with equilibrium constraints (MPEC)has extensive applications in practical areas such as traffic control, engineering design, and economic modeling. Some generalized stationary points of MPEC are studied to better describe the limiting points produced by interior point methods for MPEC.A primal-dual interior point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced without assuming strict complementarity or linear independence constraint qualification. Under very general assumptions, the algorithm can always find some point with strong or weak stationarity. In particular, it is shown that every limiting point of the generated sequence is a piece-wise stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a certain point with weak stationarity can be obtained. Preliminary numerical results are satisfactory, which include a case analyzed by Leyffer for which the penalty interior point algorithm failed to find a stationary solution. / Singapore-MIT Alliance (SMA)

The main purpose of this dissertation is to investigate necessary optimality conditions for a class of very general nonsmooth optimization problems called the mathematical program with geometric constraints (MPGC). The geometric constraint means that the image of certain mapping is included in a nonempty and closed set. We first study the conventional nonlinear program with equality, inequality and abstract set constraints as a special case of MPGC. We derive the enhanced Fritz John condition and from which, we obtain the enhanced Karush-Kuhn-Tucker (KKT) condition and introduce the associated pseudonormality and quasinormality condition. We prove that either pseudonormality or quasinormality with regularity implies the existence of a local error bound. We also give a tighter upper estimate for the Fr\'chet subdifferential and the limiting subdifferential of the value function in terms of quasinormal multipliers which is usually a smaller set than the set of classical normal multipliers. We then consider a more general MPGC where the image of the mapping from a Banach space is included in a nonempty and closed subset of a finite dimensional space. We obtain the enhanced Fritz John necessary optimality conditions in terms of the approximate subdifferential. One of the technical difficulties in obtaining such a result in an infinite dimensional space is that no compactness result can be used to show the existence of local minimizers of a perturbed problem. We employ the celebrated Ekeland's variational principle to obtain the results instead. We then apply our results to the study of exact penalty and sensitivity analysis. We also study a special class of MPCG named mathematical programs with equilibrium constraints (MPECs). We argue that the MPEC-linear independence constraint qualification is not a constraint qualification for the strong (S-) stationary condition when the objective function is nonsmooth. We derive the enhanced Fritz John Mordukhovich (M-) stationary condition for MPECs. From this enhanced Fritz John M-stationary condition we introduce the associated MPEC generalized pseudonormality and quasinormality condition and build the relations between them and some other widely used MPEC constraint qualifications. We give upper estimates for the subdifferential of the value function in terms of the enhanced M- and C-multipliers respectively. Besides, we focus on some new constraint qualifications introduced for nonlinear extremum problems in the recent literature. We show that, if the constraint functions are continuously differentiable, the relaxed Mangasarian-Fromovitz constraint qualification (or, equivalently, the constant rank of the subspace component condition) implies the existence of local error bounds. We further extend the new result to the MPECs. / Graduate / 0405

Dans cette thèse, nous étudions des approches basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) pour la programmation mathématique avec des contraintes d'équilibre, notée MPEC (Mathematical Programming with Equilibrum Constraints en anglais). Etant un sujet classique et difficile de la programmation mathématique et de la recherche opérationnelle, et de par ses diverses applications importantes, MPEC a attiré l'attention de nombreux chercheurs depuis plusieurs années. La thèse se compose de quatre chapitres principaux. Le chapitre 2 étudie une classe de programmes mathématiques avec des contraintes de complémentarité linéaire. En utilisant quatre fonctions de pénalité, nous reformulons le problème considéré comme des problèmes DC standard, i.e minimisation d'une fonction DC sous les contraintes convexes. Nous développons ensuite des algorithmes appropriés basés sur DCA pour résoudre les problèmes DC résultants. Deux d'entre eux sont reformulés encore sous la forme des problèmes DC généraux (i.e. minimisation d'une fonction DC sous des contraintes DC) pour que les sous-problèmes convexes dans DCA soient plus faciles à résoudre. Après la conception de DCA pour le problème considéré, nous développons ces schémas DCA pour deux cas particuliers: la programmation quadratique avec des contraintes de complémentarité linéaire, et le problème de complémentarité aux valeurs propres. Le chapitre 3 aborde une classe de programmes mathématiques avec des contraintes d'inégalité variationnelle. Nous utilisons une technique de pénalisation pour reformuler le problème considéré comme un programme DC. Une variante de DCA et sa version accélérée sont proposées pour résoudre ce programme DC. Comme application, nous résolvons le problème de détermination du prix de péages dans un réseau de transport avec des demandes fixes (" the second-best toll pricing problem with fixed demands" en anglais). Le chapitre 4 se concentre sur une classe de problèmes d'optimisation à deux niveaux avec des variables binaires dans le niveau supérieur. En utilisant une fonction de pénalité exacte, nous reformulons le problème considéré comme un programme DC standard pour lequel nous développons un algorithme efficace basé sur DCA. Nous appliquons l'algorithme proposé pour résoudre le problème d'interdiction de flot maximum dans un réseau ("maximum flow network interdiction problem" en anglais). Dans le chapitre 5, nous nous intéressons au problème de conception de réseau d'équilibre continu ("continuous equilibrium network design problem" en anglais). Il est modélisé sous forme d'un programme mathématique avec des contraintes de complémentarité, brièvement nommé MPCC (Mathematical Program with Complementarity Constraints en anglais). Nous reformulons ce problème MPCC comme un programme DC général et proposons un schéma DCA approprié pour le problème résultant / In this dissertation, we investigate approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for mathematical programs with equilibrium constraints. Being a classical and challenging topic of nonconvex optimization, and because of its many important applications, mathematical programming with equilibrium constraints has attracted the attention of many researchers since many years. The dissertation consists of four main chapters. Chapter 2 studies a class of mathematical programs with linear complementarity constraints. By using four penalty functions, we reformulate the considered problem as standard DC programs, i.e. minimizing a DC function on a convex set. The appropriate DCA schemes are developed to solve these four DC programs. Two among them are reformulated again as general DC programs (i.e. minimizing a DC function under DC constraints) in order that the convex subproblems in DCA are easier to solve. After designing DCA for the considered problem, we show how to develop these DCA schemes for solving the quadratic problem with linear complementarity constraints and the asymmetric eigenvalue complementarity problem. Chapter 3 addresses a class of mathematical programs with variational inequality constraints. We use a penalty technique to recast the considered problem as a DC program. A variant of DCA and its accelerated version are proposed to solve this DC program. As an application, we tackle the second-best toll pricing problem with fixed demands. Chapter 4 focuses on a class of bilevel optimization problems with binary upper level variables. By using an exact penalty function, we express the bilevel problem as a standard DC program for which an efficient DCA scheme is developed. We apply the proposed algorithm to solve a maximum flow network interdiction problem. In chapter 5, we are interested in the continuous equilibrium network design problem. It was formulated as a Mathematical Program with Complementarity Constraints (MPCC). We reformulate this MPCC problem as a general DC program and then propose a suitable DCA scheme for the resulting problem

<p>This thesis investigates the second-best toll pricing and capacity expansion problems when stated as mathematical programs with equilibrium constraints (MPEC). Three main questions are rised: First, whether conventional descent methods give sufficiently good solutions, or whether global solution methods are to prefer. Second, how the performance of the considered solution methods scale with network size. Third, how a discretized stochastic mathematical program with equilibrium constraints (SMPEC) formulation of a stochastic network design problem can be practically solved. An attempt to answer these questions is done through a series ofnumerical experiments.</p><p>The traffic system is modeled using the Wardrop’s principle for user behavior, separable cost functions of BPR- and TU71-type. Also elastic demand is considered for some problem instances.</p><p>Two already developed method approaches are considered: implicit programming and a cutting constraint algorithm. For the implicit programming approach, several methods—both local and global—are applied and for the traffic assignment problem an implementation of the disaggregate simplicial decomposition (DSD) method is used. Regarding the first question concerning local and global methods, our results don’t give a clear answer.</p><p>The results from numerical experiments of both approaches on networks of different sizes shows that the implicit programming approach has potential to solve large-scale problems, while the cutting constraint algorithm scales worse with network size.</p><p>Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem.</p><p>Further, a number of theorems providing sufficient conditions for strong regularity of the traffic assignment solution mapping for OD connectors and BPR cost functions are given.</p>

This thesis investigates the second-best toll pricing and capacity expansion problems when stated as mathematical programs with equilibrium constraints (MPEC). Three main questions are rised: First, whether conventional descent methods give sufficiently good solutions, or whether global solution methods are to prefer. Second, how the performance of the considered solution methods scale with network size. Third, how a discretized stochastic mathematical program with equilibrium constraints (SMPEC) formulation of a stochastic network design problem can be practically solved. An attempt to answer these questions is done through a series ofnumerical experiments. The traffic system is modeled using the Wardrop’s principle for user behavior, separable cost functions of BPR- and TU71-type. Also elastic demand is considered for some problem instances. Two already developed method approaches are considered: implicit programming and a cutting constraint algorithm. For the implicit programming approach, several methods—both local and global—are applied and for the traffic assignment problem an implementation of the disaggregate simplicial decomposition (DSD) method is used. Regarding the first question concerning local and global methods, our results don’t give a clear answer. The results from numerical experiments of both approaches on networks of different sizes shows that the implicit programming approach has potential to solve large-scale problems, while the cutting constraint algorithm scales worse with network size. Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem. Further, a number of theorems providing sufficient conditions for strong regularity of the traffic assignment solution mapping for OD connectors and BPR cost functions are given.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第18568号 / 工博第3929号 / 新制||工||1604(附属図書館) / 31468 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 准教授 宇野 伸宏, 准教授 山田 忠史 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

Die vorliegende Arbeit beschaeftigt sich mit Gleichgewichtsproblemen unter Gleichgewichtsrestriktionen, sogenannten EPECs (Englisch: Equilibrium Problems with Equilibrium Constraints). Konkret handelt es sich um gekoppelte Zwei-Ebenen-Optimierungsprobleme, bei denen Nash- Gleichgewichte fuer die Entscheidungen der oberen Ebene gesucht sind. Ein Ziel der Arbeit besteht in der Formulierung dualer Stationaritaetsbedingungen zu solchen Problemen. Als Anwendung wird ein oligopolistisches Wettbewerbsmodell fuer Strommaerkte betrachtet. Zur Gewinnung qualitativer Hypothesen ueber die Struktur der betrachteten Modelle (z.B. Inaktivitaet bestimmter Marktteilnehmer) aber auch fuer moegliche numerische Zugaenge ist es wesentlich, EPEC-Loesungen explizit bezueglich der Eingangsdaten des Problems zu formulieren. Der Weg dorthin erfordert eine Strukturanalyse der involvierten Optimierungsprobleme (constraint qualifications, Regularitaet), die Herleitung von Stabilitaetsresultaten bestimmter mengenwertiger Abbildungen und die Nutzung von Transformationsformeln fuer die sogenannte Ko-Ableitung. Weitere Schwerpunkte befassen sich mit der Beziehung zwischen verschiedenen dualen Stationaritaetstypen (S- und M-Stationaritaet) sowie mit stochastischen Erweiterungen der betrachteten Problemklasse, sogenannten SEPECs. / This thesis is concerned with equilibrium problems with equilibrium constraints or EPECs. Concretely, we consider models composed by coupling together two-level optimization problems, the upper-level solutions to which are non-cooperative (Nash-Cournot) equilibria. One of the main goals of the thesis involves the formulation of dual stationarity conditions to EPECs. A model of oligopolistic competition for electricity markets is considered as an application. In order to profit from qualitative hypotheses concerning the structure of the considered models, e.g., inactivity of certain market participants at equilibrium, as well as to provide conditions useful for numerical procedures, the ablilty to formulate EPEC solutions in relation to the input data of the problem is of considerable importance. The way to do this requires a structural analysis of the involved optimization problems, e.g., constraints qualifications, regularity; the derivation of stability results for certain multivalued mappings, and the usage of transformation formulae for so-called coderivatives. Further important topics address the relationship between various dual stationarity types, e.g., S- and M-stationarity, as well as the extension of the considered problem classes to a stochastic setting, i.e., stochastic EPECs or SEPECs.

Title: Hierarchical Problems with Evolutionary Equilibrium Constraints Author: Lukáš Adam Supervisor: Prof. Jiří Outrata Abstract: In the presented thesis, we are interested in hierarchical models with evolutionary equilibrium constraints. Such models arise naturally when a time-dependent problem is to be controlled or if parameters in such a model are to be identified. We intend to discretize the problem and solve it on the basis of the so-called implicit programming approach. This technique requires knowledge of a generalized derivative of the solution mapping which assigns the state variable to the control variable/parameter. The computation of this generalized derivative amounts equivalently to the computation of (limiting) normal cone to the graph of the solution mapping. In the first part we summarize known techniques for computation of the normal cone to the set which can be represented as a finite union of convex polyhedra. Then we propose a new approach based on the so-called normally admissible stratification and simplify the obtained formulas for the case of time-dependent problems. The theoretical results are then applied first to deriving a criterion for the sensitivity analysis of the solution mapping and then to the solution of two practically motivated problems. The first one concerns optimal...

[pt] Nesta de tese de doutorado é proposta uma metodologia alternativa para obter estratégias ótimas de oferta sob incerteza que maximizam o lucro de um agente em mercados dotados de um leilão de preço uniforme e envelope fechado com multiplos produtos divisíveis. A estratégia ótima de um agente price maker depende amplamente da informação conhecida dos agentes rivais. Reconhecendo que a oferta dos agentes rivais pode desviar do equilíbrio de mercado e é de difícil caracterização probabilística, nós propomos um modelo de otimização robusta dois estágios com restrições de equilíbrio para obter estratégias de oferta ótimas avessas a risco. O modelo proposto é um modelo de otimização de três níveis passível de ser reescrito como uma instância particular de um programa binível com restrições de equilíbrio. Um conjunto de procedimentos é proposto a fim de construir uma formulação equivalente de de nível único adequado para aplicação de algoritmos de Geração de Coluna e Restrição (GCC). Diferentemente de trabalhos publicados anteriormente em modelos de otimização dois estágios, nossa metodologia de solução não aplica o método de GCC para iterativamente identificar os cenários mais violados dos fatores de incerteza, variáveis que são identificadas através de variáveis contínuas. Na metodologia de solução proposta, o algoritmo GCC é aplicado para identificar um pequeno subconjunto de condições de otimalidade para o modelo de terceiro nível capaz de representar as restrições de equilíbrio do leilão na solução ótima do problema master (problema de oferta). Um estudo de caso numérico baseado em mercados de energia de curto prazo é apresentado para ilustrar a aplicabilidade do modelo robusto proposto. Resultados indicam que mesmo em um caso em que é observada uma imprecisão de 1 porcento na oferta de equilíbrio de Nash dos agentes rivais, a solução robusta provê uma redução significativa de risco em uma análise fora da amostra. / [en] We propose an alternative methodology to devise profit-maximizing strategic bids under uncertainty in markets endowed with a sealed-bid uniformprice auction with multiple divisible products. The optimal strategic bid of a price maker agent largely depends on the knowledge (information) of the rivals bidding strategy. By recognizing that the bid of rival competitors may deviate from the equilibrium and are of difficult probabilistic characterization, we proposed a two-stage robust optimization model with equilibrium constraints to devise an risk-averse strategic bid in the auction. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures are proposed to construct a single-level-equivalent formulation suitable for column and constraint generation (CCG) algorithm. Differently from previously reported works on two-stage robust optimization, our solution methodology does not employ the CCG algorithm to iteratively identify violated scenarios for the uncertain factors, which in this thesis are obtained through continuous variables. In the proposed solution methodology, the CCG is applied to identify a small subset of optimality conditions for the third-level model capable of representing the auction equilibrium constraints at the optimum solution of the master (bidding) problem. A numerical case study based on short-term electricity markets is presented to illustrate the applicability of the proposed robust model. Results show that even for the case where an impression of 1 percent on the rivals offer at the Nash equilibrium is observed, the robust solution provides a non-negligible risk reduction in out-of-sample analysis.