L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

This thesis examines the optimal scheduling of a hydroelectric power plant with cascaded reservoirs each with multiple generating units under uncertainty after testing three linearization methods. These linearization methods are Successive Linear Programming, Piecewise Linear Approximations, and a Hybrid of the two together. There are two goals of this work. The first goal of this work aims to replace the nonconvex mixed-integer nonlinear program (MINLP) with a computationally efficient linearized mixed-integer linear program (MILP) that will be capable of finding a high quality solution, preferably the global optimum. The second goal is to implement a stochastic approach on the linearized method in a pseudo-rolling horizon method which keeps the ending time step fixed. Overall, the Hybrid method proved to be a viable replacement and performs well in the pseudo-rolling horizon tests. / Thesis / Master of Applied Science (MASc)

This research effort develops a comprehensive computational framework to support the parametric optimal design of uncertain dynamical systems. Uncertainty comes from various sources, such as: system parameters, initial conditions, sensor and actuator noise, and external forcing. Treatment of uncertainty in design is of paramount practical importance because all real-life systems are affected by it; not accounting for uncertainty may result in poor robustness, sub-optimal performance and higher manufacturing costs. Contemporary methods for the quantification of uncertainty in dynamical systems are computationally intensive which, so far, have made a robust design optimization methodology prohibitive. Some existing algorithms address uncertainty in sensors and actuators during an optimal design; however, a comprehensive design framework that can treat all kinds of uncertainty with diverse distribution characteristics in a unified way is currently unavailable. The computational framework uses Generalized Polynomial Chaos methodology to quantify the effects of various sources of uncertainty found in dynamical systems; a Least-Squares Collocation Method is used to solve the corresponding uncertain differential equations. This technique is significantly faster computationally than traditional sampling methods and makes the construction of a parametric optimal design framework for uncertain systems feasible. The novel framework allows to directly treat uncertainty in the parametric optimal design process. Specifically, the following design problems are addressed: motion planning of fully-actuated and under-actuated systems; multi-objective robust design optimization; and optimal uncertainty apportionment concurrently with robust design optimization. The framework advances the state-of-the-art and enables engineers to produce more robust and optimally performing designs at an optimal manufacturing cost. / Ph. D.

過去的三十年間由於評價美式選擇權所產生的自由邊界問題已經有相當的研究成果。本論文將證明自由邊界問題的解為遞增函數。更進一步提出自由邊界凹性的嚴謹証明。利用我們的結論可以得知美式選擇權的最佳履約邊界對時間而言為嚴格遞減的凹函數。這個結果對可用來求導最佳履約邊界的漸近解。 對於美式交換選擇權，我們將其自由邊界問題轉換成單變數的積分方程，同時提供一個永續型美式交換選擇權的評價公式。對於有限時間的美式交換選擇權的最佳履約邊界，我們將提供一個接近到期日的漸近解並發展一個數值方法求其數值解。數值計算的結果顯示漸近解在接近到期日時與數值解非常接近。 對於評價美式選擇權，我們提出使用混合整數非線性規劃(MINLP)的模型，這個模型的最佳解同時提供賣方的完全避險策略、買方的最佳交易策略與美式選擇權的公平價格。因為求算MINLP模型的解需耗用大量的計算時間，我們證明此模型和其非線性規劃的寬鬆問題有相同的最佳解，所以只需求算寬鬆問題即可。觀察數值結果亦顯示非線性規劃的寬鬆問題可以大幅的降低計算的時間。此外，當市場的價格低於公平價格時，我們提出一個最小化賣方期望損失的數學規劃模型，此模型的解提供賣方最小化其期望損失的避險策略。 / In the past three decades, a great deal of effort has been made on solving the free boundary problem (FBP) arising from American option valuation problems. In this dissertation, we show that the solutions, the price and the free boundary, of this FBP are increasing functions. Furthermore, we provide a rigorous verification that the free boundary of this problem is concave. Our results imply that the optimal exercise boundary of an American call is a strictly decreasing concave function of time. These results will provide a useful information to obtain an asymptotic formula for the optimal exercise boundary. For pricing of American exchange options (AEO), we convert the associated FBP into a single variable integral equation (IE) and provide a formula for valuating the perpetual AEO. For the finite horizon AEO, we propose an asymptotic solution as time is near to expiration and develop a numerical method for its optimal exercise boundary. Compared with the computational results, the values of our asymptotic solution are close to the computational results as time is near to expiration. For valuating American options, we develop a mixed integer nonlinear programming (MINLP) model. The solution of the MINLP model provides a hedging portfolio for writers, the optimal trading strategy for buyers, and the fair price for American options at the same time. We show that it can be solved by its nonlinear programming (NLP) relaxation. The numerical results reveal that the use of NLP relaxation reduces the computation time rapidly. Moreover, when the market price is less than the fair price, we propose a minimum expected loss model. The solution of this model provides a hedging strategy that minimizes the expected loss for the writer.

Brigo與Mercurio提出了三種新的資產價格過程，分別是位移CEV過程、位移對數常態過程與混合對數常態過程。在這三種過程中，資產價格的波動度不再是一個固定的常數，而是時間與資產價格的明確函數。而由這三種過程所推導出來的歐式選擇權評價公式，將會導致隱含波動度曲線呈現傾斜曲線或是微笑曲線，且提供了參數讓我們能夠配適市場的波動度結構。本文利用台指買權來實證Brigo與Mercurio所提出的三種歐式選擇權評價公式，我們發現校準結果以混合對數常態過程優於位移CEV過程，而位移CEV過程則稍優於位移對數常態過程。因此，在實務校準時，我們建議以混合對數常態過程為台指買權的評價模型，以達到較佳的校準結果。 / Brigo and Mercurio proposed three types of asset-price dynamics which are shifted-CEV process, shifted-lognormal process and mixture-of-lognormals process respectively. In these three processes, the volatility of the asset price is no more a constant but a deterministic function of time and asset price. The European option pricing formulas derived from these three processes lead respectively to skew and smile in the term structure of implied volatilities. Also, the pricing formula provides several parameters for fitting the market volatility term structure. The thesis applies Taiwan’s call option to verifying these three pricing formulas proposed by Brigo and Mercurio. We find that the calibration result of mixture-of-lognormals process is better than the result of shifted-CEV process and the calibration result of shifted-CEV process is a little better than the result of shifted-lognormal process. Therefore, we recommend applying the pricing formula derived from mixture-of-lognormals process to getting a better calibration.

Diese Arbeit leistet Beiträge zu zwei Gebieten der mathematischen Programmierung: stochastische Optimierung und gemischt-ganzzahlige nichtlineare Optimierung (MINLP). Im ersten Teil erweitern wir quantitative Stetigkeitsresultate für zweistufige stochastische gemischt-ganzzahlige lineare Programme auf Situationen in denen Unsicherheit gleichzeitig in den Kosten und der rechten Seite auftritt, geben eine ausführliche Übersicht zu Dekompositionsverfahren für zwei- und mehrstufige stochastische lineare und gemischt-ganzzahlig lineare Programme, und diskutieren Erweiterungen und Kombinationen des Nested Benders Dekompositionsverfahrens und des Nested Column Generationsverfahrens für mehrstufige stochastische lineare Programme die es erlauben die Vorteile sogenannter rekombinierender Szenariobäume auszunutzen. Als eine Anwendung dieses Verfahrens betrachten wir die optimale Zeit- und Investitionsplanung für ein regionales Energiesystem unter Einbeziehung von Windenergie und Energiespeichern. Im zweiten Teil geben wir eine ausführliche Übersicht zum Stand der Technik bzgl. Algorithmen und Lösern für MINLPs und zeigen dass einige dieser Algorithmen innerhalb des constraint integer programming Softwaresystems SCIP angewendet werden können. Letzteres erlaubt uns die Verwendung schon existierender Technologien für gemischt-ganzzahlige linear Programme und constraint Programme für den linearen und diskreten Teil des Problems. Folglich konzentrieren wir uns hauptsächlich auf die Behandlung der konvexen und nichtkonvexen nichtlinearen Nebenbedingungen mittels Variablenschrankenpropagierung, äußerer Approximation und Reformulierung. In einer ausführlichen numerischen Studie untersuchen wir die Leistung unseres Ansatzes anhand von Anwendungen aus der Tagebauplanung und des Aufbaus eines Wasserverteilungssystems und mittels verschiedener Vergleichstests. Die Ergebnisse zeigen, dass SCIP ein konkurrenzfähiger Löser für MINLPs geworden ist. / This thesis contributes to two topics in mathematical programming: stochastic optimization and mixed-integer nonlinear programming (MINLP). In the first part, we extend quantitative continuity results for two-stage stochastic mixed-integer linear programs to include situations with simultaneous uncertainty in costs and right-hand side, give an extended review on decomposition algorithm for two- and multistage stochastic linear and mixed-integer linear programs, and discuss extensions and combinations of the Nested Benders Decomposition and Nested Column Generation methods for multistage stochastic linear programs to exploit the advantages of so-called recombining scenario trees. As an application of the latter, we consider the optimal scheduling and investment planning for a regional energy system including wind power and energy storages. In the second part, we give a comprehensive overview about the state-of-the-art in algorithms and solver technology for MINLPs and show that some of these algorithm can be applied within the constraint integer programming framework SCIP. The availability of the latter allows us to utilize the power of already existing mixed integer linear and constraint programming technologies to handle the linear and discrete parts of the problem. Thus, we focus mainly on the domain propagation, outer-approximation, and reformulation techniques to handle convex and nonconvex nonlinear constraints. In an extensive computational study, we investigate the performance of our approach on applications from open pit mine production scheduling and water distribution network design and on various benchmarks sets. The results show that SCIP has become a competitive solver for MINLPs.

The increase in electric vehicles and photovoltaic power production may introduce problems to the low-voltage distribution grid. With a higher number of electric vehicles, their accumulated charging power might breach the lowest allowed voltage level of the grid. Photovoltaic-modules can on the other hand exceed the highest allowed voltage level, by producing high accumulated power when the solar irradiance is high. Normally, electric distribution companies in Sweden reinforce the existing grid with more resilient infrastructure, such as stronger and larger cables or transformer stations. This is however a costly and time-consuming solution, which could be solved by using alternative means such as already existing resources. This Master's Thesis investigates how smart charging of batteries can support the low-voltage electrical grid with the increase in electric vehicles and photovoltaic power production. To do this, an optimization tool has been developed in Matlab. An existing model of a low-voltage grid is combined with the developed tool, where controllable batteries and photovoltaic-modules can be placed at specific households in the grid. The controllable batteries belong to either electric vehicles or stationary battery systems, and are intended to support the grid by the means of either reducing peak load powers, voltage variations, or a trade-off between them. Furthermore, this thesis investigates the maximum electric vehicle capability for a specific low-voltage electrical grid in Sweden. From the results, it can be concluded that smart charging of batteries can reduce the peak loads as well as voltage variations. The reduction of voltage variations for the entire low-voltage grid is greatest during the summer, when photovoltaic production generally is at its highest. The results also show that a stationary battery system can reduce the voltage variations to a greater extent, compared to an electric vehicle. Also, the introduction of multiple controllable batteries allows further support of the low-voltage grid. Regarding the maximum electric vehicle capability, the results show that the placement of the vehicles and the charging power strongly affect the maximum number of electric vehicles the low-voltage grid can manage. / Ökningen av elbilar och elproduktion från solceller kan ge problem i lågspänningsnätet. Med ett ökat antal elbilar kan den sammanlagrade effekten vid laddning underskrida den minsta tillåtna spänningsnivån i nätet. Solpaneler kan däremot leda till att den högsta tillåtna spänningsnivån överskrids, genom att producera en hög sammanlagrad effekt när solstrålningen är som högst. Vanligtvis förstärker elnätsbolag i Sverige det befintliga nätet med motståndskraftigare infrastruktur, såsom kraftigare och större kablar eller transformatorstationer. Detta är dock en kostsam och tidskrävande lösning, som skulle kunna lösas med alternativa medel, till exempel redan existerande resurser. Detta examensarbete undersöker hur smart laddning av batterier kan ge stöd till lågspänningsnätet, med en ökning av elbilar samt solcellsproduktion. För att undersöka detta har ett optimeringsverktyg utvecklats i Matlab. En befintlig modell av ett lågspänningsnät har kombinerats med det utvecklade optimeringsverktyget, där styrbara batterier samt solcellsproduktion kan placeras vid specifika hushåll i elnätet. De styrbara batterierna är antingen elbilar eller stationära batterisystem, och är ämnade till att stödja lågspänningsnätet genom att antingen reducera effekttoppar, spänningsvariationer eller en kompromiss av båda. Vidare undersöker detta examensarbete det maximala antalet elbilar som ett specifikt lågspänningsnät i Sverige kan hantera. Resultaten visar att smart laddning av batterier kan reducera effekttoppar samt spänningsvariationer. Reduceringen av spänningsvariationerna för hela lågspänningsnätet visar sig vara högst under sommaren, vilket är då solcellsproduktionen generellt är som högst. Resultaten visar även att stationära batterisystem kan reducera spänningsvariationer ytterligare, jämfört med en elbil. Att introducera flera styrbara batterier tillåter ett ännu större stöd till lågspänningsnätet. Angående det maximala antalet av elbilar som ett lågspänningsnät kan hantera visade resultaten att placeringen av elbilarna samt laddningseffekten har en stor påverkan.

Orientador: Rubén Augusto Romero Lázaro / Banca: Jose Roberto Sanches Mantovani / Banca: Anna Diva Plasencia Lotufo / Banca: Marcos Julio Rider Flores / Banca: Eduardo Nobuhiro Asada / Resumo: Nessa pesquisa tem-se por objetivo a análise teórica e a implementação computacional de duas propostas de solução ao problema de planejamento da expansão de sistemas de transmissão de energia elétrica considerando diferentes fatores relacionados com a confiabilidade do sistema e a adoção dos novos modelos de mercados elétricos. É importante notar, que no planejamento básico não são levados em conta esses importantes aspectos. Dessa forma, uma primeira aproximação considera um critério de confiabilidade para expandir o sistema, de forma que ele opere adequadamente no horizonte de planejamento satisfazendo um nível de confiabilidade pré-definido. O índice de confiabilidade utilizado para exigir esse nível de confiabilidade é o LOLE, que corresponde ao número médio de horas/dias em um período dado (normalmente um ano) no qual o pico da carga horária/diária do sistema possivelmente exceder'a a capacidade de geração disponível. O problema de planejamento considerando a confiabilidade é, portanto, formulado como um problema de otimização que minimiza o investimento sujeito ao critério de confiabilidade. O índice de confiabilidade para o sistema de transmissão é calculado para cada configuração, subtraindo o índice de confiabilidade do sistema de geração do sistema composto geração-transmissão (bulk power system ). Para calcular o índice no sistema composto geração transmissão, utiliza-se uma curva de duração de carga efetiva para este sistema. Esta curva acumulada de carga é obtida de um processo de convolução de outras duas curvas que representam a função de distribuição de probabilidade (FDP) das saídas aleatórias dos componentes do sistema e a curva de duração de carga, respectivamente. A avaliação de confiabilidade no sistema de geração é feita usando um método que calcula o índice de confiabilidade por meio dos momentos... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work aims to the theoretical analysis and computational implementation of two proposals for the transmission expansion planning problem considering several factors such as system reliability and new electricity market structures. It is important to observe, that the basic planning does not consider these issues. Therefore, one first approach considers a reliability criterion to expand the system, so that it operates in adequate conditions in the horizon planning while satisfying pre-defined limits in the reliability index. Transmission system reliability criterion regards to LOLE, which refers to the number of hours/days in a specified period of time (normally one year), in which the hourly/daily peak load possibly will exceed the available generation capacity. So, the planning problem considering reliability is formulated as an optimization problem that minimizes the investment subject to probabilistic reliability criterion. Reliability index for the transmission system is calculated for each configuration by subtraction of generation and bulk power reliability indexes. A composite power system effective load curve is used for reliability analysis of the bulk power system. This accumulate curve is obtained convolving two curves, one of them corresponding to a probability distribution function of the random outages of the system components, and the other one corresponding to the load duration curve. Reliability assessment in the generation system is done using a method that calculates the reliability index through the statistics moments of the frequency distribution of equivalents loads. This curve is obtained by convolving the generation units which are dispached in merit order. The proposed model is solved using the specialized genetic algorithm of Chu-Beasley (AGCB). Detailed results on two test systems are analyzed and discussed. A second approach to the transmission expansion... (Complete abstract click electronic access below) / Doutor

本論文研究如何建立一個投資組合用來追蹤穩定成長的目標線。我們將這個目標線追蹤問題建構成混合整數非線性數學規劃模型。由於用以追蹤目標線的投資組合，經過一段時間後其追蹤效能可能未如預期，本論文提出調整投資組合的數學規劃模型。這些模型中除了考量實務中的交易成本，亦考慮限制放空股票，所以將期貨加入投資組合中作為避險部位。最後，以台灣股票市場與期貨交易市場作為實證研究對象，探討投資組合建立與調整的表現，亦分析不同成長率設定之目標線與期貨投資比重上限對投資組合價值的影響。 / This thesis studies how to construct a tracking portfolio for the benchmark of a stable growth rate. This tracking problem can be formulated as a mixed-integer nonlinear programming model. Since the performance of the tracking portfolio may get worse when time elapses, this thesis proposes another mathematical programming model to rebalance the tracking portfolio. These models not only consider the transaction cost but also take into account of the limitation of shorting a stock; thus the tracking portfolio will include a futures position as a hedging position. Finally, an empirical study will be performed by using the data from the Taiwan stock market and the futures market to explore the performance of the proposed models. We will analyze how the different benchmark settings and the futures position limits will affect the value of the tracking portfolio.

本論文提出追蹤特定目標線的二階段混合整數非線性隨機規劃模型，以建立追蹤目標線的投資組合。藉由引進情境樹(scenario tree)，我們將此類二階段隨機規劃問題，轉換成為等價的非隨機規劃模型。在金融商品的價格波動及交互作用下，所建立的投資組合在經過一段時間後，其追蹤目標線的能力可能會日趨降低，所以本論文亦提出調整投資組合的規劃模型。為符合實務考量，本論文同時考慮交易成本、股票放空的限制，並且加入期貨進行避險。為了反應投資者的預期心理，也引進了選擇權及情境樹。最後，我們使用台灣股票市場、期貨交易市場及台指選擇權市場的資料進行實證研究，亦探討不同成長率設定之目標線與投資比例對於投資組合的影響。 / To construct a portfolio tracking specific target line, this thesis studies how to do it via two-stage stochastic mixed-integer nonlinear model. We introduce scenario tree to convert this stochastic model into an deterministic equivalent model. Under the volatility of price and the interaction of each financial derivatives, the performance of the tracking portfolio may get worse when time elapses, this thesis proposes another mathematical model to rebalance the tracking portfolio. These models consider the transactions cost and the limitation of shorting a stock, and the tracking portfolio will include a futures as a hedge position. To reflect the expectation of investors, we introduce scenario tree and also include a options as a hedge position. Finally, an empirical study will be performed by the data from Taiwan stock market, the futures market and the options market to explore the performance of the proposed models. We will analyze how the different benchmarks settings and invest ratio will affect the value of the tracking portfolio.