Convex Optimization

  • Home/
  • Convex Optimization

CLASS HOURS

Tues:? 5:30 pm  7:00 pm,? Thurs: 7:15 pm  8:45 pm
Location LT:1, 6th Floor.

OFFICE HOURS AND CONTACT INFO.

Instructor: Dr. Ali Ahmed
Office Hours: Tues, Thurs (2:00pm – 4:00pm)
Email:?ali.ahmed@itu.edu.pk

Teaching Assistant: Nasir Aziz
Office Hours: TBA
Email:?msee19004@itu.edu.pk

COURSE BASICS

Core Course
Credit Hours: 3
Batches: MSDS, MSCS, MSEE @ ITU

Programming
Five Assignemnts

PREREQUISITE

Linear algebra (e.g., solving systems of equations, least squares, matrix factorizations including SVD), basic probability (e.g., you should be comfortable with multivariate probability densities), and have good MATLAB or Python programming skills.

COURSE OVERVIEW

This course covers the principles of convex optimization. We discuss in detail mathematical fundamentals, formulation of problems in multiple applications as optimization programs, and iterative algorithms to numerically solve the optimization programs.

COURSE OBJECTIVES

Upon successful completion of this course, students should:

  1. Be able to recognize and differentiate between common classes of optimization problems.
  2. Have an understanding of how duality can be exploited to develop alternative approaches to solving an optimization problem.
  3. Be able to implement and analyze the convergence properties of common iterative optimization algorithms.
  4. Be able to translate practical engineering problems into optimization problems (modeling)

GRADING POLICY

  • 45% Assignments
  • 5% Class participation and Creating Notes
  • 20% Final Project
  • 10% Quizzes
  • 10% Midterm Exam
  • 10% Final Exam

HONOR CODE

All cases of academic misconduct will be forwarded to the disciplinary committee. All assignments are group-based unless explicitly specified by the instructor.

COURSE OUTLINE

Topics
Introduction to optimization, basic geometric and algebraic concepts

Convexity

  1. convex sets
  2. convex functions
  3. convexity, gradients, and optimization

Unconstrained minimization

  1. gradient descent
  2. line search methods
  3. convergence analysis
  4. accelerated first order methods (Heavy ball, Neseterov)
  5. incremental and stochastic gradients
  6. Newton’s method
  7. Quasi-Newton methods
  8. subgradient descent
  9. proximal methods

Theory for constrained optimization

  1. optimality conditions
  2. Fenchel duality
  3. Lagrange duality
  4. Karush-Kuhn-Tucker (KKT) conditions

Methods for constrained optimization

  1. barrier techniques
  2. projected gradient descent
  3. splitting methods, alternating direction method of multipliers
  4. ADMM

Applications/extensions

  1. convex relaxation and nonconvex optimization
  2. optimization for robotics
  3. optimization for control
  4. optimization for statistical inference
  5. optimization for machine learning
  6. optimization for inverse problems

COURSE NOTES

? Topics Notes / Reading Material / Comments
11th Mar?2021 Introduction to Convex Optimization
  • Notes
16th Mar?2021 Examples of convex optimization problems
  • Notes
18th Mar?2021 Convex sets and functions
  • Notes
23rd Mar?2021 Differentiable functions, convexity, and optimization
  • Notes
25th Mar?2021 Gradient descent
  • Notes
27th Mar?2021 Convergence analysis of gradient descent
  • Notes
30th Mar?2021 Convergence analysis of gradient descent
  • Notes
1st Apr?2021 Quasi-Newton methods: BFGS
  • Notes
2nd Apr?2021 Subgradients and Subgradient descent
  • Notes
3rd Apr?2021 Proximal methods
  • Notes
6th Apr?2021 Optimality conditions for constrained optimization problems
  • Notes
10th April 2021 Lagrangian duality
  • Notes
15th April 2021 KKT conditions
  • Notes
19th April 2021 Duality revisited: Convex conjugates and support functions ?
20th Apr?2021 Fenchel duality
  • Notes
22th Apr 2021 Algorithms for constrained optimization
  • Notes
27th Apr 2021 Dual ascent, dual decomposition, method of multipliers
  • Notes
29th Apr 2021 ADMM
  • Notes
1st May 2021 Distributed estimation using ADMM
  • Notes
6th May 2021 Convex relaxation
  • Notes

?

TEXT BOOK

  • Convex Optiization Book by Lieven Vandenberghe, Stephen Boyd, and Stephen P. Boyd

ASSIGNMENTS

  • ASSIGNMENT 1:?

    • Linear Program, Convexity Proofs

  • ASSIGNMENT 2:

    • Eigenvalue decomposition, symmetric positive semidefinite, Kullback-Liebler (KL) divergence

  • ASSIGNMENT 3:

    • Quadratic functions, Matlab for convex optimization

Courtesy of Mark Davenport