Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp điểm trong mới theo mô hình hiệu chỉnh–dự đoán cho tối ưu hóa hình nón đối xứng
Tóm tắt
Trong công trình này, chúng tôi trình bày một phương pháp điểm trong mô hình hiệu chỉnh–dự đoán cho tối ưu hóa hình nón đối xứng dựa trên đại số Jordan Euclid như một công cụ chính. Thực tế, chúng tôi đã mở rộng kỹ thuật ban đầu của Darvay et al. được giới thiệu trong (Cent Eur J Oper Res 28(3):1123–1140, 2020) cho tối ưu hóa tuyến tính sang tối ưu hóa hình nón đối xứng. Một phép biến đổi đại số tương đương của hệ thống xác định đường trung tâm, dựa trên hàm \psi (t)=t-\sqrt{t}, được sử dụng để nhận được các hướng tìm kiếm. Tại mỗi vòng lặp, thuật toán lấy một bước Nesterov–Todd tịt ở giai đoạn dự đoán và một bước Nesterov–Todd đầy đủ ở giai đoạn hiệu chỉnh. Chúng tôi thảo luận về phân tích hội tụ toàn cục của thuật toán đề xuất và chứng minh rằng giới hạn độ phức tạp trùng với giới hạn thu được cho tối ưu hóa tuyến tính. Hơn nữa, kết quả số cho thấy hiệu quả của phương pháp đề xuất.
Từ khóa
#tối ưu hóa hình nón đối xứng #phương pháp điểm trong #hiệu chỉnh-dự đoán #phân tích hội tụ #độ phức tạpTài liệu tham khảo
T.J. Carpenter, I.J. Lustig, J.M. Mulvey, D.F. Shanno, Higher order predictor-corrector interior point methods with application to quadratic objectives. SIAM J. Optim. 3, 696–725 (1993)
Z. Darvay, New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)
Z. Darvay, A predictor–corrector algorithm for linearly constrained convex optimization. Stud. Univ. Babeş-Bolyai Inform. 54(2), 121–138 (2009)
Z. Darvay, T. Illés, B. Kheirfam, P.R. Rigó, A corrector–predictor interior-point method with new search direction for linear optimization. Cent. Eur. J. Oper. Res. 28(3), 1123–1140 (2020)
Z. Darvay, T. Illés, J. Povh, P.R. Rigó, Feasible corrector–predictor interior-point algorithm for \(P_*(\kappa )\)-linear complementarity problems based on a new search direction. SIAM J. Optim. 30(3), 2628–2658 (2020)
Z. Darvay, P.R. Rigó, New interior-point algorithm for symmetric optimization based on a positive-asymptotic barrier function. Numer. Funct. Anal. Optim. 39(15), 1705–1726 (2018)
Z. Darvay, I.M. Papp, P.R. Takács, Complexity analysis of a full-Newton step interior-point method for linear optimization. Period. Math. Hung. 73(1), 27–42 (2016)
J. Faraut, A. Korányi, Analysis on Symmetric Cones. Oxford Mathematical Monographs (The Clarendon Press, Oxford University Press, Oxford Science Publications, New York, 1994)
L. Faybusovich, Linear system in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86(1), 149–175 (1997)
F. Gurtuna, C. Petra, F.A. Potra, O. Shevchenko, A. Vancea, Corrector–predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48, 453–485 (2011)
G. Gu, M. Zangiabadi, C. Roos, Full Nesterov–Todd step infeasible interior-point method for symmetric optimization. Eur. J. Oper. Res. 214(3), 473–484 (2011)
O. Güler, Barrier functions in interior point methods. Math. Oper. Res. 21(4), 860–885 (1996)
N.K. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)
B. Kheirfam, A predictor-corrector path-following algorithm for symmetric optimization based on Darvay’s technique. Yugosl. J. Oper. Res. 24(1), 35–51 (2014)
B. Kheirfam, An infeasible interior point method for the monotone SDLCP based on a transformation of the central path. J. Appl. Math. Comput. 57, 685–702 (2018)
B. Kheirfam, A corrector–predictor path-following method for convex quadratic symmetric cone optimization. J. Optim. Theory Appl. 164(1), 246–260 (2015)
B. Kheirfam, A corrector–predictor path-following method for second-order cone optimization. Int. J. Comput. Math. 93(12), 2064–2078 (2016)
S. Mehrotra, On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992)
S. Mizuno, M.J. Todd, Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)
R.D.C. Monteiro, Y. Zhang, A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. Math. Program. 8, 281–299 (1998)
Y.E. Nesterov, A.S. Nemirovskii, Interior Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics (SIAM, Philadelphia, 1994)
Y.E. Nesterov, M.J. Todd, Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1–42 (1997)
Y.E. Nesterov, M.J. Todd, Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2), 324–364 (1998)
B.K. Rangarajan, Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16(4), 1211–1229 (2006)
P.R. Rigó, Z. Darvay, Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier. Comput. Optim. Appl. 71(2), 483–508 (2018)
S.H. Schmieta, F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96(3), 409–438 (2003)
M.J. Todd, K.C. Toh, R.H. Tautauncau, On the Nesterov–Todd direction in semidefinite programming. SIAM J. Optim. 8(3), 769–796 (1998)
J.F. Sturm, Similarity and other spectral relations for symmetric cones. Linear Algebra Appl. 312(13), 135–154 (2000)
M.V.C. Vieira, Jordan algebraic approach to symmetric optimization. Ph.D. thesis, Electrical Engineering, Mathematics and Computer Science, Delft of Technology, The Netherlands (2007)
G.Q. Wang, Y.Q. Bai, A new full Nesterov–Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154, 966–985 (2012)
Y. Ye, M.J. Todd, S. Mizuno, An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)