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
|
- Annotated classnotes
- References: For Projected and Generalized Gradient Descent, see L. Vandenberghe, Lecture Notes for EE 236C. Some advanced reading is here
- Reference: Page 557, Problem 10.2 of Boyd and Vandenberghe
- Reference: Sections 3.2, 3.2.3, 3.2.4 (Advanced) and 3.2.5 (Advanced) of Introductory Lectures on Convex Programming by Nesterov.
- References: For solutions to SVM using different algorithms, including projected gradient descent, refer here.
- Reference: For subgradient methods, also refer to Section 1, 2 and 3 of these notes on advanced optimization by Boyd.
- References: Best convergence rate bound for gradient (steepest) descent with constant step-size from these notes
- Mandatory Problem Solving: Derive a single generalized gradient descent step for the Lasso problem (your derivation can be in terms of z) on page number 34 (slide 214) of these notes: Deadline: October 23, 2018.
- Mandatory Problem Solving: By simply adopting the proof (for a simple t < 1/L) for O(1/k) convergence rate of gradient descent, derive the O(1/k) convergence rate for generalized gradient descent described on page number 26 (slide 210) of these notes: Deadline: October 23, 2018.
|
23.10.2018
|
- Annotated classnotes
- References: For Proximal and Project Operator, see Chapter 6 of book First-Order Methods in Optimization by Amir Beck.
- References: For Proximal Gradient Algorithm, see Chapter 10 of book First-Order Methods in Optimization by Amir Beck.
- References: For Projected and Generalized Gradient Descent, see L. Vandenberghe, Lecture Notes for EE 236C. Some advanced reading is here
- Reference: Page 557, Problem 10.2 of Boyd and Vandenberghe
- Reference: Sections 3.2, 3.2.3, 3.2.4 (Advanced) and 3.2.5 (Advanced) of Introductory Lectures on Convex Programming by Nesterov.
- References: For solutions to SVM using different algorithms, including projected gradient descent, refer here.
- Reference: For subgradient methods, also refer to Section 1, 2 and 3 of these notes on advanced optimization by Boyd.
- References: Best convergence rate bound for gradient (steepest) descent with constant step-size from these notes
- Mandatory Problem Solving: By simply adopting the proof (for a simple t < 1/L) for O(1/k) convergence rate of gradient descent, derive the O(1/k) convergence rate for generalized gradient descent on page number 27, slide 185 of these notes: Deadline: April 2, 2018.
- Mandatory Problem Solving: Understand the O(1/(k+1)^2) convergence rate for accelerated gradient descent on page numbers 51-57 (slides 246-249) of these notes: Deadline: October 26, 2018.
- Optional Problem Solving: Understand the O(1/sqrt(k)) convergence rate for projected gradient descent on page numbers 61-65 (slides 252-255) of these notes: Deadline: October 26, 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
|
- Annotated classnotes
- References: For Dual Ascent, Dual Decompositon, Augmented Lagrangian and ADMM, you can read this these notes.
- References: For Interior point method, refer to Boyd and Vandenberghe Sections 11.1-11.4 and Section 4.6.2 of my lecture notes,
- References: Barrier (Interior Point) methods for Linear Programming (Section 4.7.2) vs. Simplex Algorithm for Linear Pograming (Section 4.7.1) in in Section 4.7 of my lecture notes, contrasted at a high level in page 20, slide 342 of class notes
- Mandatory Problem Solving: Try and identify/guess values of the Lagrange multipliers (\lambda(t)) that satisfy the KKT conditions for the primal problem on page number 22, that is, slide 344 of these notes Deadline: 9 November, 2018.
- Optional Problem Solving: We have already seen several algorithms for handling linear constraints. These include Project Gradient Descent, Dual Ascent and ADMM. For another approach that can use Gauss Elimination to find the family of solutions to Ax = b see Section 4.6.1 of my lecture notes as referred to on page number 18, that is, slide 340 of these notes
|
9.11.2018
|
|