MATH 589 - Conjugate Duality and Optimization (Nonlinear Programming)

Schedule

  1. PDF Aug 27 Introduction and convex sets
  2. PDF Aug 29 Carathedory thm, Affine subspace, Helly theorem, Radon theorem
  3. PDF Aug 31 Convex polytopes, H-polytope is V-polytope, faces of plytopes, connections to posets, dual polytope, connections to graph theory
  4. Sep 3 Labor day (no class)
  5. PDF Sep 5 connections to linear programming, momenty curve, cyclic polytope, many facets, separation theorem
  6. PDF Sep 7 dual program for linear program, Farkas lemma
  7. PDF Sep 10 Duality of LP, sensitivity of LP
  8. PDF Sep 12 complementary slackness, Ellipsoid method
  9. PDF Sep 14 sketch of interior point methods, convex functions
  10. PDF Sep 17 More convex functions, conjugate function
  11. PDF Sep 19 quaziconvex functions
  12. Sep 21 LECTURE MOVED
  13. PDF Sep 24 Quadratic programming, Second order cone programming
  14. PDF Sep 26 Geometric programming, Semidefinite programming
  15. PDF Sep 28 MAX-CUT approximation using semidefinite programming
  16. PDF Oct 1 support and separation theorems, MP as infimum of feasible solutions, change in contstraints and MP(z)
  17. PDF Oct 3 superconsistency, sensitivity vector, examples for MP
  18. PDF Oct 5 Karush-Kuhn-Tucker theorem - Saddle point and gradient version
  19. PDF Oct 8 Usage of KKT - solved example, linear programming duality, KKT multipliers are sensitivity vector
  20. PDF Oct 10 Developing of gemotric dual using A-G inequality
  21. PDF Oct 12 Geometric programming duality with proof using KKT - double lecture
  22. PDF Oct 15 Duality of convex programming
  23. PDF Oct 17 Penalty method
  24. PDF Oct 19 Penalty method and KKT
  25. PDF Oct 22 Newton's method for unconstrained optimization
  26. PDF Oct 24 Method of steepest descent
  27. PDF Oct 26 Developing a good method
  28. PDF Oct 29 Broyden's method for finding 0
  29. PDF Oct 31 Broyden-Fletcher-Goldfarb-Shanno (BSGF) HW1 deadline
  30. PDF Nov 2 Davidon-Fletcher-Powell, Conjugate directions
  31. PDF Nov 5 Conjugate directions
  32. PDF Nov 7 Conjugate directions and generalizations to non-quadratic programs
  33. PDF Nov 9 Interior point methods - theoretical concept
  34. PDF Nov 12 Interior point methods - practical considerations
  35. PDF Nov 14 Interior point methods - speed of convergence
  36. PDF Nov 16 Primal-dual method
  37. Nov 19 Thanksgiving (no class)
  38. Nov 21 Thanksgiving (no class)
  39. Nov 23 Thanksgiving (no class)
  40. PDF Nov 26 SDP - recalling what it was HW2 deadline
  41. Nov 28 Lecture moved
  42. Nov 30 Lecture moved
  43. PDF Dec 3 SDP - quadratic constraints and max eigenvalue example from duality
  44. PDF Dec 5 SDP - cones and dual cones
  45. PDF Dec 7 SDP - Duality from cones
  46. PDF Dec 10 SDP - Duality from cones
  47. PDF Dec 12 SDP - application to coloring of 3-colorable graphs