ECE 490: INTRODUCTION TO OPTIMIZATION, FALL 2022

Class time and place: 11:00 - 12:20 TR; In person, ECEB 3081

Instructor: Prof. Farzad Kamalabadi. 320 CSL, farzadk at illinois dot edu
Teaching Assistant: Parisa Karimi, parisa2 at illinois dot edu

TA office hours: Wednesdays 5PM - 7PM, on Zoom. Zoom Coordinates.

Announcements

Please add yourself to the C ampuswire - the entry code is here.
Please add yourself to Gradescope - the entry code is here.

Course Information

Course description: This is a senior/first year graduate-level course on optimization. Topics include necessary and sufficient conditions for local optima; characterization of convex sets and functions; unconstrained optimization, gradient descent and its variants; constrained optimization and the gradient projection method; optimization with equality and inequality constraints, Lagrange multipliers, KKT conditions; penalty and barrier function methods; weak and strong duality and Slater conditions; augmented Lagrangian methods; sub-gradient methods; proximal gradient descent; applications.
Prerequisites: Linear algebra at the level of Math 415, programming skills at the level of ECE 220.
Textbook: D. Bertsekas. Nonlinear Programming, Athena Scientific, 2016.

Other References:
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
D. Luenberger and Y. Ye. Linear and Nonlinear Programming, Springer, 2008.

Exams, homework, grading, etc.:
Homework (H) problems will be assigned on a (approx.) fortnightly basis and must be submitted via Gradescope. Collaboration on the homework is permitted; however, each student must write and submit independent solutions. No late homework will be accepted (unless an extension is granted in advance by the instructor).
There will be four machine problems (MP), which will be done in Python.
There will be two mid-term exams the dates of which are included in the syllabus.
Students taking the course for 4 credit hours will be required to do a final project (FP) as teams of two. Students may communicate via Campuswire to find teammates. The final project should be developed based on a journal article chosen and reviewed by students from relevant research papers; the choice of the paper should be presented to and cleared by the teaching staff prior to the start of the project. Each team is required to review and demonstrate the understanding of the paper, develop ideas that build on the contributions of the paper, implement software code that explores and illustrates the proposed investigation, and provide a ten minutes oral presentation, a written report of four to six pages, and a software demo on the selected project. (Suggested projects)
Grading will be done separately for the 4 credit hour and 3 credit hour students. For 4 credit hour students the course grade will be determined according to the formula:

Score = .15H + .15MP + .25FP + max{.27M1 + .18M2, .18M1 + .27M2}.

For 3 credit hour students, the course grade will be determined by the formula:

Score = .2H + .2MP + max{.36M1 + .24M2, .24M1 + .36M2}.

Here, H, M1, M2, MP and FP are normalized to 100.

Homework Assignments and Exams

Note: Please submit your homework assignments on Gradescope. Scan your handwritten solutions into a pdf file to submit. At the time of submission, please do not forget to indicate which page(s) contain the answers to each of the questions. Submissions must be uploaded to Gradescope before the due date, 11:59 PM.

Machine Problems

Note: Each student must submit their assignment as a ".ipynb" file as well as its ".pdf" version including the name and UIN of the student, the code, sufficient description about the solution (in jupyter notebook's "markdown" format), and the printed/plotted final results. Submissions must be uploaded to Gradescope before the due date, 11:59 PM.

Course Syllabus

Time

Topics

References

Homework

Week 1:

8/22 - 8/26

Course overview: outline, organization, and logistics
Notations and fundamental definitions
Some archetypical applications of optimization (least squares, supervised learning, inverse problems in imaging, recommender systems, internet reource allocation, power allocation in wireless networks, portfolio construction)
Linear algebra review (inner product, norm, eigenvalue decomposition, diagonalization of matrices, matrix norm)

Bertsekas Appendix A-B

BV Appendix A

HW1 post date:

8/23

Week 2:

8/29-9/2

Basic concepts of optimization (local and global extrema, conditions of optimality, semi/positive definite matrices definitions and tests)
Convex optimization (closed and open sets, convex sets and functions, optimization for convex functions)

Bertsekas chapter 1

BV chapters 2-3

Week 3:

9/5-9/9

Gradient methods (gradient/steepest descent)
Descent lemma (Liptchitz continuity, Cauchy-Schwartz inequality)

Bertsekas chapter 1

BV chapter 9

HW1 due date:

9/6

Week 4:

9/12-9/16

Convergence of gradient descent (fixed step size)
Convergence of gradient descent (Armijho’s rule)

Bertsekas chapter 1

BV chapter 9

HW2 post date:

9/13

MP1 post date:

9/15

Week 5:

9/19-9/23

Application: neural networks and the backpropagation algorithm
Newton’s method

Bertsekas chapter 1

BV chapter 9

HW2 due date:

9/22

HW3 post date:

9/22

Week 6:

9/26-9/30

Projected gradient method for constrained optimization
Lagrange multipliers: equality constraints

Bertsekas chapters 2-3

BV chapter 10

MP1 due date:

9/29

MP2 post date:

9/29

Week 7:

10/3-10/7

Lagrange multipliers: equality constraints
Midterm 1 in class (10/6)

Bertsekas chapters 3-4

BV chapter 10

HW3 due date:

10/4

HW4 post date:

10/6

Midterm I:

10/6 in class

Week 8:

10/10-10/14

Lagrange multipliers: inequality constraints

Bertsekas chapters 3-4

BV chapter 11

MP2 due date:

10/13

MP3 post date:

10/13

Week 9:

10/17-10/21

Examples on Lagrange multipliers
Application (e.g. wireless power allocation)

Bertsekas chapters 3-4

HW4 due date:

10/20

Week 10:

10/24-10/28

Penalty and barrier functions methods
Duality

Bertsekas chapters 3-5

BV chapter 11

MP3 due date:

10/27

MP4 post date:

10/27

Week 11:

10/31 - 11/4

Dual of linear programs
Application: support vector machines

Bertsekas chapter 3

HW5 post date:

11/1

Week 12:

11/7 - 11/11

No lecture on 11/8.
Augmented Lagrangian methods

Bertsekas chapter 4

MP4 due date:

11/10

Week 13:

11/14-11/18

Subgradient descent
Midterm 2 in class (11/17)

Bertsekas chapter 6

HW5 due date:

11/15

HW6 post date:

11/15

Midterm II:

11/17 in class

Final project topics finalized by 11/17

Week 14:

11/21-11/25

Thanksgiving break

Week 15:

11/28-12/2

Proximal gradient methods
Final project presentations (12/1)

HW6 due date:

11/27

Final project presentations on 12/1

Week 16:

12/5-12/9

Final project presentations (12/6)

Final project presentations on 12/6