NUMERICAL OPTIMIZATION METHODS
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2015/2016
- Teacher
- MICHAEL MATTHIAS HERTY
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- MAT/08
Training objectives
- The course discusses modern methods for nonlinear optimization. It provides the theoretical background and introduces the currently used methods in applied mathematics. We analyse different methods regarding convergence rate. Properties like positive definiteness and approximation theory will be discussed.
The main knowledge acquired will be:
• Karush-Kuhn-Tucker system;
• Constraint qualification knowledge;
• understanding of concepts like convergence rates;
• main methods for unconstrained optimization;
• methods for quadratic programming;
• sequential quadratic programming methods;
• interior point methods.
The main skills (that are the ability to apply knowledge acquired) will be :
• identify the modern method most suitable for the application;
• identify requirements and convergence rate for the methods;
• understand the importance of Karush-Kuhn-Tucker systems;
• identify necessary conditions for the methods;
• identify requirements for sequential quadratic programming methods;
• identify requirements for interior points methods;
• analyze optimization problem and understand basic applications.
The knowledge and skills acquired can be used in all further classes on applied mathematics. Prerequisites
- To follow the course a full knowledge of the basics of linear algebra and calculus are necessary.
Course programme
- The course includes 42 hours. By treating basic topics, preparatory for other courses, there are no lab applications.
Introduction (9 hours)
Differentiability – Necessary conditions in the case of no constraints – First-order and second-order conditions – Geometric interpretation of constraints – Karush-Kuhn-Tucker Theorem – Constraint qualifications (MFCQ,LICQ,Adabie) – Interpretation of constraint qualification – Application of conditions to examples – Linear and quadratic case
Methods for unconstrained minimization (4 hours)
Newton-Method – Gradient descent – Line-Search – Armijo-Rule – Paul-Wolffe-Rule – BFGS – DFP – SR1 method – Geometrical interpretation of methods – Necessary conditions for convergence – Convergence results and rates
Qudratic programs (5 hours)
KKT conditions – Linear case – Quadratic case – Primal Projection Method – Properties and convergence rate – Infeasible domains – Primal-Dual Method – Iterative methods by projection – Multiplier methods
Sequential Quadratic Programming (12 hours)
Lagrange-Newton Method – Local convergence – Second-order information – BFGS modification – Interpretation as Primal-Dual method – Extension to inequality constraints – Infeasible SQP methods – Adaptive methods – Globalization – Exact Penalty Function – L1 Function – Descent directions and properties – Other penality functions – Augemented Lagrangian method
Trust Region Method (6 hours)
Definitions – Practical methods – Trust-Region Radius – Cauchy Point – Convergence properties – Relation to SQP – Update Formulas – Globalization techniques – Cubic regularization – Maratos Effect – Convergence Proof
Interior Point Methods (12 hours)
Definition – Logarithmic Barrier Function – Perturbed KKT system – Central Path – Properties of central path – Update for Multipliers – Globalization techniques – Merit function – Extension to equalities – Perturbed extended KKT system – Relation to Trust Region methods – Practical problems – Implementation details Didactic methods
- The course is organized as follows :
• lectures with exercises on all topics of the course (42 hours) Learning assessment procedures
- Oral exam.
The review aims to assess the student's ability in linking the discussed optimization topics and methods. Testing the ability to identify the relevant methods and applications. Testing the understanding of the basic mechanisms of the methods.
The test covers all the topics of the course .
The student will be assigned three topics and, before exposing them, he/she can organize the response (usually from 30 ' to 60 ', depending on the student’s needs) .
Given the complexity of general optimization problems the student is not required to know all details. A basic understanding of the mechanism of the methods as well as the theoretical background is however required. The goal of the study, in fact, is not to memorize methods and problems, probably, in a few years will no longer be used, but to understand the theoretical reasons that led to the development of certain methods.
The preparation of the student will be evaluated, therefore, on the ability to recall the mechanism and ideas of the methods and to explain the reasons that led to specific and methods and to identify possible limitations . Reference texts
- Teacher’s handouts.
Specific topics can be further developed on the following texts:
Numerical Optimization by J. Nocedal and S. Wright, Springer, 2006
Numerical Methods for Unconstrained Optimization and Nonlinear Equations by J.E. Dennis and R.B. Schnabel
