2015, 5(1): 37-46. doi: 10.3934/naco.2015.5.37

Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization

1. 

College of Mathematics and Physics, Bohai University, Jinzhou, MO 121000, China, China

Received  January 2015 Revised  March 2015 Published  March 2015

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm. In this paper, a new kernel function which its barrier term is integral type is proposed. We study the properties of the new kernel function, and give a primal-dual interior-point algorithm for solving linear optimization based on the new kernel function. Polynomial complexity of algorithm is analyzed. The iteration bounds both for large-update and for small-update methods are obtained, respectively. The iteration bound for small-update method is the best known complexity bound.
Citation: Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
References:
[1]

Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,, SIAM Journal on Optimization, 15 (2004), 101.  doi: 10.1137/S1052623403423114.  Google Scholar

[2]

Y. Q. Bai, J. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms,, Acta Mathematica Sinica English Series, 25 (2009), 2169.  doi: 10.1007/s10114-009-6457-8.  Google Scholar

[3]

Y. Q. Bai and C. Roos, A polynomial-time algorithm for linear optimization based on a new simple kernel function,, Optimization Methods and Software, 18 (2003), 631.  doi: 10.1080/10556780310001639735.  Google Scholar

[4]

Y. Q. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier,, SIAM Journal on Optimization, 13 (2002), 766.  doi: 10.1137/S1052623401398132.  Google Scholar

[5]

Y. Q. Bai, C. Roos and M. El Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function,, Optimization Methods and Software, 17 (2002), 985.  doi: 10.1080/1055678021000090024.  Google Scholar

[6]

N. Karmarkar, A new polynomial-time algorithm for linear programming,, Combinatorica, 4 (1984), 373.  doi: 10.1007/BF02579150.  Google Scholar

[7]

Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming,, SIAM, (1994).  doi: 10.1137/1.9781611970791.  Google Scholar

[8]

J. M. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite programming,, European Journal of Operational Research, 143 (2002), 234.  doi: 10.1016/S0377-2217(02)00275-8.  Google Scholar

[9]

J. Renegar, A polynomial time algorithm based on Newton's method for linear programming,, Mathematical Programming, 40 (1988), 59.  doi: 10.1007/BF01580724.  Google Scholar

[10]

C. Roos and J. P. Vial, A polynomial method of approximate centers for linear programming,, Mathematical Programming, 54 (1992), 295.  doi: 10.1007/BF01586056.  Google Scholar

show all references

References:
[1]

Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,, SIAM Journal on Optimization, 15 (2004), 101.  doi: 10.1137/S1052623403423114.  Google Scholar

[2]

Y. Q. Bai, J. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms,, Acta Mathematica Sinica English Series, 25 (2009), 2169.  doi: 10.1007/s10114-009-6457-8.  Google Scholar

[3]

Y. Q. Bai and C. Roos, A polynomial-time algorithm for linear optimization based on a new simple kernel function,, Optimization Methods and Software, 18 (2003), 631.  doi: 10.1080/10556780310001639735.  Google Scholar

[4]

Y. Q. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier,, SIAM Journal on Optimization, 13 (2002), 766.  doi: 10.1137/S1052623401398132.  Google Scholar

[5]

Y. Q. Bai, C. Roos and M. El Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function,, Optimization Methods and Software, 17 (2002), 985.  doi: 10.1080/1055678021000090024.  Google Scholar

[6]

N. Karmarkar, A new polynomial-time algorithm for linear programming,, Combinatorica, 4 (1984), 373.  doi: 10.1007/BF02579150.  Google Scholar

[7]

Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming,, SIAM, (1994).  doi: 10.1137/1.9781611970791.  Google Scholar

[8]

J. M. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite programming,, European Journal of Operational Research, 143 (2002), 234.  doi: 10.1016/S0377-2217(02)00275-8.  Google Scholar

[9]

J. Renegar, A polynomial time algorithm based on Newton's method for linear programming,, Mathematical Programming, 40 (1988), 59.  doi: 10.1007/BF01580724.  Google Scholar

[10]

C. Roos and J. P. Vial, A polynomial method of approximate centers for linear programming,, Mathematical Programming, 54 (1992), 295.  doi: 10.1007/BF01586056.  Google Scholar

[1]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[2]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[3]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[4]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[5]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[6]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[7]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[8]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[9]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[10]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[11]

Xiaofeng Ren, David Shoup. The impact of the domain boundary on an inhibitory system: Interior discs and boundary half discs. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3957-3979. doi: 10.3934/dcds.2020048

[12]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

[13]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004

[14]

Xi Zhao, Teng Niu. Impacts of horizontal mergers on dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020173

[15]

Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285

[16]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[17]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404

[18]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[19]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[20]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

 Impact Factor: 

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]