Analiză Convexă şi Optimizare – Curriculum

I. PRELIMINARII

Cursul de „Analiza Convexă şi Metode de Optimizare” aprofundează cunoştinţele teoretice şi abilităţile practice obţinute de masteranzi în cadrul cursurilor licenţiale de referinţă. Studiul conceptelor, principiilor şi rezultatelor importante din Analiza Covexă este succedat de analiza, cercetarea şi rezolvarea problemor de optimizare convexă în spaţii finit şi infinit dimensionale prin metode analitice şi numerice. Metodele de optimizare sunt cercetate din perspectiva complexităţii algoritmice şi a celei de calcul, precum şi din cea a elaborării şi testării programelor în sistemul Mathematica în cadrul orelor de laborator. Temele studiate sunt aplicate la analiza, modelarea matematică şi rezolvarea unor probleme generice din domeniul economic-financiar.

II. OBIECTIVELE STANDARD ALE DISCIPLINEI

Susţinând cu succes examenul masteranzii vor fi capabili:

la nivel de cunoaştere şi înţelegere

  • să recunoască obiectele de studiu ale analizei convexe: mulţimi convexe, funcţii convexe, probleme de optimizare convexă;
  • să descrie obiectele de studiu ale disciplinei;
  • să definească şi să explice noţiunile de bază ale analizei convexe;
  • să formuleze principiile şi rezultatele de bază din analiza convexă;
  • să interpreteze problema de extrem ca model matematic al unei probleme reale de luare a deciziei (de alegere a variantei optime);
  • să definească noţiunea de soluţie a problemei de extrem (optim local sau global);
  • să clasifice problemele de extrem necondiţionat sau condiţionat conform proprietăţilor componentelor lor;
  • să formuleze şi sa interpreteze geometric condiţii, principii şi criterii de optimalitate pentru diverse clase de probleme de extrem;
  • să rezolve prin metode analitice probleme de extrem;
  • să concretizeze algoritmic ideile ce stau la baza metodelor numerice de rezolvare pentru clasele principale de probleme de extrem;

la nivel de aplicare

  • să explice esenţa, oportunitatea şi importanţa noţiunilor de bază studiate în cadrul disciplinei;
  • să explice principul dualităţii;
  • să translateze o problemă reală din limbajul uzual al domeniului concret (economie, tehnică,  informatică etc.)  în  limbajul  caracteristic  problemelor  de  extrem  (funcţie obiectiv, restricţii, soluţii admisibile, soluţii optime locale şi globale etc.);
  • să explice ideile ce stau la baza metodelor clasice de rezolvare a problemelor de extrem şi să le implementeze sub formă de algoritmi concreţi;
  • să utilizeze cunoştinţele teoretice la rezolvarea analitică a problemelor simple din compartimentele   de   bază   ale   teoriei   optimizării   matematice:   programare   liniară, programare convexă, programare neliniară;
  • să selecteze o metodă potrivită de rezolvare a unei probleme de extrem local sau global, să argumenteze oportunitatea selectării metodei, să concretizeze metoda numerică sub formă de algoritmi şi programe de calculator;
  • să interpreteze soluţia problemei reale din perspectivele: teoretică şi practică;

la nivel de integrare

  • să cerceteze probleme de extrem ce nu sunt studiate în cadrul cursului, să definească pentru ele noţiunile potrivite de soluţie, să construiască criterii şi principii de optimalitate şi să demonstreze justeţea lor;
  • să rezolve probleme de extrem din domenii concrete ale activităţii umane prin metode analitice şi numerice;
  • să poată transforma o problemă de optimizare neconvexă, în una de optimizare convexă, cănd o asemenea transformare e posibilă;
  • să interpreteze soluţia unei probleme reale de extrem în termenii domeniului practic şi să elaboreze recomandări persoanelor care iau decizii;
  • să adapteze, perfecţioneze şi să dezvolte cunoştinţele şi abilităţile dobândite în cadrul disciplinei date şi în cadrul altor discipline: calcul variaţional şi control optimal, cercetări operaţionale, modelare matematică, econometrie, programare de calculator etc.
  • să-şi perfecţioneze solitar calificarea teoretică şi practică.

III. ADMINISTRAREA MODULULUI / DISCIPLINEI

Codul modulului / disciplinei în planul de învăţământ Anul de studii Semestrul

Numărul de ore

Evaluarea

Responsabil de modul / disciplină

C

S

L

Nr. de credite

Forma de evaluare

F

I

2

30

0

30

7

Examen

V.Ungureanu

IV. TEMATICA ŞI REPARTIZAREA ORIENTATIVĂ A ORELOR

a) Tematica şi repartizarea orientativă a orelor de curs

Nr d/o

Tema

Nr ore

1.

Preliminarii. Mulţimi afine. Mulţimi convexe. Conuri. Proprietăţi.

 

Algebra mulţimilor convexe.Teoreme de separare.

4

2.

Funcţii convexe. Proprietăţi. Operaţii asupra funcţiilor convexe. Criterii de convexitate a funcţiilor diferenţiabile.

 

Proprietăţi extremale ale funcţiilor convexe pe mulţimi convexe. Probleme de optimizare convexă.

4

3.

Diferenţiere. Gradient. Derivată după direcţie. Subgradient. Subdiferenţială. Proprietăţi.

2

4.

Problema de programare convexă. Condiţii de optim.

4

5.

Dualitate. Problema duală Lagrange. Dualitate slabă şi tare. Interpretare geometică. Condiţ
ii de optim. Perturbări şi analiză senzitivă.

2

6.

Metode numerice de minim necondiţionat.

4

7.

Metode numerice de minim condiţionat.

4

8.

Metode numerice de soluţionare a problemelor variaţionale şi de control optimal.

6

Total

30

b) Tematica şi repartizarea orientativă a orelor de laborator

Nr.

 

d/o

Denumirea temelor / activităţilor

 

ore

1. Iniţiere în sistemul Mathematica. Oportunităţi matematice şi grafice. Programare în limbajul Mathematica. Lucrări de laborator.

6

2. Algebra mulţimilor convexe. Funcţii convexe.

4

3. Optimizarea necondiţionată. Metode de soluţionare. Lucrări de laborator.

6

4. Optimizarea condiţionată finitdimensională. Metode de soluţionare. Lucrări de laborator.

6

5. Optimizarea infinitdimensionlă. Metode simbolice şi numerice de soluţionare. Lucrări de laborator.

8

Total

30


V. OBIECTIVE DE REFERINŢĂ ŞI CONŢINUT

Obiective

Conţinuturi

    1. BAZELE ANALIZEI CONVEXE (Geometrie şi Analiză)
  • Muţimi convexe;
  • Combinaţii: liniare, afine, conice, convexe;
  • Mulţimi afine;
  • Mulţimi convexe;
  • Conuri;
  • Mulţimi poliedrale;
  • Lema Farkas;
  • Teorema Minkowski-Weyl;
  • Operaţii asupra mulţimilor convexe;
  • Teoremele: Carathéodory, Radon, Helly;
  • Proprietâţi topologice ale mulţimilor convexe;
  • Învelitori: convexă şi afină;
  • Închidere;
  • Interior;
  • Interior relativ;
  • Teoreme de separare;
  • Dimensiunea mulţimii convexe;
  • Proprietâţi de bază ale mulţimilor convexe;
  • Vârfuri şi faţete;
  • Teorema Krein-Milmann;
  • Funcţii convexe;
  • Funcţii, grafice, epigrafe şi hipografe;
  • Funcţii: convexe, strict convexe, tare convexe, proprii, improprii;
  • Proprietăţi ale funcţiilor convexe;
  • Operaţii asupra funcţiilor convexe;
  • Funcţii poliedrale;
  • Criterii de convexitate;
  • Inegalitatea Jensen;
  • Funcţii conjugate;
  • Funcţii quasiconvexe;
  • Proprietăţi extremale ale funcţiilor convexe pe mulţimi convexe;
  • Calcul convex.
  • Gradient şi derivată după direcţie;
  • Teorema de existenţă a derivatei după direcţie;
  • Subgradient;
  • Subdiferenţială;
  • Inegalitatea Fenchel-Young;
  • Legătura dintre subdiferenţială şi derivata după direcţie;
  • Continuitatea şi monotonia subdiferenţialei.
    2. OPTIMIZARE CONVEXĂ
  • Probleme de optimizare convexă.
  • Probleme de optimizare convexă în formă standard;
  • Restricţii implicite şi explicite;
  • Probleme quasiconvexe;
  • Soluţii locale şi globale;
  • Principiul Lagrange;
  • Criterii de optimalitate;
  • Programare liniară;
  • Programare convexă;
  • Programare liniar-fracţionară;
  • Programare conică;
  • Programare geometrică;
  • Optimizare vectorială şi multicriterială;
  • Optimizare concavă.
    3. DUALITATE
  • Concepte de dualitate (aspecte geometrice şi algebrice);
  • Dualitate slabă şi tare;
  • Funcţii conjugate;
  • Transformarea Legendre-Young-Fenchel;
  • Teorema de dualitate a obiectelor convexe;
  • Dualitatea Lagrange în programarea convexă.
    4. METODE DE REZOLVARE
  • Optimizarea fără restricţii;
  • Metode de tip gradient;
  • Funcţii auto-concordante;
  • Convergenţa metodelor de tip grafient;
  • Metode de tip Newton;
  • Convergenţa metodelor de tip Newton;
  • Optimizarea cu restricţii egalităţi;
  • Principiul Lagrange;
  • Metoda Newton pentru probleme cu restricţii egalităţi;
  • Probleme cu restricţii inegalităţi.
  • Condiţii de tip John şi Karush-Kuhn-Tucker;
  • Metode de punct interior.
    5. CALCUL VARIAŢIONAL ŞI CONTROL OPTIMAL
  • Metode de rezolvare.
  • Metode analitice. Ecuaţia Euler;
  • Principiul Lagrange;
  • Principiul de maxim al lui Pontreaghin;
  • Metode numerice.
    6. APLICAŢII
  • Modelarea problemelor economice, tehnice etc.
  • Problema portofoliului de investiţii;
  • Problema de control optimal cu timp minim;
  • Alte probleme.
VI. LUCRĂRI INDIVIDUALE

Pe durata cursului fiecare masterand va efectua o lucrare  individuală conform Indicaţiilor metodice anexate.

VII. EVALUAREA

1. Evaluări curente şi  periodice

Verificarea cunoştinţelor teoretice se va efectua prin două atestări cu notarea de la 1 la 10.

Verificarea curentă a deprinderilor practice se va face pe parcursul semestrului la orele de laborator cu notarea de la 1 la 10.

Utilizarea cunoştinţelor acumulate se va efectua prin lucrarea individuală cu notarea de la 1 la 10.

2. Evaluarea sumativă finală

Nota finală se constituie din media pentru laborator, două atestări, lucrarea individuală şi nota de examen. La evaluarea finală sunt admişi doar studenţii, care au îndeplinit toate lucrările de laborator şi lucrarea individuală şi au media pozitivă la evaluările curente.

La stabilirea notei finale se iau în considerare

Ponderea în notare, exprimată în % (Total=100%)

Examinarea continuă pe parcursul semestrului

– testarea continuă pe parcursul semestrului, rezultatele activităţii la seminare / lucrări practice / de laborator

cel puţin 60%

25

– testarea periodică prin lucrări de control

25

– activităţi  individuale (teme / referate / eseuri / traduceri / proiecte, studiu de caz,  etc.)

25

– activităţi practice

 

– alte activităţi (precizaţi)

 

Examinarea finală

Rezultatele de la examenul final

cel mult 40%

25


IX. REFERINŢE BIBLIOGRAFICE

  1. Rockafellar R.Tyrrell, Analiza convexă, Bucureşti, Theta, 2002
    (Рокафеллар Р., Выпуклый анализ, М.: Мир, 1973).
  2. Магарил-Ильяев В.М., Тихомиров В.М., Выпуклый анализ и его приложения, М.: Эдиториал УРСС, 2003.
  3. Boyd S., Vandenberghe L.., Convex Optimization, New York: Cambridge University Press, 2008, http://www.stanford.edu/~boyd/cvxbook/
  4. Borwein J., Lewis A., Convex Analysis and Nonlinear Optimization, Theory and Examples, CMS (Canadian Mathematical Society) Books in Mathematics, Volume 3, New York: Springer-Verlag, 2000.
  5. Dattorro J., Convex Optimization & Euclidean Distance Geometry, Mεβoo Publishing, USA, 2005.
  6. Barbu V., Precupanu T., Convexity and Optimization in Banach Spaces, Bucureşti: Editura Academiei, 1985.
  7. Васильев С.П., Численные методы теории экстремальных задач, М.: Наука, 1980.
  8. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации, М.: Наука, 1986.
  9. Карманов В.Г., Математическое программирование, М.: Наука, 1986.
  10. Ногин В.Д., Протодьяков И.О., Евлампиев И.И., Основы теории оптимизации, М.: ВШ, 1986.
  11. Ungureanu V., Programarea matematică, Chişinău: USM, 2001.
  12. Horst R., Tuy H., Global Optimization, Berlin-Heidelberg-New York: Springer-Verlag, 1996.
  13. Antia H.M., Numerical Methods for Scientists and Engineers, Boston-Basel-Berlin: Birkhäuser, 2002.
  14. Тихомиров В. М., Выпуклый анализ, 19 июля 2001 г.
    http://www.mathnet.ru/PresentFiles/106/v106.wmv
    http://www.mathnet.ru/PresentFiles/106/v106.pdf
Anunțuri

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s