IE 521 Convex Optimization (Spring 2017)

MW: 1:00PM 2:20PM, 136 Loomis

  

Course Information

Instructor: Niao He (niaohe@illinois.edu)

  Office Hour: Tuesday, 9-10AM at Transportation Building 211

Teaching Assistant: Shuanglong Wang (swang157@illinois.edu)

TA Office Hour: Tuesday, 3pm-4pm at Transportation Building 04

 

Course Description

 

This course is focused on learning to recognize, understand, analyze, and solve unconstrained and constrained convex optimization problems arising in engineering. The course shall focus on the fundamental subjects in convexity, duality, and convex optimization algorithms, as a complementary to IE 411 (Optimization of Large Systems), IE 511 (Integer Programming), and IE 510 (Advanced Nonlinear Programming).

 

The course is intended for students who wish to gain an in-depth understanding of the convex analysis and optimization, and hence places emphasis on rigorous proofs. Students looking for introductory knowledge and/or more practical experience with optimization should consider instead ECE 490 (Introduction to Optimization). Students looking for advanced topics in large-scale optimization should consider IE 598NH (Big Data Optimization).

Prerequisites

  Students are expected to have strong knowledge of linear algebra, real analysis, and multivariate calculus.

Textbooks

 

The recommended book (not required) for the course is

    Boyd & Vandenberghe. Convex Optimization. Cambridge University Press. 2003

Some of the course material is also covered in:

    Ben-Tal & Nemirovski. Lectures on Optimization III: Convex Analysis, Nonlinear Programming Theory, Nonlinear Programming Algorithms, SIAM. 2013

    Bertsekas, Nedich, & Ozdaglar. Convex Analysis and Optimization. Athena Scientific. 2003   

    Hiriant-Urruty & Lemarechal. Fundamentals of Convex Analysis. Springer. 2001

    Ben-Tal & Nemirovski. Lectures on Modern Convex Optimization, SIAM. 2011

    Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer-Academic. 2003

Grading Policy

Grades will be based on

    Homework (30%): approximately biweekly due in class on Wednesdays. You will get 5 bonus points if you type your homework in Latex.

    Midterm Exam (30%): Tentative Date: Wednesday in class, March 15

    Final Exam (30%): Tentative Date: Friday, May 5 8:00-11:00 a.m., Tuesday, May 9, Location: 158 Loomis

Check the final exam schedule here: http://registrar.illinois.edu/spring2017schedulingguidelinespublic

    Class Participation (10%): Attendance is required

Topical Outlines

    Part I: Fundamentals of Convex Analysis (5 weeks): convex sets, convex functions, convex programs, geometry of convexity, Lagrangian duality, optimality condition, and polynomial solvability of convex programming, etc.

    Part II: Modern Convex Optimization (4 weeks): linear program, second order conic program, semidefinite program, interior point method, etc.

    Part III: Algorithms for Non-differential Constrained Convex Programs (2 weeks): subgradient method, cutting plane method, bundle method, etc.

    Part IV: Selective Applications (2 weeks): robust optimization, sparsity optimization, portfolio optimization, statistical inference, etc.

    Part V: Large-Scale Optimization (if time permits): accelerated gradient descent, stochastic gradient descent, incremental gradient methods, proximal algorithms, etc.

 

Lectures

Lecture 0: Introduction, Wednesday, January 18th [Slides]

        Introduction to the Course

 

Classical Convex Optimization (1970s)

 

Lecture 1: Convex Set - Part I, Monday, January 23rd [Notes]

        Topology Review

        Convex Sets (definition, convex/conic/affine hulls, examples, calculus of convex sets )

        Nice Topological Properties of Convex Sets (interior, closure, relative interior)

 

Lecture 2: Convex Set - Part II, Wednesday, January 25th [Notes]

        Representation of Convex Hulls (Caratheodory theorem)

        Radon and Helley Theorems

 

Lecture 3: Convex Set - Part III, Monday, January 30th [Notes]

        Separation Theorems (separation, strict separation, supporting hyperplanes)

        Theorems of Alternatives (Farkas Lemma)

        Strong Duality of Linear Programs

 

Lecture 4: Convex Functions - Part I, Wednesday, February 1st [Notes] [Homework #1] [Solution to Homework #1]

        Convex Functions

        Examples of Convex Functions

        Convexity-Preserving Operators

 

Lecture 5: Convex Functions - Part II, Monday, February 6th [Notes]

        Characterizations of Convex Functions

o   Epigraph, level set, one-dimensional property

o   First order and second order conditions

        Continuity of Convex Functions

 

 Lecture 6: Convex Functions - Part III, Wednesday, February 8th [Notes]

        Subgradient and Subdifferential

       Existence and Subdifferential Properties

 

 Lecture 7: Convex Functions - Part IV, Monday, February 13rd [Notes]

        Closed Convex Functions

       Convex Conjugate Functions

       Conjugate Theory

 

 Lecture 8: Convex Programming Part I, Wednesday, February 15th [Notes] [Homework #2] [Solution to Homework #2]

        Basics Concepts of Convex Programs

       Convex Theorem on Alternatives

       Lagrange Duality

 

Lecture 9: Convex Programming Part II, Monday, February 20th [Notes]

        Illustrations of Lagrange Duality

       Saddle Point Interpretation

       Optimality Conditions (KKT Conditions)

 

Lecture 10: Minimax Problem (Saddle Point Problems), Wednesday, February 22th [Notes]

       Saddle Point and Minimax Problems

       Existence of Saddle Point (Minimax Theorem/Sion-Kakutani Theorem)

 

Lecture 11: Convex Programming Part III, Monday, February 7th [Notes]

       Some Remarks on Minimax Problems

       Optimality Conditions for Unconstrained Convex Problems

       Basic Concepts in Oracles, Complexity, Polynomial Solvability

 

Lecture 12: Polynomial Solvability of Convex Problems, Wednesday, March 1st [Notes] [Homework #3][Download Dataset] [Solution to Homework #3][Sample Code]

       Center-of-Gravity Method

       Ellipsoid Method

 

Modern Convex Optimization (1980s )

 

Lecture 13: Conic Programming, Monday, March 6th [Notes]

       Linear Program (LP)

       Second Order Cone Program (SOCP)

       Semidefinite Program (SDP)

 

Lecture 14: Conic Duality, Wednesday, March 8th [Notes]

       Dual Cones

       Conic Duality Theorems

 

Lecture 15: Applications of Conic Duality, Monday, March 13th [Notes]

       SOCP Duality

       SDP Duality

       SDP Relaxations for Non-convex Quadratic Programs

 

Lecture 16: Application: Robust Optimization, Monday, March 27th [Notes] [Homework #4] [Solution to Homework #4]

       Robust Linear Program

       Example: Robust Portfolio Optimization

       Example: Robust Classification

 

Lecture 17: Interior Point Method Part I, Wednesday, March 29th [Notes]

       Path-Following Scheme

       Self-Concordant Functions

 

Lecture 18: Interior Point Method Part II, Monday, April 3rd [Notes]

       Classical Newton Method for Unconstrained Minimization

 

Lecture 19: Interior Point Method Part III, Wednesday, April 5th [Notes]

       Properties of Self-concordant Functions

       Minimizing Self-concordant Functions

       Newton Method for Self-concordant Functions

 

Lecture 20: Interior Point Method Part IV, Monday, April 10th [Notes] [Homework #5] [Sample Solution to Homework #5]

       Newton Method for Self-concordant Functions

       Damped Newton Method

 

Lecture 21: Interior Point Method Part V, Wednesday, April 12th [Notes]

       Revisit Barrier Method

       Self-concordant Barriers

       Restate Path-following Scheme

 

Lecture 22: Interior Point Method for Conic Programming, Monday, April 17th [Notes]

       Summary of IPM

       Barriers for LP, SOCP, SDP

       Primal-dual Path-following IPM for SDP

 

Lecture 23: Introduction to CVX, Wednesday, April 19th

       CVX Tutorial and Examples

Reference: [Tutorial PDF][Matlab Codes]

 

Large-Scale Convex Optimization

 

Lecture 24: First-Order Methods, Monday, April 24th [Notes] [Homework #6]

       First-Order Methods and Rate of Convergence

       Subgradient Method

 

Lecture 25: Nonsmooth Minimization, Wednesday, April 26th [Notes]

       Subgradient Method

       Bundle Methods: Kelley Method and Level Method

 

Lecture 26: Nonsmooth Minimization with Functional Constraints, Monday, May 1st [Notes]

        Constrained Subgradient Method

        Constrained Level Method

        Lower Bound Complexity