Nonlinear Optimization (18799
B,PP)
IST-CMU PhD Course
Spring 2012
Contact
Instructor:
João Xavier
jxavier
(@) isr.ist.utl.pt
http://users.isr.ist.utl.pt/~jxavier
TA:
Dragana Bajovic
dbajovic
(@) andrew.cmu.edu
The past year's exams are going to be sent soon by email. If you have not received them by Wednesday, April 18, please let the TA know
Homework 5 is available here. It is due April, 4.
Homework 4 is available here. It is due March, 21.
There will be no classes next week, i.e., March 12 and 14 (CMU Spring break). We resume March 19.
Homework 3 is available here. It is due March, 7.
The annotated slides are available here.
Homework 2 is available here. It is due February, 22.
Class cancellation: there is no class on Wednesday, Feb 1.
Office hours for Lisbon students:
with João Xavier: Wednesdays 15h00-16h00 (Lisbon time)
with Dragana Bajovic: Wednesdays 12h00-13h00 (Lisbon time)
Office hours for CMU students (use skype account nonlinear.optimization.18799):
with João Xavier: Wednesdays 16h00-17h00 (Lisbon time) = 11h00-12h00 (Pittsburgh time)
with Dragana Bajovic: Fridays 17h00-18h00 (Lisbon time) = 12h00-13h00 (Pittsburgh time)
Homework 1 is available here. It is due the 8th of February.
A file with the essential background is here
The lectures start January 18, 2012. The schedule is: Mondays and Wednesdays 18h30-20h00 Lisbon time (13h30-17h00 Pittsburgh time). The classroom at CMU is on the INI building, Henry Street. The classroom at IST campus is the CMU Videoconference Room at Pavilhão de Engenharia Civil
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)
Part I: formulation of convex optimization problems