
Risorsa bibliografica obbligatoria 

Risorsa bibliografica facoltativa 

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  *  A  ZZZZ  089187  OTTIMIZZAZIONE DISCRETA  051822  NONLINEAR OPTIMIZATION  051823  DISCRETE OPTIMIZATION  Ing Ind  Inf (Mag.)(ord. 270)  MI (474) TELECOMMUNICATION ENGINEERING  INGEGNERIA DELLE TELECOMUNICAZIONI  *  A  ZZZZ  051822  NONLINEAR OPTIMIZATION  Ing Ind  Inf (Mag.)(ord. 270)  MI (481) COMPUTER SCIENCE AND ENGINEERING  INGEGNERIA INFORMATICA  *  A  ZZZZ  051822  NONLINEAR OPTIMIZATION  051823  DISCRETE OPTIMIZATION  Ing Ind  Inf (Mag.)(ord. 270)  MI (487) MATHEMATICAL ENGINEERING  INGEGNERIA MATEMATICA  *  A  ZZZZ  095972  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 decisionmaking problems arising in science, engineering and management. Modeling and applicationrelated 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 stateoftheart 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: 3D 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 BranchandBound method (the general method is a prerequisite).  Cutting plane methods: ChvátalGomory 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, cutset inequalities for TSP), separation problem and lifting procedure.  BranchandCut method.
 Largescale 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.  Onedimensional optimization (Wolfe conditions).  Line search methods: gradient, conjugate directions, Newton and quasiNewton methods (DFP and BFGS).  Subgradient method for convex nonsmooth optimization.
5. Constrained nonlinear optimization
 Examples: designing linear classifiers and training Support Vector Machines (SVMs).  Necessary optimality conditions: constraint qualification, KarushKuhnTucker 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 NPcompleteness 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 13, the exercise sets n. 15 and the computer laboratory sessions n. 13,
 the course "Nonlinear Optimization" (5 cfu) includes Chapters 1, 2, 4 e 5, the exercise sets 1,69 and the computer laboratory sessions 46.
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 halfsemester. 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.

Slides of the lectures, material for the exercise and computer laboratory sessions http://home.deib.polimi.it/amaldi/OPT1718.shtml Note:The material will be made available during the semester
M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: Theory and Algorithms. Third edition, Editore: Wiley Interscience, Anno edizione: 2006
D. Bertsekas, Nonlinear programming, Second edition, Editore: Athena Scientific, Anno edizione: 2003
S. Boyd, L. Vandenberghe, Convex optimization, Editore: Cambridge Univeristy Press, Anno edizione: 2004 http://www.stanford.edu/~boyd/cvxbook/
M. Conforti, G. Cornuejols, G. Zambelli, Integer Programming, Editore: Springer, Anno edizione: 2014
D. G. Luenberger, Y. Ye, Linear and nonlinear programming. Third edition, Editore: Springer Science+Business Media, Anno edizione: 2008
M. Minoux, Mathematical programming: Theory and algorithms, Editore: John Wiley and Sons, Anno edizione: 1986
J. Nocedal, S. Wright, Numerical optimization, First edition, Editore: Springer, Anno edizione: 1999
A. Ruszczynski, Nonlinear optimization, Editore: Princeton University Press, Anno edizione: 2006
L. A. Wolsey, Integer Programming, Editore: J. Wiley & Sons, Anno edizione: 1998

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

