American Institute of Mathematical Sciences

Advanced
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

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 & 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.  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-2178. 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-646. 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-782. 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-1008. doi: 10.1080/1055678021000090024.  Google Scholar

[6]

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

[7]

Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming, SIAM, Philadelphia, 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-256. 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-94. 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-305. 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-128. 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-2178. 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-646. 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-782. 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-1008. doi: 10.1080/1055678021000090024.  Google Scholar

[6]

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

[7]

Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming, SIAM, Philadelphia, 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-256. 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-94. 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-305. doi: 10.1007/BF01586056.  Google Scholar

[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, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[5]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134
[6]

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

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 & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[15]

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
[16]

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
[17]

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
[18]

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 & Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[19]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082
[20]

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy