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.

[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.

[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.

[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.

[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.

[6]

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

[7]

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

[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.

[9]

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

[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.

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.

[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.

[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.

[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.

[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.

[6]

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

[7]

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

[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.

[9]

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

[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.

[1]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[2]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[3]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[4]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190

[5]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[6]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[7]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[8]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[9]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[10]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[11]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[12]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[13]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[14]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[15]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[16]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569

[17]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[18]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-18. doi: 10.3934/jimo.2018107

[19]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[20]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]