ESE605 : Modern Convex Optimization

	ESE 605: Modern Convex Optimization Department of Electrical and Systems Engineering University of Pennsylvania
	Spring 2013

Announcements :
- Final Exam will be Take-Home, and will be posted on Thursday April 25
- Take-home midterm will be handed in on Teusday March 21st. You will have 24 or 48 hours to work on it.
- First class is on Thursday January 10 at 3:00pm in Towne 303.
- Linear Algebra Review on Monday January 14th at 2pm 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:
- Aryan Mokhtari , Office Hours: Thursdays, 4:30pm-6:00pm in GRW 4th floor lobby
- Hassan Lotfi, Office Hours: Tuesdays 1:30-3:00pm in GRW 4th floor lobby
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 15th

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

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). Due on Tuesday February 5th in class.

Homework 3: From textbook, problems 3.24(a,d,e), 3.25, 3.43, 4.1, 4.6, 4.9, 4.13, 4.20, 4.21. Problems 2.19, 3.2, 3.3 from additional exercises. Due on Friday February 15th 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 22th

Homework 5: Problems 4.43, 4.45, 5.9, Problem 3.18 from additional exercises. Due on Friday March 1st.

Homework 6: Problems 5.10, 5.12, 5.13, 5.14, 5.16, 5.20, 5.35, 5.39. Due in class on Tuesday March 12th.

Homework 7: Problems 5.41, 5.43. Problems 4.6., 4.7, 4.10, 4.12, 4.14 from additional exercises. Extended to Friday March 29th.

Homework 8:Problems 6.6, 6.8, 7.4 from the textbook. Problems 7.1, 7.2, 7.3 from additional exercises . Some of the problems require a data file, which can be found here . Extended to Friday April 5.

Homework 9: Problems 7.4 and 7.10 from additional exercises. Problem 8.15, 8.20, 9.7, from textbook. Due on Friday April 12th.

Homework 10: Problems 9.8, 9.17 (c), 9.18, 9.27, 9.30, 10.1, 10.2. Due on Friday April 19th.

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 11 (optional; I will drop your lowest HW): Problems 10.3, 10.5, 10.6, 10.12, 10.15, 11.5, 11.6. Problem 9.4 from additional exercises. Due on Friday May 3.

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 10 Lecture 1 Chapters1,2 Introduction

January 15 Lecture 2 Chapters 1,2 Convex Sets

January 17 Lecture 3 Chapter 2 Convex Sets

January 22 Lecture 4 Chapter 2 Convex Sets

January 24 Lecture 5 Chapters 2,3 Convex functions

January 29 Lecture 6 Chapter 3 Convex functions

January 31 Lecture 7 Chapter 3 convex functions

February 5 Lecture 8 Chapter 4 Convex Programing

February 7 Lecture 9 Chapter 5 Duality in Convex Optimization

February 12 Lecture 10 Chapter 5 Interpretations of duality

February 14 Lecture 11 Chapter 5 Geometric interpretation of duality

February 19 Lecture 12 Chapter 5 Duality and Game Theory

February 21 Lecture 13 Chapters 6 Duality in conic problems

February 26 Lecture 13 Chapters 6 More on Duality: interpretations and examples

February 28 Tentative time for Midterm Midterm (Tentative) Midterm(Tentative)

March 12 Lecture 14 Chapter 6 Approximation and fitting

March 14 Lecture 15 Chapter 6 variants of least squares/LASSO/Robust LS

March 19 Lecture 16 Chapter 7 Estimation

March 21 Lecture 17 Chapter 7 Estimation/Machine learning

March 26 Lecture 18 Chapter 9 Unconstrained Minimization

March 28 Lecture 19 Chapter 9 Unconstrained Minimization

April 2 Lecture 20 Chapter 10 Equality Constrained Minimization

April 4 Lecture 21 Chapter 10 Equality Constrained Minimization

April 9 Lecture 22 Chapter 11 Interior point methods

April 11 Lecture 23 Chapter 11 Interior point Methods

April 16 Lecture 24 Chapter 11 Complexity of Interior point methods

April 18 Lecture 25 Chapter 9,11 Self Concordant Functions

April 23 Lecture 26 Notes Advanced topics: SOS optimization/Take-home Final

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