### ESE 605: Modern Convex Optimization

Department of Electrical and Systems Engineering
University of Pennsylvania

Spring 2012

• Announcements :
• First class is on Thursday January 12 at 3:00pm in Towne 303.
• Linear Algebra Review on Thursday at 4:30pm after class in GRW 4th floor Lobby.

• Course Description: This course deals with theory, applications and algorithms of convex optimization, based on advances in interior point methods for convex programing. The course is divided in 3 parts: Theory, applications, and algorithms. The theory part covers basics of convex analysis and convex optimization problems such as linear programing (LP), semidefinite programing (SDP), second order cone programing (SOCP), and geometric programing (GP), as well as duality in general convex and conic optimization problems. In the next part of the course, we will focus on applications of convex optimization in engineering, statistics, operastions research and finance. The applications range from systems and control theory to estimation, data fitting, information theory, statistics and machine learning. Finally, in the last part of the course we discuss the details of interior point algorithms of convex programing as well as their compelxity analysis.
• Requirement: This course is math intensive. A solid working knowledge of linear algebra, analysis, probability and statistics in an advanced undergraduate level is required. Undergraduates need permission.

• Instructor:
• Lectures: Tuesdays and Thursdays 3:00pm-4:30pm in Towne 303

• Required Text
• Other References

• Homework : 25%
• Midterm : 30%
• Final : 45%

• Teaching assistants:

• Assignments and homework sets:

• It is essential that all assignments for this course be completed in accordance with the precepts of the Code of Academic Integrity.
Failure to comply with the Code of Academic Integrity will not be tolerated. Homework assignments are give on Tuesdays and are due by 5pm on the Friday after.

• Additional Exercises : Some homework problems will be chosen from this problem set.

• Homework 1: Reading: Chapter 2 of Boyd and Vandenberghe. Problems 2.1, 2.3, 2.7, 2.8(a,c,d), 2.10, 2.18, 2.19. Due on Friday January 27th.

• Homework 2: Reading: Chapter 3 of Boyd and vandenberghe. From additional exercises problems 1.1, 1.2, 2.1. From textbook, problems 3.3, 3.9, 3.13, 3.18, 3.23(b), 3.24(a,d,e), 3.25. Due on Friday February 10th at 5pm

• Homework 3: From textbook, problems 3.43, 4.1, 4.6, 4.9, 4.13, 4.20, 4.21. Problem 2.19, 3.2, 3.3 from additional exercises. Due on Friday February 17th at 5pm.

• Homework 4: Problems 4.26 , 4.34, 4.41, 4.44. Problem 3.4, 3.8, 3.10, 3.11 from additional exercises (some require CVX). Due on Friday February 24th

• Homework 5: Problems 4.43, 4.45, 5.9, 5.35, 5.39, 5.41, 5.43. Problem 3.18, 4.2, 4.3 from additional exercises (requires CVX). Due on Friday March 2.

• Homework 6: Problems 5.10, 5.12, 5.13, 5.14, 5.16, 5.20. Problems 4.6., 4.7, 4.10, 4.12, 4.14 from additional exercises. Due in class on Tuesday March 13th.

• Homework 7:Problems 6.6, 6.8, 7.4 from the textbook. Problems 7.1, 7.2, 7.3, 7.10, from additional exercises . Some of the problems require a data file, which can be found here . Due on Friday March 30th.

• Homework 8: can be found here . Due on Friday April 6th.

• Homework 9: Problems 9.7, 9.8, 9.17 (c), 9.18, 9.27, 9.30. Due on Friday April 13th.
• For problem 9.30:
• generate a random instant with n=30, m=60.
• Make sure that your line search first finds a step length for which the tentative point is in domain of f
• if you attempt to evaluate f outside its domain, you’ll get complex numbers, and you’ll never recover.
• Use chain rule to find expressions for g= ∇f(x) and H=Hessian of f. Use Vnewton=-H \ g

• Homework 10: Problems 10.1, 10.2, 10.3, 10.5, 10.6, 10.12. Due on Friday April 20th.

• Homework 11: Problems 10.15, 11.5, 11.6, 11.7, 11.9 from text. Problem 9.4 from additional exercises. Due on Friday April 27th.

• Other resources:

• Software:
• CVX A Matlab-based software for disciplined convex programing

• Lecture slides
• Tentative Schedule :

January 12 Lecture 1 Chapters1,2 Introduction
January 17 Lecture 2 Chapters 1,2 Convex Sets
January 19 Lecture 3 Chapter 2 Convex Sets
January 24 Lecture 4 Chapter 2 Convex Sets
January 26 Lecture 5 Chapters 2,3 Convex functions
January 31 Lecture 6 Chapter 3 Convex functions
February 2 Lecture 7 Chapter 3 convex functions
February 7 Lecture 8 Chapter 4 Convex Programing
February 9 Lecture 9 Chapter 5 Duality in Convex Optimization
February 14 Lecture 10 Chapter 5 Interpretations of duality
February 16 Lecture 11 Chapter 5 Geometric interpretation of duality
February 21 Lecture 12 Chapter 5 Duality and Game Theory
February 23 Lecture 13 Chapters 6 Duality in conic problems
February 28 Lecture 13 Chapters 6 More on Duality: interpretations and examples
March 1 Tentative time for Midterm Midterm (Tentative) Midterm(Tentative)
March 13 Lecture 14 Chapter 6 Approximation and fitting
March 15 Lecture 15 Chapter 6 variants of least squares/LASSO/Robust LS
March 20 Lecture 16 Chapter 7 Estimation
March 22 Lecture 17 Chapter 7 Estimation/Machine learning
March 27 Lecture 18 Chapter 9 Unconstrained Minimization
March 29 Lecture 19 Chapter 9 Unconstrained Minimization
April 3 Lecture 20 Chapter 10 Equality Constrained Minimization
April 5 Lecture 21 Chapter 10 Equality Constrained Minimization
April 10 Lecture 22 Chapter 11 Interior point methods
April 12 Lecture 23 Chapter 11 Interior point Methods
April 17 Lecture 24 Chapter 11 Complexity of Interior point methods
April 19 Lecture 25 Chapter 9,11 Self Concordant Functions
April 24 Lecture 26 Notes Advanced topics: SOS optimization/Take-home Final