ESE 605, Spring 2021 – Modern Convex Optimization

Instructor: Nikolai Matni (nmatni@seas.upenn.edu), Assistant Professor, ESE Department

TAs: Yijie (Lisa) Zhao (zhaoyij@seas.upenn.edu), Alexander Robey (arobey1@seas.upenn.edu), Alp Aydinoglu (alpayd@seas.upenn.edu)

Lectures: Tu/Th 3:00-4:30pm ET, Zoom lectures (check Piazza for Link/Passcode) will be recorded live and posted to Canvas afterwards. You may choose to attend the live recordings or watch asynchronously. Beyond showing basic respect to the instructor and your classmates, no requirements (e.g., cameras must be on, you may not watch from bed, no eating, etc.) will be asked of those tuning in to live lectures.

Syllabus: ESE605-001

If you are trying to register for the class: use this form. Do not e-mail me, I cannot help you!

Canvas: We will be using Canvas to manage class logistics. Please log in and register here. On Canvas, there will be a link to Piazza, please register there as well. We will be posting Zoom links/passcodes on Piazza approximately 30min before lecture to prevent Zoom bombing.

Office hours

  • Nikolai's OHs: Tu/Th 4:30-5:30pm ET, check Piazza for Zoom Link/Passcode

  • Lisa's OHs: Fr 9-11am ET, check Piazza for Zoom Link/Passcode

  • Alex's OHs: We 7-9pm ET, check Piazza for Zoom Link/Passcode

  • Alp's OHs: Mo 1-3pm ET, check Piazza for Zoom Link/Passcode

Course description

In this course, you will learn to recognize and solve convex optimization problems that arise in applications across engineering, statistics, operations research, and finance. Examples will be chosen to illustrate the breadth and power of convex optimization, ranging from systems and control theory, to estimation, data fitting, information theory, and machine learning. A tentative list, subject to change, of what we will cover includes: convex sets, functions, and optimization problems; the basics of convex analysis; least-squares, linear and quadratic programs, semidefinite programs, minimax, extremal volume, and other problems; optimality conditions, duality theory, theorems of alternatives, and applications; interior-point algorithms for solving convex optimization problems, and their complexity analysis; applications to signal processing, statistics and machine learning, control, digital and analog circuit design, and finance.

Course objectives

  • to give students the tools and skills needed to identify convex optimization problems that arise in applications

  • to introduce the basic theory of convex optimization problems, concentrating on results that are useful in understanding, improving, and extending computational methods

  • to give students a deep and foundational understanding of how such problems are solved, and hands on experience in solving them

  • to give students the background needed to feel comfortable in applying these methods in their own research work and/or applications

About the Course

Prerequisites

This is a math intensive course. A solid foundation in linear algebra (at the level of Math 314), as well as comfort with analysis, probability, and statistics at an advanced undergraduate level is required. Familiarity with one of Matlab, Python, or Julia. Undergraduates need permission.

Intended audience

This course will benefit anyone who uses or will use scientific computation or optimization in engineering, statistics, signal processing, or related work (e.g., machine learning, finance). More specifically, convex optimization problems are likely to pop up in the work of people in the following departments and fields: Electrical Engineering (signal/image processing, communications, control), Aero/Astro Engineering (guidance, navigation, control, design), Mechanical & Civil Engineering (robotics, control, structural analysis), Computer Science (machine learning, robotics, computer graphics, algorithms & complexity, computer networking), & Operations Research (Wharton).


Schedule

The following schedule is tentative and subject to change.

Date Topic Reading Homework
Week 1
1/21
Logistics, Introduction Chapter 1
Appendix A
Sign up for Canvas & Piazza
Week 2
1/26, 1/28
Convex sets Chapter 2 Homework 1 (due 2/15)
Week 3
2/02, 2/04
Convex functions Chapter 3 No new homework
Week 4
2/09, 2/11
Convex optimization problems Chapter 4 No new homework
Week 5
2/16 , 2/18
Convex optimization problems
Duality
Chapter 4, 5 Homework 2 (due 2/26)
Week 6
2/23, 2/25
Duality Chapter 5 No new homework
Week 7
3/02, 3/04
Approximation and fitting Chapter 6 Homework 3 due 03/12
Week 8
03/09, spring break
Statistical estimation Chapter 7 No new homework
Week 9
3/16, 3/18
Statistical Estimation
Geometric problems
Chapters 7, 8 Homework 4 (due 3/26)
Week 10
3/23, 3/25
Geometric problems
Numerical Linear Algebra Review
Chapter 8
Appendix C
No new homework
Week 11
3/30, 4/01
Unconstrained minimization Chapter 9 Homework 5 (due 4/09)
Week 12
4/06, 4/08
Equality constrained minimization Chapter 10 No new homework
Week 13
4/13, 4/15
Interior-point methods Chapter 11 Homework 6 (due 4/23)
Week 14
4/20, 4/22
Advanced topic: TBD TBD Homework 7 (due 4/29)
(out on Friday, will be shorter)
Week 15
4/27, 4/29
Advanced topic: TBD
Conclusions
N/A Final exam
date TBD

Textbook

The textbook is Convex Optimization by Boyd and Vandenberghe, available online.

Additional optional resources that may prove useful include:

  • J. Renegar, A Mathematical View of Interior Point Methods for Convex Optimization, 1998

  • A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, 2001

  • D. Bertsekas, A. Nedic, and A Ozdaglar, Convex Analysis and Optimization , 2003

  • L. El Ghaoui's EE227BT Lecture Notes

Software

You will use one of CVX (Matlab), CVXPY (Python), or Convex.jl (Julia), to write simple scripts. We refer to CVX, CVXPY, and Convex.jl collectively as CVX*.

Grading

  • Homework (50%): there will be bi-weekly homework assignments, handed out on Tuesday, and due two weeks later on Friday by 5pm (except for the final assignment which will be due the last day of class). The homework assignments must be LateXed and submitted on Canvas via Gradescope. Please use this LaTeX template – we ask that you write out detailed and rigorous solutions. You will be given 6 free late days which you may use as you please throughout the semester, after which no late assignments will be accepted. You are allowed, even encouraged, to work on homework in small groups, but you must write up your own homework solutions and code to hand in – please indicate who you collaborated with on your assignments. Each homework problem will be graded on a scale of 0-4.

  • Final take-home exam (50%): there will be a 24 hour final take-home exam scheduled during the final exam period. Please refer to the Stanford EE364a offering of this course for an idea of what the final exam will look like, as well as the logistics of how it will be administered.

Note that these weights are approximate, and we reserve the right to change them later.

Code of Academic Integrity: All students are expected to adhere to the University’s Code of Academic Integrity.