Computational Optimisation Group

Seminar: Optimal control of Weakly Connected Markov Decision Processes
2012-12-11 16:00 UTC
Title: Optimal control of Weakly Connected Markov Decision ProcessesSpeaker: Dr. Panos ParpasAffiliation: Department of Computing – Imperial College LondonLocation: Room 140 HuxleyTime: 4:00pm
Abstract. Weakly connected Markov processes are used to model stochastic dynamics across different scales. They are widely used in electrical engineering, finance and molecular dynamics simulations. In many of these applications it is becoming increasingly important to both efficiently simulate these processes as well as to control them. Classical algorithms for the control of Markov Processes cannot be directly applied to weakly connected Markov processes. The problem with existing approaches is that they exhibit an extremely slow convergence rate due to the existence of multiscale effects. We show why existing algorithms are slow, and propose a new class of algorithms with more favourable convergence properties and computational complexity. In our approach we use spectral graph theory to derive a hierarchy of models that are valid at different resolutions. We then propose a polynomial time algorithm that uses the finest resolution model only when required. The rate of convergence of the algorithm is discussed as well as its complexity.
About the speaker. Panos Parpas is a Lecturer in the Quantitative Analysis and Decision Science (QUADS) section of the Department of Computing at Imperial College London. Before joining Imperial College he was a postdoctoral fellow at the MIT Energy Initiative (2009-2011). Before that he was a quantitative associate at Credit-Suisse (2007-2009). He completed his PhD in computational optimization at Imperial College in 2006. Panos Parpas is interested in the development and analysis of quantitative optimization models under uncertainty. Stochastic optimization models are used in many areas such as economics, finance, engineering, and energy systems. Realistic models have a large number of variables, and multiple interactions across time and space. Advanced computational methods, and analytical approximations that take advantage of problem structure are needed in order to analyze realistic models. I am interested in both the development of computational methods and applications.

Seminar: The Branch-and-Sandwich Algorithm for Mixed-Integer Nonlinear Bilevel Programming Problems
2012-11-29 15:00
Title: The Branch-and-Sandwich Algorithm for Mixed-Integer Nonlinear Bilevel Programming ProblemsSpeaker: Dr. Polyxeni-Margarita KleniatiAffiliation: Centre for Process Systems Engineering at Imperial College LondonLocation: Room 144 HuxleyTime: 3:00pm
Abstract. We extend our recently introduced algorithm for general bilevel programming problems, Branch-and-Sandwich (Kleniati and Adjiman, J. Global Optim., 2012), to the class of mixed-integer nonlinear bilevel problems. As in the original algorithm, auxiliary inner lower and upper bounding problems are constructed in order to bound the inner value function and provide constant bound cuts for the outer upper and outer lower bounding problems. The KKT-based relaxations, originally proposed for the inner upper bounding and the outer lower bounding problems, are applicable with respect to the lower-level continuous variables based on appropriate constraint qualifications, but are no longer required. In the extension that we present here, a robust counterpart approach is employed to formulate the inner upper bounding problem and the resulting bound cut may be the only constraint added to the proposed outer lower bounding problem. The branching framework with auxiliary lists of nodes, as developed for the original Branch-and-Sandwich, is also applied to the discrete case. The algorithm is used to solve successfully ten literature problems.
About the speaker. Dr. Kleniati is undertaking her second postdoctoral research position with Prof. Adjiman at the Chemical Engineering department of Imperial College London. She received her PhD in Computing and Optimisation research in 2010 under the supervision of Prof. Rustem at the department of Computing in Imperial College London. The research of Polyxeni Kleniati is currently focused on the global optimisation of bilevel programming problems with applications to chemical engineering.

Seminar: Matrix Learning Problems and First-Order Optimization
2012-11-27 14:00
Title: Matrix Learning Problems and First-Order OptimizationSpeaker: Dr. Andreas Argyriou Affiliation: Toyota Technological Institute at ChicagoLocation: Room 217 Huxley BuildingTime: 2:00pm
Abstract. In the past few years, there has been significant interest in nonsmooth convex optimization problems involving matrices, especially in the areas of machine learning, statistics and control. Instances of such problems are multitask learning and matrix completion, robust PCA, sparse inverse covariance selection etc. I will present PRISMA, a new optimization algorithm for minimizing a convex objective which decomposes into three parts: a smooth part, a simple non-smooth Lipschitz part, and a simple nonsmooth non-Lipschitz part. Our algorithm combines the methodologies of smoothing and accelerated proximal methods. Moreover, our convergence result removes the assumption of bounded domain required by Nesterov's smoothing methods. I will show how PRISMA can be applied to the problems of max-norm regularized matrix completion and clustering, robust PCA and sparse inverse covariance selection, and compare to state of the art methods.
About the speaker. Andreas Argyriou has received degrees in Computer Science from MIT and a PhD in Computer Science from UCL. The topic of his PhD work has been on machine learning methodologies integrating different tasks and data sources. He has held postdoctoral and research faculty positions at UCL, TTI Chicago, KU Leuven and is currently in Ecole Centrale Paris with an RBUCE-UP fellowship. His current interests are in the areas of machine learning with big and complex data, compressed sensing and convex optimization methods.

Seminar: Algorithms and computer architectures for efficient real-time optimization and linear algebra solvers
2012-11-21 14:00
Title: Algorithms and computer architectures for efficient real-time optimization and linear algebra solversSpeaker: Eric C KerriganAffiliation: Department of Aeronautics and Department of Electrical and Electronic Engineering – Imperial College LondonLocation: Room 408 Electrical & Electronic Engineering DepartmentTime: 2:00pm
Abstract. In many engineering applications where one would like to implement control and signal processing algorithms, one needs to use the latest measurements to update and solve a sequence of numerical optimization or linear algebra problems. Solving these problems in a computationally efficient and numerically reliable fashion on an embedded computing system is a challenging task. One of the key choices that an engineer has to make in order to determine the speed, cost and power consumption of a microprocessor is the number representation that will be used in the arithmetic units. CPUs within modern desktop or laptop PCs provide hardware support for double precision floating-point arithmetic. However, most microprocessors in embedded systems do not support double precision floating-point arithmetic; they often only support single-precision floating-point and/or fixed-point arithmetic. It is therefore possible that, because of a significant decrease in precision or dynamic range, a numerical algorithm that gives reliable results on the office PC or laptop might give completely different results when implemented on an embedded computing system. We will present novel mathematical formulations, computer architectures, optimization solvers and linear algebra solvers to show that computational resources can be reduced significantly using very low precision arithmetic, without sacrificing accuracy. We will also present new mathematical results that allow one to use fixed-point arithmetic to make impressive computational savings in iterative linear algebra solvers. Our theoretical results will be supported by implementations on a Field Programmable Gate Array (FPGA) and we will show that it is possible to exceed the peak theoretical performance of a 1TFLOP/s general-purpose GPU.
About the speaker. Dr Kerrigan’s research includes the optimal and robust control of nonlinear, constrained and distributed parameter systems. His research is focused on the development of efficient numerical methods and computational hardware architectures for solving the resulting problems and is applied to a variety of problems in aerospace and fluid dynamics.

Seminar: Reflections on robustness in stochastic programs with risk constraints
2012-11-08 15:00
Title: Reflections on robustness in stochastic programs with risk constraintsSpeaker: Dr. Milos KopaAffiliation: Department of Probability and Mathematical Statistics – Charles University in PragueLocation: Room 301 William PenneyTime: 3:00pm
Abstract. This paper is a contribution to the robustness analysis for stochastic programs whose set of feasible solutions depends on the probability distribution P. For various reasons, probability distribution P may not be precisely specified and we study robustness of results with respect to perturbations of P. The main tool is the contamination technique. For the optimal value, local contamination bounds are derived and applied to robustness analysis of the optimal value of a portfolio performance under risk-shaping constraints. To illustrate the theoretical results, numerical examples for several mean-risk models are presented. Finally, under suitable conditions on the structure of the problem and for discrete distributions we shall suggest a new robust portfolio efficiency test with respect to the first (second) order stochastic dominance criterion and we shall exploit the contamination technique to analyze the resistance with respect to additional scenarios.
About the speaker. Dr. Milos Kopa is an assistant professor at Charles University in Prague. He received his Ph.D. degree in Econometrics and Operations research in 2006 (supervisor: Prof. Jitka Dupacova, Charles University in Prague). He is a member of several scientific societies: Stochastic Programming Community, EURO working group on financial modelling, EUROPT. Recently he has become an elected member (and secretary) of Managerial Board of new EURO working group on stochastic programming. He is vice-head of the Center of Excellence “Dynamic models in economics” that comprises about 40 leading researchers (in quantitative economics and finance) from Czech Republic. The research of Milos Kopa is focused on: stochastic programming theory and applications, especially financial applications. In recent years he has published several papers dealing with portfolio efficiency with respect to stochastic dominance criteria; data envelopment analysis and its relation to stochastic dominance; robustness (contamination) in stochastic programs with risk constraints, etc.

Seminar: Multi-task Learning and Matrix Regularization
2012-10-30 14:00
Title: Multi-task Learning and Matrix RegularizationSpeaker: Prof. Massimiliano PontilAffiliation: Department of Computer Science – University College LondonLocation: Room 301 William PenneyTime: 2:00pm
Abstract. We discuss the problem of estimating a structured matrix with a large number of elements. A key motivation for this problem occurs in multi-task learning. In this case, the columns of the matrix correspond to the parameters of different regression or classification tasks, and there is structure due to relations between the tasks. We present a general method to learn the tasks’ parameters as well as their structure. Our approach is based on solving a convex optimization problem, involving a data term and a penalty term. We highlight different types of penalty terms which are of practical and theoretical importance. They implement structural relations between the tasks and achieve a sparse representations of parameters. We address computational issues as well as the predictive performance of the method. Finally, we describe some recent applications of these methods to computer vision and human computer interaction.
About the speaker. Massimiliano Pontil is Professor of Computational Statistics and Machine Learning in the Department of Computer Science at University College London. His research interests are in the field of machine learning with a focus on regularization methods, convex optimization and statistical estimation. He has published about 100 research papers on these topics, is regularly in the programme committee of the leading conferences in the field, is an associate editor of the Machine Learning Journal and is a member of the scientific advisory board of the Max Planck Institute for Biological Cybernetics, Germany.

Seminar: Performance bounds in robust & stochastic optimal control problems
2012-09-13 15:00
Title: Performance bounds in robust & stochastic optimal control problemsSpeaker: Bart Van ParysAffiliation: Automatic Control Laboratory at Swiss Federal Institute of TechnologyLocation: Room 308 Computing DepartmentTime: 3:00pm
Abstract. We present a new method to bound the performance of controllers for uncertain linear systems with mixed state and input constraints and bounded persistent disturbances. We take as a performance metric either an expected-value or minimax discounted cost over an infinite horizon, and provide a method for computing a lower bound on the achievable performance of any causal control policy in either case. Our lower bound is compared to an upper performance bound provided by restricting the choice of controller to one that is affine in the observed disturbances, and we show that the two bounds are closely related. In particular, the lower bounds have a natural interpretation in terms of affine control policies that are optimal for a problem with a restricted disturbance set. We show that our performance bounds can be computed via solution of a finite dimensional convex optimization problem, and provide numerical examples to illustrate the efficacy of our method.
About the speaker. Bart holds a BA degree in electrical engineering, and a MA degree in applied/engineering mathematics, both from the University of Leuven. Since September 2011 he has been a PhD student in the Swiss Federal Institute of Technology (ETH Zürich) under the supervision of Prof. Manfred Morari and Dr. Paul Goulart.

Seminar: Optimisation with PDE constraints using automated consistent adjoints of finite element models
2012-08-30 14:00
Title: Optimisation with PDE constraints using automated consistent adjoints of finite element modelsSpeaker: Simon FunkeAffiliation: Applied Modelling and Computation Group at Imperial CollegeLocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm
Abstract. Optimisation with partial differential equations (PDE) as constraints arise in many research areas from science engineering to finance. Typical examples are data assimilation for weather forecasting or ocean modelling and shape optimisation for wing designs in which PDEs enforce the laws of physics. The resulting optimisation problems are constrained by these nonlinear, time dependent differential equations which can be computationally extremely demanding to solve. Therefore the usage of gradient based optimisation algorithms is usually essential to reduce the number of optimisation iterations. In this talk we present work towards a new framework for solving PDE constrained optimisation problems that aims to automate many of the steps involved in solving these kind of problems. Given a differentiable PDE model, the parameter set and a functional of interest, it applies gradient based optimisation to solve the optimisation problem. The key feature of this framework is the efficient gradient computation by automatically deriving and solving the associated the adjoint equation. The framework is demonstrated on examples for steady and unsteady optimal control problems. One of the major difficulties in practice is the derivation and implementation of the adjoint system to efficiently compute gradient information; Naumann (2011) described it as “[…] one of the great open challenges in the field of High-Performance Scientific Computing” for large scale simulation code. There are two current approaches to derive the adjoint equation each of which suffer from their own limitations. Algorithmic differentiation (AD) derives the adjoint model directly from the model source code. In practice this technique has strong restrictions, and requires a major initial and ongoing investment to prepare the code for automatic adjoint generation. An alternative is to formulate the adjoint PDE and to discretise this separately. This approach, known as the continuous adjoint has the disadvantage that two different model code bases must be maintained and manually kept synchronised as the model develops. In this talk, we present an alternative approach where the PDE is formulated in a high level language that resembles the matematical notation. The model is automatically generated using code generation (using the FEniCS project). In this approach it is the high level code specification which is differentiated, a task very similar to the formulation of the continuous adjoint. However since the forward and adjoint models are generated automatically, the difficulty of maintaining them vanishes and the software engineering process is therefore robust. The scheduling and execution of the adjoint model, including the application of an appropriate checkpointing strategy is managed by a library called libadjoint. In contrast to the conventional algorithmic differentiation description of considering a model as a series of primitive mathematical operations, libadjoint employs a new abstraction of considering the model as a sequence of discrete equations which are assembled and solved. It is the coupling of the respective abstractions employed by libadjoint and the FEniCS project which produces the adjoint model automatically, without further intervention from the model developer.
About the speaker. Simon is a PhD student in the Applied Modelling and Computation Group at Imperial College.

Seminar: Robust Pricing of Monopolistic Cloud Computing Services with Service Level Agreements
2012-07-05 16:30
Title: Robust Pricing of Monopolistic Cloud Computing Services with Service Level AgreementsSpeaker: Vladimir RoitchAffiliation: Department of Computing – Imperial College LondonLocation: CPSE seminar room (C615 Roderic Hill)Time: 4:30pm
Abstract. Cloud Computing is a new computing paradigm that gives end-users on-demand access to computing resources of companies that maintain large data centres. Here, we address the optimal pricing of cloud computing services from the perspective of a monopolistic service provider that needs to manage demand responsiveness and uncertainty. We formulate the pricing problem for on-demand services as a multi-stage stochastic program and model service level agreements via chance constraints. Under weak assumptions about the demand uncertainty we show that the resulting model can be reduced to an equivalent two-stage stochastic program. As cloud computing is only just emerging, it is impossible to reliably estimate demand distributions from historical data. Indeed, such data may even be difficult to collect. We address this type of model uncertainty by adopting a distributionally robust approach, assuming that only information about the location, size and support (but not the shape) of the demand distribution is available. We show that the arising robust model can be reformulated as a second-order cone program, and we analytically derive the worst-case distributions. Several extensions of the basic model are discussed. First, we study generalized models in which higher-order moments of the demand distribution are known. Next, we include multiple products and account for different product qualities. Finally, we investigate the possibility of selling unused capacity (if any) on a spot market.
About the speaker.

Seminar: A decision rule approach to medium-term hydropower scheduling under uncertainty
2012-07-05 16:00
Title: A decision rule approach to medium-term hydropower scheduling under uncertaintySpeaker: Paula RochaAffiliation: Department of Computing – Imperial College LondonLocation: CPSE seminar room (C615 Roderic Hill)Time: 4:00pm
Abstract. We present a multistage stochastic optimisation model for the medium-term scheduling of a cascaded hydropower system. Electricity spot prices change on a much shorter time scale than the hydrological dynamics of the reservoirs in the cascade. We exploit this property to reduce computational complexity: we partition the planning horizon into hydrological macroperiods, and we account for intra-stage price variability by using price duration curves. Moreover, we restrict the space of recourse decisions to those affine in the observable data, thereby obtaining a tractable approximate problem.
About the speaker.

Seminar: Protection at All Levels: Probabilistic Envelope Constraints
2012-07-03 14:00
Title: Protection at All Levels: Probabilistic Envelope ConstraintsSpeaker: Dr. Xu HuanAffiliation: Department of Mechanical Engineering at National University of SingaporeLocation: CPSE Seminar room (C616 Roderic Hill)Time: 2:00pm
Abstract. Optimization under chance constraints is a standard approach to ensure that bad events such as portfolio losses, are unlikely to happen. They do nothing, however, to protect more against terrible events (e.g., deep portfolio losses, or bankruptcy). In this talk, we will propose a new decision concept, termed "probabilistic envelop constraint", which extends the notion of chance constraints, to a formulation that provides different probabilistic guarantees at each level of constraint violation. Thus, we develop a notion of guarantee across the spectrum of disasters, or rare events, ensuring these levels of protection hold across the curve, literally. We further show that the corresponding optimization problem can be reformulated as a semi-infinite optimization problem, and provide conditions that guarantee its tractability. Interestingly, the resulting formulation is what is known as a comprehensive robust optimization in literature. This work thus provides a new fundamental link between two main methodologies in optimization under uncertainty: stochastic optimization and robust optimization. This is a joint work with Constantine Caramanis (UT-Austin) and Shie Mannor (Technion).
About the speaker. Huan Xu has been an assistant professor of Mechanical Engineering of National University of Singapore since 2011. He obtained his Ph. D. degree in ECE from McGill University, Canada, in 2009, and was a postdoctral research fellow of the University of Texas at Austin prior to joining NUS. His current research interest focuses on learning and decision-making in large-scale complex systems, including machine learning, high-dimensional statistics, robust and adaptable optimization, robust sequential decision making, and applications to large-scale systems. He has published in leading operations research and machine learning journals including Operations Research, Math. Oper. Res., IEEE Info. Theory, JMLR, and conferences including ICML, NIPS, and COLT.

Seminar: Time-Critical Cooperative Path-Following Control of Multiple UAVs
2012-07-02 14:00
Title: Time-Critical Cooperative Path-Following Control of Multiple UAVsSpeaker: Prof. Naira HovakimyanAffiliation: Department of Mechanical Science and Engineering at University of Illinois at Urbana-ChampaignLocation: Room 212 William PennyTime: 2:00pm
Abstract. Worldwide, there has been growing interest in the use of autonomous vehicles to execute cooperative missions of increasing complexity without constant supervision of human operators. Despite significant progress in the field of cooperative control, several challenges need to be addressed to develop strategies capable of yielding robust performance of a fleet in the presence of complex vehicle dynamics, communications constraints, and partial vehicle failures. In this talk, we will present a theoretical framework for the development of decentralized strategies for cooperative motion control of multiple vehicles that must meet stringent spatial and temporal constraints. The approach adopted applies to teams of heterogeneous systems, and does not necessarily lead to swarming behavior. Flight test results of a coordinated road search mission involving multiple small tactical UAVs will be discussed to demonstrate the efficacy of the multi-vehicle cooperative control framework presented.
About the speaker. Naira Hovakimyan received her M.S. in Theoretical Mechanics and Applied Mathematics in 1988 from Yerevan State University in Armenia. She received her Ph.D. in Physics and Mathematics in 1992, in Moscow, from the Institute of Applied Mathematics of Russian Academy of Sciences, majoring in optimal control and differential games. In 1997 she was awarded a governmental postdoctoral scholarship to work in INRIA, France. In 1998 she was invited to the School of Aerospace Engineering of Georgia Tech, where she worked as a research faculty member until 2003. In 2003 she joined the Department of Aerospace and Ocean Engineering of Virginia Tech, and in 2008 she moved to the University of Illinois at Urbana-Champaign, where she is a professor and Schaller faculty scholar. She is the 2011 recipient of the AIAA Mechanics and Control of Flight Award. She has coauthored one book and more than 250 refereed publications. Her research interests are in the theory of robust adaptive control and estimation with an emphasis on aerospace applications, control in the presence of limited information, networks of autonomous systems and game theory. She is an associate fellow and life member of AIAA, a Senior Member of IEEE, and a member of AMS and ISDG.

Seminar: Modeling and Solution Methods for Stochastic Programming Problems Under Endogenous Observation of Uncertainty
2012-06-21 14:00
Title: Modeling and Solution Methods for Stochastic Programming Problems Under Endogenous Observation of UncertaintySpeaker: Dr. Christos MaraveliasAffiliation: Department of Chemical and Biological Engineering at the University of Wisconsin&#45Location: Room 219A William PennyTime: 2:00pm
Abstract. We first present an overview of optimization problems under uncertainty and multi-stage stochastic programming methods. We then discuss applications where the decision maker alters the underlying stochastic process by affecting the timing of uncertainty observation, i.e. problems under endogenous observation of uncertainty. We discuss how this important but less studied class of problems can be formulated as a large-scale multi-stage stochastic programming model. To address this challenging problem, we develop a number of theoretical results, modeling methods and computational techniques. First, we show how the structure of the problem can be exploited to formulate substantially smaller yet tighter models. Second, we discuss a number of approximations (e.g. finite-horizon approximation for rolling-horizon approaches) that can be used to obtain solutions of high quality. Third, we present a novel branch-and-cut algorithm where we start from a reduced model and add essential constraints only if they are violated. The presented methods are applied to the planning of clinical trials in the pharmaceutical research and development pipeline.
About the speaker. Christos obtained his Diploma in Chemical Engineering from the National Technical University of Athens. He then moved to the London School of Economics (London, UK), where he received an MSc in Operational Research. After completing his military service in Greece, he went to Carnegie Mellon University where he worked towards his PhD under the supervision of Professor Grossmann. In the fall of 2004 he joined the faculty of the Department of Chemical and Biological Engineering at the University of Wisconsin - Madison. He is a recipient of the Inaugural Olaf A. Hougen Fellowship, an NSF CAREER award, and the 2008 W. David Smith Jr. Award from the CAST division of ACIChE. Christos' primary research interests are in the areas of a) chemical production planning and scheduling, b) process synthesis, with an emphasis on biofuels, c) optimization under uncertainty, and d) the development of computational tools for the design of chemical and biological catalysts.

Seminar: On Control and Random Dynamical Systems in Reproducing Kernel Hilbert Spaces
2012-05-25 14:00
Title: On Control and Random Dynamical Systems in Reproducing Kernel Hilbert SpacesSpeaker: Dr. Boumediene HamziAffiliation: Department of Mathematics of Imperial CollegeLocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm
Abstract. We introduce a data-based approach to estimating key quantities which arise in the study of nonlinear control systems and random nonlinear dynamical systems. Our approach hinges on the observation that much of the existing linear theory may be readily extended to nonlinear systems – with a reasonable expectation of success – once the nonlinear system has been mapped into a high or infinite dimensional Reproducing Kernel Hilbert Space. In particular, we develop computable, non-parametric estimators approximating controllability and observability energy functions for nonlinear systems, and study the ellipsoids they induce. It is then shown that the controllability energy estimator provides a key means for approximating the invariant measure of an ergodic, stochastically forced nonlinear system. We also apply this approach to the problem of model reduction of nonlinear control systems. In all cases the relevant quantities are estimated from simulated or observed data. This is joint work with J. Bouvrie (Duke University).
About the speaker. Boumediene Hamzi is a Marie Curie Fellow at the Department of Mathematics of Imperial College. He obtained his Ph.D. in Control Theory from the University of Paris-Sud and then held different visiting academic positions at UCDavis, the MSRI and then Duke University. His current research interests are the analysis of control and random dynamical systems in Reproducing Kernel Hilbert Spaces in view of developing data-based methods for the analysis and prediction of random dynamical systems and control strategies for nonlinear systems on the basis of observed data (rather than a pre-described model).

Seminar: Tutorial on Stochastic Calculus
2012-05-15 14:00
Title: Tutorial on Stochastic CalculusSpeaker: Florian LockerAffiliation: Institute for Statistics and Mathematics of WULocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm
Abstract. This tutorial session provides an introduction to stochastic calculus along the lines of the Merton model for asset pricing. Some properties of the components of this model will be explained and used to construct basic stochastic integrals. I will then proceed with the most important theorems in the general case, notably Itō’s lemma, and evaluate some examples.
About the speaker. Florian studied economics and finance at the University of Innsbruck and Tulane University and joined the Institute for Statistics and Mathematics at WU Vienna as a PhD student in 2008. He is interested in methods concerning the hedging of derivative assets within incomplete markets and when assets exhibit jumps, and their numerical implementation. He is currently visiting the QUADS research group at Imperial College.

Seminar: Scheduling Modular Projects on a Bottleneck Resource
2012-05-14 11:00
Title: Scheduling Modular Projects on a Bottleneck ResourceSpeaker: Dr. Roel Leus Affiliation: Faculty of Business and Economics of KU LeuvenLocation: Room 572A Huxley BuildingTime: 11:00am
Abstract. In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project in order to maximize the expected profit when the activities have a probability of failure and when an activity's failure can cause its module and thereby the overall project to fail. A module succeeds when at least one of its constituent activities is successfully executed. All activities are scheduled on a scarce resource that is modeled as a single machine. We describe various policy classes, establish the relationship between the classes, develop exact algorithms to optimize over two different classes (one dynamic program and one branch-and-bound algorithm), and examine the computational performance of the algorithms on randomly generated instance sets.
About the speaker. Roel Leus holds a Master's degree (1998) in Business Engineering and a PhD (2003) in Applied Economics from KU Leuven (Belgium). He is currently Associate Professor of Operations Research at the Faculty of Business and Economics of KU Leuven. He has been a visiting researcher at London Business School (2004) and at LAAS-CNRS Toulouse (2008).

Seminar: Robust Dynamic Risk Measures
2012-04-27 15:00
Title: Robust Dynamic Risk MeasuresSpeaker: Dimitra BampouAffiliation: Imperial College LondonLocation: Room 218 Huxley Building Time: 3:00pm
Abstract. Recent progress in the theory of dynamic risk measures has found a strong echo in stochastic programming, where the time consistency of dynamic decision making under uncertainty is currently under scrutiny. In this talk we first review the concepts of coherence and time consistency of dynamic risk measures and then discuss their ramifications for stochastic programming. Next, we extend these concepts to stochastic programming models subject to distributional ambiguity, which motivates us to introduce robust dynamic risk measures. We discuss conditions under which these robust risk measures inherit coherence and time consistency from their nominal counterparts. We also propose an approximation scheme based on polynomial decision rules for solving linear multistage stochastic programs involving robust dynamic risk measures. The theoretical concepts are illustrated through numerical examples in the context of inventory management.
About the speaker.

Seminar: Development and application of automatic force field parameterization software for molecular simulation
2012-04-26 14:00
Title: Development and application of automatic force field parameterization software for molecular simulationSpeaker: Dr. Lee-Ping WangAffiliation: Stanford UniversityLocation: Room 218Time: 2:00pm
Abstract. Force fields are empirical potential energy functions that describe molecules and their interactions; they constitute the physical foundation for simulations of atomic and molecular motion. The accuracy of a force field is determined by empirical parameters, and the choice of optimal parameters has been a difficult challenge for decades. The molecular simulation community is in need of an automatic and systematic method for force field parameterization, which would revolutionize the field by providing greatly improved simulation accuracy and reproducibility of force field development. With this goal in mind, I have developed an open-source software package called ForceBalance to perform automatic force field parameterization. The software is built around a standardized procedure for force field development, interfaces easily with classical and quantum simulation codes, and has the ability to produce force fields that are optimized to reproduce any experimental or theoretical reference data. I will introduce the concepts and implementation of ForceBalance, provide a simple demonstration of the software, and discuss opportunities for collaboration.
About the speaker. Lee-Ping Wang graduated from U.C Berkeley with a B.A. in Physics in 2006. He entered graduate school in the chemistry department at MIT, where he worked with Prof. Troy Van Voorhis on various topics in theoretical chemistry such as water splitting catalysis, QM/MM methods, and force field development, graduating with a Ph.D. in 2011. Lee-Ping is now working as a postdoctoral fellow at Stanford University with Profs. Todd Martinez and Vijay Pande where he is continuing to refine force field development methods and applying them to biomolecular simulation.

Seminar: Lifting Methods for Generalized Semi-Infinite Programs
2012-03-22 15:00
Title: Lifting Methods for Generalized Semi-Infinite ProgramsSpeaker: Dr. Boris HouskaAffiliation: Centre for Process Systems Engineering at Imperial CollegeLocation: Room 217 Huxley BuildingTime: 3:00pm
Abstract. In this talk we present numerical solution strategies for generalized semi-infinite optimization problems (GSIP), a class of mathematical optimization problems which occur naturally in the context of design centering problems, robust optimization problems, and many fields of engineering science. GSIPs can be regarded as bilevel optimization problems, where a parametric lower-level maximization problem has to be solved in order to check feasibility of the upper level minimization problem. In this talk we discuss three strategies to reformulate a class lower-level convex GSIPs into equivalent standard minimization problems by exploiting the concept of lower level Wolfe duality. Here, the main contribution is the discussion of the non-degeneracy of the corresponding formulations under various assumptions. Finally, these non-degenerate re-formulations of the original GSIP allow us to apply standard nonlinear optimization algorithms.
About the speaker. Boris Houska studied mathematics and physics at the university of Heidelberg in 2003-2008. He obtained his Ph.D. in 2011 in Electrical Engineering at the Optimization in Engineering Center (OPTEC) at K.U. Leuven. Since 2012 he is a postdoctoral researcher at the Centre of Process Systems Engineering at Imperial College. His research interests include numerical optimization and optimal control, robust optimization, as well as fast MPC algorithms.

Seminar: Payment Rules through Discriminant-Based Classifiers
2012-03-21 14:00
Title: Payment Rules through Discriminant-Based ClassifiersSpeaker: Prof. David ParkesAffiliation: School of Engineering and Applied Sciences at Harvard UniversityLocation: Room 217-218 Huxley BuildingTime: 2:00pm
Abstract. In mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex-post regret, we are able to adapt techniques of statistical machine learning to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi- dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a special discriminant function structure such that it implicitly establishes a payment rule with desirable incentive properties. We discuss applications to a multi-minded combinatorial auction with a greedy winner-determination algorithm and to an assignment problem with egalitarian outcome rule. Experimental results demonstrate both that the construction produces payment rules with low ex-post regret, and that penalizing classification errors is effective in preventing failures of ex-post individual rationality.
About the speaker. David C. Parkes is the Gordon McKay Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. He was the recipient of the NSF Career Award, the Alfred P. Sloan Fellowship, the Thouron Scholarship, the Harvard University Roslyn Abramson Award for Teaching. Parkes received his Ph.D. degree in Computer and Information Science from the University of Pennsylvania in 2001, and an M.Eng. (First class) in Engineering and Computing Science from Oxford University in 1995. At Harvard, Parkes founded the Economics and Computer Science research group. His research interests include mechanism design, electronic commerce, market design, and social computing. Parkes is editor of Games and Econonic Behavior, and on the editorial boards of JAAMAS, ACM TEAC and INFORMS J. Computing. Parkes also serves as the Chair of the ACM SIG on Electronic Commerce and was the Program Chair of ACMEC’07 and AAMAS’08, and General Chair of ACMEC’10.

Seminar: The Long-run Impact of Wind Power on Electricity Prices and Generating Capacity (joint work with Nicholas Vasilakos)
2012-03-08 14:00
Title: The Long-run Impact of Wind Power on Electricity Prices and Generating Capacity (joint work with Nicholas Vasilakos)Speaker: Prof. Richard Green – Alan and Sabine Howard Professor of Sustainable Energy Business at Imperial College Business SchoolAffiliation: Imperial College LondonLocation: Room 344A Huxley BuildingTime: 2:00pm
Abstract. This paper uses a market equilibrium model to calculate how the mix of generating capacity would change if large amounts of intermittent renewables are built in Great Britain, and what this means for operating patterns and the distribution of prices over time. If generators bid their marginal costs, we find that the changes to the capacity mix are much greater than the changes to the pattern of prices. Thermal capacity falls only slightly in response to the extra wind capacity, and there is a shift towards power stations with higher variable costs (but lower fixed costs). The changes to the pattern of prices, once capacity has adjusted, are relatively small. In an oligopolistic setting, strategic generators will choose lower levels of capacity. If wind output does not receive the market price, then mark-ups on thermal generation will be lower in a system with large amounts of wind power.
About the speaker. Richard Green is the Alan and Sabine Howard Professor of Sustainable Energy Business at Imperial College Business School. He was previously Professor of Energy Economics and Director of the Institute for Energy Research and Policy at the University of Birmingham, and Professor of Economics at the University of Hull. He started his career at the Department of Applied Economics and Fitzwilliam College, Cambridge. He has spent time on secondment to the Office of Electricity Regulation and has held visiting appointments at the World Bank, the University of California Energy Institute and the Massachusetts Institute of Technology. He has been studying the economics and regulation of the electricity industry for over 20 years. He has written extensively on market power in wholesale electricity markets and has also worked on transmission pricing. More recently, the main focus of his work has been on the impact of low-carbon generation (nuclear and renewables) on the electricity market, and the business and policy implications of this.

Seminar: Enclosing with Simple Bodies
2012-02-23 14:00
Title: Enclosing with Simple BodiesSpeaker: Dr. Selin Damla Ahipasaoglu – research officerAffiliation: Management Science Group at LSELocation: Room 217 Huxley BuildingTime: 2:00pm
Abstract. The Minimum Volume Enclosing Ellipsoid and Minimum Enclosing Ball problems are related to covering a given set of points with an ellipsoid or a ball with the smallest volume possible. These problems have many applications, especially in statistics. We will survey recent theoretical results and take a look at efficient algorithms for solving these problems. We will show that these algorithms can be used for very large data sets.
About the speaker. Selin Damla Ahipasaoglu received her PhD in 2009 from Cornell University under the supervision of Prof. Mike Todd. After her PhD, she worked as a postdoctoral researcher at Princeton University and London School of Economics. She specialises in developing algorithms for large scale optimization problems, in particular first-order methods for convex problems. She is also working on auctions and game theory. In April 2012, she will be joining the Singapore University of Technology and Design as an assistant professor.

Seminar: Complexity and heuristics in stochastic optimization
2012-02-15 14:00
Title: Complexity and heuristics in stochastic optimizationSpeaker: Prof. Teemu Pennanen – Professor of Mathematical Finance Probability and StatisticsAffiliation: King’s College LondonLocation: Room 218 Huxley BuildingTime: 2:00pm
Abstract. Combining recent results on numerical integration and convex optimization, we derive a polynomial bound on the worst case complexity of a class of static stochastic optimization problems. We then describe a technique for reducing dynamic problems to static ones. The reduction technique is only a heuristic but it can effectively employ good guesses for good solutions. This is illustrated on an 82-period problem coming from pension insurance industry.
About the speaker. Teemu Pennanen is the Professor of Mathematical Finance, Probability and Statistics at King’s College, London. Before joining KCL, Professor Pennanen worked as Managing Director at QSA Quantitative Solvency Analysts Ltd, with a joint appointment as Professor of Stochastics at University of Jyvaskyla, Finland. His earlier appointments include a research fellowship of the Finnish Academy and several visiting positions in universities abroad.

Seminar: Performance-Based Contracts for Outpatient Medical Services
2012-02-08 14:00
Title: Performance-Based Contracts for Outpatient Medical ServicesSpeaker: Dr. Houyuan Jiang – Senior Lecturer in Management ScienceAffiliation: Judge Business School – University of CambridgeLocation: Room 218 Huxley BuildingTime: 2:00pm
Abstract. In recent years, the performance-based approach to contracting for medical services has been gaining popularity across different healthcare delivery systems, both in the US (under the name of “Pay-for-Performance”, or P4P), and abroad (“Payment-by-Results”, or PbR, in the UK). The goal of our research is to build a unified performance-based contracting (PBC) framework that incorporates patient access-to-care requirements and that explicitly accounts for the complex outpatient care dynamics facilitated by the use of an online appointment scheduling system. We address the optimal contracting problem in a principal-agent framework where a service purchaser (the principal) minimizes her cost of purchasing the services and achieves the performance target (a waiting time target) while taking into account the response of the provider (the agent) to the contract terms. Given the incentives offered by the contract, the provider maximizes his payoff by allocating his outpatient service capacity among three patient groups: urgent patients, dedicated advance patients and flexible advance patients. We model the appointment dynamics as that of an M=D=1 queue and analyze several contracting approaches under adverse selection (asymmetric information) and moral hazard (private actions) settings. We study the first-best and the second-best solutions, as well as their specific contracting implementation schemes. Our results show that simple and popular schemes used in practice cannot implement the first-best solution and that the linear PBC cannot implement the second-best solution. In order to overcome these limitations, we propose a threshold-penalty PBC approach and show that it coordinates the system for an arbitrary patient mix and that it achieves the second-best performance for the setting where all advance patients are dedicated.
About the speaker.

Seminar: A Stochastic Capacity Expansion Model for the UK Electricity System
2012-01-26 17:30
Title: A Stochastic Capacity Expansion Model for the UK Electricity SystemSpeaker: Angelos GeorghiouAffiliation: Department of Computing – Imperial College LondonLocation: Room 217-218 Huxley BuildingTime: 5:30pm
Abstract. Energy markets are currently undergoing one of their most radical changes in history. On one hand, market liberalisation leads to a shift from state-owned utilities with a focus on failure resilience towards competitive markets where reliability is traded off with costs. This will result in a much higher utilisation of generation and transmission facilities, which in turn leads to a less predictable system behaviour and more frequent outages. Moreover, predictions about climate change dictate the gradual replacement of non-renewable energy sources with renewable alternatives such as solar or wind power. Contrary to non-renewable energy, the electricity delivered from renewable sources is highly uncertain due to the intermittency of solar radiation, wind etc. Both developments highlight the need to accommodate uncertainty in the design and management of future energy systems. This work aims to identify the most cost-efficient expansion of the UK energy grid, given a growing future demand for energy and the target to move towards a more sustainable energy system. To this end, we develop a multi-stage stochastic program where the investment decisions (generation units and transmission lines that should be built) are taken here-and-now, whereas the operating decisions are taken in hourly time stages over a horizon of 30 years. The resulting problem contains several thousand time stages and is therefore severely intractable. We develop a novel problem reformulation, based on the concept of time randomization, that allows us to equivalently reformulate the problem as a two-stage stochastic program. By taking advantage of the simple structure of the decision rule approximation scheme, we can model and solve a problem that optimises the entire UK energy grid with nearly 400 generators and 1000 transmission lines.
About the speaker.

Seminar: Multistage Stochastic Portfolio Optimisation in Deregulated Electricity Markets Using Linear Decision Rules
2012-01-26 17:00
Title: Multistage Stochastic Portfolio Optimisation in Deregulated Electricity Markets Using Linear Decision RulesSpeaker: Paula RochaAffiliation: Department of Computing – Imperial College LondonLocation: Room 217-218 Huxley BuildingTime: 5:00pm
Abstract. The deregulation of electricity markets often poses great financial risks to retailers who procure electric energy on the spot market to satisfy their customers’ electricity demand. To hedge against this risk exposure, retailers often hold a portfolio of electricity derivative contracts. In this talk, we present a multistage stochastic mean-variance optimisation model for the management of such a portfolio. To reduce computational complexity, we perform two approximations: stage-aggregation and linear decision rules (LDR). The LDR approach consists of restricting the space of recourse decisions to those affine in the history of the random parameters. When applied to mean-variance optimisation models, it leads to convex quadratic programs. Since their size grows typically only polynomially with the number of decision stages, they are amenable to efficient numerical solution. Our numerical experiments highlight the value of adaptivity inherent in the LDR method and its potential for enabling scalability to portfolio optimisation problems with many decision stages.
About the speaker.

Seminar: Universal decision rule approximations for dynamic decision-making under uncertainty
2012-01-25 17:00
Title: Universal decision rule approximations for dynamic decision-making under uncertaintySpeaker: Phebe VayanosAffiliation: Department of Computing – Imperial College LondonLocation: Room 217-218 Huxley BuildingTime: 5:00pm
Abstract.
About the speaker.

Seminar: Steam Engines Jet Fighters and Credit Crises
2012-01-12 14:00
Title: Steam Engines Jet Fighters and Credit Crises Speaker: Dr George CooperAffiliation: BlueCrest Capital Location: Room 217-218 Huxley BuildingTime: 2:00pm
Abstract. The talk will discuss some of the underlying causes of the financial crisis with particular focus on financial market instability, monetary policy and the influence of the Efficient Market Hypothesis.
About the speaker. George Cooper is a fund manager at BlueCrest Capital in London. Prior to joining BlueCrest George was the head of European interest rate research at JP Morgan and has also worked for both Deutsche Bank and Goldman Sachs. George’s book “The Origin of Financial Crises: Central Banks, Credit Bubbles and the Efficient Market Fallacy” was published in August 2008 and has now been translated into over a dozen languages. George holds a PhD in engineering from Durham University.

Seminar: Robust Optimization of Dynamic Systems and Its Applications.
2012-01-06 15:00
Title: Robust Optimization of Dynamic Systems and Its Applications.Speaker: Dr. Boris Houska Affiliation: Location: CPSE Seminar room (C616 Roderic Hill)Time: 3:00pm
Abstract. This talk gives an introduction to numerical methods for the robust optimization of uncertain dynamic systems. In contrast to standard differential equations, which describe the propagation of a single vector-valued trajectory in time, uncertain dynamic systems propagate a set valued function: the uncertainty tube. For the case that control inputs are available this uncertainty tube can be influenced and optimized such that certain robustness criteria are met. The aim of the first part of the talk is to explain how to formulate and solve such tube-based robust optimal control problems.The second part of the talk is about the software environment and algorithm collection ACADO Toolkit, which implements tools for automatic control and dynamic optimization. It provides a general framework for using a great variety of algorithms for direct optimal control, including robust optimal control and model predictive control. The ACADO Toolkit is implemented as a selfcontained C++ code, while the object-oriented design allows for convenient coupling of existing optimization packages and for extending it with user-written optimization routines. We present numerical examples from the field of mechanics and biochemical engineering.
About the speaker.

Seminar: Scenario-Free Stochastic Programming with Polynomial Decision Rules
2011-12-08 17:00
Title: Scenario-Free Stochastic Programming with Polynomial Decision RulesSpeaker: Dimitra BampouAffiliation: Department of Computing – Imperial College LondonLocation: CPSE Seminar room (C615 Roderic Hill)Time: 5:00pm
Abstract. Multi-stage stochastic programming provides a versatile framework for optimal decision making under uncertainty, but it gives rise to hard functional optimization problems since the adaptive recourse decisions must be modeled as functions of some or all uncertain parameters. We propose to approximate these recourse decisions by polynomial decision rules and show that the best polynomial decision rule of a fixed degree can be computed efficiently. We also show that the suboptimality of the best polynomial decision rule can be estimated efficiently by solving a dual version of the stochastic program in polynomial decision rules.
About the speaker.
