Apresentamos dois novos métodos para a solução de problemas de otimização convexa em dois níveis não necessariamente diferenciáveis, i.e., mostramos que as sequências geradas por ambos os métodos convergem para o conjunto ótimo de uma função não suave sujeito a um conjunto que também envolve a minimização de uma função não diferenciável. Ambos os algoritmos dispensam qualquer tipo de resolução de subproblemas ou busca linear durante suas iterações. Ao final, para demonstrar que os métodos são viáveis, resolvemos um problema de reconstrução de imagens tomográficas / We present two new methods for solving bilevel convex optimization problems, where both functions are not necessarily differentiable, i.e., we show that the sequences generated by those methods converge to the optimal set of a nonsmooth function subject to a set that also involves a function minimization. Both algorithms do not require any kind of subproblems resolution or linear search during the iterations. At the end, to prove that our methods are viable, we solve a problem of tomographic image reconstruction

Optimal parametric design of a system must be able to respond quickly to short term needs as well as long term conditions. To this end, we present an Assess-Predict-Optimize (APO) strategy which allows for easy modification of a system’s characteristics and constraints, enabling quick design adaptation. There are three components to the APO strategy: Assess - extract necessary information from given data; Predict - predict future behavior of system; and Optimize – obtain optimal system configuration based on information from the other components. The APO strategy utilizes three key mathematical ingredients to yield real-time results which would certainly conform to given constraints: dimension reduction of the model, a posteriori error estimation, and optimization methods. The resulting formulation resembles a bilevel optimization problem with an inherent nonconvexity in the inner level. Using a simple infiltration-evaporation model to simulate an irrigation system, we demonstrate the APO strategy’s ability to yield real-time optimal results. The linearized model, described by a coercive elliptic partial differential equation, is discretized by the reduced-basis output bounds method. A primal-dual interior point method is then chosen to solve the resulting APO problem. / Singapore-MIT Alliance (SMA)

This dissertation studies the competitive dynamics between two non-identical providers competing for customers seeking low-cost and quick service. Providers have generic delay functions where, asdemand received by each provider grows, so does delay in processing customers' requests. Given a pricing or capacity decision by each provider, customers determine the proportion of demand to send to each provider by minimizing generalized cost (monetary cost plus delaycost). This problem is formulated as a bilevel optimization, with providers competing at the upper level subject to the customers' decisions at the lower level. Occurrence of Nash equilibria between the providers is studied.First studied is the providers' problem of making decisions on capacities, while competing for a single customer. Conditions are derived for one provider to claim the entire market share, and for the occurrence of an equilibrium where both providers receive positivedemand. A numerical example in which no equilibrium exists is presented. Both the inelastic and elastic demand cases are studied for this scenario. In a second model, providers make pricing decisions with capacity fixed. Under some assumptions, it is shownthat a Nash equilibrium between providers always exists and a numerical example is presented. These models are then combined, in which providers make capacity decisions where prices equilibrate based on the results from the second model.Two competing customers with demand for a homogeneous product are then introduced, where providers choose prices as they compete for customers. This model is extended to an application along a highway corridor with a high-occupancy/toll (HOT) lane in parallel with a free road and transit line. A government agency chooses the transit service frequency while a private toll operator competes by choosing a toll to charge single-occupancy vehicles who wish to use the HOT lane.This scenario is also modeled as a bilevel program. For the lower level, a new dynamic equilibration process where homogeneous users make mode choice decisions based on previous generalized costs ofusing a particular mode is developed. Two numerical examples are presented showing a unique Nash equilibrium between the providers and an example in which multiple equilibria exist.

Made available in DSpace on 2014-06-11T19:30:50Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-02-16Bitstream added on 2014-06-13T19:19:29Z : No. of bitstreams: 1 lopezlezama_jm_dr_ilha.pdf: 1140558 bytes, checksum: 86f0f91a10800cda643c01c4a76fa063 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Nesta tese tem-se por objetivo a avaliação da alocação e preço de contrato de geração distribuida (GD) em ambientes competitivos. O trabalho apresentado é dividido em quatro temas principais. Na primeira parte deste trabalho é apresentado um modelo de e despacho de GD com base em um fluxo de potência ótimo AC multiperíodo. A principal vantagem deste modelo é a avaliação, de forma implícita, do impacto da GD na rede da concessionária. No modelo proposto considera-se um modelo de mercado no qual a a concessionária pode decidir comprar energia do mercado atacadista de energia através a e da subestação, ou alternativamente, das unidades de GD alocadas na sua rede, visando minimizar o pagamento no atendimento da demanda. Na segunda parte deste trabalho apresenta-se uma metodologia para calcular os preço de oferta de contrato da GD mediante programação binível. O modelo proposto considera a interação da concessionária e do proprietário da GD. De um lado, a concessionária procura minimizar o pagamento a a no atendimento da demanda. Para isto, utiliza-se um modelo de despacho simplificado similar ao apresentado na primeira parte deste trabalho. Por outro lado, o proprietário a da GD procura maximizar seus lucros mediante a venda de energia. Ambos os agentes devem cumprir, com certas restrições, por exemplo, a concessionária deve atender toda a demanda respeitando os limites técnicos da rede, enquanto o proprietário da GD deve e a fornecer sua energia considerando os limites mínimos e máximos das unidades de GD. Os a dois problemas de otimização são combinados em um problema de programação binível. A principal contribuição desta abordagem consiste na solução simultânea de dois problemas... / This work aims to the theoretical analysis and computational implementation of the operation and planning of distributed generation (DG) in a competitive framework. This report is divided in four main topics. In the first part of this work a DG dispatch model, based on a multi-period AC optimal power flow is presented. The main advantage of this model lies in the fact that it implicitly considers the impact of DG in the network of the distribution company. The proposed model considers a market model in which the distribution company can decide to purchase energy from the wholesale energy market, through the substation, or alternatively, from the DG units within its network, aiming to minimize the payments incurred in attending the demand. In the second part of this work a methodology to calculate the contract price offers of the DG by means of bilevel pro- gramming is presented. The proposed model considers the interaction of the utility and the owner of the DG. On one hand, the distribution company procures the minimization of the payments incurred in attending the demand. For this a simplified dispatch model, similar to the one presented in the first part of this work, is used. On the other hand, the DG owner procures the maximization of his profits by the selling of energy. Both agents must accomplish with certain constraints, for instance, the distribution company must attend all its demand considering the technical limits of the network, and the owner of the DG must supply his energy considering minimum and maximum limits of the gener- ation units. Both optimization problems are combined into a single bilevel optimization problem. The main contribution of this approach consists in the simultaneous solution of two optimization problems, providing contract prices that benefit both agents. In the third part of this work a Genetic... (Complete abstract click electronic access below)

Resumo: Nesta tese tem-se por objetivo a avaliação da alocação e preço de contrato de geração distribuida (GD) em ambientes competitivos. O trabalho apresentado é dividido em quatro temas principais. Na primeira parte deste trabalho é apresentado um modelo de e despacho de GD com base em um fluxo de potência ótimo AC multiperíodo. A principal vantagem deste modelo é a avaliação, de forma implícita, do impacto da GD na rede da concessionária. No modelo proposto considera-se um modelo de mercado no qual a a concessionária pode decidir comprar energia do mercado atacadista de energia através a e da subestação, ou alternativamente, das unidades de GD alocadas na sua rede, visando minimizar o pagamento no atendimento da demanda. Na segunda parte deste trabalho apresenta-se uma metodologia para calcular os preço de oferta de contrato da GD mediante programação binível. O modelo proposto considera a interação da concessionária e do proprietário da GD. De um lado, a concessionária procura minimizar o pagamento a a no atendimento da demanda. Para isto, utiliza-se um modelo de despacho simplificado similar ao apresentado na primeira parte deste trabalho. Por outro lado, o proprietário a da GD procura maximizar seus lucros mediante a venda de energia. Ambos os agentes devem cumprir, com certas restrições, por exemplo, a concessionária deve atender toda a demanda respeitando os limites técnicos da rede, enquanto o proprietário da GD deve e a fornecer sua energia considerando os limites mínimos e máximos das unidades de GD. Os a dois problemas de otimização são combinados em um problema de programação binível. A principal contribuição desta abordagem consiste na solução simultânea de dois problemas... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work aims to the theoretical analysis and computational implementation of the operation and planning of distributed generation (DG) in a competitive framework. This report is divided in four main topics. In the first part of this work a DG dispatch model, based on a multi-period AC optimal power flow is presented. The main advantage of this model lies in the fact that it implicitly considers the impact of DG in the network of the distribution company. The proposed model considers a market model in which the distribution company can decide to purchase energy from the wholesale energy market, through the substation, or alternatively, from the DG units within its network, aiming to minimize the payments incurred in attending the demand. In the second part of this work a methodology to calculate the contract price offers of the DG by means of bilevel pro- gramming is presented. The proposed model considers the interaction of the utility and the owner of the DG. On one hand, the distribution company procures the minimization of the payments incurred in attending the demand. For this a simplified dispatch model, similar to the one presented in the first part of this work, is used. On the other hand, the DG owner procures the maximization of his profits by the selling of energy. Both agents must accomplish with certain constraints, for instance, the distribution company must attend all its demand considering the technical limits of the network, and the owner of the DG must supply his energy considering minimum and maximum limits of the gener- ation units. Both optimization problems are combined into a single bilevel optimization problem. The main contribution of this approach consists in the simultaneous solution of two optimization problems, providing contract prices that benefit both agents. In the third part of this work a Genetic... (Complete abstract click electronic access below) / Orientador: Antonio Padilha Feltrin / Coorientador: Javier Contreras Sanz / Banca: Jose Roberto Sanches Mantovani / Banca: Carlos Roberto Minussi / Banca: Walmir de Freitas Filho / Banca: Flávio Antonio Becon Lemos / Doutor

Title: Bilevel optimization problems and their applications to portfolio selection Author: Lenka Godul'ová Department of Probability and Mathematical Statistics Supervisor: doc. RNDr. Ing. Miloš Kopa, Ph.D. Abstract: This work deals with the problem of bilevel tasks. First, it recalls the basic knowledge of mean-risk models, risk measure in singlelevel problems, and second degree stochastic dominance. Then it presents basic knowledge of bilevel tasks. bilevel problems have several advantages over singlelevel. In one process, it is possible to analyze two different or even conflicting situations. The bilevel role can better capture the relationship between the two objects. The main focus of the thesis is the formulation of various bilevel tasks and their reformulation into the simplest form. The numerical part deals with four types of formulated bilevel problems at selected risk measures. Keywords: Bilevel problems, Second degree stochastic dominance, Risk measures 1

Title: Bilevel optimization problems and their applications to portfolio selection Author: Lenka Godul'ová Department of Probability and Mathematical Statistics Supervisor: doc. RNDr. Ing. Miloš Kopa, Ph.D. Abstract: This work deals with the problem of bilevel tasks. First, it recalls the basic knowledge of mean-risk models, risk measure in singlelevel problems, and second degree stochastic dominance. Then it presents basic knowledge of bilevel tasks. bilevel problems have several advantages over singlelevel. In one process, it is possible to analyze two different or even conflicting situations. The bilevel role can better capture the relationship between the two objects. The main focus of the thesis is the formulation of various bilevel tasks and their reformulation into the simplest form. The numerical part deals with four types of formulated bilevel problems at selected risk measures. Keywords: Bilevel problems, Second degree stochastic dominance, Risk measures 1

Apresentamos dois novos métodos para a solução de problemas de otimização convexa em dois níveis não necessariamente diferenciáveis, i.e., mostramos que as sequências geradas por ambos os métodos convergem para o conjunto ótimo de uma função não suave sujeito a um conjunto que também envolve a minimização de uma função não diferenciável. Ambos os algoritmos dispensam qualquer tipo de resolução de subproblemas ou busca linear durante suas iterações. Ao final, para demonstrar que os métodos são viáveis, resolvemos um problema de reconstrução de imagens tomográficas / We present two new methods for solving bilevel convex optimization problems, where both functions are not necessarily differentiable, i.e., we show that the sequences generated by those methods converge to the optimal set of a nonsmooth function subject to a set that also involves a function minimization. Both algorithms do not require any kind of subproblems resolution or linear search during the iterations. At the end, to prove that our methods are viable, we solve a problem of tomographic image reconstruction

Demand Response (DR) was proposed more than a decade ago to incentivise customers to shift their electricity usage from peak demand periods to off-peak demand periods and to curtail their electricity usage during peak demand periods. However, the lack of two-way communication infrastructure weakens the influence of DR and limits its applications. With the development of smart grid facilities (e.g. smart meters and the two-way communication infrastructure) that enable the interactions between the energy retailer and its customers, demand response shows great potential to reduce customers' bills, increase the retailer's profit and further stabilize the power systems. Given such a context, in this thesis we propose smart pricing based demand response programs to study the interactions between the energy retailer and its customers based on game-theory and machine learning techniques. We conduct the research in two different application scenarios: 1) For customers with home energy management system (HEMS) installed in their smart meters, the retailer will know the customers' energy consumption patterns by interacting with the HEMS. As a result, the smart pricing based demand response problem can be modelled as a Stackelberg game or bilevel optimization problem. Further, efficient solutions are proposed for the demand response problems and the existence of optimal solution to the Stackelberg game and the bilevel model is proved; 2) For customers without HEMS installed in their smart meters, the retailer will not know the energy consumption patterns of these customers and must learn customers' behaviour patterns via historical energy usage data. To realize this, two appliance-level machine learning algorithms are proposed to learn customers' consumption patterns. Further, distributed pricing algorithms are proposed for the retailer to solve the demand response problem effectively. Simulation results indicate the effectiveness of the proposed demand response models in both application scenarios.

Cette thèse est consacrée à une étude approfondie du Rank Pricing Problem (RPP) et de deux généralisations. Le RPP est un problème d'optimisation combinatoire qui vise à fixer le prix des produits d'une entreprise afin de maximiser son profit. Elle concerne les clients à la demande, c'est-à-dire les clients qui sont intéressés par plusieurs produits de l'entreprise, mais qui n'ont l'intention d'en acheter qu'un. Les clients disposent d'un budget fixe et classent les produits qui les intéressent du "meilleur" au "pire". Lorsque l'entreprise fixe les prix, chaque client achètera son produit préféré parmi ceux qu'il peut se permettre. Dans le RPP, nous supposons que les produits sont offerts en quantité illimitée, ce qui convient si l'on considère que l'entreprise a suffisamment de produits pour satisfaire la demande, ou lorsque les produits peuvent être fabriqués rapidement avec un coût négligeable (par exemple, les biens numériques).Cette thèse se compose de quatre chapitres. Le premier est un chapitre d'introduction au problème et aux concepts mathématiques présents dans la thèse, tandis que les trois chapitres suivants se concentrent sur chacun des problèmes étudiés :le RPP et deux généralisations. Ainsi, le troisième chapitre est consacré à l'étude du Rank Pricing Problem with Ties (RPPT). Dans cette extension du problème, nous supposons que les clients peuvent exprimer leur indifférence entre les produits qui les intéressent au moyen de liens dans leur liste de préférences. Enfin, le dernier chapitre de la thèse comprend l'étude du Capacitated Rank Pricing Problem (CRPP) avec envie. Dans cette extension, nous avons supposé des prix de réserve pour les clients qui reflètent ce qu'ils sont prêts à payer pour chaque produit, plutôt qu'un budget unique par consommateur. Cependant, la principale différence est que dans le cas du CRPP, l'entreprise dispose d'un nombre limité de produits et peut ne pas être en mesure de satisfaire la demande de tous les clients. L'objectif de la thèse est d'obtenir des formulations linéaires en nombres entiers mixtes pour les trois problèmes étudiés, et de les comparer sur le plan théorique et/ou computationnel. À cette fin, la méthodologie utilisée est basée sur la proposition de variables de décision et de contraintes appropriées qui modélisent le problème. L'objectif suivant est l'amélioration de ces formulations au moyen d'inégalités valides qui réduisent l’ensemble admissible de la relaxation du problème et permettent d'obtenir une meilleure borne de la relaxation linéaire. Et enfin, un troisième objectif est la proposition d'algorithmes de résolution pour chacun de ces modèles, et leur comparaison ultérieure au moyen d'études computationnelles et de résolution au moyen de logiciels d'optimisation commerciaux. / This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g. digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies.The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished