In this paper we describe an approach for generating geometrically-parameterized integrated-circuit interconnect models that are efficient enough for use in interconnect synthesis. The model generation approach presented is automatic, and is based on a multi-parameter model-reduction algorithm. The effectiveness of the technique is tested using a multi-line bus example, where both wire spacing and wire width are considered as geometric parameters. Experimental results demonstrate that the generated models accurately predict both delay and cross-talk effects over a wide range of spacing and width variation. / Singapore-MIT Alliance (SMA)

We compare two popular scenario tree generation methods in the context of financial optimization: Moment matching and scenario reduction. Using a simple problem with a known analytic solution, we find that moment matching - accompanied by a check to ensure absence of arbitrage opportunities - replicates this solution precisely. On the other hand, even if the scenario trees generated by scenario reduction are arbitrage-free, the solutions to the approximate optimization problem represented by the reduced tree are biased and highly variable. These results hold for correlated and uncorrelated asset returns, as well as for normal and non-normal returns. (authors' abstract)

This thesis presents the main results of my research in the field of computational finance and portfolios optimization. We focus on pricing Asian basket options and portfolio problems in the presence of inflation with stochastic interest rates. In Chapter 2, we concentrate upon the derivation of bounds for European-style discrete arithmetic Asian basket options in a Black and Scholes framework.We start from methods used for basket options and Asian options. First, we use the general approach for deriving upper and lower bounds for stop-loss premia of sums of non-independent random variables as in Kaas et al. [Upper and lower bounds for sums of random variables, Insurance Math. Econom. 27 (2000) 151–168] or Dhaene et al. [The concept of comonotonicity in actuarial science and finance: theory, Insurance Math. Econom. 31(1) (2002) 3–33]. We generalize the methods in Deelstra et al. [Pricing of arithmetic basket options by conditioning, Insurance Math. Econom. 34 (2004) 55–57] and Vanmaele et al. [Bounds for the price of discrete sampled arithmetic Asian options, J. Comput. Appl. Math. 185(1) (2006) 51–90]. Afterwards we show how to derive an analytical closed-form expression for a lower bound in the non-comonotonic case. Finally, we derive upper bounds for Asian basket options by applying techniques as in Thompson [Fast narrow bounds on the value of Asian options, Working Paper, University of Cambridge, 1999] and Lord [Partially exact and bounded approximations for arithmetic Asian options, J. Comput. Finance 10 (2) (2006) 1–52]. Numerical results are included and on the basis of our numerical tests, we explain which method we recommend depending on moneyness and time-to-maturity In Chapter 3, we propose some moment matching pricing methods for European-style discrete arithmetic Asian basket options in a Black & Scholes framework. We generalize the approach of Curran M. (1994) [Valuing Asian and portfolio by conditioning on the geometric mean price”, Management science, 40, 1705-1711] and of Deelstra G., Liinev J. and Vanmaele M. (2004) [Pricing of arithmetic basket options by conditioning”, Insurance: Mathematics & Economics] in several ways. We create a framework that allows for a whole class of conditioning random variables which are normally distributed. We moment match not only with a lognormal random variable but also with a log-extended-skew-normal random variable. We also improve the bounds of Deelstra G., Diallo I. and Vanmaele M. (2008). [Bounds for Asian basket options”, Journal of Computational and Applied Mathematics, 218, 215-228]. Numerical results are included and on the basis of our numerical tests, we explain which method we recommend depending on moneyness and time-to-maturity. In Chapter 4, we use the stochastic dynamic programming approach in order to extend Brennan and Xia’s unconstrained optimal portfolio strategies by investigating the case in which interest rates and inflation rates follow affine dynamics which combine the model of Cox et al. (1985) [A Theory of the Term Structure of Interest Rates, Econometrica, 53(2), 385-408] and the model of Vasicek (1977) [An equilibrium characterization of the term structure, Journal of Financial Economics, 5, 177-188]. We first derive the nominal price of a zero coupon bond by using the evolution PDE which can be solved by reducing the problem to the solution of three ordinary differential equations (ODE). To solve the corresponding control problems we apply a verification theorem without the usual Lipschitz assumption given in Korn R. and Kraft H.(2001)[A Stochastic control approach to portfolio problems with stochastic interest rates, SIAM Journal on Control and Optimization, 40(4), 1250-1269] or [45].

No description available.

This work presents an empirical analysis of popular scenario generation methods for stochastic optimization, including quasi-Monte Carlo, moment matching, and methods based on probability metrics, as well as a new method referred to as Voronoi cell sampling. Solution quality is assessed by measuring the error that arises from using scenarios to solve a multi-dimensional newsvendor problem, for which analytical solutions are available. In addition to the expected value, the work also studies scenario quality when minimizing the expected shortfall using the conditional value-at-risk. To quickly solve problems with millions of random parameters, a reformulation of the risk-averse newsvendor problem is proposed which can be solved via Benders decomposition. The empirical analysis identifies Voronoi cell sampling as the method that provides the lowest errors, with particularly good results for heavy-tailed distributions. A controversial finding concerns evidence for the ineffectiveness of widely used methods based on minimizing probability metrics under high-dimensional randomness.

Analytical interpolation theory has several applications in systems and control. In particular, solutions of low degree, or more generally of low complexity, are of special interest since they allow for synthesis of simpler systems. The study of degree constrained analytic interpolation was initialized in the early 80's and during the past decade it has had significant progress. This thesis contributes in three different aspects to complexity constrained analytic interpolation: theory, numerical algorithms, and design paradigms. The contributions are closely related; shortcomings of previous design paradigms motivate development of the theory, which in turn calls for new robust and efficient numerical algorithms. Mainly two theoretical developments are studied in the thesis. Firstly, the spectral Kullback-Leibler approximation formulation is merged with simultaneous cepstral and covariance interpolation. For this formulation, both uniqueness of the solution, as well as smoothness with respect to data, is proven. Secondly, the theory is generalized to matrix-valued interpolation, but then only allowing for covariance-type interpolation conditions. Again, uniqueness and smoothness with respect to data is proven. Three algorithms are presented. Firstly, a refinement of a previous algorithm allowing for multiple as well as matrix-valued interpolation in an optimization framework is presented. Secondly, an algorithm capable of solving the boundary case, that is, with spectral zeros on the unit circle, is given. This also yields an inherent numerical robustness. Thirdly, a new algorithm treating the problem with both cepstral and covariance conditions is presented. Two design paradigms have sprung out of the complexity constrained analytical interpolation theory. Firstly, in robust control it enables low degree Hinf controller design. This is illustrated by a low degree controller design for a benchmark problem in MIMO sensitivity shaping. Also, a user support for the tuning of controllers within the design paradigm for the SISO case is presented. Secondly, in ARMA estimation it provides unique model estimates, which depend smoothly on the data as well as enables frequency weighting. For AR estimation, a covariance extension approach to frequency weighting is discussed, and an example is given as an illustration. For ARMA estimation, simultaneous cepstral and covariance matching is generalized to include prefiltering. An example indicates that this might yield asymptotically efficient estimates. / QC 20100928

Rational Krylov methods for model order reduction are studied. A dual rational Arnoldi method for model order reduction and a rational Krylov method for model order reduction and eigenvalue computation have been implemented. It is shown how to deflate redundant or unwanted vectors and how to obtain moment matching. Both methods are designed for generalised state space systems---the former for multiple-input-multiple-output (MIMO) systems from finite element discretisations and the latter for single-input-single-output (SISO) systems---and applied to relevant test problems. The dual rational Arnoldi method is designed for generating real reduced order systems using complex shift points and stabilising a system that happens to be unstable. For the rational Krylov method, a forward error in the recursion and an estimate of the error in the approximation of the transfer function are studie. A stability analysis of a heat exchanger model is made. The model is a nonlinear partial differential-algebraic equation (PDAE). Its well-posedness and how to prescribe boundary data is investigated through analysis of a linearised PDAE and numerical experiments on a nonlinear DAE. Four methods for generating reduced order models are applied to the nonlinear DAE and compared: a Krylov based moment matching method, balanced truncation, Galerkin projection onto a proper orthogonal decomposition (POD) basis, and a lumping method. / QC 20101013

<p>Rational Krylov methods for model order reduction are studied. A dual rational Arnoldi method for model order reduction and a rational Krylov method for model order reduction and eigenvalue computation have been implemented. It is shown how to deflate redundant or unwanted vectors and how to obtain moment matching. Both methods are designed for generalised state space systems---the former for multiple-input-multiple-output (MIMO) systems from finite element discretisations and the latter for single-input-single-output (SISO) systems---and applied to relevant test problems. The dual rational Arnoldi method is designed for generating real reduced order systems using complex shift points and stabilising a system that happens to be unstable. For the rational Krylov method, a forward error in the recursion and an estimate of the error in the approximation of the transfer function are studie.</p><p>A stability analysis of a heat exchanger model is made. The model is a nonlinear partial differential-algebraic equation (PDAE). Its well-posedness and how to prescribe boundary data is investigated through analysis of a linearised PDAE and numerical experiments on a nonlinear DAE. Four methods for generating reduced order models are applied to the nonlinear DAE and compared: a Krylov based moment matching method, balanced truncation, Galerkin projection onto a proper orthogonal decomposition (POD) basis, and a lumping method.</p>

La solution numérique des systèmes dynamiques est un moyen efficace pour étudier des phénomènes physiques complexes. Cependant, dans un cadre à grande échelle, la dimension du système rend les calculs infaisables en raison des limites de mémoire et de temps, ainsi que le mauvais conditionnement. La solution de ce problème est la réduction de modèles. Cette thèse porte sur les méthodes de projection pour construire efficacement des modèles d'ordre inférieur à partir des systèmes linéaires dynamiques de grande taille. En particulier, nous nous intéressons à la projection sur la réunion de plusieurs sous-espaces de Krylov standard qui conduit à une classe de modèles d'ordre réduit. Cette méthode est connue par l'interpolation rationnelle. En se basant sur ce cadre théorique qui relie la projection de Krylov à l'interpolation rationnelle, quatre algorithmes de type Lanczos rationnel pour la réduction de modèles sont proposés. Dans un premier temps, nous avons introduit une méthode adaptative de type Lanczos rationnel par block pour réduire l'ordre des systèmes linéaires dynamiques de grande taille, cette méthode est basée sur l'algorithme de Lanczos rationnel par block et une méthode adaptative pour choisir les points d'interpolation. Une généralisation de ce premier algorithme est également donnée, où différentes multiplicités sont considérées pour chaque point d'interpolation. Ensuite, nous avons proposé une autre extension de la méthode du sous-espace de Krylov standard pour les systèmes à plusieurs-entrées plusieurs-sorties, qui est le sous-espace de Krylov global. Nous avons obtenu des équations qui décrivent cette procédure. Finalement, nous avons proposé une méthode de Lanczos étendu par block et nous avons établi de nouvelles propriétés algébriques pour cet algorithme. L'efficacité et la précision de tous les algorithmes proposés, appliqués sur des problèmes de réduction de modèles, sont testées dans plusieurs exemples numériques. / Numerical solution of dynamical systems have been a successful means for studying complex physical phenomena. However, in large-scale setting, the system dimension makes the computations infeasible due to memory and time limitations, and ill-conditioning. The remedy of this problem is model reductions. This dissertations focuses on projection methods to efficiently construct reduced order models for large linear dynamical systems. Especially, we are interesting by projection onto unions of Krylov subspaces which lead to a class of reduced order models known as rational interpolation. Based on this theoretical framework that relate Krylov projection to rational interpolation, four rational Lanczos-type algorithms for model reduction are proposed. At first, an adaptative rational block Lanczos-type method for reducing the order of large scale dynamical systems is introduced, based on a rational block Lanczos algorithm and an adaptive approach for choosing the interpolation points. A generalization of the first algorithm is also given where different multiplicities are consider for each interpolation point. Next, we proposed another extension of the standard Krylov subspace method for Multiple-Input Multiple-Output (MIMO) systems, which is the global Krylov subspace, and we obtained also some equations that describe this process. Finally, an extended block Lanczos method is introduced and new algebraic properties for this algorithm are also given. The accuracy and the efficiency of all proposed algorithms when applied to model order reduction problem are tested by means of different numerical experiments that use a collection of well known benchmark examples.

The purpose of this thesis is to develop an optimization model that chooses the optimal and price efficient combination of underlying assets for a equally weighted basket option. To obtain a price efficient combination of underlying assets a function that calculates the basket option price is needed, for further use in an optimization model. The closed-form basket option pricing is a great challenge, due to the lack of a distribution describing the augmented stochastic price process. Many types of approaches to price an basket option has been made. In this thesis, an analytical approximation of the basket option price has been used, where the analytical approximation aims to develop a method to describe the augmented price process. The approximation is done by moment matching, i.e. matching the first two moments of the real distribution of the basket option with an lognormal distribution. The obtained price function is adjusted and used as the objective function in the optimization model. Furthermore, since the goal is to obtain en equally weighted basket option, the appropriate class of optimization models to use are binary optimization problems. This kind of optimization model is in general hard to solve - especially for increasing dimensions. Three different continuous relaxations of the binary problem has been applied in order to obtain continuous problems, that are easier to solve. The results shows that the purpose of this thesis is fulfilled when formulating and solving the optimization problem - both as an binary and continuous nonlinear optimization model. Moreover, the results from a Monte Carlo simulation for correlated stochastic processes shows that the moment matching technique with a lognormal distribution is a good approximation for pricing a basket option. / Syftet med detta examensarbete är att utveckla ett optimeringsverktyg som väljer den optimala och priseffektiva kombinationen av underliggande tillgångar för en likaviktad aktiekorg. För att kunna hitta en priseffektiv kombination av underliggande tillgångar behöver man finna en passande funktion som bestämmer priset på en likaviktad aktiekorg. Prissättningen av dessa typer av optioner är en stor utmaning. Detta är på grund av bristen av en sannolikhetsfördelning som kan beskriva den utökade och korrelerade stokastiska prisprocess som uppstår för en aktiekorg. Många typer av prissättningar har undersökts och tillämpats. I detta arbete har en analytisk approximation använts för att kunna beskriva den underliggande pris processen approximativt. Uppskattningen görs genom att matcha de tvåförsta momenten av den verkliga fördelningen med motsvarande moment för en lognormal fördelning. Den erhållna prisfunktionen justeras och används som målfunktionen i optimeringsmodellen. Binära ickelinjära optimeringsproblem är i allmänhet svåra att lösa - särskilt för ökande dimensioner av variabler. Tre olika kontinuerliga omformuleringar av det binära optimeringsproblemet har gjorts för att erhålla kontinuerliga problem som är lättare att lösa. Resultaten visar att en optimal och priseffektiv kombination av underliggande aktier är möjlig att hitta genom att formulera ett optimeringsproblem - både som en binär och kontinuerlig ickelinjär optimeringsmodell. Dessutom visar resultaten från en Monte Carlo-simulering, i detta fall för korrelerade stokastiska processer, att moment matching metoden utförd med en lognormal fördelning är en god approximation för prissättningen av aktiekorgar.