CS 709: Convex Optimization

Instructor: Ganesh Ramakrishnan

Class Timings: 2 PM - 3:30 PM on Mondays and Thursdays
Venue: SIC 201, KReSIT
Office hours: 3 PM - 4 PM on Wednesdays (preferred). 12:30 PM to 2 PM on Mondays, Wednesdays and Thursdays. If this time does not suit you, you could take an appointment with me for clearing doubts etc over email(s)
Current Course Calendar
TAs: Pankaj Joshi

Tentative Syllabus

  1. Quick Review of Linear Algebra and Optimization principles for univariate functions
  2. Introduction to the fundamental theory of convex sets and functions.
  3. General properties of convex optimization problems.
  4. Duality theory
  5. Algorithms for unconstrained minimization
  6. Algorithms for constrained minimization
  7. Sub-gradient methods for non-differentiable functions
  8. Cutting-plane methods
  9. Important standard classes such as linear and quadratic programming, semidefinite programming, (possibly also second-order cone programming), etc.
  10. Applications of the standard classes in probabilistic models and machine learning problems.
  11. Recognizing and formulating convex optimization problems in practice.
  12. Beyond convex optimization: Examples and challenges. Sequential Convex Optimisation.

Class Timings, Venue and Grading

Intro to CVX use
Time: Tuesdays and Fridays, 2:00-3:30 PM
Venue: SIC 201, KReSIT
Credit/Audit Requirements Anyone who does an exceptional course project that has the potential to be a publishable paper is eligible for a straight AA grade. Otherwise the grading breakup would be:
  • 25% Mid-semester exam
  • 40% End semester exam
  • 15% Project: A basic project will take any of the algorithms we study or any related papers, implement the algorithms in the paper, do a basic performance study and diagnose the performance. However, I would expect most projects to suggest ideas for improvement (atleast in specific settings such as multi core or multiple nodes or reasonable assumptions on matrices etc in the problem for which greater speedup is possible). A more advanced project would take a problem specification for which no solution is publicly available, figure out how to solve it, and implement the solution.
  • 15% Quizzes and Assignments.
  • 5% In-class performance and serious attempt to solve homework problem posed in each class. I will use this to ensure class participation
  • Audit students have to perform assignments and project.
  • Prerequisites: Sound understanding of linear algebra.


    • You can check out this link for a growing list of papers that we plan to cover in the assignments/projects or sometimes through discussions in the class. Please start looking at these papers for your seminar and/or projects. We also have some papers on submodularity. Roughly, submodularity is for discrete optimisation what convexity is for continuous optimisation. Check this out.



    Reading/Formulation/Simulation Assignment 1 Reading and presentation assignment 1 will focus on formulation of convex optimisation problems, alternatives and solving using standard solvers. You will need to analyse both analytically as well as empirically. The formal assignment 1 problem statement can be found here.

    Reading/Algorithm design/programming Assignment 2 Reading and presentation assignment 2 will focus on optimisation algorithms.

    References

    1. Lecture Notes
    2. Convex Optimization by Stephen Boyd and Lieven Vandenberghe
    3. Lectures on Modern Convex Optimization by Aharon Ben-Tal and Arkadi Nemirovski
    4. Convex Analysis by R. T. Rockafellar, Vol. 28 of Princeton Math. Series, Princeton Univ. Press, 1970 (470 pages)
    5. Linear Algebra and Its Applications by Gilbert Strang
    6. Nonlinear Programming: 2nd Edition by Dimitri P. Bertsekas
    7. Numerical Optimization by Nocedal, Jorge, Wright, Stephen
    8. An Introduction to Optimization by E.K.P Chong and S.H.Zak
    9. Introduction to Nonlinear Optimization - Theory, Algorithms and Applications by Amir Beck


    You can check out this link for a growing list of resource material (slides/videos/code/lecture notes, etc) for optimisation in general, and convex optimisation in particular. Please let me know if you come across some useful resource material that I could add to this list.


    Course Notes
    Lecture Notes

    Some applets for illustration purposes
    Link to spreadsheet

    Course Exercises
    Exercises

    Sample Matlab Files
    Sample Matlab Files

    Homework Solutions
    Homework Solutions