Nonlinear Optimization

Nonlinear Optimization (18799 B,PP)
IST-CMU PhD Course
Spring 2013

Contact
Announcements
Course info
Lecture slides
Homeworks

Contact

Instructor: João Xavier
jxavier (@) isr.ist.utl.pt
http://users.isr.ist.utl.pt/~jxavier

TA: Augusto Santos, Ricardo Cabral
augustos (@) andrew.cmu.edu, ric.s.cabral ( @ ) gmail.com

Announcements

The exam has been sent by email at 14h00 Lisbon = 9h00 Pittsburgh (May 9). If you haven't received yet contact immediately the TAs.

Homework 6 has been posted. (This is the last homework.)

Homework 5 has been posted.

Extra classes: Friday, April, 26, 15h30-16h50 (Portugal) = 10h30-11h50 (Pittsburgh) and Friday, May, 3, 15h00-16h20 (Portugal) = 10h00-11h20 (Pittsburgh)

A new version of the homework has been posted. The deadline is extended to April 19.

The 24h exam is scheduled for Thursday, May, 9. You'll receive the exam by email at 14h00 Lisbon = 9h00 Pittsburgh.

Homework 4 has been posted.

Homework 3 has been posted. Thursday, March 28, and Tuesday, April 2, there is no class.

The new deadline for Homework 2 is: Tuesday, March 19.

Homework 2 has been posted.

Homework 1 has been posted.
Office hours for Lisbon students:
- with João Xavier: Tuesdays 17h30-18h30 (Lisbon time)
- with Augusto Santos: Wednesdays 15h00-16h00 (Lisbon time)
Office hours for CMU, Porto and Aveiro students (use skype account nonlinear.optimization.18799):
- with João Xavier: Thursdays 17h30-18h30 (Lisbon time) = 12h30-13h30 (Pittsburgh time)
- with Augusto Santos: Fridays 17h00-18h00 (Lisbon time) = 12h00-13h00 (Pittsburgh time)
The lectures start January 22, 2013. The schedule is: Tuesdays and Thursdays 16h00-17h20 Lisbon time (11h00-12h20 Pittsburgh time). The classroom at CMU is in Hamerschlag Hall 1107. The classroom at IST campus is the CMU Videoconference Room at Pavilhão de Engenharia Civil.

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.

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 50% (24h take home)

Lecture slides

Part I: formulation of convex optimization problems

Homeworks