aboutpage archive
Syllabus
Saturday, November 17th, 2007Prerequisites: basic linear algebra, multi-variate calculus, probability
Introduction to Optimisation
Motivating Examples (Network Applications)
Dynamic Optimization (Dynamic Programming)
Applications to optimal routing
- Fundamental Concepts in Convex Optimization
- Convex Sets and Functions
- Convex Optimization Problems:
- Existence of Solutions
- Optimality Conditions
- Projection Theorem and Separation Theorems
- Lagrangian Duality Theory
- Linear Programming Duality
- Slater Condition
- Karush-Khun-Tucker System
- Static Optimization (vector-space methods)
- Primal Algorithms
- Simplex Algorithm
- Gradient Projection Algorithm
- Dual Algorithms (differentiable case only)
- Primal Algorithms
- Classical Network Flow Problems
- Shortest Path
- Max-Flow Min-Cut
- Distributed Network Optimization
- Kelly’s Utility Maximization Framework
- Examples of routing, congestion control, rate allocation
- Fundamental Concepts and Bellman’s Equation
- Stochastic Shortest Path
- Infinite Horizon Problems
- Discounted Cost
- Average Cost
- Dijkstra’s Shortest Path Algorithm
- Max-Throughput (Tassiulas, Stolyar, and Neely)
- Min-Delay Model (Gallagher’s data routing)
Introduction to Optimisation
Saturday, November 17th, 2007Calendar
Saturday, November 17th, 2007| Monday | |
| 9am – 1pm: Fundamentals of Probability | |
| Tuesday | |
| 9am – 1pm: Generating Functions and Inequalities | |
| 2.30pm-3.30pm: Applications Lecture – Dr. Wilhelm Huisinga, Hamilton Institute.
“Beyond Stabililty: The Mathematics of Molecular Flexibility in the Context of Virtual Screening” | |
| Wednesday | |
| 9am – 1pm: Markov Chains | |
| 2.30pm-3.30pm: Applications Lecture – Dr. Ken Duffy, Hamilton Institute.
“Predicting the performance of IEEE 802.11 wireless networks with | |
| Thursday | |
| 9am – 1pm: Limit Theorems | |
| 2.30pm-3.30pm: Applications Lecture – Prof. Rod Murray-Smith, Hamilton Institute.
“The role of probability in dynamics and interaction” | Friday |
Reading and Course Material
Saturday, November 17th, 2007Background Material
Lecture Notes
Further Reading
P. Billingsley, Probability and Measure, Wiley Inter-Science.
Y. Suhov and M. Kelbert, Probability and statistics by example.
Vol. I., Cambridge University Press.
Syllabus
Saturday, November 17th, 2007Fundamentals of Probability
- Fundamentals
- Review of elementary probability: conditional probability, independence, random variables, expectations, conditional expectation
- Probability triples: Lebesgue-Stieltjes measure and product measure
- Random variables: cdf and pdf, independence, expectation, calculational tools, stochastic processes
- Generating Functions and Inequalities
- Moments and moment generating function
- Inequalities: Markov, Chebyshev, Jensen, Holder
- Conditional probabilities and conditional expectation
- Markov Chains
- Discrete-time Markov chains, finite state space: absorbing chains, ergodic chains, stationary distributions, fundamental matrix
- Discrete-time Markov chains, countable state space: classification of states and chains, time reversible chains
- Stopping times
- Limit Theorems
- Modes of convergence for sequence of random variables
- Weak Law of Large Numbers
- Strong law of large numbers
- Characteristic functions
- Central limit theorem
- Cramer’s theorem
Fundamentals of Probability
Saturday, November 17th, 2007Reading and Course Material
Saturday, November 17th, 2007Background Material
Lecture Notes
Nonnegative Matrices and Positive Systems
Further Reading
A. Berman and R. Plemmons, Nonnegative matrices in the mathematical sciences, SIAM Classics in Applied Mathematics
L. Farina and S. Rinaldi, Positive Linear Systems, Wiley Interscience
A. Berman, M. Neumann, R. Stern, Nonnegative matrices in dynamic systems, Wiley Pure and App Mathematics
Calendar
Saturday, November 17th, 2007| Monday | |
| Bank Holiday | |
| Tuesday | |
| 9am – 12.30pm: Basics of Nonnegative Matrices | |
| Wednesday | |
| ALL DAY: Third Hamilton Institute Workshop on Nonnegative Matrices | Thursday |
| 9am – 11.45am: Third Hamilton Institute Workshop on Nonnegative Matrices | |
| 12.45 pm – 1.45 pm: Applications Lecture – Prof. Shmuel Friedland, University of Illinois, Chicago.
“Examples of Applications of Nonnegative Matrices” | |
| 2pm – 6pm: Graphs and Matrices | |
| Friday | |
| 9am – 10 am: Applications Lecture – Prof. Amy Langville, College of Charleston
“Ranking and Clustering” | |
| 10am – 1pm: Stability and Convergence | |
| 2pm – 6pm: Applications and Extensions |
Syllabus
Saturday, November 17th, 2007Positive Systems and Nonnegative Matrices
- Basics of nonnegative matrices
- Perron theorem for positive matrices
- Frobenius theorem for nonnegative irreducible matrices
- Stochastic matrices and Markov chains
- Graphs and Matrices
- Incidence matrices
- Laplacians
- Colin de Verdiere parameters
- Stability and Convergence
- Z-matrices, M-matrices and P-matrices
- Stability, Diagonal stability and D-stability
- Paracontractivity and Projective metrices
- Applications and Extensions
- Nonnegative matrices and the internet – Google, congestion control
- Completely positive matrices
- Extensions of the Perron-Frobenius theory
