 |
Extending first- and second order algorithms for nested classes of optimization problems to solve computationally challenging industrial questions
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
125700 |
| Type |
SNN |
| Principal investigator |
Illés, Tibor |
| Title in Hungarian |
Első- és másodrendű algoritmusok kiterjesztése optimalizálási problémák bonyolultabb osztályaira ipari kérdések megoldása céljából |
| Title in English |
Extending first- and second order algorithms for nested classes of optimization problems to solve computationally challenging industrial questions |
| Keywords in Hungarian |
lineáris komplementaritási problémák, belsőpontos algoritmusok, egyensúlyi feladatok, bilineáris és multilineáris optimalizálási feladatok, megoldási módszerek |
| Keywords in English |
linear cmplementarity problems, interior point algorithms, equilibrium problems, bilinear and multilinear optimization problems, solution methods |
| Discipline |
| Operational Research (Council of Physical Sciences) | 100 % | | Ortelius classification: Operations research |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Department of Differential Equations (Budapest University of Technology and Economics) |
| Participants |
Eisenberg-Nagy, Marianna
Morapitiye, Gábor Sunil
Naszvadi, Péter
Rigó, Petra Renáta
Tollner, Dávid
Török, Roland
Varga, Anita
|
| Starting date |
2017-12-01 |
| Closing date |
2021-09-30 |
| Funding (in million HUF) |
35.472 |
| FTE (full time equivalent) |
7.58 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Jól strukturált, de NP-nehéz nemlineáris optimalizálási feladatok (NLOF) vizsgálatát tervezzük: egyes multi-lineáris optimalizálási feladatokhoz szeretnénk új, hatékony, közepes- és nagyméretű ipari feladatok megoldására alkalmas eljárásokat fejlesztünk. A vizsgált NLOF-ek: gazdasági egyensúlyi feladatok (GEF), keverési feladatok (KF) és tri-mátrix problémák (TMP). Kidolgozzuk a problémák dualitás elméletét. Erre támaszkodva új első és másodrendű megoldó algoritmusokat hozunk létre. Végül globális optimalizálásból is ismert technikákkal (lokális keresés, meta-heurisztikus eljárások, trust region technikák) ötvözve gyakorlati problémák megoldására alkalmas hibrid módszerekké fejlesztjük, melyeket szuper számítógépeken is tesztelünk.
Az egyik legalapvetőbb GEF az Arrow-Debreu modell, amely bizonyos esetekben lineáris komplementaritási feladatként is megfogalmazható. Itt a már meglévő belsőpontos algoritmusunk (BA) viselkedését vizsgálnánk (például több centrális út létezése esetén), majd kiválasztott heurisztikák beépítésével hoznánk létre a feladatra hangolt megoldót.
A KF matematikai modelljében bi-lineáris feltételek jelennek meg. Jelenleg az iparban használt szoftverek szekvenciális lineáris programozási technikákon alapulnak, ahol pivot algoritmusokat (PA) használnak. A PA-kat BA-ra cserélve javulna a megoldó numerikus stabilitása és növelné a megoldható feladatok méretét.
A nem negatív mátrix tri-faktorizáció (egy nagyméretű mátrixot szeretnénk három kisebb méretű mátrix szorzatára bontani) matematikai elmélete jelenleg egyáltalán nem kidolgozott, holott például biológiai alkalmazásokban nagy szükség lenne a feladat legalább közelítő megoldására.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatási projekt során három gyakorlati probléma (gazdasági egyensúlyi feladat, olajipari keverési feladat és biológiai alkalmazásból származó trimátrix faktorizációs probléma) számítógépes megoldására összpontosítunk. Mindhárom feladat multi-lineáris optimalizálási probléma, ahol az ismeretlenek szorzatai jelennek meg. Ennek következtében nem-konvex feladatokról van szó, melyek megoldáshalmaza általában nem is összefüggő, ami a megoldást nagyban megnehezíti. Célunk megmutatni, hogy annak ellenére, hogy ezek a feladatok NP-nehezek,
• az operációkutatás elmélete (egzakt első és másodrendű eljárások),
• heurisztikus módszerek,
• a globális optimalizálásból is ismert technikák (például: különböző pontokból indítjuk el a keresést, korlátozás és szétválasztás módszere) és
• szuperszámítógépek, párhuzamosítási technikák
segítségével, megfelelő összehangolásával létrehozott hibrid számítási eljárások (HSE) alkalmasak arra, hogy valós feladatok közelítő megoldását megadják, az alkalmazások szempontjából kielégítő pontosságú közelítő megoldásokat állítsanak elő.
Az elméleti kutatás főként az első pont vizsgálatánál történik. Itt a dualitás elmélet részleteinek kidolgozása, és a feladatok speciális szerkezetének pontos megértése segít. A második, harmadik pontban az eljárások paramétereit kell megfelelően beállítanunk az elméleti vizsgálódásokra, illetve a futási eredményekre támaszkodva. Az utolsó pont az implementáció kérdése, de a végső cél eléréséhez elengedhetetlen a gondos kivitelezése.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A projektben három (gazdasági egyensúlyi modellek (GEM), keverési feladatok (KF) és tri-mátrix problémák (TMP)) NP-nehéz nem lineáris és nem-konvex optimalizálási feladat és ipari alkalmazásainak numerikus megoldásával foglalkozunk. Mindhárom feladat az un. multi-lineáris optimalizálási feladatosztályba tartozik, amelyik elméleti vizsgálata a szakirodalomból alig ismert. A feladatok megoldására léteznek próbálkozások a szakirodalomban, de ezek hiányosságai eléggé közismertek.
A GEM-ek köréből leginkább a Leontief hasznossági függvényes Arrow-Debreu piaci egyensúlyi modell érdekel bennünket, amelynek a megoldása ekvivalens egy általános lineáris komplementaritási feladat (LCP) megoldásával. Csizmadia és Illés (2006); Csizmadia, Illés és Nagy A. (2012, 2013); Illés és Nagy A. (2014) cikksorozatban LP-re és LCP-re kidolgozták a felexibilis ciklizálás ellenes pivot szabályok egy bő családját. LCP-k esetén ez a criss-cross algoritmussal (CCA) összekapcsolva jól működik, lehetővé téve kisméretű általános LCP-k megoldását. Másfelől Illés, Nagy M. és Terlaky (2009, 2010) három cikkben kidolgozta a belsőpontos algoritmusokkal (BA) igazolható, LCP-s EP-tételeket, amelyek új távlatokat nyitottak általános LCP-k megoldására. Ezeket az elméleti és algoritmikus eredményeket felhasználva lehetővé válik GEM-ek eléggé nagy osztályába tartozó nagyméretű feladatok numerikus megoldása, ha megfelelő globális optimalizálási (GO) technikákkal közösen alkalmazzuk.
Illés és tanítványai a MOL Csoport megbízásából vizsgálták az olajipari termelés tervezési modelljüket (OTTM) és a megoldásra használt programcsomagot. Az OTTM-ek nehéz feltételei bilineáris jellegűek és a keverési feltételek leírására szolgálnak. A jelenlegi szekvenciális lineáris programozási módszerek (SLPM) alapvetően az 1980-as évek eredményeire épülnek, figyelmen kívül hagyva a BA-okat. BA-kra épülő SLPM módszereket kell kifejleszteni GO technikák alkalmazásával, annak érdekében, hogy stabil, közel optimális megoldás legyen előállítható.
Povh és munkatársai bioinformatikai kérdések matematikai modellezése során jutottak nem negatív TMP-kra. Ezek hatékony megoldása azonnal alkalmazást nyerne biológiai problémák megoldásában.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Gazdasági egyensúlyi modellek (GEM). A gazdasági elméletek többsége mögött matematikai modelleket találunk. A GEM-ekhez kapcsolódó elméleti kutatásokért Arrow, Debreu és Leontief is Közgazdasági Nobel díjat kaptak. Az elméletek által megjósolt egyensúlyi állapotok meghatározása komoly matematikai kihívás. A GEM-ek egyes osztályainak a megoldása terén az átütő siker még várat magára, pedig ezek gyakorlati alkalmazására, pl. több vállalat termelésének az összehangolása nem a nyereség maximalizálása, hanem a fenntartható termelés megvalósítása érdekében, társadalmi szinten komoly előrelépést jelentene.
Keverési problémák a gyakorlatban. A kőolajiparban fontos probléma a végtermékek gazdaságos előállítása a finomítókban. A matematikai nehézséget több finomító termelésének az összehangolása okozza, mert a modellek nemlineáris és nem konvex feltételeket is tartalmaznak. Az ipar számára kínált szoftverek azonban nagyon régi technikákat alkalmaznak, amellyel jónak gondolt megoldásokat állítanak elő, de azt a kérdést, hogy milyen közel van a globális optimumhoz, nem vizsgálják. Az optimumtól távoli termelési módok pazarlóak és így a szükségesnél nagyobb mennyiségű alapanyagot, kőolajat használnak fel. Kutatásunk eredményeképpen a globális optimumot jobban közelítő megoldást állítunk elő, gyorsabban, ezzel lehetővé válik az egy modellbe szervezhető finomítók számának a növelése is.
Bio-informatika az élvonalban. A diagnosztikai orvostudomány legdinamikusabban fejlődő ága a képalkotó eljárások alkalmazása. Ezért az ennek elméleti hátterét fejlesztő alapkutatás azonnali elismertségre s ipari felhasználásra számíthat.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
We are going to study well structured, but NP-hard non-linear optimization problems (NLOP) with the aim to develop efficient methods to solve medium- and large size industrial problems modelled by multi-linear optimization problems. The NLOPs discussed in this projects are economic equilibrium problems (EEP), blending problems (BP) and tri-matrix problems (TMP). We will work out duality theories for these problems. Based on these results, first and second order algorithms will be developed. Final goal is to introduce hybrid computational methods (HCM) as combination of global optimization techniques (local search, meta-heuristic methods, trust region techniques) and exact algorithms. HCM will be implemented and tested on a supercomputer.
One of the basic EEP is the Arrow-Debreu model that in some cases can be formulated as linear complementarity (LCP) problem. For the given LCPs we are going to examine the behaviour (for example, the existence and effect of more central paths) of the existing interior point algorithms (IPA). Finally, we plan to incorporate selected heuristics to create a well-tuned HCM for EEPs.
The mathematical model of BPs contains bi-linear conditions. The currently used software in the industry is based on sequential linear programming techniques using pivot algorithms (PA). The PA can be replaced by IPAs improving the numerical stability and increasing the size of the problem that can be solved.
The mathematical theory for non-negative matrix tri-factorization problems (NMTFP) has not been developed yet. The NMTFP has many applications including medical imaging applications, where the accurate solution is required.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The research project focuses on computational solution of three (economic equilibrium problem, blending problem of oil industry, non-negative trimatrix factorization for biological applications) real-life problems. All three optimization problem falls into the class of multi-linear optimization problems that are characterized by constraints containing product of several unknowns. As a result, non-convex optimization problem is obtained that has no connected solution set, making even harder to solve these problems. Our aim is to show that - despite these problems being NP-hard - with suitable understanding of the structure of the problems, HCMs could be developed for finding approximate solutions with sufficient accuracy. The main research steps are
• using the theory of operations research to develop exact first and second order algorithms,
• defining useful variants of meta-heuristics,
• applying necessary techniques of global optimization (multi-start, branch and bound), and
• using parallelization of computations and utilizing a supercomputer.
The theoretical research methodology is mainly used in analysing properties of the problems. Then we develop duality theory and KKT results for these problem classes by analysing their structures. Based on theoretical and algorithmic developments we will fine-tune the HCMs but that still will be a computationally challenging task. For successfully attacking real-life, industrial problems parallelization of the computations and utilizing a supercomputer are essential.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
In this project we are dealing with three NP-hard non-linear and non-convex optimization problems (economic equilibrium problem (EEP) and blending problem (EP) and non-negative matrix tri-factorization problems (NMTFP)). Our goal is to compute numerical solutions of industrial applications. All three problems fall into the multi-linear optimization problem class for which theoretical results are hardly known. There are attempts reported to solve these problems, but these have known shortcomings.
From the class of EEPs we are going to deal with Arrow-Debreu market equilibrium models with Leontief’s utility function that is equivalent to a general linear complementarity problem (LCP). Csizmadia and Illés (2006); Csizmadia, Illés and Nagy A. (2012, 2013); Illés and Nagy A. (2014) in a series of papers worked out a wide class of flexible anti-cycling pivot rules for the pivot algorithms of LP and LCP. For LCPs, these flexible anti-cycling pivot rules improves the computational performance of the criss-cross algorithm (CCA) allowing solution of small size general LCPs. On the other hand, Illés, Nagy M. és Terlaky (2009, 2010) in three papers developed interior point algorithms (IPA) that served as constructive proofs for new EP-theorems that opened new perspectives in solving general LCPs. These theoretical and algorithmic results make it possible to solve large scale EEPs, by developing HCMs using appropriate global optimization (GO) techniques.
Illés and his students worked for MOL Group as operations research (OR) experts studying their production planning model (PPM) and a software widely used in process industry. The used sequential linear programming methods (SLPM) of the software are mainly based on the OR results from early 1980s ignoring the development of IPAs. The hard constraints of PPM are those related to blending problem and described as bilinear constraints. Our aim is to develop such SLPMs that are based on IPAs GO techniques, in order to compute near-optimal solution faster and in a numerically stable way.
Povh and his colleagues using NMTFPs modelled some important questions in bioinformatics. Efficient solutions of NMTFPs will have immediate applications in medical imaging.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Economic equilibrium models (EEM). Behind most of the economic theories there are mathematical models. For theoretical research related to the EEM - Arrow, Debreu and Leontief all received the Nobel Prize in Economics. But calculation of these equilibrium states predicted by the theory is still a serious mathematical challenge. Finding the solution in some of these EEM classes might provide us with practical applications. For example, instead of maximizing individual profits from production two or more companies could team up to achieve sustainable growth, or other socially important goal – it would be a significant step forward.
Blending problems in practice. One of the major problems of the oil industry is producing final products in the refineries in an economical way. Coordinating the production of several refineries is a mathematical challenge because the models include nonlinear and non-convex conditions. Unfortunately in the industry old software techniques are used generating approximate solutions, but they do not give any information on how close the constructed solution to the global optimum is; that question is not even examined. The far-from-optimum production plans use excessive amounts of raw material (crude oil). Our research will result in closer to global optimum solution that can be achieved faster, making it possible to model numerous refineries at the same time.
Bio-informatics in the forefront. The fastest growing area of diagnostic medicine is medical imaging techniques. Therefore, the mathematics of medical imaging is in the forefront too. Any improvement on its techniques leads to instant recognition and industrial applications.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| Illés Tibor, Morapitiye Sunil: Generating sufficient matrices, In: F. Friedler, (editor) Short Papers of the 8th VOCAL Optimization Conference: Advanced Algorithms, pp. 56-61., held in Esztergom, Hungary, December 10-12, 2018., 2018 | | Illés Tibor, Varga Anita: A new interior point algorithm for a class of market equilibrium problems, In: F. Friedler, (editor) Short Papers of the 8th VOCAL Optimization Conference: Advanced Algorithms, pp. 62-68., held in Esztergom, Hungary, December 10-12, 2018., 2018 | | Rigó Petra Renáta: New trends in interior-point algorithms, In: F. Friedler, (editor) Short Papers of the 8th VOCAL Optimization Conference: Advanced Algorithms, pp. 85-91., held in Esztergom, Hungary, December 10-12, 2018., 2018 | | Eisenberg-Nagy Marianna, Illés Tibor, Lovics Gábor: Market exchange models and geometric programming, Cent Eur J Oper Res on-line pp. 1-21., 2018 | | Eisenberg-Nagy Marianna, Illés Tibor, Lovics Gábor: Market exchange models and geometric programming, Cent Eur J Oper Res 27(2): 415-435, June 2019, 2019 | | Zs. Darvay, T. Illés, B. Kheirfam and P.R. Rigó: A corrector–predictor interior-point method with new search direction for linear optimization, Cent Eur J Oper Res online first: 15 May 2019, 2019 | | Zs. Darvay, B. Kheirfam and P.R. Rigó: A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization, Opt Letters online first: 24 August 2019, 2019 | | Zs. Darvay, P.R. Rigó, E. Szénási: Infeasible interior-point algorithm for linear optimization based on a new search direction, In L. Zadnik Stirn, M. Kljajic Borstnar, J. Žerovnik, S. Drobne, J. Povh eds., Proc. of the 15th International Symposium on Operational Research SOR'19, Bled, Slovenija, 2019 | | Illés Tibor: Sufficient Linear Complementarity Problems – Pivot Versus Interior Point Algorithms (plenáris előadás), In L. Zadnik Stirn, M. Kljajic Borstnar, J. Žerovnik, S. Drobne, J. Povh eds., Proc. of the 15th International Symposium on Operational Research SOR'19, Bled, Slovenija,, 2019 | | Zs. Darvay, T. Illés, and Cs. Majoros: Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation, Operations Research Reports, ORR-2018-02, pp. 1-27, 2018 June, 2018 | | Illés Tibor: Nehéz elégséges lineáris komplementaritási feladatok hatékony megoldása új belsőpontos algoritmusokkal (felkért előadás), Új irányzatok az operációkutatásban, tudományos ülésszak, 2019. november 28., Magyar Tudományos Akadémia, Budapest, 2019 | | Zs. Darvay, T. Illés, J. Povh, and P. R. Rigó: Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new search direction, Operations Research Reports, ORR-2018-03, pp. 1-47, 2018 June, 2018 | | P.R. Rigó and E. Szénási: Interior-point algorithm for linear optimization based on a new search direction, Operations Research Report, ORR 2019-01, pp. 1-18, 2019 March, 2019 | | L. Mályusz, A. Varga: A New Primal-dual Algorithm for Separable Bregman Divergence Minimization Under Linear Constraints, Operations Research Report, ORR 2019-02, pp. 1-23, 2019 June, 2019 | | Eisenberg-Nagy Marianna, Illés Tibor, Lovics Gábor: Market exchange models and geometric programming, Cent Eur J Oper Res 27(2): 415-435, 2019, 2019 | | Zs. Darvay, T. Illés, B. Kheirfam and P.R. Rigó: A corrector–predictor interior-point method with new search direction for linear optimization, Cent Eur J Oper Res 28: 1123–1140, 2020, 2020 | | Zs. Darvay, B. Kheirfam and P.R. Rigó: A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization, Opt Letters 14:1747-1763, 2020, 2020 | | Zs. Darvay, T. Illés, and Cs. Majoros: Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation, Optimization Letters, Published: 24 June 2020, 2020 | | Zs. Darvay, T. Illés, J. Povh, and P. R. Rigó: Feasible Corrector-Predictor Interior-Point Algorithm for P*(κ)-Linear Complementarity Problems Based on a New Search Direction, SIAM Journal on Optimization 30(3):2628-2658, 2020, 2020 | | S. Asadi, N. Mahdavi-Amiri, Zs. Darvay, P. R. Rigó: Full-Nestrov-Todd step feasible interior-point algorithm for symmetric cone horizontal linear complementarity problem based on a positive-asymptotic barrier function, Optimization Methods and Software, published online: 09 Mar 2020, 2020 | | Darvay Zs., Szénási E., Rigó P. R.: Új keresési irányra épülő belsőpontos algoritmus lineáris optimalizálásra, Alkalmazott Matematikai Lapok, 37(2):277-286, 2020, 2020 | | Zs. Darvay, T. Illés, P. R. Rigó: New predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new type of algebraic equivalent transformation technique, Corvinus Economics Working Papers - CEWP 2020/03, 2020 | | A. Csizmadia, Zs. Csizmadia and T. Illés: Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied, Cent Eur J Oper Res, 2018 | | Zs. Darvay, T. Illés, P.R. Rigó: Predictor-corrector interior-point algorithm for P*(κ)-linear complementarity problems based on a new type of algebraic equivalent transformation technique, Eur J Oper Res, 2021 | | Zs. Darvay, P.R. Rigó: New predictor-corrector interior-point algorithm for symmetric cone horizontal linear complementarity problems, Corvinus Economics Working Papers, CEWP, 01/2021, 2021 | | T. Illés, P. R. Rigó, R. Török: Predictor-corrector interiorpoint algorithm based on a new search direction working in a wide neighbourhood of the central path, Corvinus Economics Working Papers, CEWP, 02/2021, 2021 | | M. E.-Nagy, A. Varga: A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation, Corvinus Economics Working Papers, CEWP 06/2021, 2021 | | M. E.-Nagy, A. Varga: A numerical comparison of long-step interior point algorithms for linear optimization, In S. Drobne, L. Zadnik Stirn, M. Kljajic Borstnar, J. Povh, J. Žerovnik eds., Proc. of the 16th International Symposium on Operational Research in Slovenia, SOR'21, Bled, 2021 | | R. Török, T. Illés, R.P. Rigó: Implementation of Primal-dual interior-point algorithms for solving sufficient linear complementarity problems, In S. Drobne, L. Zadnik Stirn, M. Kljajic Borstnar, J. Povh, J. Žerovnik eds., Proc. of the 16th International Symposium on Operational Research in Slovenia, SOR'21, Bled, 2021 |
|
|
|
|
|
|
|
|
|
