Lecturer: Raffaella Guglielmann  

Course name: Optimization
Course code: 503030
Degree course: Ingegneria Informatica
Disciplinary field of science: MAT/08
University credits: CFU 6
Course website: http://www-dimat.unipv.it/~gugliel/teach.html

Specific course objectives

The course main purpose is twofold: to provide students with topics and tools related to continuous optimization problems, both constrained and unconstrained; to stimulate students to classify and solve optimization problems. The course will introduce the students to main algorithms implemented in the scientific calculus libraries, in particular in the Matlab Optimization Toolbox. During lessons both drawbacks and advantages of the considered optimization algorithms will be illustrated.

Course programme

Course programme deals with the main algorithms used to approximate solutions of continuous optimization problems: the motivating ideas and the convergence properties will be discussed. A considerable part of the course deals with the computer laboratory exercises focused on the implementation of some of the algorithms.

Nonlinear equations

• Newton-Raphson's method for systems of nonlinear equations; convergence results for Newton's method
• Methods based on the approximation of the derivatives: finite-difference approximation of the jacobian; quasi-Newton approximation (rank-1 updates). Convergence analysis of quasi-Newton methods.
• Broyden method: good Broyden update. Sherman-Morrison-Woodbury formula, update of the inverse. Updating factorizations.
• Inexact Newton methods: some hints

Unconstrained optimization problems
Theoretical aspects related to unconstrained optimization problems are firstly illustrated; then the main algortihms are described.

• Newton's method: quadratic model, convergence properties, advantages and drawbacks.
• Line search method: gradient method; Wolfe-Powell conditions. Global convergence analysis.
• Quasi-Newton methods: secant equation; symmetric rank-1 update (SR1); symmetric rank-2 matrix updates. Properties of the updates. Definite positive updates: DFP, BFGS. The Broyden class updates. Global and superlinear convergence results, Dennis-More` theorem.
• Conjugate direction methods: algorithm finite termination in the case of quadratic functions. Nonlinear conjugate gradient method: properties. Strong Wolfe conditions and convergence of the Fletcher-Reeves algorithm.
• Trust region method. Global convergence results. Exact and approximate methods to solve the constrained subproblem.
• Nonlinear least-squares problems: Gauss-Newton methods, damped Gauss-Newton, Levenberg-Marquardt algorithm. Quasi-newton update formulae, hybrid method

Constrained optimization problems
The general formulation and the classification of constrained problems will be illustrated. Then a brief overview of the related algorithms is given.

• Equality and inequality constraints, feasible set, first order KKT conditions, second order optimality conditions. Lagrangian function and multipliers.
• Nonlinear programming: quadratic penalty method, sequential quadratic programming (SQP).
• Linear programming: problem formulation. Linear constraint representation. The simplex method: some hints.

Course entry requirements

Topics related to mathematics courses of the "laurea triennale" (with particular regard to multivariable calculus, numerical linear algebra).

Course structure and teaching

Lectures (hours/year in lecture theatre): 34
Practical class (hours/year in lecture theatre): 8
Practicals / Workshops (hours/year in lecture theatre): 22

Suggested reading materials

J. Nocedal, S.J. Wright. Numerical Optimization. . Springer Verlag, 1999. (Testo di riferimento)..

J. E. Dennis Jr., R. B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM 1996.

Testing and exams

Oral examination and assessment of the computer lab project.