logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2017/2018
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 095972 - OPTIMIZATION
Docente Amaldi Edoardo
Cfu 8.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (473) AUTOMATION AND CONTROL ENGINEERING - INGEGNERIA DELL'AUTOMAZIONE*AZZZZ089187 - OTTIMIZZAZIONE DISCRETA
051822 - NONLINEAR OPTIMIZATION
051823 - DISCRETE OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ051822 - NONLINEAR OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ051822 - NONLINEAR OPTIMIZATION
051823 - DISCRETE OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (487) MATHEMATICAL ENGINEERING - INGEGNERIA MATEMATICA*AZZZZ095972 - OPTIMIZATION

Programma dettagliato e risultati di apprendimento attesi

Aim

 

The purpose of the course is to present the main concepts and methods of discrete optimization and nonlinear (continuous) optimization, which allow to tackle a wide variety of decision-making problems arising in science, engineering and management. Modeling and application-related aspects are also covered. Optimization problems from, among others, data mining, economics, energy, healthcare, machine learning, logistics, production, telecommunications and transportation, are discussed.

After some fundamentals of convex analysis, the course is subdivided into two parts. The first one deals with integer linear programming, that is, optimization problems with a linear objective function and linear constraints where some (or all) variables are restricted to take discrete (integer) values. The second part is devoted to nonlinear optimization with continuous variables.

During the computer laboratory sessions, the students will learn how to use AMPL modeling language (with state-of-the-art solvers like CPLEX) and MATLAB to build optimization models and solve (mixed) integer linear and nonlinear optimization problems.

 

Detailed program

 

1. Introduction

 

Discrete (integer) and nonlinear (continuous) optimization models, local and global optima. Three examples: 3-D image reconstruction (computed tomography), location and transportation problem, winner determination in combinatorial auctions. Some fields of application.

2. Fundamentals of convex analysis

 

Separating/supporting hyperplanes, main consequences (Farkas Lemma), characterization of convex functions, subgradients.

3. Discrete optimization


- Integer linear programming (ILP) problems and modeling techniques. Examples: assignment, matching, knapsack, cutting stock, covering, packing, partitionning, location, routing, network flows, scheduling,...
- Valid inequalities. Alternative, strong and ideal formulations.
- "Easy" ILP problems and totally unimodular matrices.
- Linear, surrogate and combinatorial relaxations.
- Lagrangian relaxation: Lagrangian subproblem, dual problem, subgradient method, choice of Lagrangian dual.  Examples: symmetric travelling salesman and generalized assignment problems.
- Branching and bounding strategies for the Branch-and-Bound method (the general method is a prerequisite).
- Cutting plane methods: Chvátal-Gomory procedure, fractional and mixed integer Gomory cuts, facets of polyhedra, strong valid inequalities for structured ILP problems (cover inequalities for the binary knapsack problem, clique and odd cycle inequalities for the independent set problem, cut-set inequalities for TSP), separation problem and lifting procedure.
- Branch-and-Cut method.

- Large-scale problems: (delayed) column generation and Benders' decomposition.
- Heuristics: greedy, local search and Tabu search.

4. Unconstrained nonlinear optimization


- Examples: statistical estimation, traning artificial neural networks.

- Optimality conditions based on feasible directions.
- Line search methods and convergence rate.
- One-dimensional optimization (Wolfe conditions).
- Line search methods: gradient, conjugate directions, Newton and quasi-Newton methods (DFP and BFGS).
- Subgradient method for convex non-smooth optimization.

5. Constrained nonlinear optimization

 

- Examples: designing linear classifiers and training Support Vector Machines (SVMs).
- Necessary optimality conditions: constraint qualification, Karush-Kuhn-Tucker conditions.
- Sufficient optimality conditions: Lagrange function, saddle points, weak and strong duality.
- Quadratic programming: examples from portfolio optimization and machine learning, null space method for equality constrained problems, active set methods for problems with also inequality constraints.
- Penalty methods and augmented Lagrangian methods.

- Barrier method and an application to linear programming (interior point method).

- Fundamentals of quadratic sequential programming.

 

Prerequisites

 

The prerequisites for the course include linear programming (basic feasible solutions, simplex algorithm, duality), graph optimization (minimum spanning tree, shortest paths, maximum flow), Branch and Bound method for ILP and combinatorial optimization problems, and the basics of NP-completeness theory. These topics are covered in the course "Foundations of Operations Research".

 

Organization

 

Besides the lectures, the course includes 9 sessions devoted to exercises (90 minutes each) and 6 sessions devoted to computer laboratory work (90 minutes each).

Every week the students will be assigned a set of exercises to be solved before the next exercise session.
 

Joint courses: "Discrete Optimization" and "Nonlinear Optimization"

 

The courses "Discrete Optimization" and "Nonlinear Optimization" (5 cfu) correpond to two overlapping parts of the course "Optimization" (8 cfu).

While "Optimization" includes all the material presented during the lectures, the exercise and computer laboratory sessions,

- the course "Discrete Optimization" (5 cfu) includes Chapters 1-3, the exercise sets n. 1-5 and the computer laboratory sessions n. 1-3,

- the course "Nonlinear Optimization" (5 cfu) includes Chapters 1, 2, 4 e 5, the exercise sets 1,6-9 and the computer laboratory sessions 4-6.

The students enrolled in both courses "Discrete Optimization" (5 cfu) and "Nonlinear Optimization" (5 cfu) must take the written exam of "Optimization" (8 cfu) and conduct a project or an individual study (2 cfu) to be defined with the instructor.

 


Note Sulla Modalità di valutazione

A written exam covering all the material presented during the lectures, the sessions devoted to exercises and the sessions devoted to computer laboratory work.

Two computer laboratory tests scheduled at the end of each half-semester. The first computer laboratory test deals with Discrete Optimization (using AMPL and CPLEX) and the second one with Nonlinear Optimization (using Matlab).

The final grade is determined by adding to the grade of the written exam the points obtained in the two computer laboratory tests.

 


Bibliografia
Risorsa bibliografica obbligatoriaSlides of the lectures, material for the exercise and computer laboratory sessions http://home.deib.polimi.it/amaldi/OPT-17-18.shtml
Note:

The material will be made available during the semester

Risorsa bibliografica facoltativaM. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: Theory and Algorithms. Third edition, Editore: Wiley Interscience, Anno edizione: 2006
Risorsa bibliografica facoltativaD. Bertsekas, Nonlinear programming,  Second edition, Editore: Athena Scientific, Anno edizione: 2003
Risorsa bibliografica facoltativaS. Boyd, L. Vandenberghe, Convex optimization, Editore: Cambridge Univeristy Press, Anno edizione: 2004 http://www.stanford.edu/~boyd/cvxbook/
Risorsa bibliografica facoltativaM. Conforti, G. Cornuejols, G. Zambelli, Integer Programming, Editore: Springer, Anno edizione: 2014
Risorsa bibliografica facoltativaD. G. Luenberger, Y. Ye, Linear and nonlinear programming. Third edition, Editore: Springer Science+Business Media, Anno edizione: 2008
Risorsa bibliografica facoltativaM. Minoux, Mathematical programming: Theory and algorithms, Editore: John Wiley and Sons, Anno edizione: 1986
Risorsa bibliografica facoltativaJ. Nocedal, S. Wright, Numerical optimization, First edition, Editore: Springer, Anno edizione: 1999
Risorsa bibliografica facoltativaA. Ruszczynski, Nonlinear optimization, Editore: Princeton University Press, Anno edizione: 2006
Risorsa bibliografica facoltativaL. A. Wolsey, Integer Programming, Editore: J. Wiley & Sons, Anno edizione: 1998

Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
54.0
esercitazione
30.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.2 / 1.6.2
Area Servizi ICT
04/06/2020