Nemlineáris optimalizálás

Dr. Házy, Attila

Új Széchenyi Terv logó.

Miskolci Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Kivonat

Kivonat

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Kósa Péter

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

1. Bevezetés
2. Jelölések és alapfogalmak
2.1. 2.1. Konvexitás, kvázikonvexitás
2.2. 2.2. Definitség, feltételes definitéség
2.3. 2.3. Differenciálhatóság
2.4. 2.4. Karakterizációs tételek
2.5. 2.5. Farkas lemma
2.6. 2.6. Dualitás
2.7. 2.7. Függvények szélsőértékei
2.8. 2.8. Matematikai programozási (MP) feladat
2.9. 2.9. Lineáris programozási (LP) feladat
2.10. 2.10. Gráfelméleti fogalmak, jelölések
2.11. 2.11. Gráfok ábrázolási módjai
2.11.1. 2.11.1. Szomszédsági listás
2.11.2. 2.11.2. Szomszédsági mátrixos
3. Általános nemlineáris optimalizálási feladat
3.1. 3.1. Nemlineáris optimalizálási feladatok osztályozása
3.2. 3.2. Kvadratikus függvények és szélsőértékeik
3.3. 3.3. Egyenlőségi feltételek
3.4. 3.4. Egyenlőtlenségi feltételek
3.5. 3.5. A konvex optimalizálási feladat
3.6. 3.6. Duális programozási feladatok
4. Minimumkereső eljárások
4.1. 4.1. Egyváltozós függvények kereső eljárásai
4.1.1. 4.1.1. Általános minimum kereső algoritmus
4.1.2. 4.1.2. Dichotomous keresés
4.1.3. 4.1.3. Aranymetszéses keresés
4.1.4. 4.1.4. Fibonacci keresés
4.1.5. 4.1.5. Parabola kereső eljárás
4.1.6. 4.1.6. Newton módszer
4.2. 4.2. Többváltozós függvények kereső eljárásai
4.2.1. 4.2.1. A Newton-módszer
4.2.2. 4.2.2. Módosított Newton-módszer
4.2.3. 4.2.3. A Gill-Murray algoritmus
4.2.4. 4.2.4. A Levenberg-Marquardt módszer
4.2.5. 4.2.5. Trust region módszerek
4.2.6. 4.2.6. Kvázi-Newton módszerek
4.2.7. 4.2.7. Broyden módszer
4.2.8. 4.2.8. BFGS (Broyden-Fletcher-Goldfarb-Shanno) eljárás
4.2.9. 4.2.9. A vonalmenti minimalizálás algoritmusa
4.2.10. 4.2.10. Armijo-Goldstein feltételek
4.2.11. 4.2.11. Szögfeltétel
4.2.12. 4.2.12. Iránykeresési módszerek
4.2.13. 4.2.13. Gradiens módszer (Cauchy módszer, 1847)
4.2.14. 4.2.14. Konjugált gradiens módszer (Fletcher, Reeves)
4.2.15. 4.2.15. Newton-módszer vonalmenti minimalizálással
4.2.16. 4.2.16. Módositott Newton-módszer vonalmenti minimalizálással
4.2.17. 4.2.17. DFP (Davidon-Fletcher-Powell) eljárás
4.2.18. 4.2.18. Hooke-Jeeves módszer
4.3. 4.3. A büntetőfüggvény módszerek
5. A játékelmélet elemei
5.1. 5.1. Bimátrix játékok
5.2. 5.2. Mátrixjátékok
5.3. 5.3. A játék alsó és felső értéke, a ”minimax” elv
5.4. 5.4. Mátrixjátékok kevert bővítése
5.4.1. 5.4.1. A mátrixjáték és a lineáris programozás kapcsolata
6. Egészértékű lineáris programozási (ILP) feladat
6.1. 6.1. Egészértékű optimalizálási modellek
6.1.1. 6.1.1. Befektetési modellek
6.1.2. 6.1.2. Transzformálás 0-1 programozási feladattá
6.1.3. 6.1.3. Hátizsák feladat
6.1.4. 6.1.4. Halmazlefedési, halmazfelbontási és halmazkitöltési feladatok
6.2. 6.2. Integer lineáris programozási feladatok megoldási módszerei
6.2.1. 6.2.1. Integer és folytonos lineáris programozás kapcsolata
6.2.2. 6.2.2. A korlátozás és szétválasztás módszer (Branch and Bound)
6.2.3. 6.2.3. Vágási módszerek
7. Gráfelméleti algoritmusok
7.1. 7.1. A szélességi keresés
7.2. 7.2. A mélységi keresés
7.3. 7.3. Minimális feszítőfa
7.3.1. 7.3.1. Kruskal-algoritmus
7.3.2. 7.3.2. Prim-algoritmus
7.4. 7.4. Legrövidebb utak
7.5. 7.5. Adott csúcsból induló legrövidebb utak
7.5.1. 7.5.1. Bellman-Ford algoritmus
7.5.2. 7.5.2. Dijkstra algoritmusa
7.6. 7.6. Legrövidebb utak minden csúcspárra
7.6.1. 7.6.1. A Floyd-Warshall-algoritmus
8. Feladatok
Irodalomjegyzék