### ESE 605: Modern Convex Optimization

Department of Electrical and Systems Engineering
University of Pennsylvania

Spring 2011

• Announcements :
• First class is on Thursday January 13 at 3:00pm in Towne 303.

• 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 engineering applications of convex optimization, 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 is required. Undergraduates need permission.

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

• Required Text
• Other References

• Homework : 30%
• Midterm : 30%
• Final : 40%

• 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. Homeworks are due at the beginning of class on the day indicated.
• 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 29th at 5pm.

• Homework 2: Reading: Chapter 3 of Boyd and vandenberghe. Problems 2.20, 2.33, 2.34, 2.36, 3.2, 3.7, 3.16. Due on Friday February 5th at 5pm.

• Homework 3: Reading: Chapter 4 of Boyd and vandenberghe. Problems 3.18, 3.23(b), 3.24(a,d,e), 3.25, 3.26(a,b), 3.37,3.43. Due on Friday February 12th.

• Homework 4: Problems 4.2, 4.6, 4.7, 4.9, 4.13,4.20,4.21. Due on Friday February 26th.

• Homework 5: Problems 4.26, 4.34, 4.41, 4.44, 5.11, 5.12, 5.14 . Due on Friday March 5.

• Homework 6: Problems 5.9, 5.35, 5.39, 5.41, 5.43, Robust least squares problem. Due on Friday March 26th.

• Homework 7: Problems 7.4, 8.9, 8.16, 8.20. Due on Friday April 9.

• Homework 8: Problems 9.7, 9.8, 9.17 (c), 9.18, 9.27. Due on Friday April 16.
• Homework 9: Problems 9.30, 10.2, 10.15, 11.5, 11.6, 11.7, 11.9. Due on April 30th.

• 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

-->

• Other resources:

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

• Lecture slides
• Tentative Schedule :

January 14 Lecture 1 Chapters1,2 Introduction, Convex Sets
January 14 Lecture 2 Chapters 1,2 Convex Sets
January 19 Lecture 3 Review Linear Algebra Review
January 21 Lecture 4 Chapter 2 Convex Sets
January 26 Lecture 5 Chapters 2,3 Convex sets and Optimization Problems
January 28 Lecture 6 Chapter 4 Convex Optimization Problems
February 2 Lecture 7 Chapter 4 Vector Optimization, Conic programming
February 4 Lecture 8 Chapter 5 Duality
February 9 Lecture 9 Chapter 5 Duality in Convex Optimization
February 11 Lecture 10 Chapter 5 Interpretations of duality
February 16 Lecture 11 Chapter 6 Approximation and fitting
February 18 Midterm Midterm Midterm
February 23 Lecture 12 Chapters 6,7 Approximation and fitting/ Statistics
February 25 Lecture 13 Chapter 7,8 Geometric Problems, Distance Geometry
March 2 Lecture 14 Notes Numerical Linear Algebra
March 5-15 Spring Break Spring Break Spring Break
March 16 Lecture 15 Chapter 9 Unconstrained Minimization
March 18 Lecture 16 Chapter 9 Unconstrained Minimization
March 23 Lecture 17 Chapter 10 Equality Constrained Minimization
March 25 Lecture 18 Chapter 10 Equality Constrained Minimization
March 30 Lecture 19 Chapter 11 Interior point methods
April 1 Lecture 20 Chapter 11 Interior point Methods
April 6 LECTURE 21 Chapter 11 Complexity of Interior point methods
April 8 Lecture 22 Chapter 9,11 Self Concordant Functions
April 13 Lecture 23 Notes Advanced topics: SOS optimization
April 15 LECTURE 24 Notes Sum of Squares Methods
April 20 Lecture 25 Notes Advanced Topics
April 27 Lecture 26 Notes Review/Take Home Final