A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term

Authors

  • B. Kheirfam Department of Mathematics Azarbaijan Shahid Madani University Tabriz, Iran
  • M. Moslemi Department of Mathematics Azarbaijan Shahid Madani University Tabriz, Iran

DOI:

https://doi.org/10.2298/YJOR120904006K

Keywords:

Kernel function, interior-point algorithm, linear optimization, polynomial complexity, primal-dual method

Abstract

In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. We show that if a strictly feasible starting point is available, then the new algorithm has O(3/4log n/ε) iteration complexity.

References

Andersen, E.D., Gondzio, J., Mészaros, Cs., and Xu, X. “Implementation of Interior Point Methods for Large Scale Linear Programming.” In: T. Terlaky (Ed.), Interior Point Methods of Mathematical Programming. Kluwer Academic Publishers, The Netherlands, 1996.

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 Journal on Optimization, 15(1) (2004) 101-128.

Bai, Y.Q., Guo, J., and Roos, C. “A New Kernel Function Yielding the Best Known Iteration Bounds for Primal-Dual Interior-Point Algorithms.” Acta Mathematica Sinica, English Series, 25 (12) (2009) 2169-2178.

Bai, Y.Q., and Roos, C. “A Polynomial-Time Algorithm for Linear Optimization Based on a New Simple Kernel Function.” Optimization Methods and Software, 18 (6) (2003) 631-646.

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.” Journal of Optimization Theory and Applications, 138 (3) (2008) 341-359.

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 Journal on Optimization, 13 (3) (2003) 766-782.

Cho, G.M. “An Interior-Point Algorithm for Linear Optimization Based on a New Barrier Function.” Journal of Applied Mathematics and Computing, 218 (2011) 386-395.

El Ghami, M. “Primal-Dual Algorithms for P∗(κ) Linear Complementarity Problems Based on Kernel-Function with Trigonometric Barrier Term.” Springer Proceedings in Mathematics and Statistics, 31 (2013) 331-349.

El Ghami, M., Guennoun, Z.A., Bouali, S., and Steihaug, T. “Interior-Point Methods for Linear Optimization Based on a Kernel Function with Trigonometric Barrier Term.” Journal of Computational and Applied Mathematics, 236(15) (2012) 3613-3623.

Gonzaga, C.C. “Path Following Methods for Linear Programming.” SIAM Review, 34 (2) (1992) 167-227.

Hertog, D. den. Interior Point Approach to Linear, Quadratic and Convex Programming. Mathematics and its Applications, 277. Kluwer Academic Publishers, Dordrecht, 1994.

Karmarkar, N.K. “A New Polynomial-Time Algorithm for Linear Programming.” Combinatorica, 4 (1984) 375-395.

Kheirfam, B. “Primal-Dual Interior-Point Algorithm for Semidefinite Optimization Based on a New Kernel Function with Trigonometric Barrier Term.” Numerical Algorithms, 61(4) (2012) 659-680.

Kheirfam, B., and Hasani, F. “A Large-Update Feasible Interior-Point Algorithm for Convex Quadratic Semi-Definite Optimization Based on a New Kernel Function.” Journal of the Operations Research Society of China, 1 (3) (2013) 359-376.

Kheirfam, B. “A Generic Interior-Point Algorithm for Monotone Symmetric Cone Linear Complementarity Problems Based on a New Kernel Function.” Journal of Mathematical Modelling and Algorithms in Operations Research, (2013) DOI 10.1007/s10852-013-9240-x.

Kim, M.K., Cho, Y.Y., and Cho, G.M. “New Path-Following Interior-Point Algorithms for P∗(κ)-Nonlinear Complementarity Problems.” Nonlinear Analysis: Theory, Methods and Applications, 14 (2013) 718-733.

Lee, Y.H., Cho, Y.Y., and Cho, G.M. “Interior-Point Algorithms for P∗(κ)-LCP Based on a New Class of Kernel Functions.” Journal of Global Optimization, (2013) DOI 10.1007/s10898-013-0072-z.

Peng, J., Roos, C., and Terlaky, T. “Self-Regular Functions and New Search Directions for Linear and Semidefinite Optimization.” Mathematical Programming, 93 (1) (2002) 129-171.

Peng, J., Roos, C., and Terlaky, T. Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002.

Roos, C., Terlaky, T., and Vial, J.-Ph. Theory and Algorithms for Linear Optimization: An Interior-Point Approach. John Wiley and Sons, Chichester, UK, 1997.

Downloads

Published

2015-06-01

Issue

Section

Research Articles