Lecture Schedule

• No class - semester begins Aug. 23rd
  Quirk in the web script I am using so the first lecture will be numbered 2
  

• Review Syllabus
  Linear Programming fundamentals: Formulation, convexity and extreme points
  
• L2. Slides
• L2. Recording

• Linear Programming: Basic feasible solutions and the simplex method.
  Weak and strong duality
  
• L3. Slides
• L3. Recording

• Method of Lagrange multipliers and KKT conditions
  Relationship between dual variables and Lagrange multipliers
  Dual variables and prices
  Piecewise linear formulations - convex and nonconvex
  
• L4. Slides
• L4. Recording

• Integer and binary programming
  Branch and bound method
  Some problem formulations - Least absolute value and set covers
  
• L5. Slides
• L5. Recording

Homework 1 Due

• Path problems formulated as a linear program
  Integer solutions for some path problems
  Network Simplex method - general overview only
  
• L6. Slides
• L6. Recording

• Computational complexity of simplex method
  Interior point methods (brief for now)
  Search in graphs - Dijkstra's algorithm and A*
  
• L7. Slides
• L7. Recording

• Example of graph search - Depth-first, Dijkstra and A*
  General duality (Lagrangean duality)
  
• L8. Slides
• L8. Recording

Homework 2 Due

• Review of homework 1 and 2
  Solutions using the dual
  Lagrangean relaxation - LR
  
• L9. Slides
• L9. Recording

• Continuation of LR examples
  LR for network problems
  Augmented Lagrangean relaxation - ALR
  Link to Lagrangian Relaxation on networks example from MIT
  With some annotations
  
• L10. Slides
• L10. Recording

• Quadratic Programming (QR)
  Solving QR with the simplex method
  General iterative methods and relationship to optimization
  Gauss and Newton methods and relationship to gradient methods
  
• L11. Slides
• L11. Recording

• Some simple ways to approximate gradients - Secant method and sectioning methods
  Convergence characteristics of Gauss and Newton's method based on Mean Value Theorem
  Discussion on modifications / approximations of the derivative
  Newton's method for solving constrained optimization problems
  
• L12. Slides
• L12. Recording

Homework 3 Due

• Out of town - recording only
  HW1 review of extreme directions
  Successive Quadratic Programming (SQP)
  Barrier function methods
  

• Formulating problems to reflect decision-maker preferences
  Multi-objectives and soft constraints
  Utility theory
  Goal progamming and levels of aspirations
  Optimal trade-offs - max-min vs. product
  
• L14. Slides
• L14. Recording

• Out of town - recording only - relatively brief
  Constrained optimization from data - classifiers
  Support vector machines (SVM) as a Quadratic program
  
• L15. Slides
• L15. Recording

• Dimension reduction - principal component analysis (PCA) as constrained optimization
  Arbritrary classification functions - the special case of Artificial Neural Networks
  Backpropagation and the gradient descent method
  
• L16. Slides
• L16. Recording

Homework 4 Due

• High level discussion on data driven methods (data mining) and optimization
  Other classifiers - decision trees and Bayesian analysis
  
• L17. Slides
• L17. Recording

• Population based methods
  Downhill Simplex
  Evolutionary programming vs. Evolutionary strategies
  Genetic algorithms as a special case of ES
  
• L18. Slides
• L18. Recording

• Review homework and practice exam - no slides
  
• L19. Recording

• Midterm Exam - class begins at 9:30
  

• Review midterm exam
  Summary of class to date - see summary table
  Managing uncertainties - Introduction to robust optimization
  
• L21. Slides
• L21. Recording

• More on robust optimization - budget of uncertainty and scenario reduction (brief)
  Introduction to game theory - two player matrix games
  Relationship to linear programming and duality for zero sum games
  
  
• L22. Slides
• L22. Recording

• More on game theory - non-collusion and collusion solutions using KKT conditions
  Some loose ends on methods for including constraints
  Barrier functions and interior point methods
  Active set methods (brief)
  
• L23. Slides
• L23. Recording

• Partial orderings
  Second order cones
  (semi)-Definite cones
  Generalized inequalities
  Second order cone program (SOCP) and Quadratically constrained quadratic program (QCQP)
  
• L24. Slides
• L24. Recording

Homework 5 Due

• Interior point methods and SOCP - calculation of gradient
  More examples of SOCP - Robust linear program; Sum of norms
  (semi)-definite programming (SDP) - SOCP as a subset of SDP
  Linear matrix inequalities (LMIs) as an example SDP
  SDP contains SOCP contains QCCP contains QP contains LP
  
• L25. Slides
• L25. Recording

Mini Homework 6 Due

• Project presentations
  

• Project presenations