Syllabus – Introduction to Optimisation

Prerequisites: basic linear algebra, multi-variate calculus, probability

Introduction to Optimisation

  1. Fundamental Concepts in Convex Optimization
    1. Convex Sets and Functions
    2. Convex Optimization Problems:
      1. Existence of Solutions
      2. Optimality Conditions
    3. Projection Theorem and Separation Theorems
    4. Lagrangian Duality Theory
      1. Linear Programming Duality
      2. Slater Condition
      3. Karush-Khun-Tucker System
  2. Static Optimization (vector-space methods)
    1. Primal Algorithms

      1. Simplex Algorithm
      2. Gradient Projection Algorithm
    2. Dual Algorithms (differentiable case only)
  3. Motivating Examples (Network Applications)

    1. Classical Network Flow Problems

      • Shortest Path
      • Max-Flow Min-Cut
    2. Distributed Network Optimization
      • Kelly’s Utility Maximization Framework
      • Examples of routing, congestion control, rate allocation
  4. Dynamic Optimization (Dynamic Programming)

    1. Fundamental Concepts and Bellman’s Equation
    2. Stochastic Shortest Path
    3. Infinite Horizon Problems
      • Discounted Cost
      • Average Cost
    4. Applications to optimal routing

      • Dijkstra’s Shortest Path Algorithm
      • Max-Throughput (Tassiulas, Stolyar, and Neely)
      • Min-Delay Model (Gallagher’s data routing)