Module page
Numerical approximation methods
| academic year: | 2013/2014 |
| instructor: | Maurizio Falcone |
| degree course: | Mathematics - DM 270/04 (triennale) |
| type of training activity: | affine e integrativa |
| credits: | 6 (48 class hours) |
| teaching language: | italiano |
| period: | I sem (30/09/2013 - 17/01/2014) |
Lecture meeting time and location
Presence: highly recommended
Module aims:
The main goal of this course is to present and analyze numerical methods for classical constrained and unconstrained optimization problems in R^n. Several algorithms will be implemented (in C, C++ or MATLAB) in the Lab sessions.
Module subject:
Characterization of minima and maxima for constrained and unconstrained
Characterization of convex functions and convex sets, strong convexity, subdifferential. Projection on a convex set. Separation theorem.
Unconstrained optimization problems. Methods of descent: the gradient method. Convergence of the gradient method with optimal step-size. Error estimates. Step-size control techniques for the gradient method. Relaxation method.
Constrained optimization problems. Karush-Kuhn-Tucker conditions. Some algorithms for constrained optimization: projected gradient, projected relaxation, penalization, Uzawa. Linear programming (LP). Duality in LP and duality theorem. The simplex method. Sketch of the interior point method.
Some applications in control problems, image processing, economy and finance, physics.
The laboratory activity will be devoted to the implementation of several algorithms in C, C++ or MATLAB.
Suggested reading: Dispense del docente J. Nocedal, S.J. Wright, Numerical Optimization, Springer, 2002 J.F. Bonnans, J.C. Gilbert, C. Lemarechal, C.A. Sagastizabal, Numerical Optimization: theoretical and practical aspects, Springer, 2003
Type of course: standard
Prerequisites:
The students attending this course should have the basic notions of mathematical analysis and linear algebra corresponding, for example, to the courses "Calcolo I" and "Calcolo II", "Algebra Lineare" and "Analisi Matematica I". The knowledge of basic results in optimization is recommended but not strictly necessary. Moreover, the basic knowledge of a programming language (C, C++ or MATLAB) is required. The level required can be achieved in the courses "Laboratorio di Programmazione e Calcolo" or in a course of "Abilita' Informatiche".
Knowledge and understanding: The students will know the classical methods and algorithms for numerical optimization. Moreover, they will be able to code the corresponding algorithms and solve optimization problems in low dimension.
Skills and attributes:
The students will be able to choose a correct numerical method to solve their problem and they will be able to write the code corresponding to the algorithm.
Personal study: the percentage of personal study required by this course is the 65% of the total.