Abstract
Kernel functions play an important role in the complexity analysis of the interior point methods for linear optimization. In this paper, we present a primal-dual interior point method for linear optimization based on a new kernel function consisting of a trigonometric function in its barrier term. By simple analysis, we show that the feasible primal-dual interior point methods based on the new proposed kernel function enjoys \(O\left (\sqrt {n}\left (\log {n}\right )^{2}\log \frac {n}{\epsilon }\right )\) worst case complexity result which improves the results obtained by El Ghami et al. (J Comput Appl Math 236:3613–3623, 2012) for the kernel functions with trigonometric barrier terms.
Similar content being viewed by others
References
Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004)
Bai, Y.Q., El Ghami, M., Roos, C.: A new efficient large-update primal-dual interior-point methods based on a finite barrier. SIAM J. Optim. 13(3), 766–782 (2003)
El Ghami, M., Roos, C.: Generic primal-dual interior point methods based on a new kernel function. Int. J. RAIRO Oper. Res. 42(2), 199–213 (2008)
El Ghami, M., Guennoun, Z.A., Boula, S., Steihaug, T.: Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math. 236, 3613–3623 (2012)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375–395 (1984)
Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods, pp. 29–47. Springer, New York (1989)
Megiddo, N.: Pathways to the optimal set in linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods, pp 131–158. Springer, New York (1989)
Monteiro, R.D.C., Adler, I.: Interior-point path following primal-dual algorithms: Part I: linear programming. Math. Program. 44, 27–41 (1989)
Nesterov, Y.E., Nemirovskii, A.S.: Interior Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia (1994)
Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton, NJ (2002)
Peyghami, M., Amini, K.: A kernel function based interior-point methods for solving P ∗(κ)-linear complementarity problem. Acta Math. Sin. (Engl. Ser.) 26(9), 1761–1778 (2010)
Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Springer, New York (2005)
Sonnevend, G.: An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Prakopa, A., Szelezsan, J., Strazicky, B. (eds.) Lecture Notes in Control and Information Sciences, vol. 84, pp. 866–876. Springer, Berlin (1986)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peyghami, M.R., Hafshejani, S.F. Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function. Numer Algor 67, 33–48 (2014). https://doi.org/10.1007/s11075-013-9772-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-013-9772-1