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

Previous Article
Optimality of piecewise thermal conductivity in a snow-ice thermodynamic system
NACO Home
This Issue
Next Article
On the global convergence of a parameter-adjusting Levenberg-Marquardt method

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

Siqi Li ^1, and Weiyi Qian ^1,

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

Received January 2015 Revised March 2015 Published March 2015

Abstract
Related Papers

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.

Keywords: kernel function, polynomial complexity., Linear optimization, primal-dual interior-point algorithm.

Mathematics Subject Classification: Primary: 90C05, 90C5.

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 and 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-128. 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-2178. 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-646. 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-782. 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-1008. doi: 10.1080/1055678021000090024.
[6]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395. doi: 10.1007/BF02579150.
[7]	Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming, SIAM, Philadelphia, 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-256. 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-94. 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-305. 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-128. 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-2178. 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-646. 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-782. 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-1008. doi: 10.1080/1055678021000090024.
[6]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395. doi: 10.1007/BF02579150.
[7]	Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming, SIAM, Philadelphia, 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-256. 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-94. 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-305. 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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[2]	Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022003
[3]	Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[4]	Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[5]	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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[6]	Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021134
[7]	Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[8]	Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
[9]	Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[10]	Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[11]	Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[12]	Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[13]	Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[14]	Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022008
[15]	Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[16]	Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[17]	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 and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91
[18]	Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[19]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[20]	Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Siqi Li Weiyi Qian
on Google Scholar
Siqi Li Weiyi Qian

[Back to Top]