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

• 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.
• Suggested 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
• Explain the optimization problem on slide 16 of the notes.
• Present a geometric intepretation of the solution to the least squares optimization problem on slide 12 of the notes.

• Annotated classnotes and Non-annotated version
• Reference: Refer to Section 4.1.3 (pages 216 to 231) of these notes.
• Suggested reading: Page 26 onwards until 50 (part remaining from previous class) before next class: Calculus brushup for brushing up of principles for optimization of univariate functions
• Prove the necessary and sufficient first order conditions for (strictly) increasing functions of single variable and also characterize their local and global maxima and minima Deadline: January 11 2018.
• What will be the necessary and sufficient second order conditions for (strictly) increasing functions of single variable and also characterize their local and global maxima and minima Deadline: January 11 2018.

• Annotated classnotes and Non-annotated version
• Reference: Refer to Section 4.1.3 (pages 216 to 231) of these notes.
• Mandatory Problem Solving: Solve exercises from pages 31 (slide 38) onwards until 53 before next class: from these notes for brushing up application of what was taught in previous class: Deadline: January 15 2018.
• A more compact proof of sufficiency of slopeless interpretation of convexity that assumes some comfort level with left and right derivatives is here.

• Annotated classnotes part 1 and Annotated classnotes part 2
• 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: Identify a topological space that is NOT a metric space: referring to slides numbered 9,10 and 11 of these notes: Deadline: January 17 2018.
• Mandatory Problem Solving: Identify a metric space that is NOT a normed space: referring to slides 10-13 of these notes: Deadline: January 17 2018.

• Annotated classnotes
• 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-
• 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 slide number 23 of these notes: Deadline: January 22 2018.

• Annotated classnotes
• Reference: Refer to Sections 3.7 until 3.9.4 (pages 175 to 187) of these notes.
• More basic Reference: Refer to Sections 3.1 until 3.6 (pages 145 to 175) 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 (Section 2.1) of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Prove that the inner product defined on pages 1 and 2 of these class notes can be expressed as a (Eucledian) dot product of two vectors in a possibly rotated space (see page 47 of the same notes): Deadline: January 25 2018.
• Mandatory Problem Solving: Present a hierarchical diagram depicting the different spaces described so far and their relationships in terms of specialization or generalization: Deadline: January 25 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.
• Chapter 2 (From Section 2.1 until 2.2.3) of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Making use of the basic idea of solving linear system of equations, show that every affine set can be expressed as a solution set of system of linear equations (slide number 82 or page 5 of these class slides): Deadline: January 29 2018.
• Mandatory Problem Solving: Try and make some sense of matrix norms induced by vector norms (slide number 90 or page 16 of these class slides): Deadline: January 29 2018.

• Annotated classnotes
• Chapter 2 (From Section 2.2.3 until 2.2.5) of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Derive the expression for the matrix norm induced by the infinity norm on slide number 90 or page 3 of these class slides : Deadline: February 1 2018.
• Mandatory Problem Solving: Read about simplexes, a special type of polyhedron in Section 2.2.4 in Boyd's book, and as summarized in slide number 106 or page 30 of these class slides : Deadline: February 1 2018.
• Mandatory Problem Solving and Assignment 1: Complete dual interpretation of the positive semi-definite cone on slide number 104 or page 27 of these class slides Plot a finite number of half-spaces parametrized by \theta to verify the dual description: Deadline: February 10 2018.

• Annotated classnotes
• Chapter 2 (From Section 2.2.3 until 2.2.5) of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Derive the expression for the matrix norm induced by the infinity norm on slide number 90 or page 3 of these class slides : Deadline: February 1 2018.
• Mandatory Problem Solving: Read about simplexes, a special type of polyhedron in Section 2.2.4 in Boyd's book, and as summarized in slide number 106 or page 30 of these class slides : Deadline: February 1 2018.
• Mandatory Problem Solving and Assignment 1: Complete dual interpretation of the positive semi-definite cone on slide number 104 or page 27 of these class slides Plot a finite number of half-spaces parametrized by \theta to verify the dual description: Deadline: February 10 2018.

• Annotated classnotes
• Chapter 2 (From Section 2.2.4 until 2.3) of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Prove closure of convexity under intersection on slide number 116 or page 14 of these class slides : Deadline: February 5 2018.
• Mandatory Problem Solving: Prove closure of convexity under affine transform on slide number 119 or page 17 of these class slides : Deadline: February 5 2018.
• Mandatory Problem Solving: Prove closure of convexity under perspective function on slide number 122 or page 22 of these class slides : Deadline: February 5 2018.

• Annotated classnotes
• Chapter 3 (Section 3.1.1) of Convex Optimization by Boyd and Vandenberghe
• Sections 4.2.7 and 4.1.4 of my Convex Optimization notes
• Mandatory Problem Solving: Prove that if a function is both concave and convex, it must be affine on slide number 130 or page 20 of these class slides : Deadline: February 5 2018.
• Mandatory Problem Solving: Prove closure of convexity under intersection on slide number 116 or page 14 of these class slides : Deadline: February 8 2018.
• Mandatory Problem Solving: Prove closure of convexity under affine transform on slide number 119 or page 17 of these class slides : Deadline: February 8 2018.
• Mandatory Problem Solving: Prove closure of convexity under perspective function on slide number 122 or page 22 of these class slides : Deadline: February 8 2018.
• Mandatory Problem Solving: Appreciate how the concepts of closed, open sets, interior, boundary etc extend to general topological/metric spaces on slide number 139 or page 38 of these class slides : Deadline: February 5 2018.

• Annotated classnotes
• Section 4.2.2 of Convex Optimization by Boyd and Vandenberghe
• Sections 4.2.8 and 4.1.4 of my Convex Optimization notes
• Mandatory Problem Solving: Prove that if a function is both concave and convex, it must be affine on slide number 130 or page 20 of these class slides : Deadline: February 12 2018.
• Mandatory Problem Solving: Compute the directional derivatives (and the gradient vectors) for each of the two homework problems on slide number 14 or page 26 of these class slides : Deadline: February 12 2018.

• Annotated classnotes
• Section 3.4 (and partly 2.5) of Convex Optimization by Boyd and Vandenberghe
• Section 4.1.4 of my Convex Optimization notes
• Mandatory Problem Solving: Prove that negative of the normal distribution is not convex. Optionally try proving that it is quasi-convex. See slide number 35 or page 44 of these class slides : Deadline: February 15 2018.

• Annotated classnotes
• Sections 3.1.3, 3.1.7, 3.4, 3.5, 2.5 of Convex Optimization by Boyd and Vandenberghe
• Pages 263, 269, 270, 272 of my Convex Optimization notes
• Mandatory Problem Solving: Find the equation of the tangent hyperplane to an epigraph as stated on page number 22 of these class slides : Deadline: February 19 2018.
• Mandatory Problem Solving: Try and prove defintion of convexity for a differentiable function as per equation (7) on page number 23 or slide 50 of these class slides inspired the proof of equivalences between two definitions of convexity as discussed for a function of single variable on pages 9 to 26 or slides 29 to 34 of these older class notes: Deadline: February 19 2018.
• Optional Problem Solving: Try and interpret the gradient wrt to epigraph from the point of view of minimizing the alternative optimization formulation on page number 18 or slide 44 of these class slides : Deadline: February 19 2018.

• Annotated classnotes
• Sections 3.4, 3.5 of Convex Optimization by Boyd and Vandenberghe
• Pages 272, 274 of my Convex Optimization notes
• Mandatory Problem Solving: Understand the proof of the necessity of the first order conditions for convexity on page number 21, slide 52 of these class slides : Deadline: February 22 2018.
• Mandatory Problem Solving: Derive the expression for the subdifferential of the indicator function on page number 28, slide 58 of these class slides : Deadline: February 22 2018.

• Annotated classnotes
• Sections 6.5.5 of Convex Optimization by Boyd and Vandenberghe
• Pages 1-8 of notes from S. Boyd, Lecture Notes for EE 264B

• Annotated classnotes
• Pages 271, 275-277 in Section 4.2.9 and pages 279-280 in Section 4.2.10 of my Convex Optimization notes
• Sections 3.2 and 3.6.9 and 6.5.5 of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Derive the subgradient for the second case (concave q_i, convex and non-increasing p) following the derivation of the first case presented on on page numbers 9-12, slide 69 of these class slides : Deadline: March 12 2018.
• Mandatory Problem Solving: Prove, from first principles that the general infimum function d(x) = inf over y in C of c(x,y) is convex when C is a convex set and c(x,y) is a convex function on page number 13, slide 70 of these class slides : Deadline: March 12 2018.

• Annotated classnotes
• Pages 275 in Section 4.2.9 and pages 239-243 in Section 4.1.4 of my Convex Optimization notes
• Sections 3.1.2 and 3.1.3 of Convex Optimization by Boyd and Vandenberghe
• Mandatory Problem Solving: Derive the necessary condition for descent direction motivated on on page numbers 35, slide 101 of these class slides : Deadline: March 15 2018.
• Mandatory Problem Solving: Verify that the point of minimum we found for Lasso as per sufficient condition is also a critical point on page number 25, slide 92 of these class slides : Deadline: March 15 2018.
• Mandatory Problem Solving: Derive the necessary condition for local maximum of a differentiable function on page number 13, slide 86 of these class slides : Deadline: March 15 2018.

• Annotated classnotes
• Reference: Joint Wolfe conditions for line search described around equations (4.90) and (4.91) of the basic class notes
• 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
• Mandatory Problem Solving: Show that if f is itself quadratic, exact ray search gives an optimal solution to the minimization of f on page number 6, slide 104 of these notes : Deadline: March 19 2018.
• Mandatory Problem Solving: Explain why the step t corresponding to the next iterate in orange might satisfy the Armijo condition but not the second Strong Wolfe condition on page number 12, slide 107 of these notes : Deadline: March 19 2018.
• Mandatory Problem Solving: Explain for the example quadratic program why the step sizes might satisfy the Armijo condition but not the second Strong Wolfe condition on page number 12, slide 107 of these notes : Deadline: March 19 2018.

• Annotated classnotes
• References: Boyd and Vandenberghe Sections 9.3 and 9.4 and Nemirovski Section C.4 (appendix)
• 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: Show that if f is itself quadratic, exact ray search gives an optimal solution to the minimization of f on page number 6, slide 104 of these notes : Deadline: March 22 2018.
• Mandatory Problem Solving: Study the plots of functions on page numbers 23-28 of these notes for Lipschitz continuity of the function OR its gradient, etc: Deadline: March 22 2018.
• Mandatory Problem Solving: What is the connection between Lipschitz continuity of a function and Lipschitz contunity of its gradient. Does one imply the other on page number 28, slide 125 of these notes : Deadline: March 22 2018.

• Annotated classnotes
• References: Boyd and Vandenberghe Sections 9.3.1, 9.4, 9.5 and Nocedal and Wright Section A.2 (subsection "Rates of Convergence"). Extra advanced reading: Nemirovski Section 5.4.2
• References: Best convergence rate bound for gradient (steepest) descent with constant step-size from these notes
• Several graphical illustrations can be found in the matlab code available here.
• Think of more examples of sequences that are R-convergent but not Q-convergent
• Mandatory Problem Solving: Understand the second order conditions for convexity and the proofs for the same on page numbers 30-35, slide 152-156 of these notes: Deadline: March 26 2018.

• Annotated classnotes
• References: Section 9.3 and 9.4 of Boyd and Vandenberghe and Section 3.4 of Nocedal and Wright
• References: Sections 1.2.2, 1.2.3, 2.1.3 and 3.2.3 of Introductory Lectures on Convex Programming by Nesterov.
• 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 the conjugate f* and conjugate of the conjugate f** for the function f=ax^2+bx (where a > 0 and a and b are reals on on page number 11 of these notes: Deadline: March 29 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 20, slide 181 of these notes: Deadline: April 2, 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 on page number 27, slide 185 of these notes: Deadline: April 2, 2018.

• Annotated classnotes
• References: Section 16.1 (and partly 16.2) of Nocedal and Wright (on Equality-Constrained Quadratic Programs)
• References: Geometric motivation for lagrange multipliers in Section 4.4.1 (page 282 onwards) of my lecture notes
• References: Boyd and Vandenberghe beginning of Section 5.1.
• 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.
• References: Best convergence rate bound for gradient (steepest) descent with constant step-size from these notes
• Mandatory Problem Solving: Understand the proof for (order and rate of) convergence of accelerated generalized gradient descent while also appreciating conditions for convergence on page numbers 17-23, slides 194-197 of these notes: Deadline: April 5, 2018.
• Mandatory Problem Solving: Is the projected step of projected gradient descent always a descent direction on page number 30, slide 202 of these notes?: Deadline: April 5, 2018.
• Optional Problem Solving: Understand the geometry of the projected descent on page numbers 43-47, slides 213-217 of these notes?: Deadline: April 5, 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
• References: For Projected and Generalized Gradient Descent, see L. Vandenberghe, Lecture Notes for EE 236C. Some advanced reading is here
• Mandatory Problem Solving: Prove that the Lagrange dual function is always concave on page number 42, slide 236 of these notes?: Deadline: April 5, 2018.

• Recap Solution to Lasso
• some slides explaining the Matrix Completion problem that comes up in situations such as predicting user preferences for market items, movies etc and the generalized gradient descent algorithm for solving it. Its connection with (as a generalization to) Quiz 2, Problem 3 has also been highlighted

• 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: Complete your understanding of the geometric intepretation of the Lagrange dual and the duality gap on page numbers 34-36, that is, slides 254-255 of these notes: Deadline: April 12, 2018.
• Mandatory Problem Solving: Derive the Lagrange dual for the Quiz 1, Problem 1reproduced on page number 37, that is, slide 256 of these notes: Deadline: April 12, 2018.
• Optional Problem Solving: How will the dual of the equation (***) on page number 14, slide 242 of these notes be different from the dual i equation (75) of the primal in (*) on page 10, slide 241 of the same set of slides: Deadline: April 12, 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 24, slide 249 of these notes: Deadline: April 12, 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 previous year's 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 29, that is, slide 268 of these notes: You can read about several optimization algorithms applied to SVMs here. Deadline: April 16, 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 23, that is, slide 266 of these notes

• 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 a high level in page 28, slide 295 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 30, that is, slide 297 of these notes Deadline: April 19, 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 29, that is, slide 296 of these notes

• Annotated classnotes
• Extra optional slides on Active Set Method, several optimization algorithms for Machine Learning Problems, etc
• References: Boyd and Vandenberghe Sections 9.3 and Sections 1.2.2, 1.2.3 and 1.2.4 of Introductory Lectures on Convex Programming by Nesterov.
• 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 a high level in page 28, slide 295 of class notes
• Iterative methods such as Krylov method (conjugate gradient method being a specific example) to solve equations resulting from the KKT conditions. See pages 32-39 of class notes for details of conjugate gradient algo and its variants