Introduction to Optimization
Elad Yarkony
Course description
A first course in optimization theory.
- Instructor: Elad Yarkony
- yarkony2 [at] illinois [dot] edu
- Office hours: Tuesday 2pm–4pm, 167 CSL
- Teaching assistant: Haoxiang Wang
- hwang264 [at] illinois [dot] edu
- Office hours: Wed 1-3pm, ECEB3013
- Meetings: Tuesday and Thursday, 11:00–12:20pm, 2017 ECEB
- Schedule: Midterm: 3/12/20 in class. Final: May 8th 2020, noon. Take home
Announcements
- 1/21/20: Welcome Students !
- 1/31/20: Homework 1 released. Due 2/13 8PM CDT. Submit through Compass2g.
- 2/3/20: TA Office Hours announced.
- 2/3/20: TA Office Hours of 2/5/20 moved to Mon. 2/10/20 ECEB4034, same hours
- 2/5/20: Instructor’s additional office hours on Fri. 2/7/20 3-4pm, ECEB lobby
- 2/20/20: Homework 2 released. Due 3/1 8PM CDT. Submit through Compass2g.
- 3/3/20: Homework 3 released. Due 3/10 8PM CDT. Submit through Compass2g.
- 3/3/20: Midterm 2 will be held on Mar 12th, regular class hours, and will cover HW1-HW3.
- As of Mar 24th 2020, all announcements and communication will be done on Piazza
- 5/8/20: Final Exam
Ongoing Syllabus
- Week 1 (1/20–1/24):
- Week 2 (1/27–1/31):
- Week 3 (2\3–2/7):
- Lecture 5: Cones Contd., Convex Sets PDF
- Lecture 6: Convex Cones, Generalized Inequalities, Dual Cones PDF
- Reading assignment: Boyd, Chapter 2
- Week 4 (2\10–2/14):
- Lecture 7: Convex Cones Wrap up, Convex Functions PDF Jupyter notebook
- Lecture 8: First and Second Order Convexity Conditions, Minima of Convex Functions, Jensen’s Inequality, Convexity Preserving Operations PDF Jupyter notebook
- Reading assignment: Boyd, Chapter 3.1-3.2
- Week 5 (2/17-2/21):
- Lecture 9: Convex-preserving operations, Quasi-Convex and Log-Convex Functions PDF Jupyter notebook
- Lecture 10: Vector/Matrix-valued Convex Functions, Convex Conjugates PDF
- Reading assignment: Boyd, Chapter 3.3-3.6
- Homework 2 released. Due 3/1 8PM CDT. Submit through Compass2g.
- Week 6 (2/24-2/28):
- Week 7 (3/2-3/6):
- Lecture 13: Problem Equivalence, Linear Programs PDF, Chebyshev Center Demo Jupyter notebook
- Homework 3 released. Due 3/10 8PM CDT. Submit through Compass2g.
- Lecture 14: Estimator Bounds, Quadratic Programming, Second Order Cone Programming, Geometric Programming PDF, Jupyter notebook,
- Reading assignment: Boyd, Chapter 4.3-4.5
- Week 8 (3/9-3/13):
- Midterm practice: homework review + the midterms in this link should be useful (note that we did not cover disciplined convex programming, so ignore everything DCP-related)
- Reading assignment: Boyd, Chapter 4.6-4.7
- Week 9 (3/23-3/27):
- Lecture 15: Midterm review, Lagrange Multipliers and Lagrangian Function PDF
- Lecture 16: Dual Problem, Dual Function PDF, Jupyter notebook,
- Reading assignment: Boyd, Chapter 5.1-5.4
- Homework 4 released. Due 4/7 8PM CDT. Submit through Compass2g.
- Week 10 (3/29-4/3):
- Week 11 (4/5-4/10):
- Recorded session: KKT Solution Example (video links on Piazza) Jupyter PDF Annotated
- Recorded session: Analytic Center Dual Example (video links on Piazza) Jupyter
- Recorded session: LP Dual Examples (video links on Piazza) Jupyter
- Recorded session: LP Dualily Through Certification (video links on Piazza) Jupyter
- Live session Apr 6th: Quadratic Forms Jupyter (video links on Piazza)
- Live session Apr 8th: (video links on Piazza)
- Reading assignment: Boyd, Chapter 5.1-5.5
- Week 12 (4/13-4/17):
- Recorded session: Slater’s Condition of Strong Duality (video links on Piazza) Jupyter
- Recorded session: Proof of Slater’s Condition (video links on Piazza) Jupyter
- Recorded session: Perturbation Analysis (video links on Piazza) Jupyter
- Recorded session: Piecewise Affine Program Example (video links on Piazza) Jupyter
- Reading assignment: Boyd, Chapter 5.3-5.6
- Homework 5 released. Due 4/26 8PM CDT. Submit through Compass2g.
- Week 13 (4/20-4/25):
- Recorded session: Unconstrained Minimization (video links on Piazza) Jupyter
- Recorded session: Descent Methods (video links on Piazza) Jupyter
- Recorded session (Apr 23rd): Convergence Analysis (video links on Piazza) Jupyter
- Recorded session: Newton Decrement and Conjugate Gradients (video links on Piazza) Jupyter
- Reading assignment: Boyd, Chapter 9
- Week 14 (4/27-4/30):
- Homework 6 released. Due 5/6 8PM CDT. Submit through Compass2g.
- Recorded session (Apr 27th): Minimization Subject to Affine Equality Constraints (video links on Piazza) Jupyter
- Recorded session (Apr 27th): Barrier Method: Minimization Subject to Convex Inequality Constraints (video links on Piazza) Jupyter
- Reading assignment: Boyd, Chapters 10-11
- Week 15 (5/4-5/8):
- Recorded session (May 5th): Review and Demos (video links on Piazza) Jupyter
- Thu. is reading day
Tentative Syllabus
- Introduction
- Mathematical Background (BV, Appendix A)
- Convex Sets, Cones (BV, Chapter 2)
- Convex Functions, Optimality Conditions (BV Chapter 3)
- Anatomy of Optimization Problems
- Optimization Problems Prototypes (BV, Chapter 4)
- Lagrange Duality (BV, Chapter 5)
- Common Applications
- Data Fitting, Approximation (BV, Chapter 6)
- Estimation (BV, Chapter 7)
- Geometric Problems (BV, Chapter 8)
- Standard Algorithms
- Unconstrained Optimization (BV, Chapter 9)
- Equality constraints (BV, Chapter 10)
- Inequalities (interior point methods, barrier methods) (BV, Chapter 11)
Grading
Recommended Reading
Textbooks and Other Resources
- Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”, book (online version)
- Osman Güler, “Foundations of Optimization”, available as PDF through UIUC online library catalog (click “SpringerLink - Full text online” at the bottom of the page)
Computer Programs
- Python/NumPy tutorials literally all over such as this beautiful lecture
- Plenty of Jupyter references such as this and this
- Download Python 3 here
Other Useful Articles (might grow…)