This page will provide information on what is covered in each lecture along with pdf of the hand written material from each class. This page will be updated as the class progresses.

The course notes for this course offered in spring 2018 are available here. The course notes for this course offered in spring 2015 are available here. The course notes for this course offered in autumn 2013 are available here.

The course notes are available from course page. You can check out this link for a growing list of resource material (slides/videos/code/lecture notes, etc) for optimisation in general, and convex optimisation in particular. Please let me know if you come across some useful resource material that I could add to this list.
You can check out this link for a growing list of papers that we plan to cover in the assignments/projects or sometimes through discussions in the class. Please start looking at these papers for your seminar and/or projects.

Date Summary

-

Practice problem set: Please find here a growing list of practice problems, including some previous year's question papers and their solutions. In particular, do look at this set. You can also refer to this wiki for definitions of several concepts relevant to this course, connections between those concepts through theorems and proofs of those theorems.

It is very important that you attempt the homework problems that were posted at the end of (almost) each lecture.

You can consider solving the following problems from Boyd (solutions to few of them has been discussed in class or moodle): (A) 2.1 to 2.37 and 2.39 (B) 3.1 to 3.35 (question involving quasi-convexity are optional) and 3.47 to 3.56. (C) 4.1 to 4.6 and 4.8 to 4.20 and 4.8 to 4.29 and 4.38 to 4.49 and 4.56, 4.61, 4.63. (D) 5.1, 5.2, 5.4 5.5, 5.7, 5.9, 5.10 to 5.13 5.14 to 5.20, 5.21 to 5.23, 5.26 to 5.31 and 5.39, 5.41 to 5.43 (E) 9.1 to 9.11 and 9.23 to 9.32. 9.12 to 9.22 are optional (F) 11.1 to 11.12, 11.15 to 11.18


17.07.2018

  • Annotated classnotes and Non-annotated version
  • Reference: Section 4.1.1 (pages 213 to 214) of these notes.
  • You can refer to Linear Algebra Done Right for brushing up/reading up on linear algebra.
  • Reading before next class: Calculus brushup for brushing up of principles for optimization of univariate functions
  • Suggested reading before next class: Linear Algebra Done Right for brushing up of principles for optimization of univariate functions
  • Mandatory Problem Solving: Explain the role of the eigenvalues and eigenvectors of the Matrix A in the geometry of the ellipsoid described on page 8 (slide 4) of these notes
  • Present a geometric intepretation of the solution to the least squares optimization problem on page 46 (slide 31) of the notes

20.07.2018

  • Annotated classnotes and Non-annotated version
  • Reference: Refer to Section 4.1.3 (pages 216 to 231) of these notes and you may also watch the video recording here.
  • Advanced Reference on maxima and minima: Stories About Maxima and Minima (Mathematical World) by Vladimir M. Tikhomirov
  • Advanced Reference on analysis for optimization: Variational Analysis by Rockafellar, R. Tyrrell, Wets, Roger J.-B.
  • Mandatory Problem Solving: Solve exercises on pages 46-46 (slides 27-28) before next class: from these notes: Deadline: July 24 2018.
  • A compact proof of sufficiency of slopeless interpretation of convexity that assumes some comfort level with left and right derivatives is here.

24.07.2018

  • Annotated classnotes
  • Reference: Refer to Sections 3.7 until 3.9.4 (pages 175 to 187) of these notes.
  • Important Reading before next class: pages 34 to 73 (slides 59 to 98) of these notes.
  • More basic Reference: Refer to Sections 3.1 until 3.6 (pages 145 to 175) of these notes.
  • Chapter 2 (Section 2.1) of Convex Optimization by Boyd and Vandenberghe
  • Advanced Reference on topology, normed spaces, open sets, continuity etc: Geometry I - Basic ideas and concepts of differential geometry by R.V. Gamkrelidze, E. Primrose, D.V. Alekseevskij, V.V. Lychagin, A.M. Vinogradov-
  • Advanced Reference on maxima and minima: Stories About Maxima and Minima (Mathematical World) by Vladimir M. Tikhomirov
  • Advanced Reference on analysis for optimization: Variational Analysis by Rockafellar, R. Tyrrell, Wets, Roger J.-B.
  • Advanced Reference on convex analysis, spaces etc: Fundamentals of Convex Analysis, by Hiriart-Urruty, Jean-Baptiste, Lemarechal, Claude
  • Mandatory Problem Solving: Intuitively identify a topological space that is NOT a metric space: referring to page 22 (slide numbered 46 of these notes): Deadline: July 27 2018.
  • Mandatory Problem Solving: Intuitively identify a metric space that is NOT a normed space: referring to page 22 (slide numbered 46 of these notes): Deadline: July 27 2018.
  • Mandatory Problem Solving: Provide an intuitive explanation why for norms other than the 2-norm, there is no notion of an inner product: referring to page 23 (slide number 47) of these notes: Deadline: July 27 2018.

27.07.2018

  • Annotated classnotes and more brushup from linear algebra on solving systems of linear equations
  • Basic Reference: Refer to Sections 3.1 until 3.6 (pages 145 to 175) of these notes.
  • Reference: Refer to Sections 3.7 until 3.9.4 (pages 175 to 187) of these notes.
  • Advanced Reference on topology, normed spaces, open sets, continuity etc: Geometry I - Basic ideas and concepts of differential geometry by R.V. Gamkrelidze, E. Primrose, D.V. Alekseevskij, V.V. Lychagin, A.M. Vinogradov-
  • Chapter 2 (From Section 2.1 until 2.2.3) of Convex Optimization by Boyd and Vandenberghe
  • Mandatory Problem Solving: Prove that the inner product defined on page 11 (slide 101) of these class notes can be expressed as a (Eucledian) dot product of two vectors in a possibly rotated space (see pages 12 and 13 of the same notes): Deadline: July 31 2018.
  • Mandatory Problem Solving: What would be the dual description for a Convex polyhedron? (page 26 or slide 111 of these class slides): Deadline: July 31 2018.

31.07.2018

  • Annotated classnotes
  • Reference: Chapter 2 (From Section 2.1 until 2.2.5) of Convex Optimization by Boyd and Vandenberghe
  • Advanced Reference: See the Weyl-Minkowski theorem < a href="https://www.math.ucdavis.edu/~jhaddock/Teaching/BMSSummerSchool2015/CombinatorialConvexityCourse0.pdf">on these slides
  • Read about simplexes, a special type of polyhedron in Section 2.2.4 in Boyd's book, and as summarized in page 16 and 18 of these class slides
  • Problem Solving: Fill in the blanks for the proof of Separating Hyperplane theorem on page numbers 36 (single blank) and 38 (two blanks) of these class notes: Deadline: August 3 2018.
  • Mandator Problem Solving: Prove how the Supporting Hyperplane theorem follows from the Separating Hyperplane theorem based on slides 35 and 39 of these class notes: Deadline: August 3 2018.

3.08.2018

  • Annotated classnotes
  • Reference: Section 2.5 of Convex Optimization by Boyd and Vandenberghe
  • Advanced References: For Ellipsoid and Interior point method, refer to these notes from Boyd, Section 14.2 of the book by Nocedal, this survey paper as well as the book by Boyd and Vandenberghe Sections 11.1-11.4
  • Mandatory Problem Solving: Try and explain and possibily derive the simplified expressions for the three matrix norms on page 31 (slide 148) of these class notes: Deadline: August 7 2018.

7.08.2018


10.08.2018


14.08.2018


21.08.2018


24.08.2018


28.08.2018


31.08.2018


1.09.2018


4.09.2018


7.09.2018


18.09.2018

  • Annotated classnotes
  • Reference: Joint Wolfe conditions for line search described around equations (4.90) and (4.91) and Pages 275 in Section 4.2.9 and pages 239-243 in Section 4.1.4 of the basic class notes
  • Reference: Sections 9.3.1 and Sections 3.1.2 and 3.1.3 of Convex Optimization by Boyd and Vandenberghe . Extra advanced reading: Nemirovski Section 5.4.2
  • Mandatory Problem Solving: Fill in the three blanks on on page number 35 (slide 130) of these notes : Deadline: March 21 2018.
  • Mandatory Problem Solving: Show that if f is itself quadratic, exact ray search can give an optimal solution to the minimization of f on page numbers 9-11 (slides 114-115) of these notes : Deadline: March 21 2018.

21.09.2018

  • Annotated classnotes
  • References: Boyd and Vandenberghe Sections 9.3 and 9.4 and Nemirovski Section C.4 (appendix). Extra advanced reading: Nemirovski Section 5.4.2
  • Extra Reference: For understanding Conjuate Gradient, see Figure 4.55 (and pages 317-323) of the basic c lass notes
  • Reference: Joint Wolfe conditions for line search described around equations (4.90) and (4.91) of the basic class notes
  • Several graphical illustrations can be found in the matlab code available here.
  • An illustration of Random walk based descent based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming
  • Understand the relation between Lipschitz continuity, continuity, uniform continuity, differentiability, continuous differentiability and so on.
  • Mandatory Problem Solving: What is the connection between Lipschitz continuity of a function and Lipschitz contunity of its gradient. Does one imply the other?: Deadline: Friday 28 2018.
  • Mandatory Problem Solving: Show that f is continuous and differentiable everywhere while not being Lipschitz continuous on page number 31 (slides 136) of these notes : Deadline: Friday 28 2018.
  • Optional Problem Solving: Study the plots of functions on page numbers 26-34 of these notes for Lipschitz continuity of the function OR its gradient, etc

28.09.2018

  • Annotated classnotes
  • References: Boyd and Vandenberghe Sections 9.3 and 9.4 and Nemirovski Section C.4 (appendix). Extra advanced reading: Nemirovski Section 5.4.2
  • Reference: Boyd and Vandenberghe Sections 9.3.1 and Nocedal and Wright Section A.2 (subsection "Rates of Convergence"). Extra advanced reading: Nemirovski Section 5.4.2
  • Several graphical illustrations can be found in the matlab code available here.
  • An illustration of Random walk based descent based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming
  • Mandatory Problem Solving: Understand and complete the derivations on page numbers 23-24 of these notes for the rate of convergence of the gradient descent algorihtm for convex functions etc

2.10.2018

  • Annotated classnotes
  • Reference: Boyd and Vandenberghe Sections 9.3.1 and Nocedal and Wright Section A.2 (subsection "Rates of Convergence"). Extra advanced reading: Nemirovski Section 5.4.2
  • Several graphical illustrations can be found in the matlab code available here.
  • Mandatory Problem Solving: Constrast the order and rate of convergence of the sequence s2 on page number 31 (slide 161) of these notes against the sequences s1 and r1 discussed a few slides before: Deadline 5th October 2018
  • Mandatory Problem Solving: Understand the derivation of the second order condition for convexity on page numbers 35 to 41 (slides 166-170) of these notes: Deadline 5th October 2018

5.10.2018


9.10.2018


16.10.2018


23.10.2018


26.10.2018

  • Annotated classnotes
  • References: Boyd and Vandenberghe Sections 5.1, 5.2. Geometric motivation for lagrange multipliers and KKT necessary conditions in Section 4.4.1 and 4.4.2 (page 282 onwards) of my lecture notes
  • Mandatory Problem Solving: Prove that the minimizing the Lagrange function with respect to x yields a concave function with reference to these notes?: Deadline: October 27, 2018.

27.10.2018

  • Annotated classnotes
  • References: Geometric interpretation of duality in optimisation problems: Boyd and Vandenberghe Section 5.3, Page 10 to 13 of class notes, Section 4.4.3 (page 292 onwards) of my lecture notes.
  • References: Boyd and Vandenberghe Sections 5.1, 5.2. Nemirovski: Lecture Notes on Modern Convex Optimization Sections 1.4.5 (esp theorem 1.4.2). Advanced: To appreciate theorem of alternatives that is used to prove strong duality in linear and conic duality see Boyd and Vandenberghe Section 5.8 (especially page 263) and Nemirovski Sections 1.4.4 (extra reading for geometric interpretation of conic dual). You can read more about the Lasso and its dual here.
  • Mandatory Problem Solving: Reconfirm your understanding of the geometric intepretation of the Lagrange dual and the duality gap on page numbers 19-36, that is, slides 293-302 of these notes: Deadline: October 30, 2018.
  • Mandatory Problem Solving: Derive the Lagrange dual for the Problem 1 reproduced on page number 37, that is, slide 303 of these notes: Deadline: October 30, 2018.
  • Optional Problem Solving: How will the dual of the problem on page number 15, slide 290 of these notes be different from the dual in equation (82) of the primal on page 10, slide 288 of the same set of slides: Deadline: October 30, 2018.
  • Optional Problem Solving: If f(x) and gi(x) are convex then complete the proof that the set I will be convex on page number 23, slide 296 of these notes: Deadline: October 30, 2018.

30.10.2018

  • Annotated classnotes
  • References: Geometric interpretation of duality in optimisation problems: Boyd and Vandenberghe Section 5.3, Page 10 to 13 of class notes, Section 4.4.3 (page 292 onwards) of my lecture notes.
  • References: Boyd and Vandenberghe Sections 5.1, 5.2. Nemirovski: Lecture Notes on Modern Convex Optimization Sections 1.4.5 (esp theorem 1.4.2). Advanced: To appreciate theorem of alternatives that is used to prove strong duality in linear and conic duality see Boyd and Vandenberghe Section 5.8 (especially page 263) and Nemirovski Sections 1.4.4 (extra reading for geometric interpretation of conic dual). You can read more about the Lasso and its dual here.
  • References: For Dual Ascent, Dual Decompositon, Augmented Lagrangian and ADMM, you can read this these notes.
  • References: Section 2 of >these notes by Bertsekas for weak duality and min-max inequality and Section 3 of the same notes for conditions for strong duality and analysis of saddle points.
  • References: For constraint qualificiations on specific cases of Linear and Conic Linear programs, read until lecture 10 on 13.2.2015 of 2015 notes. Else see Nemirovski's notes here. Also see some slides here that I have put together
  • References: For SMO and SVM Optimization, you can refer to this link and this one . For solutions to SVM using different algorithms, including projected gradient descent, refer here.
  • Mandatory Problem Solving: Revisit the Support Vector Regression problem and see how the KKT condition and convexity were used to infer 0 duality gap and therefore go ahead and derive the dual optimization problemas mentioned on page number 4, that is, slide 283 of these notes: You can read about several optimization algorithms applied to SVMs here. Deadline: November 5, 2018.
  • Optional Problem Solving: In the analysis for sufficiency of KKT conditions, what if the inequality constraints gi's are quasi-convex instead of convex as mentioned on page number 18, that is, slide 314 of these notes

5.11.2018


9.11.2018