آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 108 |
| تعداد مقالات | 1,228 |
| تعداد مشاهده مقاله | 1,147,061 |
| تعداد دریافت فایل اصل مقاله | 1,005,984 |
A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 3، دوره 7، شماره 1، شهریور 2022، صفحه 29-44 اصل مقاله (398.99 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27044.1185 | ||
| نویسندگان | ||
| Behrouz Kheirfam* 1؛ Afsaneh Nasrollah2 | ||
| 1Mathematics | ||
| 2Department of Mathematics, Azarbaijan Shahid Madani University | ||
| چکیده | ||
| 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})$. | ||
| کلیدواژهها | ||
| Linear optimization؛ predictor-corrector methods؛ wide neighborhoods؛ polynomial complexity | ||
| مراجع | ||
|
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.
| ||
|
آمار تعداد مشاهده مقاله: 375 تعداد دریافت فایل اصل مقاله: 471 |
||