A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function

Document Type : Original paper

Authors

1 Mathematics

2 Department of Mathematics, Azarbaijan Shahid Madani University

Abstract

In this paper, we present a second-order corrector infeasible
interior-point method for linear optimization in a large
neighborhood of the central path. The innovation of our method is to
calculate the predictor directions using a specific kernel function
instead of the logarithmic barrier function. We decompose the
predictor direction induced by the kernel function to two orthogonal
directions of the corresponding to the negative and positive
component of the right-hand side vector of the centering equation.
The method then considers the new point as a linear combination of
these directions along with a second-order corrector direction. The
convergence analysis of the proposed method is investigated and it
is proved that the complexity bound is
$\mathcal{O}(n^{\frac{5}{4}}\log\varepsilon^{-1})$.

Keywords

Main Subjects

References

1] W. Ai, Neighborhood-following algorithms for linear programming, Science in China Series A: Mathematics 47 (2004), no. 6, 812–820.
[2] W. Ai and S. Zhang, An O(√nl) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP, SIAM J. Optim. 16 (2005), no. 2, 400–417.
[3] 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 J. Optim. 15 (2004), no. 1, 101–128.
[4] Zs. Darvay, A new predictor-corrector algorithm for linear programming, Alkalmazott Matematikai Lapok (in Hungarian) 22 (2005), 135–161.
[5] Z. Feng, A new iteration large-update primal-dual interior-point method for second-order cone programming, Numer. Func. Anal. Optim. 33 (2012), no. 4, 397–414.
[6] Z. Feng and L. Fang, A new O(√nl) -iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming, J. Comput. Appl. Math. 256 (2014), 65–76.
[7] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), no. 4, 373–395.
[8] B. Kheirfam, A predictor-corrector interior-point algorithm for P∗(κ)-horizontal linear complementarity problem, Numer. Algorithms 66 (2014), no. 2, 349–361.
[9] B. Kheirfam, A corrector–predictor path-following method for convex quadratic symmetric cone optimization, J. Optim. Theory Appl. 164 (2015), no. 1, 246–260.
[10] B. Kheirfam, A corrector–predictor path-following method for second-order cone optimization, Int. J. Comput. Math. 93 (2016), no. 12, 2064–2078.
[11] B. Kheirfam, A predictor-corrector infeasible-interior-point algorithm for semidefinite optimization in a wide neighborhood, Fundam. Inform. 152 (2017), no. 1, 33–50.
[12] B. Kheirfam and M. Chitsaz, A new second-order corrector interior-point algorithm for P∗(κ)-LCP, Filomat 31 (2017), no. 20, 6379–6391.
[13] B. Kheirfam and M. Haghighi, A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function, Period. Math. Hung. 79 (2019), no. 1, 94–105.
[14] B. Kheirfam and M. Mohamadi-Sangachin, A wide neighborhood second-order predictor-corrector interior-point algorithm for semidefinite optimization with modified corrector directions, Fundam. Inform. 153 (2017), no. 4, 327–346.
[15] Y. Li and T. Terlaky, A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√n log(tr(x0s0)/ε)) iteration complexity, SIAM J. Optim. 20 (2010), no. 6, 2853–2875.
[16] C. Liu and H. Liu, A new second-order corrector interior-point algorithm for semidefinite programming, Math. Meth. Oper. Res. 75 (2012), no. 2, 165–183.
17] H. Liu, X. Yang, and C. Liu, A new wide neighborhood primal–dual infeasibleinterior-point method for symmetric cone programming, J. Optim. Theory Appl. 158 (2013), no. 3, 796–815.
[18] N. Megiddo, Pathways to the optimal set in linear programming, Progress in Mathematical Programming, Springer-Verlag, New York, 1989, pp. 131–158.
[19] S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim. 2 (1992), no. 4, 575–601.
[20] S. Mizuno, M.J. Todd, and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res. 18 (1993), no. 4, 964–981.
[21] J. Peng, C. Roos, and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program. 93 (2002), no. 1, 129–171.
[22] F.A. Potra, Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity, SIAM J. Optim. 24 (2014), no. 1, 1–28.
[23] C. Roos, T. Terlaky, and J.-P. Vial, Theory and algorithms for linear optimization: an interior point approach, John Wiley & Sons, Chichester, UK, 1997.
[24] G. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) optimization, In A. Pr´ekopa and J. Szelezs´an and B. Strazicky editor, System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, Lecture Notes in Control and Information Sciences, 84, Springer Verlag, Berlin, West-Germany, 1986, pp. 866–876.
[25] G.-Q. Wang and Y.-Q. Bai, A new full nesterov–todd step primal–dual pathfollowing interior-point algorithm for symmetric optimization, J. Optim. Theory Appl. 154 (2012), no. 3, 966–985.
[26] G.Q. Wang, Y.Q. Bai, X.Y. Gao, and D.Z. Wang, Improved complexity analysis of full Nesterov–Todd step interior-point methods for semidefinite optimization, J. Optim. Theory Appl. 165 (2015), no. 1, 242–262.
[27] G.Q. Wang, X.J. Fan, D.T. Zhu, and D.Z. Wang, New complexity analysis of a full-newton step feasible interior-point algorithm for P∗(κ)-LCP, Optim. Lett. 9 (2015), no. 6, 1105–1119.
[28] S.J. Wright, Primal-Dual Interior-Point Methods, SIAM, 1997.
[29] Y. Ye, Interior Point Algorithms: Theory and Analysis, vol. 44, John Wiley & Sons Inc., New York, 1997.
[30] Y. Zhang and D. Zhang, On polynomiality of the mehrotra-type predictor–corrector interior-point algorithms, Math. Program. 68 (1995), no. 1, 303–318.
 
Communications in Combinatorics and Optimization
Volume 7, Issue 1
June 2022
Pages 29-44

Files

Share

How to cite

Statistics