Optimality conditions for linear programs
| dc.contributor.advisor | Bessenyei, Mihály | |
| dc.contributor.author | Tóth, Norbert | |
| dc.contributor.department | Matematika- és számítástudományok doktori iskola | hu |
| dc.contributor.submitterdep | Természettudományi és Technológiai Kar::Matematikai Intézet::Analízis Tanszék | |
| dc.date.accessioned | 2025-10-09T19:28:07Z | |
| dc.date.available | 2025-10-09T19:28:07Z | |
| dc.date.defended | 2025-12-12 | |
| dc.date.issued | 2025 | |
| dc.description.abstract | A lineáris programozási feladatok olyan feltételes optimalizálási feladatok, amelyekben a célfüggvény és a feltételi rendszer is lineáris kifejezésekkel adott. A szisztematikus tanulmányozásuk a 20: század első felében kezdődött amerikai oldalról Dantzig, míg orosz (szovjet) oldalról Kantorovich által. Klee és Minty megmutatta, hogy a Dantzig által kifejlesztett szimplex módszer a Bland-szabállyal kiegészítve exponenciális idejű lehet. Továbbá, azóta az is kiderült, hogy a szimplex módszernek eddig valamennyi ismert variációja ugyanezzel a tulajdonsággal bír, de továbbra is nyitott kérdés maradt, hogy esetleg létezik-e olyan változat, amely polinomiális idejű. A szimplex módszer mellett azonban más algoritmusokat is kifejlesztettek, mint például Khachiyan ellipszoid módszere vagy Karmarkar belső pontos módszere. A motivációnk egy másik algoritmuscsalád adja, nevezetesen a belsőpontos módszerek közé tartozó logaritmikus sorompó probléma újratárgyalása. A belső pontos módszerekről igazolták, hogy van köztük polinomiális időben futó algoritmus, vagyis a lineáris programozási feladatok polinomiális komplexitásúak. A lineáris programozási problémák speciális geometriai tulajdonságai továbbá lehetővé teszik geometriai feltételek és új típusú módszerek kifejlesztését. Az értekezés célja a lineáris programozási feladatoknak a konvex analízis és a konvex geometria eszközeivel való megközelítése úgy, hogy elkerüljük a szimplex módszer használatát. | |
| dc.description.abstract | Linear programs are constrained optimization problems in which the objectives and the feasible sets are given in terms of linear expressions. Their systematic study has begun in the first half of the 20th century by Dantzig on the American side, and by Kantorovich on behalf of the Russians (Soviets). Klee and Minty illustrated that the simplex method developed by supplemented with Bland’s Rule may terminate exponentially. Moreover, it turned out since then, that almost every known variant of the simplex method has the same feature. An unsolved problem is, whether there exists a version of the simplex method that runs in polynomial time. However, other methods were also developed like the ellipsoid method developed by Khachiyan or interior point methods by Karmarkar. Our motivation is to revisit one of the interior point methods, namely the log-barrier problem, which has been proved to have polynomial complexity. Moreover, the geometrical properties of linear programs allow us to develop geometrical conditions and new type of methods for these problems, as well. Our aim is to approach linear programs via the tools of Convex Analysis and Convex Geometry while we avoid the usage of the simplex method. | |
| dc.format.extent | 73 | |
| dc.identifier.uri | https://hdl.handle.net/2437/397867 | |
| dc.language.iso | en | |
| dc.language.iso | hu | |
| dc.subject | Linear programming | |
| dc.subject | Interior point methods | |
| dc.subject | Geometric optimality condition | |
| dc.subject | Computer implementation | |
| dc.subject | Recession cone | |
| dc.subject.discipline | Matematika- és számítástudományok | hu |
| dc.subject.sciencefield | Természettudományok | hu |
| dc.title | Optimality conditions for linear programs | |
| dc.title.translated | Optimalitási feltételek lineáris programozási feladatokhoz | |
| dc.type | PhD, doktori értekezés | hu |
Fájlok
Engedélyek köteg
1 - 1 (Összesen 1)
Nincs kép
- Név:
- license.txt
- Méret:
- 1.93 KB
- Formátum:
- Item-specific license agreed upon to submission
- Leírás: