Home  
  Teaching  
  Research  
  Misc  
Milan Hladík
Teaching

Ročníkové projekty a bakalářské práce

Projekty a práce tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. U projektů preferuji pokračování do bakalářské práce.

Některá témata jsou v SISu. Další navrhovaná témata jsou dole (můžete přijít i s vlastním tématem), jedná se zejména o problémy z intervalového počítání, proto jsem sepsal pár základních informací a odkazů o intervalovém počítání. Může se také hodit pár užitečných odkazů.

  • Utažení pivota pro parametrické lineární soustavy rovnic [zabráno]
  • Utažení pivota je způsob jak zefektivnit (z hlediska výsledné obálky množiny řešení) metody na řešení soustav intervalových lineárních rovnic, a to konkrétně Gaussovy eliminace pro obecnou soustavu a Choleského rozklad pro soustavu s positivně definitní maticí. Cílem projektu je rozšířit tento způsob na intervalové soustavy s lineárními závislostmi. Součástí by mělo být i numerické porovnání s jinými metodami řešení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff. Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations. Comput. 94(2-4):97-107, 2012.
    2. J. Garloff. Interval Gaussian elimination with pivot tightening. SIAM J. Matrix Anal. Appl. 30(4):1761-1772, 2009.
    3. M. Hladík. Enclosures for the solution set of parametric interval linear systems. Int. J. Appl. Math. Comput. Sci., 22(3):561–574, 2012.

  • Obraz boxu při bilineárním a kvadratickém zobrazení
  • Obraz intervalového boxu při bilineárním a kvadratickém zobrazení se dá snadno odhadnout vyhodnocením intervalovou aritmetikou, ale výsledek může být značně nadhodnocen. Cílem této práce je vylepšit tyto základní odhady použitím algebraických maticových dekompozic, linearizací používaných v optimalizaci, heuristik a jiných technik. Součástí by měla být implementace a numerické porovnání metod. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. C. A. Floudas. Deterministic Global Optimization. Theory, Methods and Applications, Kluwer, 2000.
    2. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.
    3. S. M. Rump. Verification methods: Rigorous results using floating-point arithmetic. Acta Numer., 19:287-­449, 2010.

  • Grafické znázornění komplexních vlastních čísel intervalové matice
  • Problém spočívá ve vykreslení množiny všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Tato množina není jednoduše popsatelná, a proto se musí aproximovat. Například metody založené na principu branch & bound aproximují množinu s libovolnou přesností. Cílem projektu je navrhnout a implementovat metodu, která vykreslí tyto množiny s předem danou přesností. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Garajová: Intervalový solver nelineárních podmínek, 2014.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J. Rohn. Checking properties of interval matrices. Technical Report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, 1996.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Lokalizace vlastních čísel intervalových matic
  • Zde nás zajímá množina všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Cílem práce je zapouzdřit tuto množinu pomocí jednoduchých odhadů založených na Gerschgorinových discích, Cassiniho oválech a dalších pokročilých technik. Konkrétně, jedná se o adaptaci výše zmíněných metod na intervalové matice, porovnání metod a jejich implementace. Programovací část (jazyk Matlab/Octave + Intlab) zahrnuje i vizualizaci odhadů.

    Odkazy:

    1. H.-B. Li, T.-Z. Huang, and H. Li On some subclasses of P-matrices. Numer. Linear Algebra Appl., 14: 391–405, 2007.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J.M. Peña. On an alternative to Gerschgorin circles and ovals of Cassini. Numer. Math., 95(2): 337-­345 , 2003.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • AE řešení a řešitelnost intervalových lineárních rovnic s absolutními hodnotami
  • Soustava intervalových lineárních rovnic s absolutními hodnotami je soustava ve tvaru Ax+B|x|=b, kde koeficienty matic A, B a vektoru b nejsou známé přesně, ale mohou nabývat hodnot v daných intervalech. Reálný případ je studován a dobře známy jsou obyčejné intervalové lineární rovnice, ale kombinace obojího je téměř neprostudovaná. Silné resp. slabé řešení je řešení, které splňuje všechny resp. aspoň jednu realizaci hodnot z intervalů. Podobně silná resp. slabá řešitelnost znamená, že soustava je řešitelná pro všechny resp. aspoň jednu realizaci hodnot z intervalů. AE řešení a řešitelnost pak umožňuje použití obou kvantifikátorů z definici. Cílem projetu je rozšířit charakterizaci a různé postačující/nutné podmínky na silnou, slabou a AE řešitelnost a řešení. Výsledné podmínky a metody by se pak implementovaly v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík. AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl., 465(0):221-238, 2015.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. M. Hladı́k and L. Ptáčková. Absolute value equations with interval uncertainty. Submitted, 2023.
    4. M. Hladík and M. Zamani. Absolute Value Programming. In P.M. Pardalos and O.A. Prokopyev, Encyclopedia of Optimization, third edition, Springer, Cham, 2023.

  • Vizualizace množiny řešení intervalových soustav
  • Pro soustavy lineárních rovnic a nerovnic s intervalovými koeficienty neexistuje jednoznačný koncept pojmu řešení, ale existuje několik možností, jak řešení definovat. Ve většině případů je množina řešení nekonvexní polyedrická množina. Cílem práce by bylo pro různé typy soustav a pro různé typy řešení graficky znázornit množinu řešení a její hlavní charakteristiky. Zatím se umí znázorňovat jen tzv. slabá množina řešení, viz např.: příklad 3D soustavy v Intlabu.

    Odkazy:

    1. M. Hladík. AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl., 465(0):221-238, 2015.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
    4. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.
    5. I. Skalna and M. Hladík. Direct and iterative methods for interval parametric algebraic systems producing parametric solutions. Numer. Linear Algebra Appl., 26(3):e2229:1-e2229:24, 2019.

  • Plná sloupcová hodnost intervalové matice
  • Regularita intervalové matice je celkem probádané téma, ale pro plnou sloupcovou hodnost obdélníkové intervalové matice je známo jen několik podmínek. Cílem práce by bylo sepsat známé výsledky, rozšířit charakterizace a různé podmínky pro regularitu na případ plné sloupcové hodnosti. Výsledné podmínky by se pak implementovaly a porovnaly numericky. Programovací jazyk: Matlab/Octave + Intlab. Další možné rozšíření je tzv. AE kvantifikace intervalových parametrů.

    Odkazy:

    1. M. Hladík. AE regularity of interval matrices. Electron. J. Linear Algebra, 33:137-146, 2018.
    2. J. Rohn. Forty necessary and sufficient conditions for regularity of interval matrices: A survey. Electron. J. Linear Algebra, 18:500-512, 2009.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.
    4. S.P. Shary. On full-rank interval matrices. Numer. Anal. Appl., 7(3):241-254, 2014.

  • Kontraktor pro třídy intervalových matic
  • Buď [A] intervalová matice a P nějaká maticová vlastnost. Některé matice v [A] vlastnost P mají, jiné nikoli. Úkolem kontraktoru je ořezat intervalovou matici [A] na nějakou menší (ve smyslu inkluze) co nejvíc a tak, abychom neodstranili žádnou matici s vlastností P. Vlastnost P bude zahrnovat základní maticové vlastnosti jako je positivní semidefinitnost, singularita, M-matice, P-matice, rank-one matice či různé druhy stability. Cílem práce je navrhnout co nejefektivnější kontraktor na vybrané typy maticových tříd a implementovat kontraktor v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. G. Chabert and L. Jaulin. Contractor programming. Artif. Intell. 173(11):1079-1100, 2009.
    2. J. Garloff, D. Al-Saafin and M. Adm. Further matrix classes possessing the interval property. Reliable Computing, to appear.
    3. M. Hladík and L. Jaulin. An eigenvalue symmetric matrix contractor. Reliab. Comput., 16:27-37, 2011.
    4. K. Krejčová. Ortogonální kontraktor. bakalářská práce, MFF UK, 2013.

  • Intervalové stochastické matice a markovské řetězce [zabráno]
  • Je-li [A] intervalová stochastická matice, pak ne každá její realizace je stochastická matice (množina [A] obsahuje i nestochastické matice). Proto se zaměříme jen na podmnožinu stochastických matic, a bude nás zajímat, jaké má vlastnosti. Speciálně, jestli základní vlastnosti stochastických matic a markovských řetězců platí pro všechny (resp. pro některé) realizace. Můžeme se zaměřit na vlastnost ireducibility, výpočet stacionárních vektorů atp. Výsledné podmínky a metody by se pak implementovaly v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. P. Diamond, P. Kloeden, and A. Pokrovskii. Interval stochastic matrices: A combinatorial lemma and the computation of invariant measures of dynamical systems. J. Dyn. Diff. Equat., 7:341-364, 1995.
    2. D. Hartman, M. Hladík, and D. Říha. Computing the spectral decomposition of interval matrices and a study on interval matrix powers. Appl. Math. Comput., 403:126174:1-13, 2021.
    3. A. Rivaz, M.M. Moghadam, and S.Z. Zadeh. Doubly Stochastic Interval Matrices. Çankaya Univ. J. Sci. Eng., 12(2):12-19, 2015.

  • Topologické vlastnosti zobecněných lineárních rovnic s absolutními hodnotami [zabráno]
  • Zobecněné lineární rovnice s absolutními hodnotami je soustava ve tvaru Ax+B|x|=b. Množina řešení je obecně nesouvislá či nekonvexí, ale představuje afinní podprostor v každém ortantu. Cílem práce by bylo vyšetřit nutné/postačující podmínky pro různé topologické vlastnosti množiny řešení, jako je například konvexita, souvislost, omezenost, konečný počet řešení, či řešitelnost jen v nezáporném ortantu. Výsledné podmínky a metody by se pak implementovaly v jazyku Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík. Properties of the solution set of absolute value equations and the related matrix classes. SIAM J. Matrix Anal. Appl., 44(1):175-195, 2023.

  • Reprezentace po částech lineárních funkcí
  • Spojité a po částech lineární funkce mohou být reprezentovány různými způsoby: maximum z minim lineárních funkcí, lineární kombinace maxim lineárních funkcí, vnořený výraz s absolutními hodnotami, explicitně seznamem regionů a přidružených funkcí, anebo implicitně jako řešení soustavy rovnic s absolutními hodnotami. Cílem práce je implementovat, pokud možno co nejefektivnějším způsobem, přecházení mezi jednotlivými reprezentacemi a analyzovat jejich složitost. Programovací jazyk: Matlab/Octave.

    Odkazy:

    1. A. Griewank, J.-U. Bernt, M. Radons, and T. Streubel. Solving piecewise linear systems in abs-normal form. Linear Algebra Appl., 471:500-530, 2015.
    2. C. Koutschan, B. Moser, A. Ponomarchuk, et al. Representing piecewise linear functions by functions with small arity. Applicable Algebra in Engineering, Communication and Computing, 2023, in press.
    3. A. Kripfganz and R. Schulze. Piecewise affine functions as a difference of two convex functions. Optim., 18(1):23-29, 1987.
    4. J.-N. Lin and R. Unbehauen. Canonical piecewise-linear networks. IEEE Trans. Neural Netw., 6(1):43-50, 1995.

  • Testování kopositivity pomocí branch & bound [zabráno]
  • Matice A je kopositivní pokud xTAx je nezáporné pro všechny nezáporné vektory x. Navzdory jednoduché definici je NP-těžké ověřit, zda je daná matice kopositivní. Cílem práce by bylo implementovat metodu branch & bound na testování kopositivity matice. Metoda by využila Čebyševovo znormování vektorů a intervalovou analýzu pro ověřování podmínky na subregionech. Výstupem by bylo numerické testování a porovnání s jinými metodami. Programovací jazyk: Matlab + Intlab.

    Odkazy:

    1. A. Berman et al. Open problems in the theory of completely positive and copositive matrices. Electron. J. Linear Algebra 29, 46-58, 2015.
    2. I.M. Bomze. Copositive optimization - recent developments and applications. Eur. J. Oper. Res., 216:509-520, 2012.
    3. M. Dür. Copositive Programming - a Survey. In: Diehl M., Glineur F., Jarlebring E., Michiels W. (eds) Recent Advances in Optimization and its Applications in Engineering, pp. 3-20, Springer, Berlin, Heidelberg, 2010.

  • Vyhodnocování funkce na simplexech a simplexová aritmetika
  • V globální optimalizaci je úkolem najít globální optimum a metody k tomu účelu používané prohledávají přípustný prostor metodou branch & prune a dělením prostoru na menší části. Simplexová varianta používá simplexy (tj. n-dimensionální polytopy s n+1 vrcholy) a dělí je na menší simplexy. Tudíž potřebujeme umět odhadnout účelovou funkci na simplexu. Je zde velký potenciál adaptovat metody vyhodnocování funkcí na intervalovém boxu. Také se zde nabízí navrhnout simplexovou aritmetiku, která by umožňovala základní operace se simplexy a výsledný simplex by zapouzdřoval skutečný výsledek operace. Cílem práce je navrhnout různé metody na vyhodnocování funkce na simplexu, implementovat je a porovnat z hlediska časové složitosti a těsnosti výsledku. Programovací jazyk: Matlab/Octave.

    Odkazy:

    1. L. Jaulin, M. Kieffer, O. Didrit, and E. Walter. Applied Interval Analysis. Springer, 2001
    2. E. Hansen and W. Walster. Global Optimization using Interval Analysis. MIT Press, 2004
    3. R. Paulavičius and J. Žilinskas. Simplicial Global Optimization. Springer, 2014.

  • Semiinfinitní programování pomocí intervalových metod globální optimalizace
  • Semiinfinitní programování je optimalizační úloha s nekonečně omezeními, které jsou dány paramericky (např. x+py<=5 pro všechna p v intervalu [2,3]). Metody globální optimalizace si kladou za cíl nalézt garantovaně (tj. se zárukou) globální optimum. Fungují obvykle tak, že region přípustných řešení dělí na menší části a rekurzivně metodou branch & prune. Intervalové počítání se pak konkrétně využívá pro odhady funkcí, zmenšování regionů a zahazování regionů, které prokazatelně neobsahují optimum. Cílem práce je adaptovat a implementovat základní intervalové metody globální optimalizace na úlohu semiinfinitního programování. Programovací jazyk: Matlab/Octave.

    Odkazy:

    1. M.A. Goberna and M.A. López. Linear semi-infinite programming theory: An updated survey. Eur. J. Oper. Res. 143(2):390-405, 2002.
    2. E. Hansen and W. Walster. Global Optimization using Interval Analysis. MIT Press, 2004
    3. M. López and G. Still. Semi-infinite programming. Eur. J. Oper. Res. 180(2):491-518, 2007.

  • Doplňování a aktualizace prvků matice porovnání
  • Matice porovnání je standardní způsob získání preferencí mezi různými objekty od uživatele. Základní úloha pak zní určit váhy jednotlivým objektům. K tomuto existuje řada metod. Práce by měla rozšířit postupy na případ, kdy neznáme všechny prvky matice resp. uživatel je zadává postupně. Program by pak měl automaticky doplňovat prázdné políčka. Stejně tak by měl zareagovat na změnu hodnot a vydat nejlepší přibližné řešení. Cílem práce je implementace těchto metod ve formě online webové aplikace.

    Odkazy:

    1. M. Hladík. Vícekriteriální optimalizace, doprovodný text, sekce 5.2.
    2. R. Hlavatý. Saaty's matrix revisited: Securing the consistency of pairwise comparisons, proceedings of 32nd International Conference Mathematical Methods in Economics MME 2014, Olomouc, 2014.
    3. T. L. Saaty, Relative measurement and its generalization in decision making. Why pairwise comparisons are central in mathematics for the measurement of intangible factors. The analytic hierarchy/network process, RACSAM - Rev. R. Acad. Cien. Serie A. Mat., 102(2):251–318, 2008.
    4. T. L. Saaty and L. G. Vargas. Models, Methods, Concepts & Applications of the Analytic Hierarchy Process. Springer, New York, second edition, 2012.



    Ryze teoretické bakalářské práce

    Co to je teoretická bakalářka a mám se toho bát? Ne, rozhodně není třeba se bát. Pokud si student vybere téma, které ho baví a věnuje tomu přiměřené úsilí, pak je riziko neúspěchu minimální. Teoretická bakalářka je typicky zaměřená na speciální problém, který ještě nikdo neřešil, nebo na rozšíření známých výsledků na větší třídu úloh. Proto když student na začátku nastuduje problematiku, tak má připravenou půdu ke zdárnému výsledku. Zde samozřejmě závisí na invenci a píli studenta, a na kousku štěstí k jak velkým výsledkům se dostane. Historie ale ukazuje, že studenti naší katedry mají dobré výsledky, leckdy i publikovatelné v odborném tisku, a také bývají úspěšní v soutěžích typu SVOČ.

  • Zobecněná Perron-Frobeniova teorie pro intervalové matice
  • Perron-Frobeniova teorie říká, že nezáporné matice mají z hlediska vlastních čísel a vlastních vektorů speciální vlastnosti. Nezápornost matice A znamená, že A leží v kuželi nezáporných směrů. Jedno z možných rozšíření uvažuje obecný kužel a zobecňuje některé výsledky pro tento případ. Cílem práce je prozkoumat tuto zobecněnou teorii, adaptovat výsledky na intervalové matice a vyjádřit podmínky na ověření předpokladů.

    Odkazy:

    1. M. Hladík. An overview of polynomially computable characteristics of special interval matrices. preprint arXiv: 1711.08732, 2017.
    2. L. Hogben. Handbook of Linear Algebra. CRC Press, Second Edition, 2014

  • Celočíselné lineární programování s intervalovými koeficienty
  • Lineární programování (LP) a celočíselné LP jsou základní úlohy optimalizace, používané k řešení mnoha praktických úloh. Reálná data ale jsou často odhadnuta či známa jen s určitou přesností. To vede na úlohy s intervalovými daty. Zatímco intervalové LP je předmětem zkoumání řadu let, o celočíselném se ví mnohem méně. Cílem práce je prozkoumat, které výsledky z intervalového LP platí pro celočíselný případ a které již nikoliv. U těch druhých se pokusit je adaptovat na celočíselné prostředí.

    Odkazy:

    1. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    2. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Zobecněné lineární rovnice s absolutními hodnotami a singulárními maticemi
  • Zobecněné lineární rovnice s absolutními hodnotami je soustava ve tvaru Ax+B|x|=b. Vyřešit tuto soustavu nebo zjistit zda je řešitelná je tzv. NP-těžké. Existují však různé podmínky, které garantují řešitelnost i metody, které v mnohých případech rozumně fungují. Cílem práce by bylo zaměřit se na případ, kdy matice A,B jsou singulární. V této situaci některé podmínky selhávají, takže úkolem by bylo je adaptovat na naši situaci. Singularita matic by také mohla umožnit zredukovat dimenzi celého problému. Zajímavé by bylo prošetřit použití tzv. znaménkové Gaussovy eliminace.

    Odkazy:

    1. M. Hladík and M. Zamani. Absolute Value Programming. In P.M. Pardalos and O. Prokopyev, Encyclopedia of Optimization, third edition, to appear, 2022.
    2. O. L. Mangasarian and R. R. Meyer. Absolute value equations.. Linear Algebra Appl., 419(2):359-367, 2006.
    3. M. Radons and S.M. Rump. Convergence results for some piecewise linear solvers. Optimization Letters. in presss, 2022.
    4. S. Wu and S. Shen. On the unique solution of the generalized absolute value equation. Optimization Letters, 15:2017-2024, 2021.



    Diplomové práce

    Tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. Některá témata jsou v SISu. Další navrhovaná témata (můžete přijít i s vlastním tématem):

  • Verifikace v lineárním programování
  • Používání floating-point aritmetiky vede k zaokrouhlovacím chybám a v důsledku toho mohou solvery na lineární programování dávat chybné výsledky. Verifikační metody jsou postupy, které dokážou potvrdit optimalitu vypočítaného řešení (resp. optimální báze) vhledem k dané přesnosti. Cílem práce by bylo zmapovat verifikaci v lineárním programování, porovnat a případně navrhnout vylepšení. Předpokládá se i implementace ve vhodném prostředí - nejspíše v Matlabu s použitím Intlabu.

    Odkazy:

    1. Christian Jansson. Rigorous Lower and Upper Bounds in Linear Programming, SIAM J. Optim. 14(3): 914-935, 2004.
    2. Arnold Neumaier and Oleg Shcherbina. Safe bounds in linear and mixed-integer linear programming, Math. Program., Ser. A, 99(2):283-296, 2004.
    3. Siegfried M. Rump. Verification methods: Rigorous results using floating-point arithmetic, Acta Numerica 19: 287-449, 2010.
    4. Jiří Rohn. VERSOFT: Verification software in MATLAB / INTLAB, version 10, 2009.
    5. Christian Keil and Christian Jansson. Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library , Reliab. Comput. 12(4): 303-321, 2006.
    6. Christian Keil. Lurupa - Rigorous Error Bounds in Linear Programming, Dagstuhl Seminar Proceedings 05391, 2006.

  • Intervalová maticová norma
  • Jsou známy různé způsoby jak rozšířit maticové normy na intervalové matice. Cílem této práce by bylo porovnat různé normy mezi sebou, jak moc je těsná ekvivalence mezi nimi, zjistit jejich vlasnosti (konsistence, výpočetní složitost atp.). Zajímavým rozšířením by bylo zobecnění norem tak, aby měly intervalovou hodnotou.

    Odkazy:

    1. R. Farhadsefat, J. Rohn and T. Lotfi. Norms of interval matrices. Technical Report No. 1122, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 2011.
    2. Behnam Hashemi and Hanieh Tavakolipour. A non-induced interval matrix norm. Reliable Computing 18, 144-146, 2013.
    3. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University, 1985.

  • Slabá a silná řešitelnost vybraných intervalových soustav nelineárních rovnic a nerovnic
  • Slabá a silná řešitelnost je celkem dobře prostudovaná pro případ intervalových soustav lineárních rovnic a nerovnic, ale pro nelineární funkce je známo mnohem méně. Cílem práce by bylo adaptovat charakterizace a nutné či postačující podmínky pro řešení a řešitelnost intervalových lineárních soustav na vybrané nelineární soustavy. Zaměřilo by se především na kvadratické a bilineární funkce, semidefinitní omezení a případně další důležité typy funkcí a omezení.

    Odkazy:

    1. J. Rohn. Solvability of systems of interval linear equations and inequalities, in Fiedler et al., Linear optimization problems with inexact data, chapter 2, 35-77, 2006.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. M. Hladík. Strong solvability of restricted interval systems and its applications in quadratic and geometric programming. Linear Algebra Appl., 2023. in press.
    4. J. Rohn. Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl., 15(1): 175-184, 1994.

  • Exponenciála s intervalovou maticí
  • Exponent s maticí je definován přirozeně pomocí Taylorovy řady jako matice eA=∑k=0Ak/k!. Cílem je určit co nejlepší dolní a horní odhady na prvky eA pokud prvky matice A perturbujeme v rámci předem daných intervalů. Motivace tohoto problému pochází v mikro-robotiky, vzniká při hledání robustního řešení v teorii řízení robota.

    Odkazy:

    1. Micky Rakotondrabe, homepage.
    2. Alexandre Goldsztejn. On the Exponentiation of Interval Matrices, arXiv, 2009.
    3. M. Althoff, O. Stursberg, and M. Buss. Reachability analysis of linear systems with uncertain parameters and inputs. In Proc. of the 46th IEEE Conference on Decision and Control, 726-732, 2007.
    4. E.P. Oppenheimer and A.N. Michel. Application of Interval Analysis Techniques to Linear Systems. II. The Interval Matrix Exponential Function. IEEE Trans. Circuits Syst., 35(10):1230-1242, 1988.

  • Znaménková stabilita inverze intervalové matice
  • Znaménková stabilita inverze intervalové matice znamená, že každý prvek inverzní matice má konstantní znaménko pro jakoukoli realizaci hodnot z daných intervalů. Tato vlastnost se umí charakterizovat exponenciální podmínkou, samotná složitost problému je ale neznámá. Cílem práce je nejen prozkoumat složitost, ale i vyšetřit speciální případy, kdy má znaménkový vzor malou hodnost nebo intervalová matice je silně regulární. Dále by se měla prozkoumat nestriktní verze znaménkové stability, zahrnující i nulovou hodnotu.

    Odkazy:

    1. M. Fiedler et al., eds., Linear Optimization Problems with Inexact Data, Springer, New York, 2006.
    2. J. Rohn. Inverse interval matrix. SIAM Journal on Numerical Analysis, 30: 864-870, 1993.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.
    4. J. Rohn and R. Farhadsefat. Inverse interval matrix: A survey. Electronic Journal of Linear Algebra 22:704-719, 2011.

  • Číslo podmíněnosti ve vícekriteriálním lineárním programování
  • Číslo podmíněnosti v optimalizaci kvantitativně udává, jak moc je daná úloha blízko "špatně podmíněné" úloze, tj. úloze, která je nepřípustná, neomezená či jinak nestabilní. Jiný přístup je měřit citlivost optimální hodnoty při lokální změně dat. Cílem práce je navrhnout a porovnat vhodné koncepty pro číslo podmíněnosti ve vícekriteriálním lineárním programování, případně i v kontextu výběru Pareto-optimálního řešení. Součástí práce by mohla být i analýza složitosti jednotlivých přístupů či alespoň diskuse algoritmického hlediska.

    Odkazy:

    1. D. Cheung, F. Cucker, and J. Peña. Unifying condition numbers for linear programming. Math. Oper. Res., 28(4):609-624, 2003.
    2. R. M. Freund and J. R. Vera. On the complexity of computing estimates of condition measures of a conic linear system. Math. Oper. Res., 28(4):625-648, 2003.
    3. M. Hladík. On relation of possibly efficiency and robust counterparts in interval multiobjective linear programming. In A. Sforza and C. Sterle, editors, Optimization and Decision Science: Methodologies and Applications, volume 217 of Springer Proceedings in Mathematics & Statistics, pages 335-343. Springer, Cham, 2017.
    4. J. Rohn. On sensitivity of the optimal value of a linear program. Ekonom.-Mat. Obzor, 25(1):105-107, 1989

  • Optimální partitioning a optimální support set invariance v intervalovém lineárním programování
  • Stabilita lineárních programů se tradičně studuje na základě zachování optimální báze. Není to však jediný možný přístup. Alternativně lze studovat zachování optimálního partitioningu nebo optimálního support setu. Práce by byla zaměřená na analýzu nových typů invariancí pro případ, že vstupní hodnoty lineárních programů se pohybují v rámci zadaných intervalů. Cílem je charakterizovat či navrhnout podmínky pro tyto invariance a prozkoumat speciální případy, které by mohly být řešitelné efektivně.

    Odkazy:

    1. M. Hladík. Multiparametric linear programming: support set and optimal partition invariancy. Eur. J. Oper. Res., 202(1):25-31, 2010
    2. M. Hladík. How to determine basis stability in interval linear programming. Optim. Lett., 8(1):375-389, 2014
    3. O. Král. Metody na výpočet optimálních hodnot intervalového lineárního programování. diplomová práce, MFF UK, 2020
    4. N. Mehanfar, A. Ghaffari-Hadigheh. Optimal partition invariancy in multi-parametric linear optimization. J. Math. Model., 10(3):433-448, 2022

  • Porovnání metod intervalového lineárního programování
  • Úlohou intervalového lineárního programování rozumíme množinu úloh lineárního programování, v nichž parametry nabývají hodnot z daných intervalů. Jedním z cílů tohoto problému je najít extrémní meze, ve kterých se nabývají optimální hodnoty jednotlivých lineárních programů. To lze řešit různými metodami, např. dekompozicí na exponenciálně mnoho lineárních programů, metodami globální optimalizace či nehladké nekonvexní optimalizace. Cílem práce je implementace a porovnání základních metod s využitím vhodných dolních a horních odhadů na meze optimálních hodnot. Programovací jazyk: Matlab/Octave + Intlab. Tato práce by byla více programovací a implementační.

    Odkazy:

    1. E. Hansen and G.W. Walster. Global optimization using interval analysis. 2nd ed., Marcel Dekker, 2004.
    2. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    3. M. Hladík. On approximation of the best case optimal value in interval linear programming. Optim. Lett., 8(7):1985–1997, 2014.
    4. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.

  • Silné Nashovo ekvilibrium v intervalových maticových hrách [zabráno]
  • Nashovo ekvilibrium je takový rovnovážný výběr strategií, že žádnému hráči se nevyplatí jeho stretegii změnit, protože by si pohoršil. Silné Nashovo ekvilibrium je pak taková situace, že ani žádná koalice hráčů si nepolepší. Polepšením výplaty koalice myslíme, že by se mohli domluvit mezi sebou, změnit stretegii a každý ze členů koalice by měl větší výplatu. Zatímco Nashovo ekvilibrium existuje, silné již existovat nemusí. Cílem práce je prozkoumat silné Nashovo ekvilibrium pro hry s intervalovými maticemi, navrhnout postup jak určit, že existuje instance se silným ekvilibriem (resp., že všechny instance jej mají).

    Odkazy:

    1. R. Aumann. Acceptable points in general cooperative n-person games, Acceptable points in general cooperative n-person games, in "Contributions to the Theory of Games IV", Princeton Univ. Press, Princeton, N.J., 1959.
    2. M. Hladík. Interval valued bimatrix games. Kybernetika, 46(3):435-446, 2010.
    3. B. Kubica, A. Wozniak. Interval methods for computing strong Nash equilibria of continuous games. Decision Making in Manufacturing and Services, 9(1), 63-78, 2016.
    4. R. Nessah, G. Tian. On the existence of strong Nash equilibria. J. Math. Anal. Appl., 414(2), 871-885.

  • Koncepce eficientních řešení v intervalových maticových hrách s více kritérii
  • V maticových hrách s více kritérii se eficientní řešení dá zavést jako ekvilibrium nějaké skalarizace (konvexní kombinace kritérií). Pokud jsou ale výplaty hráčů intervalové, rozšíření pojmu eficientní řešení není přímočaré. Cílem práce je zobecnit nutné a (nebo) postačující podmínky pro to, kdy řešení je eficientním pro nějaké resp. všechny realizace výplat. Dalším krokem zobecnění mohou být intervalové váhy. Uvažujeme hry s nulovým součtem, případně bimaticové hry.

    Odkazy:

    1. M. Hladík. Various approaches to multiobjective linear programming problems with interval costs and interval weights. Cent. Eur. J. Oper. Res., 31(3):713-731, 2023.
    2. M. Hladík. Interval valued bimatrix games. Kybernetika, 46(3):435-446, 2010.
    3. Miroslav Rada and Michaela Tichá Finite game with vector payoffs: how to determine weights and payoff bounds under linear scalarization. In A. Kocourek and M. Vavroušek, editors, 34th International Conference Mathematical Methods in Economics 2016. Conference Proceedings, pp. 717-722, Technical University of Liberec, 2016.
    4. M. Zeleny. Games with multiple payoffs. Int. J. Game Theory 4:179-191, 1975.



    Další užitečné odkazy