Show The Graduate Center Menu
 
 

Stochastic Optimization

Preamble

Optimization is the "science of the best". Today, there is a sound body of models and methods to nd 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 nance 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 dierent 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 eciency using risk-theoretical concepts that allows to rank

methods via the ubiquitous trade-o between precision and speed. We will illustrate dicult 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 lls that need.


Learning Goals

1. Acquire fundamental knowledge in the area of stochastic processes and optimization.

2. Formulate mathematical models for stochastic optimization.

3. Formulate the required characteristics for the computer code.

4. Understand the convergence properties of various methods.

5. Understand how dierent methods apply to dierent models in machine learning, intelligent agents

and self-optimized complex systems.

6. 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

nal report (20%). Learning goals 1, 4 and 5 will be assessed through the homework assignments (30%)

and the nal 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 nal 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, func-

tional 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 Dierential Equation
  • Stochastic approximation methodology
  • Asymptotic eciency of numerical algorithms
  • Statistical estimation of gradients, sensitivity analysis
  • Stochastic approximation at work (examples of applications and case studies)
  • Discrete optimisation: MCMC, simulated annealing, randomised methods, evolutionary algorithms.


Prerequisites

A good background in probability and statisics. 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 renement of student projects, which they have co-authored. I love the

subject and I try to communicate my enthusiasm to younger generations.