Optimization (the English translation of "Ottimizzazione")
Teacher
prof. aggr. Daniele CASAGRANDE
Credits
6 CFU
Language
Italian
Objectives
The course introduces to the theory of optimization in finite dimensional spaces and the main algorithms for minima seeking. Both exact and approximated algorithms will be studied. The course aims at extending the knowledge acquired in the courses of mathematical analysis and linear algebra by applying it to the optimization problems. At the end of the course the student should be able to interpret a wide class of optimization problems not only from the theoretic point of view, by obtaining the mathematical model of the problem, but also by proposing, for each problem, a suitable solving algorithm.
Acquired skills
The course introduces to the interpretation of a wide class of static and dynamic optimization.
The student will acquire both the ability of formalizing a problem in mathematical terms and the theoretical tools to study the solution and, when possible, to find it.
Lectures and exercises (topics and specific content)
Introduction: introduction to the course; examples of optimization problems (2 hours).
Overview on the optimization problems: classification of the optimization problems; constrained and unconstrained problems; static and dynamic problems; linear, quadratic, geometric and non-linear problems; integer programming; optimal control; discrete-time example; continuous-time example.; stochastic optimization (6 hours).
Existence results: preliminary definitions; local minimum; global minimum; existence results in the constrained and in the unconstrained case, radially unbounded functions; level sets (4 hours).
Convex problems: convex sets; definitions; convex functions; definitions and conditions for the convexity; convex problems (4 hours).
Unconstrained optimization: overview on the unconstrained optimization; descent direction; necessary and sufficient conditions; structure of an optimization algorithm; remarks on the initial point, on the descent direction, an the displacement, on the existence of accumulation points; speed of convergence; conditions on the angle; line search exact and not exact methods; Armijo's method; geometric interpretation, termination theorem and convergence theorem; Goldstein's method; geometric interpretation; Gradient method; particular case of the quadratic functions; conjugate directions method; conjugate gradient method (12 hours).
Constrained optimization: overview; definitions; introduction to the simplex method for the linear programming (4 hours).
Simplex method: base solutions, definitions and interpretation; how to obtain a base solution; justification of the simplex method; diagonalization of the equations of the constraints; geometric interpretation of the base change (6 hours).
Non-linear programming: first order necessary conditions (Karush‐Kuhn‐Tucker); second order sufficient condition for a local minimum; example; non-linear programming; overview; sequential penalty functions method; sequential augmented Lagrangian functions method; exact penalty functions method; exact augmented Lagrangian functions method; recursive quadratic programming (12 hours).
Optimal control: formalization of an optimal control problem; examples of a problem without admissible controls; example of a problem that does not admit solution; example of a problem that admit an infinite number of solutions; existence and uniqueness conditions; Hamilton-Jacobi equation; Bellman equation; Pontryagin maximum principle; definition and interpretation of the co-state; necessary conditions for a solution; meaning of the transversality conditions (10 hours).
References
- L.D. Berkovitz, "Optimal control theory", Springer verlag
- S.S. Rao, "Optimization", Wiley
- L.C. Young, "Optimal Control Theory", AMS Chelsea Publishing
- P. Serafini, "Ottimizzazione", Zanichelli
Type of exam
Oral