Nonlinear Optimization

Nonlinear Optimization (18799 B,PP)
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:

The classroom (in Portugal) for the lecture on 28th January will be V0.15 (Pavilhão Civil)
Office hours (with Augusto Santos):

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.

Textbooks (main):

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

Textbooks:

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

Grading: Homework 50% (7 homeworks), final exam 40% (24h take home) , oral examination 10% (1h)