Convex optimization Winter 2019/20

Scheduling

Mon, 9:00 – 10:30, lecture in K12

Mon, 10:40 – 12:00, office hours, Department of Algebra, K313

Wed, 17:20 – 18:50,~~lecture~~ tutorial in K7 (by Jiří Pavlů)

Fri 10:40 – 12:10, lecture in K8

Credit (zápočet)

Credit is awarded for earning at least 160 points out of 240 for homework and quizzes.

There will be 12 sets of homework problems and 12 quizzes in total, each worth 10 points.

After your solutions are corrected, you can earn up to 50 % of deduced points for correcting your solution. Exception: It is not possible to "correct" your solution for a quiz that you did not actually hand in the first time.

Credit is needed to sign up for the final exam.

Final exam info

The final exam will be oral and have two parts: In the first part you will be randomly assigned 2 topics from the list of overview topics. Tenative list of topics and in the second part you will be asked two questions that are either of the form "prove a theorem from class" or "solve a problem."

To pass the exam (with a grade 3) you need to give a good answer in the first part and at least acceptable answer in the second part. To get a grade of 1 you need to give a good answer in the first part and a great answer in the second part (a very small number of small mistakes will be tolerated).

Office hours

Mon, 10:40 – 12:00, Department of Algebra, K313

E-mail me if you want to meet outside the regular office hours.

Lecture plan (to be adjusted)

2. 10. 2019: Introduction, basic notions of optimization (problem, feasible solution, optimal solution, optimal value), the nutrition problem, linear programming
7. 10. 2019: Least squares, convex sets, affine and convex hull, convex cone, proper cones
9. 10. 2019: The cone of positive semidefinite matrices, generalized inequalities, half spaces and ellipsoids, convex functions
14. 10. 2019: Recognizing convex functions from their derivatives
18. 10. 2019: Examples of convex functions, epigraphs of (convex functions), Jensen inequality, operations preserving convexity
21. 10. 2019: Composition and infimum-taking and convexity. Sublevel sets and quasiconvex problems. Formal definition of optimization problems (programs), equivalent problems
25. 10. 2019: Important classes of convex optimization problems: LP, FLP, QP, QCQP, SOCP, geometric programming
1. 11. 2019: Geometric programming in convex form, properties of optimal solutions of convex problems, optimization problems with generalized inequalities
4. 11. 2019: SDP, conic form problems (cone programs), introduction to vector optimization
8. 11. 2019: Vector optimization, sufficient and necessary conditions for a point to be an optimal solution of a vector program
11. 11. 2019: Lagrange dual function, weak duality
15. 11. 2019: Duality for LP, the statement of, Slater's condition, strong duality for LPs
18. 11. 2019: Proof of (special case of) strong duality condition
22. 11. 2019: Complementarity, Karush-Kuhn-Tucker conditions for primal-dual optimal solutions, zero-sum games
25. 11. 2019: Duality for game theory, duality and sensitivity to initial conditions
29. 11. 2019: Norm minimization applications: Approximation, function fitting, regression
2. 12. 2019: Robust approximation, machine learning, linear classifiers
6. 12. 2019: Support Vector Machines and duality, Maximum likelihood estimates in statistics
9. 12. 2019: Bayesian estimates, MAP (maximum a posteriori probability) estimate
13. 12. 2019: Experiment/detector design
16. 12. 2019: Experiment design, ellipsoids
20. 12. 2019: Löwner-John ellipsoid, gradient descent for unconstrained minimization
6. 1. 2020: Newton's method
10. 1. 2020: Minimizing a function constrained to an affine subspace, interior point methods

Tutorical classes

4. 10. 2019: Simple linear optimization problems, Lagrange multipliers, introduction to CVXOPT. Problems from the class (in Czech).
11. 10. 2019: Cones, convex sets and functions. Problems from the class
Simple Python code for CVXOPT, the same code in a Jupyter notebook form and the diet problem using CVXPY.
16. 10. 2019: Properties of convex functions Problems from class
23. 10. 2019: Quasiconvex functions, questions about convex functions Problems from class
30. 10. 2019: Translating LFP into LP and other miscallaneous problems Problems from class (Last problem had an error in it; this version is corrected)
6. 11. 2019: Conic programming Problems from class
13. 11. 2019: Duality Problems from class
20. 11. 2019: Duality Problems from class
27. 11. 2019: KKT conditions Problems from class
4. 12. 2019: Approximation problems Problems from class
11. 12. 2019: Estimating a random variable Problems from class
18. 12. 2019: Detectors and ellipsoids Problems from class
8. 1. 2020: Löwner-John ellipsoid, gradient descent methods Problems from class

Homework

The homework is to be handed in at the begining of tutorial classes. We will make exceptions for ilness or other serious situations on a case by case basis.

If you are asked to write and submit programs, send the program to Jiří Pavlů by the due date. The same holds for when you are asked to submit the output of your program. You do not have to print your programs on paper.

Set 1, due date 10:41, 18. 10. 2019
Set 2, due date 10:41, 25. 10. 2019
Set 3 , due date 17:21, 30.10.2019 Data file for Problem 4
Correction to problem 5: Entropy is supposed to be concave, not convex.
Set 4, due date 17:21, 6.11.2019
Set 5, due date 17:21, ~~13.11.2019~~ 15.11.2019
Set 6, due date 17:21, 20.11.2019
Correction to problem 4: The sum of the amounts of stocks we are buying should be 1, not 0.
Set 7, due date 17:21, 27.11.2019
Set 8, due date 17:21, 4.12.2019 Data for Problem 4
Set 9, due date 17:21, 11.12.2019
Correction to problem 3: The second row of the 3 x 3 matrix should all have indices beginning with 2.
Set 10, due date 17:21, 18.12.2019 Data for Problem 5
Correction to problem 2: The entries in the matrix U should all be assumed to have mean 0.
Set 11, due date 17:21. 8. 1. 2020
Set 12, due date 17:21. 8. 1. 2020

You can use without proof: Theorems from the bachelor courses and from the lecture. When you are asked for a proof, you should prove everything else on your own in detail. If you are asked to "justify" or "sketch", you do not have to write a full proof, but do make sure to express the core ideas of what are you doing and why.

You can consult your friends when solving the problems, but write your solution of your own and do not share your submission-ready solutions. The same rules apply to programs.

Course materials

Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Prof. Boyd's slides
Prof. Boyd's videos
CVXOPT
Jupyter