Optimization Seminar of the Corvinus Center for Operational Research

8 October 2020
Solymosi Tamás (CUB): Redundant coalitions for the core

Abstract:

The various solutions of transferable utility games take into account the cooperative possibilities of all coalitions of players in one way or another. Although their definitions formally involve each of the exponentially many coalitional values, many of the excess-based solutions are actually determined by a smaller family of coalitions. Disregarding redundant coalitions can make the analysis and computation of solutions significantly easier.

In the talk we focus on the core, and identify smaller (in some cases the smallest) families of coalitions which completely determine the core. We present several old and some new results, and demonstrate the usefulness of such simplification possibilities on various classes of games related to optimization problems.

15 October 2020Rigó Petra Renáta (CUB): New predictor-corrector interior-point algorithm for sufficient linear complementarity problems (Joint work with Zsolt Darvay and Tibor Illés)

Abstract:

We present a new predictor-corrector (PC) interior-point algorithm (IPA) for solving sufficient linear complementarity problems (LCPs). The introduced IPA uses a new type of algebraic equivalent transformation (AET) on the centering equations of the system defining the central path. We apply the square root function in this new type of AET in order to determine the search directions. We prove that the PC IPA retains polynomial iteration complexity in the handicap of the problem’s matrix, the size of the problem and the bit size of the data.


22 October 2020
Roland Török (BME): Belsőpontos algoritmusok implementációja elégséges lineáris komplementaritási feladatok megoldására

Absztrakt:

Lineáris komplementaritási feladatoknak (LCP) szerteágazó alkalmazási területei ismertek. Érdekes mérnöki (pl. optimális irányítási probléma), közgazdasági (pl. piaci egyensúlyi modellek, portfólió optimalizálás), játékelméleti vagy éppen optimalizálási (pl. kopozitív mátrixok eldöntési kérdései) kérdések fogalmazhatók meg LCP alakban. Az alkalmazások szempontjából felmerülő igény ellenére azonban nagyon kevés olyan megoldó szoftver található, amely képes az (általános) LCP feladatok hatékony megoldására.

Bemutatjuk az elégséges LCP feladatok belsőpontos algoritmusainak (IPA) legfontosabb ismérveit és a számítógépes implementációból adódó numerikus kihívásokat. A primál-duál Newton-barrier módszer implementációjában lehetőség nyílik különböző IPA variánsok futtatására, tesztelésére. A program futtatása során lehetőség van a centrális út algebrailag ekvivalens transzformációjának (AET) az alkalmazására a következő függvények felhasználásával. Választható továbbá az is, hogy a Newton-rendszer elméletileg ekvivalens alakjainak melyikét használjuk a numerikus megoldás során.

A tesztfeladatok, amiken a szoftverek működése bemutatásra kerül a következőek: Morapitiye Sunil által generált elégséges LCP-k, Csizmadia Zsolt által bevezetett LCP feladat különböző dimenziókban, Eisenberg-Nagy Marianna által előállított elégséges LCP-k.

Az implementálásra került IPA eredményeit összehasonlítjuk Darvay Zsolt szoftverének az eredményeivel, illetve különböző state-of-the-art solverek által adottakkal.

5 November 2020
Anita Varga (BME): Új hosszúlépéses belsőpontos algoritmus a lineáris programozási feladatra (Társszerző: Eisenberg-Nagy Marianna)

Absztrakt:

Az előadásban bemutatunk egy új hosszúlépéses belsőpontos algoritmust a lineáris programozási feladat megoldására. A Darvay Zsolt által 2002-ben bevezetett algebrailag ekvivalens átalakítások módszere új keresési irányok meghatározását teszi lehetővé belsőpontos algoritmusok esetén. Különböző függvények alkalmazásával számos új algoritmust definiáltak lineáris programozási feladatok, lineáris komplementaritási feladatok és számos más feladatosztály esetében is.

A lépéshossz alapján a belsőpontos algoritmusok két csoportra oszthatók, rövid- és hosszúlépéses módszerekre. A gyakorlatban hatékonyabb hosszúlépéses algoritmusok elméleti komplexitása azonban sokáig elmaradt a rövidlépéses változatokétól. Ai és Zhang 2005-ben egy új széles környezet alkalmazásával bevezetett egy új hosszúlépéses belsőpontos algoritmust, amelyre tudták igazolni a rövidlépéses módszerekre jellemző jobb komplexitást.

2018-ban Darvay Zsolt és Rigó Petra Renáta adta meg az első, Ai-Zhang típusú széles környezetre és a négyzetgyök-függvénnyel alkalmazott algebrailag ekvivalens átalakítások módszerére épülő hosszúlépéses algoritmust.

Az előadásban ismertetett algoritmus szintén Ai-Zhang típusú környezetet használ és az algebrailag ekvivalens átalakítások módszerére épül, a φ(t) = t − √t függvény alkalmazásával. Az elemzés ismertetésén túl bemutatjuk a NETLIB LP-feladatokra kapott numerikus eredményeket és összehasonlítjuk őket az identitás- és négyzetgyökfüggvényre épülő algoritmusok működésével.

19 November 2020
Sorin-Mihai Grad (University of Vienna): Strong convergence of trajectories of dynamical systems associated to monotone inclusions with composite structure

Abstract:

Zeros of the sum of a maximally monotone operator with a single-valued monotone one can be obtained as weak limits of trajectories of dynamical systems, for strong convergence demanding hypotheses being imposed. We extend an approach due to Attouch and Cominetti with several coauthors (see [1, 2]), where zeros of maximally monotone operators are obtained as strong limits of trajectories of Tikhonov regularized dynamical systems, to forward-backward and forward-backward-forward dynamical systems whose trajectories strongly converge towards zeros of such sums of monotone operators under reasonable assumptions. We also discuss how ODE solvers can be employed in convex optimization by presenting applications in split feasibility problems and variational inequalities.

This talk is based on joint work [3] with Radu Ioan Boţ, Dennis Meier and Mathias Staudigl.

[1] H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, Journal of Differential Equations 128:519–540, 1996
[2] R. Cominetti, J. Peypouquet, S. Sorin: Strong asymptotic convergence of evolution equations governed by maximal monotone operators with Tikhonov regularization, Journal of Differential Equations 245:3753–3763, 2008
[3] R.I. Boţ, S.-M. Grad, D. Meier, M. Staudigl: Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure, Advances in Nonlinear Analysis 10:450–476, 2021

3 December 2020
Kristály Sándor (Óbudai Egyetem, Babeş-Bolyai Tudományegyetem): Geodetikus konvexitás az optimizációban: (téves) fogalmak és alkalmazások

Absztrakt:

Az elmúlt tíz évben különböző optimizációs feladatokat vizsgáltak negatívan görbült Riemann-sokaságokon, melyek kidolgozásához bizonyos konvexitási fogalmak használata volt létfontosságú (geodetikus konvexitás, geodetikusan konvex burkoló, geodetikusan affin függvények). Az előadás első részében egy olyan eredményünket mutatom be (lásd [1]), mely rávilágít több ilyen fogalom konceptuális tévességére, azaz, a görbült téren az adott fogalom akkor és csakis akkor használható, ha az adott tér izometrikus az Eukleidészi térrel. Ennek fényében, több optimizációs eredmény nem mond többet, mint a már jól ismert Eukleidészi eredmények. Az előadás második részében, egy Nash-egyensúlypontokra vonatkozó eredményemet mutatom be negatívan görbült Riemann-tereken (lásd [2]). Ennek vizsgálatára a sokaság természetes geodetikus konvexitását, metrikus projekciók tulajdonságait, valamint diszkrét/folytonos dinamikus rendszerek elméletét használom. Az előadás végén megmutatom, hogy a természetes geometriai közeget a Nash-egyensúlyelmélet kidolgozására kizárólag a negatívan görbült Riemann-sokaságok szolgáltatják.

[1] Kristály, Alexandru; Li, Chong; López-Acedo, Genaro; Nicolae, Adriana What do `convexities’ imply on Hadamard manifolds? J. Optim. Theory Appl. 170 (2016), no. 3, 1068–1074.
[2] Kristály, Alexandru Nash-type equilibria on Riemannian manifolds: a variational approach. J. Math. Pures Appl. (9) 101 (2014), no. 5, 660–688.