Strukturált nemlineáris programozási feladatok: elmélet, algoritmusok és alkalmazások
Title in English
Structured Nonlinear Programming Problems: Theory, Algorithms and Applications
Panel
Mathematics and Computing Science
Department or equivalent
Department of Operations Research (Eötvös Loránd University)
Participants
Csizmadia, Zsolt Gábor Nagy, Ádám
Starting date
2005-01-01
Closing date
2009-12-31
Funding (in million HUF)
6.588
FTE (full time equivalent)
4.75
state
closed project
Final report
Results in Hungarian
Kutatásunk középpontjában a lineáris optimalizálás területén kifejlesztett pivot- illetve belsőpontos algoritmusok általánosításának a kérdései álltak. Általános lineáris komplementaritási feladatok (LCP) megoldásával foglalkoztunk, amelyeknek számos alkalmazási területe van, mint például a játékelmélet vagy a gazdasági egyensúlyi modellek.
Algoritmusaink kidolgozásához nélkülözhetetlen volt a megfelelő elméleti háttér megismerése és szükség esetén annak a célirányos továbbfejlesztése. Ezért foglalkoztunk az LCP-k dualitás elméletével, a témakörhöz kapcsolódó EP-tétellel és a kapcsolódó mátrixosztályok tulajdonságaival.
Általános LCP feladatok megoldására alkalmas criss-cross algoritmust fejlesztettünk ki, foglalkoztunk a módszer ciklizálás mentességének a kérdésével (új ciklizálás ellenes szabályokat fogalmaztunk meg és vizsgáltunk). Algoritmusunk hatékonyságát numerikus teszteken mutattuk be.
A belsőpontos módszerek legfőbb osztályainak (útkövető-; affin skálázású-; prediktor-korrektor algoritmusok) egy-egy képviselőjét általánosítottuk, általános LCP feladatok EP-megoldásának az előállítására. Algoritmusaink EP-megoldást polinom időben állítanak elő és alkalmasak arra is, hogy általános LCP feladatokat - klasszikus értelemben - oldjanak meg.
Foglalkoztunk például szeparábilis konkáv célfüggvényes, lineáris feltételes minimalizálási feladattal és más alkalmazásból érkező bonyolult optimalizálási feladatokkal.
Results in English
Our main goal was to extend the applicability of pivot and interior point algorithms from linear optimization problem to a wider class of optimization problems. We were dealing with solvability of general linear complementarity problem (G-LCP) that has many interesting application area like game theory or economical equilibrium problems.
In our research it was essential to learn and - when it was necessary - to further develop the duality theory of LCPs, EP-theorems and properties of important matrix classes.
We developed new variants of criss-cross algorithms for GLCP, introduced new anti-cycling pivot rules and tested its efficiency on practical problems.
One member from each main class of interior point (path-following-, affine scaling-, predictor-corrector) algorithms (IPA) has been generalized to GLCP problems. These general IPAs solve the GLCP problem in EP-sense with polynomial running time. Furthermore, these algorithms are appropriate tools for computing solution of GLCP, as well.
In the past 5 years, during this research project we worked on other interesting, structured nonlinear programming problems like separable concave minimization problem with linear constraints as well.
Zs. Csizmadia, T. Illés: New criss-cross type algorithms for linear complementarity problems with sufficient matrices, Optimization Methods and Software 21(2):247-266, 2006
F. Bilen, Zs. Csizmadia, T. Illés: Új monoton jellegű szimplex algoritmusok elemzése megenegedttségi feladatok esetén, Alkalmazott Matematikai Lapok, 24(1-2):163-185, 2007
F. Bilen, Zs. Csizmadia, T. Illés: Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems, Optimization Methods and Softwares, Vol. 22, No. 4: 679-695, 2007
T. Illés, M. Nagy: A new variant of Mizuno-Todd-Ye predictor-corrector algorithm for sufficient matrix linear complementarity problem, European Journal of Operations Research, Vol. 181, No. 3: 1097-1111, 2007., 2007
Illés T., Nagy M.: Mizuno-Todd-Ye típusú prediktor-korrektor algoritmus elégséges mátrixú lineáris komplementaritási feladatokra, Alkalmazott Matematikai Lapok, 22:41-61, 2005
Illés T., Nagy M., Terlaky T.: Belsőpontos algoritmusok, Iványi A. (alkotó szerkesztő), Informatikai Algoritmusok 2. kötet, ELTE Eötvös Kiadó, 25. fejezet, 1230-1297, 2005
T. Illés, Á. Nagy: A sufficient optimality criteria for linearly constrained, separable concave minimization problems, Journal of Optimization Theory and Applications, 125 (3): 559-575, 2005
Csizmadia Zs., Illés T.: A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra, Szigma, XXXVI. Évf. 3-4. szám, 163-188, 2006
Zs. Csizmadia: New pivot based methods in linear optimization and application in the petroleum industry, PhD Thesis, 2007
Hamvas J., Illés T.,: A vonattovábbítás környezetvédelmi-energetikai optimalizálása, MÁV ZRT. Fejlesztési és Kisérleti Intézet, Évkönyve, 2005, Szerkesztők: Kovács K. és Kovács L., 2006
T. Illés, M. Makai, Zs. Vaik: Railway Engine Assignment Models Based on Combinatorial and Integer Programming, http://oldwww.cs.elte.hu/opres/kutatas.html, 2005
T. Illés, M. Makai, Zs. Vaik: Combinatorial Optimization Model for Railway Engine Assignment Problem, Selected Papers from the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, http://drops.dagstuhl.de/portals/ATMOS/, 2006
Illés T., Nagy M., Terlaky T.: EP theorem for dual linear complementarity problem, Journal of Optimization Theory and Application, Vol. 140:233-238, 2009
Nagy M.: Interior point methods for general linear complementarity problems, PhD Thesis, 2009
Illés T., Nagy M., Terlaky T.: A polynomial path-following interior point algorithms for general linear complementarity problems, Journal of Global Optimization, in print, 2009
Csizmadia Zs., Illés T.: The s-Monotone Index Selection Rules for Pivot Algorithms of Linear Programming, kézirat, közlésre benyújtva, 2009
Illés T., Nagy M. and Terlaky T.,: Polynomial interior point algorithms for general linear complementarity problems, Algorithms of Operations Research, Vol. 5:1-12, 2010
E. de Klerk, M. Nagy: On the complexity of computing the handicap of a sufficient matrix, kézirat, közlésre benyújtva, 2009
