**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 18^{th} [Slides]

·
Introduction to the Course

** Classical Convex Optimization **(–1970s)

Lecture 1: **Convex Set -
Part I**, Monday, January 23^{rd} [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 25^{th} [Notes]

·
Representation of Convex Hulls (Caratheodory
theorem)

·
Radon and Helley Theorems

Lecture 3: **Convex Set -
Part III**, Monday, January 30^{th} [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 1^{st} [Notes] [Homework #1] [Solution to Homework #1]

·
Convex Functions

·
Examples of Convex Functions

·
Convexity-Preserving Operators

Lecture 5: **Convex
Functions - Part II, **Monday, February 6^{th} [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 8^{th}
[Notes]

·
Subgradient and Subdifferential

· Existence and Subdifferential Properties

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

·
Closed Convex Functions

· Convex Conjugate
Functions

· Conjugate Theory

Lecture 8: **Convex Programming – Part I, **Wednesday,
February 15^{th}
[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 20^{th} [Notes]

·
Illustrations of Lagrange Duality

· Saddle Point
Interpretation

· Optimality Conditions
(KKT Conditions)

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

· Saddle Point and
Minimax Problems

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

Lecture 11: **Convex
Programming – Part III, **Monday, February 7^{th} [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 1^{st} [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 6^{th}
[Notes]

· Linear Program (LP)

· Second Order Cone
Program (SOCP)

· Semidefinite Program
(SDP)

Lecture 14:** Conic
Duality, **Wednesday, March 8^{th} [Notes]

· Dual Cones

· Conic Duality
Theorems

Lecture 15:** Applications
of Conic Duality,** Monday, March 13^{th} [Notes]

· SOCP Duality

· SDP Duality

· SDP Relaxations for
Non-convex Quadratic Programs

Lecture 16:** Application:
Robust Optimization,** Monday, March 27^{th} [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 29^{th} [Notes]

· Path-Following Scheme

· Self-Concordant
Functions

Lecture 18:** Interior
Point Method – Part II, **Monday, April 3^{rd} [Notes]

· Classical Newton
Method for Unconstrained Minimization

Lecture 19:** Interior
Point Method – Part III, **Wednesday, April 5^{th} [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 10^{th} [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 12^{th} [Notes]

· Revisit Barrier
Method

· Self-concordant
Barriers

· Restate
Path-following Scheme

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

· Summary of IPM

· Barriers for LP,
SOCP, SDP

· Primal-dual
Path-following IPM for SDP

Lecture 23:** Introduction
to CVX, **Wednesday, April 19^{th}

· CVX Tutorial and
Examples

Reference: [Tutorial
PDF][Matlab Codes]

__Large-Scale Convex Optimization__

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

· First-Order Methods
and Rate of Convergence

· Subgradient Method

Lecture 25:** Nonsmooth Minimization, **Wednesday, April 26^{th} [Notes]

· Subgradient Method

· Bundle Methods:
Kelley Method and Level Method

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

·
Constrained Subgradient Method

·
Constrained Level Method

·
Lower Bound Complexity