Growing problem set: Please find here a growing list of practice problems. 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.

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 (discussed in midsem), 5.5, 5.7, 5.9, 5.10 to 5.13 (partly discussed in midsem), 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

Homeworks: With each of the homework problems mentioned below (often referred to in a lecture), are associated deadlines. After the specified deadline, I will randomly pick a student and ask him/her to solve or present solution to the homework. If the student has made an effort that impresses me, he/she will earn 1% marks. If I realise the student has not even made an attempt to solve the problem, I will deduct 1% marks.

• 24/07/2013 You know that the solution set to Ax = b is affine. When is it empty? When is it conic? Can you think of characterising the geometry of an affine set using linear algebra discussions in the class? Making use of the analysis in the class, prove that the any affine set can be expressed as solution set of system of linear equations. Deadline: July 31 2013.
• 24/07/2013 We showed that an affine set is a translated (displaced) subspace. Show that there can be only one subspace S associated with an affine set A. Deadline: August 2 2013.
• 26/07/2013 Brush up the concepts of eigenvalues, eigenvectors and postive (semi-)definite matrices. Deadline: August 2 2013.
• 31/07/2013 Understand the different types of sets and spaces discussed so far and understand their relationships. Deadline: August 2 2013.
• 31/07/2013 Complete the proof that x'Px is a norm for vector x, if P is positive definite. Thus, an ellipsoid is a norm ball. Deadline: August 2 2013.
• 31/07/2013 Prove that an inner product vector space is a normed vector space. Deadline: August 2 2013.
• 31/07/2013 Show that the following are vector spaces (assuming scalars come from a set S), and then answer questions that follow for each of them: Set of all matrices on S, set of all polynomials on S, set of all sequences of elements of S. (HINT: You can refer to this book for answers to most questions in this homework.) How would you understand the concepts of independence, span, basis, dimension and null space (chapter 2 of this book), eigenvalues and eigenvectors (chapter 5), inner product and orthogonality (chapter 6)? EXTRA: Now how about set of all random variables and set of all functions. Deadline: August 7 2013.
• 07/08/2013 Understand the different types of norms, the shapes of different norm balls and norm cones and nature of the sparsity induced by each norm. A nice motivation for why the l1 norm works can be found here. Deadline: August 14 2013.
• 07/08/2013. Show the equivalence between the two definitions of convex/conic/affine hulls discussed in class: (a) as set of all convex/conic/affine combinations of points in S and (b) as the smallest convex/conic/affine set that contains S. Deadline: August 14 2013.
• 14/08/2013 Systematically prove that the Hyperbolic cone is convex by using the property that images and inverse images under affine transformations of convex sets are convex sets. Deadline: August 16 2013.
• 14/08/2013. Take some arbitrary sets (I encourage you to take the set of constraints in the paper you have chosen in assignemt 1, as well as other relevant/cited papers for example) and try to show/disprove that they are convex. Try writing convex program to show that some of them are/are not convex. Deadline: August 21 2013.
• 16/08/2013 Prove that if S is convex and its closure does not contain 0, then there exists a hyperplane that strictly separates S from {0}. Deadline: August 21 2013.
• 21/08/2013. Understand the concept of Conic Programming/Optimisation by reading up this paper by Nemirovski. Now prove that K being a proper/regular cone is a necessary and sufficient condition for the corresponding induced inequality to be a well-defined partial order. Understand how linear programs, semi-definite programs etc are special cases of conic programs. Deadline: August 23 2013.
• 21/08/2013. Complete the proof for step (1) of the Duality theorem for Linear Programs from Nemirovski's notes Deadline: August 28, 2013.
• 23/08/2013. Brush up optimisation principles for univariate functions (extreme value theorem, mean value theorem, increasing/decreasing functions and convexity, criteria for maxima and minima etc) and some possibly new concepts for functions of multiple variables such as gradient, direction of gradient, level curves, etc. See page numbers 216 to 253 of my optimisation notes. Deadline: August 30 2013.
• 21/08/2013. Complete the proof (especially step (3) of the Duality theorem for Linear Programs. Likewise, prove Theorem 1.2.3 from Nemirovski's notes making use of Thereom 1.2.2. Deadline: September 4, 2013.
• 25/09/2013. Prove the necessary and sufficient first order conditions for (strictly) increasing functions of single variable Deadline: September 27 2013.
• 27/09/2013. Complete the proof of the claim on page 16: I = II = III = IV after understanding the proof for "I = II" (with some hints provided for "I => III"). Deadline: October 4 2013.
• 04/10/2013. Make sure that you understand the proofs for local minimizer=global minimizer, unique global minimizer for a strictly convex function, equivalence of different mathematical specifications (gradient free, first order, gradient monotonicity and Hessian) of convexity spanning pages 25 to 36. Now solve following problems (i) Show that the sum of a convex and a strictly/strongly convex function is strictly/strongly convex. (ii) Suppose that f(x)= x'Qx, where Q is an n x n matrix. Show conditions under which f(x) is (strictly/strongly) convex and show this using each of the 4 equivalent conditions for (strict/strong) convexity.(we will try to discuss convexity of more functions through such assignments) Deadline: October 9 2013.
• 04/10/2013. After understanding the proofs spanning pages 25 to 36, reproduce the proof for uniform monotonicity of the gradient of a strongly convex function. Deadline: October 11 2013.
• 04/10/2013. Consider the function f(x1,x2)=3+(x1-1.5*x2)^2 + (x2-2)^2 which we discussed in class. You should easily show that f is convex. Now using the level curve applet here convince yourself that the sublevel set of a convex function is convex if and only if the function is convex. Deadline: October 11 2013.
• 21/08/2013. Along the lines of the proof for the (weak and strong) duality theorem for Linear Programs, prove the (weak and strong) duality theorem for Conic programs, more specifically Theorem 2.1 of this paper on conic programs by Nemirovski. You can refer to these slides and this paper for a sketch of the proof. Deadline: October 11 (you need to submit the proof by October 11 and this carries 5 Marks)
• 11/10/2013. Provide a rough sketch of the proof that (1) [page 40] In general any induced matrix norm is convex (2) [page 41] There exist independent orthonormal eigen vectors of X'X for any matrix X. In fact, X'X is called a normal matrix (see these notes and these notes) (3) [page 45] (gradient f(x), -1 ) is the normal to the supporting hyperplane to epigraph of f at x. Deadline: October 16
• 11/10/2013. Provide a rough sketch of the proof that (1) [page 42] X+tv = X(I+ tX^(-0.5) V X^(-0.5)) if X is positive definite (2) [second last problem on page 48] \sum_i log g_i(x) is concave if g_i are concave and postive (3) [last problem on page 48] log \sum_i exp g_i(x) is convex if g_i are convex. Deadline: October 18
• 18/10/2013 [Page 10] Prove that if f:D->R is continuously differentiable on D and f is bounded below along { x^(k) + t delta x^(k) | t>0 } and if 0 < c1 < c2 <1, there exist intervals of step length t^(k) satisfying the wolfe conditions 4.90 and 4.91. Hint: make use of the mean value theorem. Deadline: October 23
• 18/10/2013 [Page 15] Verify that the unnormalized steepest descent direction satisfies the expression that its dot product with the gradient is the negative of the square of the dual norm of the gradient. Deadline: October 23
• 23/10/2013 [Page 17] What is steepest descent with v restricted to unit value under the infinity norm? How do you prove it? You might want to take hint from page 18, where we prove how steepest descent with l1 norm constraint on v gives the descent direction based on the corresponding component of the infinity norm. Deadline: October 25
• 23/10/2013 Consider the function f(x,y) = x^2+y^2 with domain={(x,y)|x>1}. What is (x*,y*), the point of minimum? Draw the sublevel set S={(x,y)| f(x,y)<=f(x0,y0)} for (x0,y0)=(2,2). Is the sublevel set S closed? Is f strongly convex on S? What happens if we apply the gradient descent method with backtracking line search, starting at (x0,y0)? Does f(xk,yk) converge to (x*,y*)? Deadline: October 30
• 01/11/2013. Show that every convex optimisation program (problem) can be represented in the form of a conic optimisation program (problem) Optional: Solution on page 4 of these notes .
• 30/10/2013. Identify choice of non-affine hj(x) (in the constraint hj(x)=0) in the optimisation problem on page 9 (unlike that on page 1) of these notes that yields convex domain. Deadline: November 1st .
• The following question on weak duality are in reference to the book "An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods" by John Shawe Taylor. Try and derive the dual for the SVM objective formulations in equations (a) 6.4, (b) 6.4, (c) 6.7 and (d) 6.8. For all these objectives, the final dual formulations are described in the sections immediately following the speficiation of the respective objectives. Deadline: 6th November.
• 06/11/2013. For the problem of least norm solution of linear equations (page no 13), show that A is an m x n matrix with m < n and if A has full row rank, strong duality holds, that is, there exists a point x satisfying the primal constraints such that the lower bound obtained using weak duality is actually attained. Hint: Refer to this. Deadline: 8th November.
• 06/11/2013. For the two-way partitioning example (page no 15), study the effect of different types of matrices W on the lower bound based on the smallest eigenvalue.Deadline: ???
• The following questions on KKT conditions and strong duality are in reference to the book "An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods" by John Shawe Taylor. Derive the KKT conditions and the dual for the SVM objective formulations in equations (a) 6.4, (b) 6.4, (c) 6.7 and (d) 6.8. For all these objectives, the KKT conditions and the dual are described in the sections immediately following the speficiation of the respective objectives. Deadline: ??.
• 21/08/2013. Prove that the dual cone of a linear set is its orthogonal complement. Deadline: ??

Introduction. Illustration of solving optimisation problem using CVX and instructions for matlab/cvx access.

• Intro to CVX use.

Introduction to convex optimisation, introduction to affine sets

• Handwritten class notes. Please note recommended reading for the next class at the end of the class notes.

Introduction to convex sets and their properties, introduction to convex cones and their properties

• Handwritten class notes. Please note recommended reading for the next class at the end of the class notes.

Norms, Normed Vector spaces, Topological Spaces, Inner Product vector spaces, their relationships, positive definiteness concepts

• Handwritten class notes. Please note recommended reading for the next class at the end of the class notes.

Continuation of proofs from previous lecture and generalisation of concepts such as norm, inner product, dimension, eigenvalues, null space, etc to Matrix spaces, space of polynomials, functions, etc

• Handwritten class notes. Please note recommended reading for the next class at the end of the class notes.

Generalisation of concepts such as norm, inner product, dimension, eigenvalues, null space, etc to Matrix spaces, space of polynomials, functions, etc, Compact representation, dual representation and examples, geometric understanding of norm balls, affine and conic hulls, polyhedra and simplices

• Handwritten class notes.
• Handwritten class notes (part 2).
• A nice motivating explanation for why the l1 norm induces sparsity..

Conically spanning set, PSD cone, convexity preserving operations, affine function

• Handwritten class notes.

Some topological concepts, Separating Hyperplane Theorem, Supporting Hyperplane Theorem and their proofs

• Handwritten class notes.

Solution to homework problem (also introduced connecting between derivatie and increasing/decreasing function), Generalised inequalities and regular cones, linear programs and conic programs

• Handwritten class notes.

Discussion of solution to homework problem, linear program and its dual, weak and strong duality for linear programs

• Handwritten class notes.

Solution to homework problem, Farkas' Lemma for LP, Dual cone, properties of dual cone with illustrations, weak duality for CP, duality theorems for LP and CP

• Handwritten Class Notes.
• Basic definitions for Optimisation of multivariate functions.

Solution to homework problem (Farkas Lemma leading to strong duality for LP) followed by discussion on basics of univariate optimisation and extensions to mutivariate case

• Solution to homework problem.
• Basics of Univariate Optimisation and its Generalisation.

Mean value theorem, Taylors theorem for functions of single and multiple varibles, first and higher order approximations. Introduction to the Hessian.

• Mean value theorem, Taylors theorem for functions of single and multiple varibles, first and higher order approximations. Introduction to the Hessian..

Basics of Univariate Optimisation and its Generalisations, equivalent convexity conditions, strong convexity conditions for convergence of algos, properties of convex functions, examples of convex functions, epigraphs, sublevel sets, subgradients, all with illustrations and proofs

• Several illustrations are based on the matlab code available here.

Algorithms for Unconstrained Minimisation: (Pages 1-10) Descent conditions, Line search methods, Strong Wolfe conditions

• Several illustrations are based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming

Algorithms for Unconstrained Minimisation: (Pages 6-16) Convergence of descent algos under Lipshitz continuity and Wolfe conditions, example illustrating importance of second wolfe condition, steepest descent algos, existence proof for step sizes for Wolfe conditions

• Several illustrations are based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming

Algorithms for Unconstrained Minimisation: (Pages 10-12) Existence of step size satisfying Wolfe conditions, (Pages 17-29) coordinate and gradient descent as steepest descent algos, order and rate of convergence, linear rate of congerence for gradient descent.

• Several illustrations are based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming

Algorithms for Unconstrained Minimisation: (pages 28-29) order and rate of convergence, (page 30) linear rate of congerence for gradient descent without need for strong convexity, (page 31) convergence rate for steepest descent using other norms, (pages 32-39) conjugate gradient algo and its variants, (pages 39-43) newton's method, newton decrement, interpretations of both and proof of convergence

• Several illustrations are based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming

Algorithms for Unconstrained Minimisation: (pages 47-60) Quasi-Newton methods such as Gauss-Newton, Levenberg-Marquardt, Newton method on self-concordant functions, BFGS, DFP, LBFGS

• Several illustrations are based on the matlab code available here, which is adopted from matlab code accompannying the book Applied Optimization with MATLAB Programming

Algorithms for Constrained Minimisation (Pages 1-11): Every convex program can be expressed as a conic program, recapping duality theory for linear and conic programs from previous lectures, Duality theory for general constrained optimisation problems, weak duality, concavity of dual.

Algorithms for Constrained Minimisation (Pages 11-26): Example optimisation problems and their duals, Strong duality conditions for convex functions, graphical understanding of strong duality

Algorithms for Constrained Minimisation (Pages 27 onwards): Necessary KKT conditions and their graphical understanding, necessary and sufficient KKT conditions for convex program, interior point methods, barrier method

Algorithms for Constrained Minimisation: projected (sub)gradient descent, (primal) active set, (kelley's) cutting plane, references to all these constrained optimisation techniques applied to SVM objective

• Example 1: Constrained Quadratic optimisation using active set.
• Example 2: Kelly's cutting plane algo.
• Other examples from Machine Learning Linearly & Quadratically constrained least squares, Logarithmic barrier methods, subgradient descent etc.
• Illustration of the various constrained optimisation techniques (interior point, projected subgradient decent, active set and cutting plane) applied either to the primal or to the dual of the SVM objective
• 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

Endsem questions and solutions