Show The Graduate Center Menu

Stochastic Optimization

 
 

Stochastic Optimization

Instructor: Professor Felisa Vazquez-Abad


Preamble

Optimization is the "science of the best". Today, there is a sound body of models and methods to find the best decision or choices. These methods are widely used in airlines, hospitals, banks, computer engineering, manufacturing and scheduling, among other sectors. We will specialize our study to stochastic optimization, which incorporates randomness (uncertainty). Among the problems that we will discuss are the following. Aerospace engineers need to control fuel and routes of vehicles to make a rendez-vous in space, under various risks. The value of an American option in finance can be obtained in terms of an optimal exercise time. An urban transportation subway needs to revise and automatically adapt frequencies to operate optimally under changing demands. Telecommunication and manufacturing networks need algorithms for optimal routing and scheduling, under demand uncertainty. These seemingly different problems can be solved using computer methods for optimization under randomness.

Algorithms can be compared in terms of speed of execution and accuracy in the approximation. Central to our course is the analysis of convergence (in a probabilistic sense) of these computer methods. We will study a mathematical approach for algorithmic efficiency using risk-theoretical concepts that allows to rank methods via the ubiquitous trade-off between precision and speed. We will illustrate difficult concepts with actual problems for students to code and see the methods at work.
 

Rationale

Markov chain models abound in Computer Science applications, from speech recognition and machine learning to bioinformatics. However most undergraduate programs in CS do not have courses on the subject. This course fills that need.
 

Learning Goals

  • Acquire fundamental knowledge in the area of stochastic processes and optimization.
  • Formulate mathematical models for stochastic optimization.
  • Formulate the required characteristics for the computer code.
  • Understand the convergence properties of various methods.
  • Understand how different methods apply to different models in machine learning, intelligent agents and self-optimized complex systems.
  • Acquire the capability to carry out consulting projects in the public and private sector.

In addition, students who succeed the course will be better placed to conduct fundamental research in stochastic optimization and provide advise concerning current optimization practices and methodologies for continuous optimization and "big data" search methods such as evolutionary algorithms.
 

Assessment

Learning goals 2,3, and 6 will be assessed through the team projects via a class presentation (15%) and a final report (20%). Learning goals 1, 4 and 5 will be assessed through the homework assignments (30%) and the final exam (35%). Threshold: in order to pass the subject, a minimum of 55 in the exam is required.
 

Course Description

We will study continuous optimization, dealing with continuous decision variables (how much to invest, how much hydroelectric energy to produce, etc), for which we will provide a summary of known convergence results. In a final stage, we will discuss some methods for discrete optimization (how many buses should a transportation company buy, DNA sequencing, etc) and include reading current research papers.

The subject of stochastic optimization integrates sophisticated knowledge in probability theory, functional analysis, dynamical systems and computer simulation. Our pedagogical formula focuses on individual needs and goals, and we will emphasize understanding through hands-on experience with examples and computer exercises. We will provide a full set of lecture notes with the mathematical detail.
 

Syllabus

  • Overview of deterministic non-linear constrained optimization

  • The iterative method as an Ordinary Differential Equation

  • Stochastic approximation methodology

  • Asymptotic efficiency of numerical algorithms

  • Statistical estimation of gradients, sensitivity analysis

  • Stochastic approximation at work (examples of applications and case studies)

  • Discrete optimization: MCMC, simulated annealing, randomized methods, evolutionary algorithms.


Prerequisites

A good background in probability and statistics. Some experience with computer simulation. This course will be suitable for students specializing in Computer Science, Mathematics and Statistics, Electrical and Computer Engineering, Bioinformatics and Geography.
 

Lectures

The course consists of an equivalent of 15 two-hour lectures with assigned reading. There will be student presentations of research projects. A full set of Lecture Notes will be provided with exercise suggestions. Recent research papers will be recommended according to the interests of the students.
 

Historical Remarks

This course has evolved over the years to its present form. Parts of the material were developed earlier on from 1996 to 2004, as part of a course in Stochastic Modelling and Simulation that I taught at the Computer Science Department at the University of Montreal, with students in various joint programs in Computer Science, Management, Industrial Engineering, Finance, and Mathematics. I taught a preliminary version of this subject to graduate and postdoctoral students in Electrical Engineering at the University of Melbourne in 1999, and then as an Honours course for students in Mathematics and Statistics from 2004 to 2008. The current version was delivered as a Doctoral course for Engineering students in the University of Vienna in 2009. Students have expressed in their evaluations that they have enjoyed and appreciated the learning process just as much as the acquired knowledge, particularly through the research projects.
 
Currently, the lecture notes are being co-authored with Prof Bernd Heidergott (of the Vrije Universiteit) as a full book, incorporating our recent research on the subject of gradient estimation. The topic of stochastic modeling and simulation is my main research area. I have worked on it for many years and some of my publications are the result of refinement of student projects, which they have co-authored. I love the subject and I try to communicate my enthusiasm to younger generations.