Servizi per la didattica
PORTALE DELLA DIDATTICA

Convex optimization and engineering applications

01OUWQW, 01OUWNG, 01OUWOQ, 01OUWOV

A.A. 2018/19

Course Language

English

Course degree

Master of science-level of the Bologna process in Mechatronic Engineering - Torino
Master of science-level of the Bologna process in Mathematical Engineering - Torino
Master of science-level of the Bologna process in Electronic Engineering - Torino
Master of science-level of the Bologna process in Computer Engineering - Torino

Course structure
Teaching Hours
Lezioni 40
Esercitazioni in aula 20
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Calafiore Giuseppe Carlo Professore Ordinario ING-INF/04 40 20 0 0 8
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
ING-INF/04 6 D - A scelta dello studente A scelta dello studente
2018/19
The course is taught in English. Il corso fornisce agli studenti la capacità di riconoscere e risolvere problemi di ottimizzazione convessa, che sono diventati pervasivi nelle moderne applicazioni ingegneristiche. Argomenti trattati sono: preliminari di analisi convessa, insiemi e funzioni convesse, problemi di ottimizzazione; minimi quadrati, programmazione lineare e quadratica; programmazione conica e semidefinita; problemi minimax, problemi geometrici (estremal volume, linear discrimination, support vectors machines). Condizioni di ottimalità, dualità, teorema delle alternative. Metodi di soluzione interior-point. Applicazioni nell’ambito del signal processing, dei sistemi dinamici e del controllo, del progetto di circuiti digitali e analogici, del progetto di filtri, della geometria computazionale, della statistica e della meccanica strutturale.
Optimization is a technology that can be used to devise effective decisions or predictions in a variety of contexts, ranging from production planning, to engineering design, finance, machine learning and data science, to mention just a few. In simplified terms, the process for reaching a decision starts with a phase of construction of a suitable mathematical model for a concrete problem, followed by a phase where the model is solved by means of suitable numerical algorithms. An optimization model typically requires the specification of a quantitative objective criterion of goodness for our decision, which we wish to maximize (or, alternatively, a criterion of cost, which we wish to minimize), as well as the specification of constraints, representing the physical limits of our decision actions, budgets on resources, design requirements than need be met, etc. An optimal design is one who gives the best possible objective value, while satisfying all problem constraints. While a generic optimization approach typically leads to computational problems that are very hard to solve in practice, convex problems, which are the core of this course, possess special properties that make them amenable to very efficient numerical solution techniques. This course therefore concentrates on recognizing, modeling and solving convex optimization problems that arise in several scientific contexts (engineering, finance, control, data science, etc.), and in showing the relevance of these methodologies in practical applications.
Capacità di riconoscere e modellare problemi ingegneristici sotto forma di programmi convessi, conoscere la teoria di base di tali problemi ed acquisire l’abilità a risolverli sia sviluppando algoritmi ad-hoc, sia utilizzando solver e ambienti software esistenti.
To give students the tools and training to recognize convex optimization problems that arise in engineering and other branches of science; to present the basic theory of such problems, concentrating on results that are useful in computation; to give students an understanding of how such problems are solved, and some experience in solving them.
Buona conoscenza di algebra lineare e geometria; basi di analisi matematica e probabilità. Conoscenze introduttive di calcolo numerico, ricerca operativa, teoria dei sistemi e di altre materie applicative sono utili ma non indispensabili per la fruizione del corso.
Good knowledge of linear algebra, geometry, analysis and some exposure to probability. Exposure to numerical computing, optimization, systems and control theory, and application fields is helpful but not strictly required.
Programma Systems of linear equations, Least Squares (LS), Linear Programming (LP), Ell-one norm optimization, Chebychev approximation. Introduction, convex sets and convex functions. Optimization problems in standard form, Introduzione, insiemi e funzioni convesse, proprietà. Ellissoidi, norm-balls, poliedri, etc. Problemi di ottimo in forma standard, criteri di ottimalità. Sistemi di equazioni lineari, minimi quadrati (LS), Programmazione Lineare (LP), problemi di ottimizzazione in norma \ell_1, approssimazione di Chebichev. Esempi applicativi: generazione di forza-coppia tramite thrusters, illuminazione uniforme di superfici a patch, etc. Programmazione Quadratica (QP), Ottimizzazione su coni del secondo ordine (SOCP). Esempi e applicazioni: progetto di filtri a risposta all'impulso finita (FIR), antenna array design, beamforming con minimizzazione livelli sidelobe. Linear Matrix Inequalities (LMI) e programmazione semidefinita (SDP). Geometric programming (GP). Introduzione agli ambienti di ottimizzazione convessa CVX e/o YALMIP. Applicazioni: data-fitting, stima e approssimazione, dimensionamento di strutture meccaniche a truss, transistor sizing, minimi quadrati con dati incerti (Robust Least Squares), Bounded-Real Lemma, passività e applicazioni nella teoria dei circuiti. Problemi geometrici: contenimento di poliedri, classificazione, ellissoidi di Lowner-John, linear discrimination, support vector machines. Metodi e algoritmi interior-point. Focus seminariali (mutuamente esclusivi, a rotazione negli anni): - LMI nella teoria dei sistemi e del controllo - Sparse optimization e compressed sensing - Ottimizzazione convessa in finanza - Ottimizzazione convessa e geometria algebrica, positività di polinomi - Ottimizzazione distribuita
Introduction, convex sets and convex functions. Optimization problems in standard form, optimality criteria. Systems of linear equations, Least Squares (LS), Linear Programming (LP), Ell-one norm optimization, Chebychev approximation. Application examples: generation of force/torque via thrusters, uniform illumination of patch surfaces, etc. Quadratic Programming (QP) and Second Order Cone Programming (SOCP). Application examples (e.g. FIR filter design, antenna array design, sidelobe level minimization, etc.). Linear Matrix Inequalities (LMI) and semidefinite programming (SDP). Geometric programming (GP). Software tools (CVX and/or YALMIP). Applications: data-fitting, approximation and estimation, uncertain and robust Least Squares, portfolio optimization. Geometrical problems: containment of poyhedra, classification, Lowner-John ellipsoids, linear discrimination, support vector machines. Focus topics (mutually exclusive, to be offered alternatively over years): - LMIs in systems and control theory. - Sparse optimization and compressed sensing. - Convex optimization in Finance. - Convex optimization in algebraic geometry, global polynominal positivity (positivstellensaatz). - Network optimization, distributed optimization.
Il corso si articola il circa 30 ore di lezione in aula e 30 ore di esercitazioni in laboratorio informatico.
The course is organized in a series of lectures (about 1/3 of the course) and computer lab exercises and practice sessions (about 2/3 of the course).
1. S. Boyd and L. Vandenberghe; Convex Optimization, Cambridge Univ. Press, 2004. 2. L. El Ghaoui, G. Calafiore; Optimization Models, Cambridge Univ. Press (in preparation) (draft to be made available to students)
G.C. Calafiore and L. El Ghaoui, Optimization Models, Cambridge Univ. Press, 2014. S. Boyd and L. Vandenberghe; Convex Optimization, Cambridge Univ. Press, 2004.
Modalità di esame: prova scritta; progetto di gruppo;
Scritto
Exam: written test; group project;
The final exam consists in a written test, which will contain a mixture of methodological questions and numerical exercises (to be executed with pen and paper, use of a calculator is allowed) and which will take the form of multiple-choice questionar. For students who fully participate in the lab sessions an optional alternate form of final exam is offered, which consists of a written report on an applicative project assigned by the instructor. In this case, the students can work on the project in groups of at most five persons; a reasonable time will be allowed for completing the report (typically, one week), and each group is requested to give a public presentation of their results in front of the class. The evaluation and corresponding score will be based on the results of lab assignments and factors including technical correctness of the report, organization of the presentation, and autonomy in the report development. No oral exams are foreseen, besides the oral presentation of the report.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il