Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T06:57:50.008Z Has data issue: false hasContentIssue false
  • English
  • Français

A PRIMAL-DUAL INTERIOR-POINT ALGORITHM BASED ON A NEW KERNEL FUNCTION

Published online by Cambridge University Press:  03 February 2011

G. M. CHO ,
Y. Y. CHO  and
Y. H. LEE
G. M. CHO*
Affiliation:
Department of Multimedia Engineering, Dongseo University, Busan 617-716, South Korea (email: [email protected])
Y. Y. CHO
Affiliation:
Department of Mathematics, Pusan National University, Busan 609-735, South Korea (email: [email protected])
Y. H. LEE
Affiliation:
Department of Mathematics, Pusan National University, Busan 609-735, South Korea (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We propose a new primal-dual interior-point algorithm based on a new kernel function for linear optimization problems. New search directions and proximity functions are proposed based on the kernel function. We show that the new algorithm has and iteration bounds for large-update and small-update methods, respectively, which are currently the best known bounds for such methods.

Keywords

primal-dual interior-point methodkernel functioncomplexitypolynomial algorithmlinear optimization problem

MSC classification

Secondary: 90C05: Linear programming
Type
Research Article
Information
The ANZIAM Journal , Volume 51 , Issue 4 , April 2010 , pp. 476 - 491
Copyright
Copyright © Australian Mathematical Society 2011

References

[1]Amini, K. and Haseli, A., “A new proximity function generating the best known iteration bounds for both large-update and small-update interior point methods”, ANZIAM J. 49 (2007) 259–270.CrossRefGoogle Scholar
[2]Amini, K. and Peyghami, M. R., “Exploring complexity of large update interior-point methods for P *(κ) linear complementarity problem based on kernel function”, Appl. Math. Comput. 207 (2009) 501–513.Google Scholar
[3]Andersen, E. D., Gondzio, J., Meszaros, Cs. and Xu, X., “Implementation of interior point methods for large scale linear programming”, in: Interior point methods of mathematical programming, (ed. Terlaky, T.), (Kluwer Academic Publisher, Dordrecht, 1996) 189–252.CrossRefGoogle Scholar
[4]Bai, Y. Q., El Ghami, M. and Roos, C., “A new efficient large-update primal-dual interior-point method based on a finite barrier”, SIAM J. Optim. 13 (2003) 766–782.CrossRefGoogle Scholar
[5]Bai, Y. Q., El Ghami, M. and Roos, C., “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization”, SIAM J. Optim. 15 (2004) 101–128.CrossRefGoogle Scholar
[6]Bai, Y. Q., Lesaja, G., Roos, C., Wang, G. Q. and El Ghami, M., “A class of large-update and small-update primal-dual interior-point algorithms for linear optimization”, J. Optim. Theory and Appl. 138 (2008) 341–359.CrossRefGoogle Scholar
[7]Bai, Y. Q. and Roos, C., “A primal-dual interior point method based on a new kernel function with linear growth rate”, Proceedings of the 9th Australian Optimization Day, Perth, Australia, 2002.Google Scholar
[8]Bai, Y. Q. and Roos, C., “A polynomial-time algorithm for linear optimization based on a new simple kernel function”, Optim. Methods Software 18 (2003) 631–646.CrossRefGoogle Scholar
[9]den Hertog, D., Interior point approach to linear, quadratic and convex programming, Volume 277 of Mathematics and its Applications (Kluwer Academic Publishers, Dordrecht, 1994).CrossRefGoogle Scholar
[10]El Ghami, M., Ivanov, I., Melissen, J. B. M., Roos, C. and Steihaug, T., “A polynomial-time algorithm for linear optimization based on a new class of kernel functions”, J. Comput. Appl. Math. 224 (2009) 500–513.CrossRefGoogle Scholar
[11]El Ghami, M. and Roos, C., “Generic primal-dual interior point methods based on a new kernel function”, RAIRO Oper. Res. 42 (2008) 199–213.CrossRefGoogle Scholar
[12]Gonzaga, C. C., “Path following methods for linear programming”, SIAM Rev. 34 (1992) 167–227.CrossRefGoogle Scholar
[13]Karmarkar, N. K., “A new polynomial-time algorithm for linear programming”, Combinatorica 4 (1984) 373–395.CrossRefGoogle Scholar
[14]Kojima, M., Mizuno, S. and Yoshise, A., “A primal-dual interior-point algorithm for linear programming”, in: Progress in mathematical programming: interior point and related methods, (ed. Megiddo, N.), (Springer, New York, 1989) 29–47.CrossRefGoogle Scholar
[15]Peng, J., Roos, C. and Terlaky, T., “Self-regular functions and new search directions for linear and semidefinite optimization”, Math. Program. 93 (2002) 129–171.CrossRefGoogle Scholar
[16]Peng, J., Roos, C. and Terlaky, T., Self-regularity: a new paradigm for primal-dual interior-point algorithms (Princeton University Press, Princeton, NJ, 2002).Google Scholar
[17]Roos, C., Terlaky, T. and Vial, J. Ph., Theory and algorithms for linear optimization: an interior approach (Wiley, Chichester, UK, 1997).Google Scholar
[18]Sonnevend, G., “An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming”, System modeling and optimization: proceeding of the 12th IFIP-conference, Budapest, Hungary, September 1985, Volume 84 of Lecture Notes in Control and Information Sciences (eds A. Prekopa, J. Szleezsan and B. Strazicky), (Springer, Berlin, 1986) 866–876.CrossRefGoogle Scholar
[19]Todd, N. J., “Recent developments and new directions in linear programming”, in: Mathematical programming: recent developments and applications, (eds Iri, M. and Tanabe, K.), (Kluwer Academic Publishers, Dordrecht, 1989) 109–157.Google Scholar