Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp phân tách cho bài toán lập trình quadractic
Tóm tắt
Một phương pháp phân tách ma trận được trình bày để tối thiểu hóa một bài toán lập trình bậc hai (QP), và một thuật toán tổng quát được thiết kế để giải quyết bài toán QP và phát sinh một chuỗi các điểm lặp. Chúng tôi chứng minh rằng chuỗi các điểm được phát sinh bởi thuật toán hội tụ về giải pháp tối ưu và có tỷ lệ hội tụ R-tuyến tính nếu bài toán QP là lồi chặt chẽ và không suy biến, và rằng mỗi điểm tích lũy của chuỗi phát sinh bởi thuật toán tổng quát là một điểm KKT của bài toán gốc dưới giả thiết rằng giá trị của hàm mục tiêu được giới hạn dưới trên khu vực ràng buộc, và chuỗi hội tụ về một điểm KKT nếu bài toán không suy biến và khu vực ràng buộc là hữu hạn.
Từ khóa
#phương pháp phân tách #bài toán lập trình bậc hai #thuật toán tổng quát #hội tụ #điểm KKTTài liệu tham khảo
N. Dyn, W.E. Ferguson. The Numerical Solution of Equatlity-constrained Quadratic Programming Problems.Mathematical Computation, 1983, 41: 165–170
Z.Q. Luo, P. Tseng, On the Convergence of a Matrix Splitting Algorithm for the Symmetric Monotone Linear Comlementarity Problem.SIAM J. Control and Optimization, 1991, 29: 1037–1060
Z.Q. Luo, P. Tseng. Error Bound and Convergence Analysis of Matrix Splitting Algorithm for the Affine Variational Inequality Problem.SIAM J. Optimization, 1992, 2: 43–54
O.L. Mangasarian. Solution of Symmetric Linear Complementarity Problem by Iterative Methods.Journal of Optimization Theory and Applications, 1977, 22: 465–485
J.S. Pang. More Results on the Covergence of Iterative Methods for the Symmetric Linear Complementarity Problem.Journal of Optimization Theory and Applications, 1986, 49: 107–134
A.N. Iusem. On the Convergence of Iterative Methods for Symmetric Linear Comlementarity Problems.Mathematical Programming, 1993, 59: 33–48
Z.L. Wei. Subspace Search Method for Quadratic Programming with Box Constraints.Journal of Computational Mathematics, 1999, 17: 307–314
I.I. Dikin. Iterative Solution of Problem of Linear and Quadratic Programming.Soviet Mathematical Doklady, 1967, 8: 674–675
D. Goldfarb, S. Liu. AO(n 3 L) Primal Interior Point Algorithm for Solving Strictly Convex Quadratic Programs.Mathematical Programming, 1991, 49: 325–340
Y. Ye. On Affine Scaling Algorithms for Nonconvex Quadratic Programming.Mathematical Programming, 1992, 56: 285–300
Y. Yuan. Numerical Methods for Nonlinear Programming, Shanghai Scientific and Technical Publishers, 1993 (in Chinese)
A.M. Ostrowski. Solution of Equations and Systems of Equation, 2-nd Edition. Academic Press, New York, 1966