Graduate course in nonlinear optimization

Key words:

Convex sets and functions, separation, cones and polarity, polyhedral sets, extreme points and directions, subgradients, minima and maxima, support functions, the Fritz John and Karush-Kuhn-Tucker conditions, constraint qualifications, Farkas Lemma, sensitivity analysis, Lagrangean duality, duality gap, saddle points, Lagrangean dual problem, nonsmooth optimization, decomposition, closed algorithmic maps, unconstrained optimization, line searches, gradient-based optimization methods, coordinate search, convergence rates, derivative-free optimization, penalty and barrier methods, interior point methods, feasible direction methods.

Credits:

Eight (old) credits in the PhD program, five for the theory part, three for the algorithmic part

Literature:

M S Bazaraa, H D Sherali and C M Shetty: Nonlinear Programming: Theory and Algorithms (Wiley, 2006) (main course book, [BSS])
D P Bertsekas: Nonlinear Programming (Athena, 1999) (supplementary material, [Ber])

A few selected articles are also included

Examination:

Exercises, oral examination and a project.

Reading list by topic:

BSS, Chapter 1 (Introduction)
Exercises: 2, 6, 12, 13
Topics for oral exam: Section 1.3
BSS, Chapter 2 (Convex sets)
Exercises: 1, 2, 9, 11, 16, 17, 18, 19, 20, 21, 25, 27, 29, 30, 31, 38, 39, 42, 44, 46, 52, 53, 54
Topics for oral exam: Theorems 2.1.6, 2.3.1, 2.4.1, 2.4.4, 2.4.5, 2.5.4, 2.6.5, 2.6.7
Additional topic: generalization of Theorem 2.4.5 to nonlinear systems
BSS, Chapter 3 (Convex functions and generalizations)
Exercises: 9, 10, 12, 14, 16, 17, 18, 20, 21, 22, 23, 24, 26, 27, 31, 32, 33 38, 40, 43, 45, 46, 47, 50, 51, 52, 54, 55, 56, 57, 69
Topics for oral exam: Theorems 3.1.3, 3.4.2, 3.4.3, 3.4.4, 3.4.7; the subdifferential
Additional topics: generalized convex functions and monotone mappings; generalizations of Theorem 3.4.4 (establish similar statement for non-differentiable convex functions; re-prove Theorem 3.4.4 where f in C^1 replaces f in C^2)
Ber, Chapter 2.1 (Optimality conditions)
Exercises: 1.10, 11, 12
BSS, Chapter 4 (The Fritz John and the Karush-Kuhn-Tucker optimality conditions)
Exercises: 4, 6, 9, 12, 13, 14, 15, 16, 17, 19, 20, 24, 26, 29, 30, 31, 32, 34, 37, 39, 41, 45, 46, 47, 48
Topics for oral exam: Theorems 4.2.2, 4.2.5, 4.2.8, 4.2.13, 4.2.15, 4.2.16; differences between FJ and KKT; Example 4.4.4
Ber, Chapter 3.2 (Sufficient conditions and sensitivity analysis)
Exercises: 3.1, 2, 3
Additional topic: upper semicontinuity of solutions to linear programs
BSS, Chapter 5 (Constraint qualifications)
Exercises: 3, 5, 6, 12, 13, 14, 15, 16, 20
Topics for oral exam: relations between CQ, and their role in the convex and linear cases
BSS, Chapter 6 (Lagrangian duality and saddle point optimality conditions)
Exercises: 1, 3, 4, 5, 6, 7, 9, 13, 14, 16, 18, 19, 22, 25, 26, 29, 30, 34, 36, 37, 38, 41, 42, 43, 44
Topics for oral exam: geometry of the dual problem; Theorems 6.2.5, 6.3.1, 6.3.2, 6.3.3, 6.3.11, 6.5.1
Ber, Chapter 5 [Section 5.4 orientation] (Duality and convex programming)
Exercises: 3.1, 3
Topics for oral exam: duality gaps in integer optimization; Propositions 5.1.1, 5.1.4, 5.1.5, 5.1.6, 5.3.1
Ber, Chapter 6 [see also BSS, Section 8.9] (Dual methods)
Exercises: 2.1; 3.1, 4, 5, 8, 10, 12
Topics for oral exam: Propositions 6.1.2, 6.3.1
Additional topics: ergodic convergence [Shor, Larsson et al.], convexification by dualization
BSS, Chapter 7 (The concept of an algorithm)
Exercises: TBA
Topics for oral exam: closedness of a mapping
Additional topics: closedness versus upper semicontinuity; spacer steps [Luenberger]
BSS, Chapter 8 (Unconstrained optimization)
Exercises: TBA
Topics for oral exam: relationships between gradient and trust region methods; Theorem 8.8.3
Ber, Chapter 1 [Section 1.9 orientation] (Unconstrained optimization)
Exercises: 2.4, 5, 6, 10
Additional topics:
- the Wolfe condition in line search methods [Dennis and Schnabel, 1983, 6.3]
- convergence of steepest descent methods [Bertsekas and Tsitsiklis, SIAM J Optim, 2000]
- convergence of Gauss-Seidel and Jacobi methods [Bertsekas and Tsitsiklis, 1989, 5.1, 5.5, 5.6]
- pattern search [Lewis, Torczon, and Trosset, OPTIMA, 1998]
- trust region methods [Dennis and Schnabel, 1983, 6.4]
- non-monotone and curvilinear searches [Toint, SIAM J Sci Comput, 1996, Ferris, Lucidi, and Roma, COAP, 1996]
- closedness of some iterative methods [Patriksson]
BSS, Chapter 9 (Penalty and barrier functions)
Exercises: TBA
Topics for oral exam: interpretations; relationships
Ber, Chapter 2 (Optimization over a convex set)
Exercises: 2.2, 3, 6, 7; 3.2, 6, 8; 7.2
Topics for oral exam: relationships between optimality and the construction of improving directions
BSS, Chapter 10 [orientation] (Methods of feasible directions)
Exercises: TBA
Topic for oral exam: relationships between optimality and the construction of improving directions
Additional topics: simplicial decomposition [Hearn et al., Patriksson]

Project:

Implementation and evaluation of some iterative methods for nonlinear optimization.