| Date | Topics | Reference | Homework |
|---|---|---|---|
| 2.10 | Pr.: Introduction to Python and the CVXPY package | Pr0, Pr1 | |
| 3.10 | Optimization problems Convex problems can be solved efficiently (e.g. linear programming, least-squares) |
BV 1 | |
| 4.10 | Convex sets: Important examples (affine spaces, halfspaces, balls, cones,...) closedness under intersection and affine/perspective functions |
BV 2.1-2.3 | |
| 9.10 | Pr.: Examples of LPs and least-squares problems | Pr2 | |
| 10.10 | Separating hyperplane theorem convex/concave function: important examples, first and second order criteria |
BV 2.5, 3.1 | |
| 11.10 | the epigraph, operations that preserve convexity (weighted sums, suprema, infima, composition) |
BV 3.1., 3.2 | |
| 16.10 | Pr.: Convex sets and functions, the perspective of a function | Pr3 | [HW1] - 30.10 |
| 17.10 | Quasiconvex functions; Important definition for general optimization problems Convex OPs: local optima are optima; optimality criterion in differentiable case |
BV 3.4, 4.1, 4.2 |
|
| 18.10 | LP, QP, QCQP, SOCP + Examples (Chebyshev center, distance of polyhedra, robust LP...); Transforming Optimization Problems |
BV 4.3, 4.4, 4.2 |
|
| 23.10 | Pr.:Transforming Optimization Problems, standard form of LP | Pr4 | |
| 24.10 | Geometric programming, linear-fractional programs bisection method for quasiconvex problems, proper cones |
BV 4.5, 4.3.2 4.2,5, 2.4 |
|
| 25.10 | Generalized inequality constraints (conic problems), SDPs the SDP-relaxation of Max-Cut, LP relaxations |
BV 4.6 Notes |
|
| 30.10 | Pr.: Examples of SDPs, reduction of LP, QCQP, SOCP to SDPs | Pr5 | |
| 31.10 | Multiobjective optimization problems, finding Pareto optima via scalarization; scalarization for general K via dual cones K* |
BV 4.7, 2.6 | |
| 1.11 | Duality: Lagrangian, dual function, dual problem, weak duality Slater's condition for strong duality |
BV 5.1, 5.2 | |
| 6.11 | Pr.: Duality | Pr6 | [HW2] - 20.11 |
| 7.11 | Different interpretations of duality (geometrical, saddle point interpretation) Examples, randomized strategies for randomized matrix games |
BV 5.3, 5.7 5.2.5 |
|
| 8.11 | Farkas lemma, strong duality for LPs | BV 5.8, Notes | |
| 13.11 | Pr.: Duality, Slater's condition | Pr7 | |
| 14.11 | KKT conditions, perturbation analysis | BV 5.5, 5.6 | |
| 15.11 | Duality for generalized inequalities Norm and penality function approximation |
BV 5.9, 6.1 | |
| 20.11 | Pr.: KKT conditions, perturbation analysis; log barrier penalty function | Pr8 | [HW3] - 4.12 |
| 21.11 | Comparisons of different penalty functions, Huber penalty for robust approximation least-norm problems, regularization problems and applications in signal processing |
BV 6 | |
| 22.11 | maximimum likelihood estimates and examples: linear measurement models, Poisson distributon, logistic regression, covariance matrix |
BV 7.1 | |
| 27.11 | Pr.:Function fitting | Pr9 | |
| 28.11 | Function fitting (discussion practicals Pr9), MAP estimates Binary hypothesis testing |
BV 7.1, 7.3 | |
| 29.11 | Binary hypothesis testing, Optimal experiment design | BV 7.3, 7.5 | |
| 4.12 | Pr.:statistical estimation | Pr10 | [HW4] - 22.12 |
| 5.12 | Geometric problems: distance between convex sets, outer and inner Loewner-John ellipsoids, centering |
BV 8.1,8.2, 8.4,8.5 |
|
| 6.12 | Linear discriminators, support vector machines Newton's method to approximate roots of a real-valued function |
BV 8.6, [wiki] |
|
| 11.12 | Pr.: Geometric problems (projections onto convex sets) | Pr11 | |
| 12.12 | Unconstraint optimization: Strong convexity and some consequences the (gradient) descent method, backtracking line search |
BV 9.1-9.3 | |
| 13.12 | convergence analysis for gradient descent Newton descent (motivation for Newton step; convergence analysis without proof) |
BV 9.3-9.5 | |
| 18.12 | Pr.: Steepest descent and Newton descent | Pr11 | [HW5] - 8.1 |
| 19.12 | Newton descent for problems with equality constraints (feasible and infeasible initial point) |
BV 10 | |
| 20.12 | the (log-)barrier method (for general convex problems), central path proof of convergence, discussion of examples |
BV 11.1-11.6 | |
| 8.1 | Pr.: | ||
| 9.1 | |||
| 10.1 |