IST-CMU PhD Course

Spring 2011

Contact

Instructor: Joćo Xavier

jxavier (@) isr.ist.utl.pt

http://users.isr.ist.utl.pt/~jxavier

TA: Augusto Santos

augustos (@) andrew.cmu.edu

Announcements

- The exam has been sent by email (14h20 Lisbon time = 9h20 Pittsburgh time)
- Homework 7 is available here
- Homework 6 is available here
- Homework 5 is available here
- Deadline extension for homework 4: the due date is Friday 18 March
- Homework 4 is available here
- Spring break: there will be no classes on Wednesday 9 March and Friday 11 March
- Homework 3 is available here
- Deadline extension for homework 2: the due date is Friday 18 Feb
- Special office hours (Lisbon students): Tuesday 15 Feb 15h00-16h30
- Special skype office hours (Pittsburgh students): Friday 11 Feb 16h00-17h30 USA time (skype username: nonlinear.optimization.18799)
- Homework 2 is available here
- There was a misstep in today's lecture (2 Feb) - see slide 139: the fix is in slide 140 (annotated slides)
- Change in the grading policy: only the 6 best homeworks will be taken into account
- The deadline for receiving the homeworks by email (send them to the TA's email) is:
- Pittsburgh students: 6 PM (Pittsburgh time)
- Lisbon students: 11 PM (Lisbon time)
- The classroom (in Portugal) for the lecture on 28th January will be V0.15 (Pavilhćo Civil)
- Office hours (with Augusto Santos):
- Pittsburgh students: Tuesdays 15h30-17h00 USA time (office B9, Porter Hall)
- Office hours (with Joćo Xavier):
- Lisbon students: Fridays 15h00-16h30 Portugal time (office 7.22, North tower, 7th floor)
- Pittsburgh students: Wednesdays 10h00-11h30 USA time (skype username: nonlinear.optimization.18799)
- The annotated slides are available here
- Please fill this form
- Homework 1 is available here
- A file with the essential background is here
- The lectures start Friday 14 January 2011. The schedule is: Wednesdays and Fridays 13h30-15h00 Lisbon time (8h30-10h00 Pittsburgh time). The classroom at CMU is on the INI building, Henry Street. The classroom at IST campus is the Videoconference Room in Instituto de Sistemas e Robotica, North Tower, Floor 7

Course info

Syllabus:

- Part I: formulation of optimization problems. Convex sets and functions. Recognizing canonical classes of convex programs: linear, quadratic, posynomial, geometric, second-order cone, semidefinite positive. Usage of software packages. Applications in communications, estimation, approximation, control, pattern recognition, graphs, networks, etc.
- Part II: conditions for optimality and duality theory. The Karush-Kuhn-Tucker (KKT) conditions for optimality. Geometrical interpretation of KKT conditions. Dual programs, the duality gap and its geometrical interpretation. Applications of duality: provable lower bounds, problem simplification, problem decomposition, convex relaxations of combinatorial problems (e.g. MAXCUT).
- Part III: algorithms. Line-search based algorithms for unconstrained optimization: gradient,quasi-Newton BFGS,Newton. Convergence theory and convergence rates. Algorithms for constrained optimization. Interior point algorithms for convex programs. Penalty, barrier, augmented Lagrangian and SQP methods for general (nonconvex) programs.
- Part IV:
special topics. Nonsmooth optimization and optimization over manifolds.

- Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge University Press
- Numerical Optimization, J. Nocedal and S. Wright, Springer Series in Operations Research

- Lectures on Modern Convex Optimization, A. Ben-Tal and A. Nemirovski, MPS-SIAM Series on Optimization
- Nonlinear Programming, D. Bertsekas, Athena Scientific

Lecture slides

- Course overview
- Part I: formulation of convex optimization problems
- Annotated slides (a)
- Annotated slides (b)
- Part II: conditions for optimality and duality theory
- Annotated slides (updated after each class)
- Part III: numerical algorithms

Homeworks