EE5606 Convex Optimization

Each student will be expected to

• attend classes and solve short in-class quizzes
• participate in class
• solve a mid-term exam
• solve homework assignments
• present a paper/do a project/solve a final exam

• Slot P: Mondays 14:30-16:00, Thursdays 16:00-17:50
• Class venue: A-112

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.
• Lecture notes, available here. These notes will be updated periodically.

Other references will be indicated below.

Programming:

• A short introductory video series on python programming

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
• Walter Rudin, Principles of mathematical analysis: for basic topology
• Terence Tao, Analysis 1 is a more gentle introduction to real analysis, and mostly deals with \(\mathbb{R}\).

Some of the recorded classes will be made available in this playlist.

Python code for some of the programs demonstrated in class can be found here.

For the final project, you must pick one problem (or class of problems) and provide a solution/partial solution. The problem may be very applied, or very mathematical, but every submission must mainly use techniques from convex sets or convex optimization techniques (even if the original problem is essentially nonconvex). You must also connect this to what was discussed in class. Each submission must contain

• Clear description and mathematical formulation of the problem - what it is, why is it interesting/relevant, any assumptions made and why they make sense, and the precise formulation
• Some mathematical analysis, and
• Some code for solving/analyzing the problem.

For the programming part, you may use numpy, scipy, matplotlib, cvxpy libraries. Please take permission before using other libraries.

You must submit a report and code for your project. You are encouraged to work in groups of 2 members each.

Grading will be based on the following metrics:

• Technical content: how challenging the problem is, and how much you cover about the problem
• Presentation: how well you explain your problem and solutions

Here are some suggested topics. You are free to pick any other problem, but please consult me before finalizing your topic.

• Belief propagation is a popular algorithm used in decoding error correcting codes, and many machine learning algorithms. There is also a nice connection to statistical physics wherein the fixed points of the BP algorithm are in one-one correspondence with relaxations of a certain “free energy” functional. This landmark paper describes the connection.
• Similar approaches to the above are used in statistical inference. See, eg this paper for a review of variational inference methods.
• There are various functionals that can be defined on matrices. The permanent of a matrix has a very similar expression as the determinant, but while the determinant can be computed in polynomial time, computation of the permanent is known to be a hard problem. There has been a lot of work in obtaining approximation algorithms for the permanent. See this and the papers citing this for details.
• A very recent development in theoretical computer science is this approach called the “sum of squares method” for obtaining approximation algorithms for computationally hard problems. The high-level idea is to express the problem as a sum of squares optimization problem and relax some integer constraints to obtain an SDP (see Assignment 2 for a sum of squares constraint and connection to SDPs). This set of lecture notes has several problems that can be solved using this method, including the max cut problem discussed in the first class.

• Several problems in statistical inference can be solved using convex optimization techniques:

  • Sparse recovery
  • Hypothesis testing
  • Functional estimation
  • Linear estimation for signal recovery

  See the book “Statistical Inference via Convex Optimization” by Juditsky and Nemirovski.

• A challenging but interesting area is online convex optimization, wherein the optimization is done interatively. This is useful in areas such as reinforcement learning. See “Introduction to online convex optimization” by Hazan for details.
• You may also present some algorithms/advanced techniques used for numerically solving convex optimization techniques. See “Algorithms for Convex Optimization” by Vishnoi.
• The area of convex analysis is a very useful tool in many problems beyond optimization. The formal study of polyhedra and convex sets was initiated by Minkowski (to the best of my knowledge). See these lecture notes or “A course in convexity” by Barvinok.
• You may also present problems that are posed in Boyd&Vandenburghe but not covered in class. You are encouraged to however go through other references on the same problem to go in depth.
• The problem of computing the capacity of a discrete memoryless channel can be solved using an interative algorithm (called the Blahut-Arimoto algorithm). Here is the original paper. Also see this one. See the papers citing this for more recent work on computing capacity of more complicated problems.
• Many problems in network optimization (resource allocation) can be formulated as optimization problems and solved using convex optimization techniques.
• SDP based techniques have been developed for MIMO detectors in communications, radar code design, and matrix decompositions.
• Many papers use convex optimization techniques for nonnegative matrix factorization and blind source separation.
• Many problems in game theory have minimax optimization problems wherein the goal is to find the saddle point.

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.

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.