ESE605 : Modern Convex Optimization

	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:
- 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 : 25%
- Midterm : 30%
- Final : 45%
Teaching assistants:
- Fei Miao , Office Hours: Thursdays 4:30-6:30pm
- Ross Boczar , Office Hours: Mondays 1:00-3:00pm
Further review and reading
- Professor Gallier's lecture notes on linear algebra and optimization. If you feel ypu dont remember your lienar algebra, I suggest auditing this course
- 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:

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

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

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:

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 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

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

Last modified : January 12, 2012. Send comments to Ali Jadbabaie

ESE 605: Modern Convex Optimization