Nonlinear optimisation

Important dates:

Quiz 1: Sep 7

Drop date: October 5

Quiz 2: October 12

Final : Nov 20

Mini-quizzes: As scheduled in class.

Schedule/Logistics:

Classes will be held in CS26 in the E-slot.

Class timings:

Tuesday: 11 -- 11:50 AM

Wednesday: 10 -- 10:50 AM

Thursday: 8 -- 8:50 AM

Friday: 4:50 -- 5:40 PM

Office hours:

Tuesday: 10 -- 11

Wednesday: 11 -- 12

First day handout pdf.

Prerequisites:

1. Undergraduate multivariate calculus.

2. Linear algebra. (Students doing a such a course in parallel are also welcome.)

3. Basic Numpy/python programming. (Students should be able pick it up along the way. A tutorial on numpy/python can be arranged based on demand.)

The first few classes will mainly focus on a recap of the above topics, and here are some links below for further reading/watching/studying

1a. https://ocw.mit.edu/courses/mathematics/18-01sc-single-variable-calculus-fall-2010/unit-2-applications-of-differentiation/ (Part A)

1b. https://ocw.mit.edu/courses/mathematics/18-02sc-multivariable-calculus-fall-2010/2.-partial-derivatives/ (Part A and B)

2a. https://youtu.be/kjBOesZCoqc (Essence of linear algebra, youtube series)

2b. https://youtu.be/ZK3O402wf1c (Gilbert Strang course on Linear algebra.)

Evaluation:

Final: 30

Quiz 1: 20

Quiz 2: 20

Mini-quiz: 25 (Best 5 out of 8)

Class participation: 5

Reference Books:

[BV] Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. Link.

[LY] David G. Luenberger , and Yinyu Ye. Linear and nonlinear programming. 4th edition. Springer, 2015.

[NW] Jorge Nocedal and Wright, Stephen. Numerical optimization. Springer, 1999

[N] Yu Nesterov. Introductory lectures on convex programming. 1999. Link.

[B] Sebastien Bubeck. Convex Optimization: Algorithms and Complexity. Link.

Other reference material:

NPTEL course on numerical optimisation by Prof. Shevade: https://youtu.be/biwjg9tpOvM

Convex optimisation course by Prof. Stephen Boyd: https://youtu.be/McLq1hEq3UY

Convex optimisation course by Moritz Hardt. https://ee227c.github.io/

Miscellaneous Notes:

The course EE5121, intersects significantly with this course, and students who have taken that course cannot credit this course.

Class details:

1. July 31: Logistics and Optimisation introduction. Slides.
2. Aug 1: Metric spaces, continuity, differentiability.
3. Aug 2: Linear and quadratic approximations. Instructor notes for Aug 1 and Aug 2.
4. Aug 3. Tutorial on linear algebra and contour plots.
5. Aug 7. Functions of several variables, gradients
6. Aug 9. Gradients continued. Instructor notes for Aug 7 and Aug 9.
7. Aug 10. Gradients, directional derivative example. Tutorial quiz 1.
8. Aug 13. Subspaces, affine spaces, cones, and convex sets.
9. Aug 14. Subspaces, affine spaces, cones, and convex sets contd. Instructor notes for Aug 13 and Aug 14.
10. Aug 16. Convex sets: Half-spaces, polyhedra, balls. Intersection of convex sets. (Refer Boyd: Section 2.2, Subsection 2.3.1)
11. Aug 17. Class cancelled due to Institute announcement.
12. Aug 21. Affine functions. Separating and supporting hyperplanes. (Refer Boyd: Subsection 2.3.2)
13. Aug 23. Separating and supporting hyperplanes. Norm cones, positive semidefinite cone. (Refer Boyd: Subsection 2.2.3, 2.2.5 and Section 2.5)
14. Aug 24. Tutorial quiz 2.
15. Aug 28. Tutorial quiz discussion. Convex functions: definition, epigraph, sub-level sets. (Refer Boyd: 3.1)
16. Aug 29. Sub-level sets, first order characterisation of convexity. (Refer Boyd: 3.1)
17. Aug 30. Jensen's inequality. Hessians and Second order characterisation of convexity. Examples. AM-GM inequality, Entropy and KL divergence. (Refer Boyd: 3.1)
18. Aug 31. Convex functions tutorial.
19. Sep 3. Using epigraphs for proving convexity. Preserving convexity: Addition (Refer Boyd 3.2, Solutions to problems 3.3, 3.6)
20. Sep 4. Preserving convexity: Maximisation, Composition. (Refer Boyd 3.2)
21. Sep 5. Convex functions as maximum of Affine functions. Second order characterisation of convexity. (Refer Boyd 3.2, solution to problem 3.8)
22. Sep 6. Sub-gradients, supporting hyperplanes. (Refer Boyd 2.5, Wikipedia page)
23. Sep 7. Quiz 1. Question paper. Instructor answers/solutions.
24. Sep 11. Optimisation problem terminolgy: problem, solution, domain, constraints, local and global minima.
25. Sep 12. Convexity and minima. Oracle methods and equivalent optimisation problems.
26. Sep 14. Necessary conditions and sufficient conditions for local minima. Lipschitz functions. Instructor notes for Sep 11, 12 and 14. Other references: Boyd chapter 4.1, Nocedal/Wright chapter 2.1. Nesterov 1.1, 1.2.1, 1.2.2.
27. Sep 17. Tutorial session. Rough notes of discussion.
28. Sep 18. Tutorial quiz 3. Solution.
29. Sep 19. Lipschitzness continued. Zero-order algorithm analysis of error and complexity.
30. Sep 20. Lipschitz smoothness. Instructor notes for Sep 19 and Sep 20. Other references: Nesterov 1.2.1, 1.2.2, 1.2.3.
31. Sep 25. Gradient descent continued.
32. Sep 26. Gradient descent convergence proof for convex Lipschitz smooth functions. Instructor notes for Sep 25 and 26. Ipython notebook 1 used in class. Other references: Nesterov 1.2.3, Bubeck 3.2.
33. Sep 27. Gradient descent convergence issues for convex quadratic functions. Badly conditioned quadratics. Instructor notes.
34. Sep 28. Tutorial quiz 4 . Solution.
35. Oct 1. Python tutorial. Ipython notebook 2.
36. Oct 3. Newton and Quasi Newton methods.
37. Oct 4. Quasi Newton methods continued. Instructor notes. Other references: Nocedal & Wright Chapter 6.
38. Oct 5. Python session for optimisation algorithms. Linear regression. Ipython notebook 3.
39. Oct 9. Python session optimisation algorithms. Logistic regression.
40. Oct 10. Python session optimisation algorithms. Logistic regression.
41. Oct 11. Python session optimisation algorithms. Logistic regression with multilayer networks.
42. Oct 12. Quiz 2. Question paper. Solutions.
43. Oct 16. Constrained optimisation theory.
44. Oct 17. First order necessary conditions for inequality constrained optimisation.
45. Oct 18. Constrained optimisation theory contd. KKT conditions. Section 12.1, 12.2, 12.3 in Nocedal and Wright.
46. Oct 23. KKT conditions continued. Instructor notes for KKT.
47. Oct 24. Guest lecture by Aswin Kannan from IBM.
48. Oct 25. Lagrangian Duality.
49. Oct 26. Lagrangian duality applied to SVMs.
50. Oct 30. Example dual derivation. Weak duality proofs.
51. Oct 31. Tutorial quiz 5 on KKT and duality. Question paper. Solutions.
52. Nov 1. Strong duality proof for convex problems. Instructor notes for Duality.
53. Nov 2. Projected gradient descent. Examples. Lasso Regression. Instructor notes for projected gradient descent.
54. Nov 7. Lasso Regression wrap up. Optimisation solvers. Ipython notebook 4.
55. Nov 8. Using software to solve convex optimisation problems. Ipython notebook 5. CVXOPT. CVXOPT for Cone programming (includes: LP, QP, SDP).
56. Nov 9. Using software to solve convex optimisation problems. Instructor notes for CVXOPT reformulations.
57. Nov 13. Tutorial quiz 6. Question paper. Solutions.
58. Nov 20. Final exam (as scheduled on Institute calendar)

Announcements:

• Aug 5. Worksheet 1 is up here. Corresponding quiz will be held on Aug 10.
• Aug 18. Worksheet 2 is problems from Chapter 2 of Boyd and Vandenberghe. In particular: 2.5, 2.6, 2.7, 2.8, 2.9, 2.12, 2.14, 2.15, 2.16, 2.20
• Aug 29. Worksheet 3 is problems from chapter 3 of Boyd and Vandenberghe, corresponding to sections 3.1 and 3.2. In particular: 3.1, 3.2, 3.3, 3.6, 3.7, 3.8, 3.11*, 3.12, 3.13, 3.14*, 3.15*, 3.16, 3.17*, 3.18*, 3.21, 3.24, 3.29 (assume f is convex), 3.32, 3.34*.
• Sep 15. Worksheet 4 is up here. Tutorial session for discussing the problems here will be on Sep 17.
• Sep 26. Worksheet 5 is up here. It is mainly computational. Hints/Approaches for solving Armijo-Goldstein conditions here.
• Oct 9. Worksheet 6 is here.
• Oct 9. Programming Assignment 1: Implement the functions in Worksheet 6, problem 13, put them in a single Python file and submit in Moodle by Oct 26.
• Oct 22. Reminder programming assignment is due by Friday this week.
• Oct 25: A template Jupyter notebook giving an example get_value and get_gradient functions, and the corresponding answers and evaluation scripts are available here. Jupyter notebook containing template. Answer file for GD. Answer file for QN.
• Oct 23. Collect quiz 2 papers after class on Tuesday.
• Oct 29. Worksheet 7 is up here.
• Nov 8. Worksheet 8 is up here. Notes containing solutions to problems 6d, 6e and 6f. Ipython notebook with solutions for 6a, 6e, 6f..
• Nov 19.Programming Assignment 2 is out. Problem statement is here. A template python notebook containing function names and definitions is here. The submission is due on Dec 5. Every extra day taken reduces 0.5 points from maximum points possible.