|
|
|
|
I teach the lecture together with M. Loebl.
The lecture is scheduled on Friday at 10:40 in S7.
The tutorial is done by means of homeworks and consultations, so ignore the official schedule.
Exams: There will be two small sub-exams for each of the two parts (mine and those of M. Loebl). For my part, I prefer examination jointly in the same time with the examination of the course of Linear algebra I, which take place on 16.1. (S3), 19.1. (S3), 26.1. (S3), 6.2. (S9), 9.2. (S3), and 16.2. (S3) starting at 9:00. Let me know when you come or to arrange another term. Anyway, there will be no official terms recorded in SIS.
Done:
| 7.10. | Reminder of convexity: convex sets, convex functions and convex optimization. Quasiconvex functions: definition, examples, sublevel set and first order characterizations. |
| 14.10. | Chain rules for quasiconvexity: maximum, product, division, composition. Quasiconvex optimization: local and global solutions, convexity of the optimal solution set, optimality condition. Generalized linear fractional programming and application in von Neumann economic growth model. Pseudoconvexity: relation to convexity and quasiconvexity, pseudoconvex optimization: optimality conditions. |
| 21.10. | Reminder of Farkas lemma. Gordan theorem. Necessary optimality conditions: Conditions of Fritz John, Karush-Kuhn-Tucker (KKT) conditions. Constraint qualifications for KKT: linear independence, Slater condition and Abadie condition. |
| 4.11. | KKT and linear approximation, KKT for linear and quadratic programming, Sufficient KKT conditions. Example on signal reconstruction. Lagrange duality: dual function and dual problem, weak duality theorem, application in approximation, and a reformulation example. |
| 11.11. | Lagrange duality: geometric interpretation, strong duality under the Slater condition, examples of (non-)strong duality, duality for linear programming, sensitivity analysis and shadow prices. |
| 18.11. | Lagrange duality for convex quadratic programming and semidefinite programming. Application: Support vector machines. |
| 9.12. | Cardinality problems and L1-norm approximation: examples, interpretation of the approximation, simple methods, rank minimization. |
| 16.12. | Linear complementarity problem (LCP): relation to quadratic programming, integer programming and bimatrix games. P-matrices, their characterization, complexity issues, and relation to uniqueness of LCP. |
Homeworks: PDF
Lecture notes (in Czech): PDF
Literature:
