Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
Předmět volně navazuje na předmět Základy Nelineární Optimalizace. V tomto předmětu budeme rozebírat
jednotlivé algoritmy na řešení různých typů typicky konvexních úloh. Kromě základních vlastností metod týkajících
se jejich struktury a konvergence předmět popisuje přehled metod využívaných pro úlohy bez omezení a úlohy s
omezeními. Kromě samotných metod nás často bude zajímat vhodnost metody pro danou třídu problémů,
případně její konvergence.
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
The course follows the course Fundamentals of Nonlinear Optimization organized in preceding term. In this course
we will focus on individual algorithms for solving different types of typically convex optimization problems. In
addition to the basic features of methods relating to their structure and convergence, the course provides an
overview of the methods used for problems without constraints as well as problems with constraints. Together with
description of methods themselves, we will often be interested in the suitability of the method for a given class of
problems or its convergence.
Podmínky zakončení předmětu
Poslední úprava: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D. (24.05.2019)
Pro zápočet je potřeba získat dostatečný počet bodů z projektu vypracovávaného během semestru a konzultovaného na cvičeních.
Účast na cvičení není povinná.
Bližší informace k možným projektům jsou k dispozici na stránce:
https://iuuk.mff.cuni.cz/~hartman/teach/ANO/
Přístup na stránky může obsahat i individuální informace a je chráněn heslem. Studentům je přístup poskytnut na začátku semestru.
Literatura -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, 2009
A. Ruszczynski: Nonlinear Optimization. Princeton University Press, 2006.
L. Lukšan: Numerické optimalizační metody - nepodmíněná optimalizace. Technical Report n. 1152, UIVT AVČR, 2011.
M. Maňas: Optimalizační metody. STNL, 1979.
J. Nocedal, S. J. Wright: Numerical Optimization. 2nd edition, Springer, 2006.
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, 2009
A. Ruszczynski: Nonlinear Optimization. Princeton University Press, 2006.
L. Lukšan: Numerické optimalizační metody - nepodmíněná optimalizace. Technical Report n. 1152, UIVT AVČR, 2011.
M. Maňas: Optimalizační metody. STNL, 1979.
J. Nocedal, S. J. Wright: Numerical Optimization. 2nd edition, Springer, 2006.
Požadavky ke zkoušce
Poslední úprava: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D. (22.09.2020)
Zkouška je ústní a požadavky odpovídají sylabu předmětu v rozsahu, který byl presentován na přednášce. Zkouška může mít kontaktní nebo distanční formu.
Bližší informace k přednáškám i spolu s materiály k probíraným tématům jsou k dispozici na stránce:
https://iuuk.mff.cuni.cz/~hartman/teach/ANO/
Přístup na stránky může obsahat i individuální informace a je chráněn heslem. Studentům je přístup poskytnut na začátku semestru.
Sylabus -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
1) Úvod do metod optimalizace bez vazeb … obecná optimalizační metoda, řády metod, základní klasifikace metod
2) Konvergence metod … Q-kovergence a její důležité třídy - lineární, superlineární a kvadratická, R-konvergence a souvislosti různých definicí konvergencí
3) Základní gradientní metody … Metody spádových směrů, volba kroku - linesearch, metody volby kroku - Armijo, Goldstein, Wolfe, existence intervalů pro Wolfeho podmínku
4) Metody spádových směrů a Newtonovské metody … metody spádových směrů a Newtonovské metody, Zoutendijkova věta a její souvislost s konvergencí, podmínka silné konvexity a Lipschitzovsky spojitých gradientů.
5) Trust-region methody … Různé strategie stanovenı́ kroku a směru trust-region metod a Cauchyho bod, popis dogleg metody, Sorensenovo lemma
6) Kvazi-newtonovské metody … princip kvazinewtonovstkých metod, aproximace Hesiánu, konvergence metod (Dennis-Moré), metody DFP, BFGS, L-BFGS a Broydenovy metody.
7) Metody konjugovaných směrů … metody konjugovaných směrů, volba směru a konvergence pro specifické systémy, předpodmiňování a PCG metoda, metoda Fletchera a Reevese a metoda Polak a Ribiere.
8) Základní optimalizace s vazbami … základní úloha podmíněné optimalizace, KKT matice a její využití pro konstrukci metod - aktivní množina, Newtonova metoda.
9) Bariérové metody … bariérové metody, princip metody vnitřních bodů pro nelineární úlohy jako rozšíření metod lineárních, související konvergence metod.
10) Penalizačnı́ metody … princip penalizační metody a jejich konvergence.
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (03.05.2018)
1) Introduction to optimization methods without constraints ... general optimization method, order of methods, basic classification of methods
2) Convergence of methods ... Q-covergence and corresponding important classes of algorithms - linear, superlinear and quadratic, R-convergence and context of different definitions of convergence
4) Gradient Methods and Newtonian Methods ... gradient methods and Newtonian Methods, Zoutendijk's theorem and its relation to convergence, the condition of strong convexity and the Lipschitz continuity of gradients.
5) Trust-region method ... various strategies to select step and direction of trust-region methods, Cauchy point, description of dogleg method, Sorensen lemma.
6) Quasi-Newtonian methods ... the principle of quasinewton methods, Hessian approximation, convergence of methods (Dennis-Moré), DFP, BFGS, L-BFGS and Broyden methods.
7) Conjugate gradient methods ... conjugate gradient methods, determination of direction, convergence for specific systems, preconditioning and PCG Methods, methods of Fletcher and Reeves Method and methods of Polak and Ribier.
8) Basic optimization with constraints ... basic problem of conditional optimization, KKT matrix and its use for the construction of constraint methods - active set, Newton method.
9) Barrier methods ... the principle of barrier methods, interior-point method for nonlinear tasks as an extension of the methods of linear, related method convergence.
10) Penal and barrier methods ... penalizing methods, barrier methods and their convergence
