EE5606 Convex Optimization

Each student will be expected to

• attend classes and solve short in-class (surprise) quizzes
• participate in class
• solve homework assignments
• write exams (3-4)

• Slot R: Tuesdays 14:30-16:00, Fridays 16:00-17:30
• Class venue: A-221

We will primarily use the following material:

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization. (BV) Soft copy available for free. A few physical copies also available in the campus library.
• Edwin Chong and Stanislaw Zak, An Introduction to Optimization, 4th ed.
• Nisheeth Vishnoi, Algorithms for Convex Optimization

Other references will be indicated below.

Programming:

• A short introductory video series on python programming
• The numpy quickstart is a good place to learn the basics of the numpy library.
• The same holds true for matplotlib. As long as you can create basic 2d and surface plots, it should be sufficient.
• We will also use the cvxpy library in python. This website has a very detailed documentation, and a large number of examples.

Basics:

• Gilbert Strang, Introduction to linear algebra for very basic stuff
• Jimmie Gilbert and Linda Gilbert, Linear algebra and matrix theory
• Roger Horn and Charles Johnson, Matrix analysis: good for topics starting from eigenvalues and eigenvectors
• Terence Tao, Analysis 1 is a more gentle introduction to real analysis, and mostly deals with \(\mathbb{R}\).
• Walter Rudin, Principles of mathematical analysis: for basic topology

Recorded lectures from the previous edition of this course can be accessed via this playlist.

Tentative list of topics:

• Introduction
• Review of real analysis, derivatives, gradient, hessian (Refs: books by Tao and Rudin. Also see the first few chapters of Chong-Zak and appendix in Boyd-Vandenburghe)
• Review of linear algebra: basics, symmetric and PSD matrices (Refs: Strang, Gilbert-Gilbert, Horn-Johnson)
• Definitions and basic properties of convex sets and convex functions
• Unconstrained convex optimization, and numerical algorithms for solving these
• Cvxpy for solving constrained convex optimization problems
• Deep dive into convex sets and their properties
• Deep dive into convex functions and their properties
• Convex optimization problems with constraints
• Lagrange multiplier method and KKT conditions

Students are encouraged to discuss with each other regarding class material and assignments. However, verbatim copying in any of the assignments or exams (from your friends or books or an online sources) is not allowed. This includes programming assignments. It is good to collaborate when solving assignments, but the solutions and programs must be written on your own. Copying in assignments or exams, will be dealt with severely.

See this page (maintained by the CSE department), this page, and this one to understand more about plagiarism.

• When writing/submitting code, make sure that the code works. Ensure that there are no spurious lines, missing declarations/initializations, etc. This is particularly true for jupyter notebooks, and more so if you are exporting ipynb to py. There is a tendency to perform out of order execution in jupyter notebooks (which is generally a bad habit and should be avoided as much as possible, but can be helpful for quick checks), but your final code should work when executed in order.
• If you are using a particular dataset/additional files, you must provide this along with your code, or a working link to the data.
• Please comment your code! The main advantage of jupyter notebooks is that you can intersperse detailed text with code. This is particularly necessary when someone else is going to see your work (or you want to go through it at some later point in time)
• Follow good programming practices: use good naming convention for variables, try to write modular code, and keep it as simple as possible.
• Unless your code just involves executing one py file, or ordered execution of cells in a jupyter notebook, you should provide instructions for running the files. You must also specify what environment/libraries are required for running your files. You must not expect the user to figure this out.

In addition to learning cool stuff, you should also learn to present your work. The final presentation is an opportunity to develop your presenting skills. You must be able to convey your ideas and thoughts clearly to another person. Here are some general comments for making good presentations:

• Make sure that you acknowledge all the references/material that you used (papers/code/etc.) While it does not matter much for the purposes of this class, this is very important to keep in mind when you are delivering presentations at bigger venues
• In a presentation, always introduce yourself and your team members/collaborators in the very beginning.
• If much of the presentation is based on on one/two papers/references, explicitly state which references you are using in the first/second slide.
• Avoid saying “We did this/we showed that…” when you are in fact talking about some other authors’ work. Unless you have derived something/programmed something yourself, always say “they/the authors did/showed/observed that…”
• A presentation/report is like telling a story: even before preparing the slides/document, imagine that you want to explain the work to a friend in 15-20 mins, identify exactly what you want to convey, and only then proceed.
• Make sure that you explain the problem clearly.
• When reading a paper, you should first understand what the problem is, what makes it challenging, and why it is worthwhile solving the problem. Then, you should identify what is new about the paper, and what the contributions are. To understand the rest of the paper, you should then try to understand the constructions/proof techniques/ideas. Your presentation should also bring out these aspects. See this article and this one on how to read a paper.
• There is no single best rule for presentations, but generally in any presentation, the viewer/audience’s attention is maximum in the first 5-10 minutes and then gradually decreases. So it is helpful to get to the punchline in the first few minutes.
• Citations should be treated differently in papers and slides. When you are making a reference to a particular paper/book/website (for e.g., when you say that result A can be found in paper B) in your slides, mention the paper/book/website as a footnote rather than saying [1], and putting the reference in the last slide. 
• Do not put too much text on your slides. This is bad practice. Each slide should contain at most 3-5 points. You should absolutely avoid long sentences. 
• Do not copy text directly from the paper.
• Do not read out your slides word-to-word.
• Similarly, do not put too many lemmas in a slide. Each slide should convey a single idea. Unless very important, do not put too much math/long derivations in a short presentation. It is more important to convey ideas/intuition. But at the same time, there should be a significant amount of technical content. It is therefore very useful to instead explain using examples.
• Make sure that the fonts/diagrams/labels/plots are clear. Label all the axes on your plots.
• Speak clearly, and make sure that the audio quality is fine. Check your mic volume. Do a couple of dry runs.
• If you are using Google meet to record, then make sure that you “pin” the slides since meet might automatically switch displaying you/your icon instead of the presentation. 
• Make sure that you check, and double check the slides and report for typos, technical and grammatical errors.
• If your group has more than one person, then the presentation must be shared equally.
• Use a standard document format for reports (not slides), preferably latex for typesetting math.
• Use standard formats for citing references in reports: e.g., see this and this