Strukturált nemlineáris programozási feladatok: elmélet, algoritmusok és alkalmazások = Structured Nonlinear Programming Problems: Theory, Algorithms and Applications

Illés, Tibor and Csizmadia, Zsolt Gábor and Nagy, Ádám (2010) Strukturált nemlineáris programozási feladatok: elmélet, algoritmusok és alkalmazások = Structured Nonlinear Programming Problems: Theory, Algorithms and Applications. Project Report. OTKA.

Preview

PDF 49789_ZJ1.pdf Download (116kB)

Abstract

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. | 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.

Actions (login required)

Edit Item