ESE605 : Modern Convex Optimization

	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:
- Ali Jadbabaie , jadbabai (at) seas (dot) upenn (dot) edu ,
  Office hours : Wednesdays 3:00-5:00pm or by appointment, 365 GRW Moore bldg
Lectures: Tuesdays and Thursdays 3:00pm-4:30pm in Towne 303

Required Text
- S. P Boyd and L. Vandenberghe, Convex Optimization
Other References
- J. Renegar, A Mathematical View of Interior Point Methods for Convex Optimization
- 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.
Grading:
- Homework : 30%
- Midterm : 30%
- Final : 40%
Teaching assistants:
- Pooya Molavi , Office Hours: Monday 2-3pm, and Arastoo Fazeli , Office hours: Wednesdays 1-2pm.
Further review and reading
- Some introductory mathematical preliminaries by Professor Mehran Mesbahi
- Linear Algebra Review by Professor Fernando Paganini, UCLA.
- More on convex sets, polytopes, and polyhedra by Professor Jean Gallier
Assignments and homework sets:

Read the mathematical preliminaries and the linear algebra notes before the next lecture on Tuesday January 20th

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:

Professor Stephen Boyd's lectures at Stanford.
Professor Gilbert Strang's Linear Algebra lectures at MIT.

Software:

CVX A Matlab-based software for disciplined convex programing

Lecture slides

Tentative Schedule :

Date Lecture Reading Contents

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

Date	Lecture	Reading	Contents
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

Last modified : January 11, 2010. Send comments to Ali Jadbabaie

ESE 605: Modern Convex Optimization