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