Introduction to Convex Optimization (MICAS-901)

Course Curriculum

The course will broadly cover the five modules below. 

1. Theory of convex, affine, conic functions and sets; Supporting and separating hyperplane theorem, caratheodory theorem; Second order cones; Differentiability of convex functions; Strongly convex and L-Smoothness

2. Understanding mathematical optimization, contour level sets, sublevel sets; Hierarchy of Optimization problems and their equivalences: linear programming, quadratic programming, second order conic programming, and semi-definite programming

3. Lagrange duality: Lagrangian function, properties of Lagrangian, Dual function, and dual problem formulation, Weak duality, Strong duality;  Slaters condition for guaranteeing strong duality, KKT conditions

4. Deterministic and stochastic algorithms for convex optimization problems: 1st order descent methods (gradient descent, first order acceleration (Nesterov/ heavy ball method)) and 2nd order descent methods (Newton raphson method); the  stopping criterion, convergence analysis; Sub-gradient methods; Stochastic gradient descent

5. Non-convex optimization algorithms: Approximate gradient and hessian algorithm, Successive approximation methods (linear and quadratic approx.), Coordinate descent methods (block coordinate descent and block successive upperbound minimization), Branch and bound method; Heuristic algorithms: Simulated annealing, Genetic algorithms, and Ant Colony Optimization 

Evaluation: Assignments/ Quiz: 20%, Take-home programming assignment: 10%, Exam: 70%

References: 

[1] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.

[2] A. Antoniou and W.-S. Lu, Practical optimization: Algorithms and engineering applications. Springer, 2007. https://link.springer.com/book/10.1007/978-1-0716-0843-2 

[3] S. Diamond and S. Boyd, “Cvxpy: A python-embedded modeling language for convex optimization,” Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016.

[4] S. Boyd, Subgradient methods https://web.stanford.edu/class/ee364b/lectures/subgrad_method_notes.pdf 

[5] Hong, Mingyi, Xiangfeng Wang, Meisam Razaviyayn, and Zhi-Quan Luo. ”Iteration complexity analysis of block coordinate descent methods.” Mathematical Programming163, no. 1 (2017): 85-114. https://arxiv.org/abs/1310.6957 

[6] Boyd, Stephen, and Jacob Mattingley. ”Branch and bound methods.” Notes for EE364b, Stanford University 2006 (2007): 07. https://see.stanford.edu/materials/lsocoee364b/17-bb_notes.pdf , https://see.stanford.edu/materials/lsocoee364b/17-bb_slides.pdf