Analiza złożoności i zbieżności w algorytmach punktów wewnętrznych

• Autorzy: Henryk Jan Runka

Warianty tytułu

Complexity and Convergence Analysis in Interior-Point Algorithms

• Języki publikacji: PL

Abstrakty

W artykule rozważa się związki pomiędzy złożonością algorytmów punktów wewnętrznych w optymalizacji liniowej i ich zbieżnością w analizie numerycznej. Analizę złożoności i zbieżności zastosowano do algorytmów: skalującego prymarnego i prymarno-dualnego. W obydwu wypadkach wprowadza się algebraiczne warunki spowalniające zbliżanie się do brzegu zbioru rozwiązań podczas przeszukiwania punktów wewnętrznych przez zastosowanie funkcji barierowych. (fragment tekstu)

EN

This paper contains analysis of complexity of interior-point algorithms and their connections with convergence of algorithms in nonlinear optimization and numerical analysis. In first part there are presented definitions using in complexity , in convergence theory and in interval arithmetic theory. Later, by definition of a class in C + +, was shown, how to use rational numbers in interior-point algorithms. Then we can apply complexity analysis for such algorithms. Practically, we still use float point arithmetic on common used processors. Some data about floating point arithmetic in new Intel's processors is presented, too. The second part contains analysis of complementary conditions in primal and primal-dual interior point algorithms and complementary reduction in iteration processes using complexity theory. In the third part we present convergence analysis of complementary reduction for some cases of constraints in primal-dual systems. There was shown influence of feasible starting point on convergence primal-dual interior point algorithm. (original abstract)

Słowa kluczowe

PL

Algorytmy; Ekonometria; Optymalizacja

EN

Algorithms; Econometrics; Optimalization

• Czasopismo: Zeszyty Naukowe / Akademia Ekonomiczna w Poznaniu
• Rocznik: 2005
• Numer: nr 64
• Strony: 297--319

Twórcy

autor

Henryk Jan Runka

• Akademia Ekonomiczna w Poznaniu

Bibliografia

• Bazaraa, M.S., Sherall, H.D., Shetty, C.M., Nonlinear Programming. Theory and Algorithms, 2nd ed., J. Wiley & Sons, 1993.
• Brassard, G., Bratley, P., Fundamentals of Algorithmics, Prentice Hall, 1996.
• Fang Shu-Chemg, Puthenpura, S., Linear Optimization and Extensions. Theory and Algorithms, Prentice Hall, 1993.
• Ford, W., Topp, W., Data Structures with C+ + , Prentice Hall, 1996.
• Giannesi, F., Rapisak, T., Komlosis, S., New Trends in Mathematical Programming, Kluwer, 1998.
• Jansen, B., Interior Point Techniques in Optimization. Complementarity, Sensitivity and Algorithms, Kluwer, 1997.
• Lassonde, M. (red.), Approximation, Optimization and Mathematical Economics, Springer Verlag, 2001.
• Nocedal, J., Wright, S.J., Numerical Optimization, Springer (Series in Operations Research), 1999.
• Runka, H.J., Początkowe rozwiązanie dla afinicznego algorytmu skalującego, Przegląd Statystyczny 1999, z. 2.
• Runka, H.J., Optymalizacja w procesach gospodarczych, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań 2003.
• Runka, H.J., Układy prymalne i prymalno-dualne ograniczeń w optymalizacji ciągłej, w: E. Panek (red.), Matematyka w ekonomii, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań 2004.
• Vanderbei, R.J., Linear Programming. Foundations and Extensions, Kluwer, 2000.
• Van Hentenryck, P., Laurent, M., Deville, Y., Numerica. A Modeling Language for Global Optimization, MIT Press, 1997.
• Yuan Ya-xiang (red.), Advances in Nonlinear Programming, Kluwer 1998.
• SAS/OR 9.1 User's Guide: Mathematical Programming, SAS Publishing, 2004.
• Internet i czasopisma komputerowe (NetWorld, Chip, PC World Komputer).