Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về số bigℳ trong thuật toán định tỷ lệ affine
Tóm tắt
Khi chúng ta áp dụng thuật toán định tỷ lệ affine cho một chương trình tuyến tính, chúng ta thường xây dựng một chương trình tuyến tính nhân tạo có một nghiệm khả thi bên trong mà từ đó thuật toán bắt đầu. Chương trình tuyến tính nhân tạo liên quan đến một số dương được gọi là bigℳ. Về lý thuyết, tồn tại mộtℳ
* sao cho vấn đề ban đầu cần giải quyết tương đương với chương trình tuyến tính nhân tạo nếuℳ >ℳ
*. Tuy nhiên, trên thực tế, ℳ
* như vậy thường không được biết đến và một ước lượng an toàn choℳ thường quá lớn. Bài báo này đề xuất một phương pháp cập nhậtℳ đến một giá trị phù hợp trong quá trình lặp của thuật toán định tỷ lệ affine. Khiℳ trở nên lớn, phương pháp này cung cấp thông tin về tính không khả thi của vấn đề ban đầu hoặc vấn đề đối xứng của nó.
Từ khóa
#thuật toán định tỷ lệ affine; chương trình tuyến tính; nghiệm khả thi; số bigℳ; tính không khả thiTài liệu tham khảo
I. Adler, N. Karmarkar, M. Resende and G. Veiga, “An implementation of Karmarkar's algorithm for linear programming,”Mathematical Programming 44 (1988) 297–335.
E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675.
I.I. Dikin, “On the speed of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60.
I.I. Dikin, “The convergence of dual variables,” Technical Report, Siberian Energy Institute (Irkurtsk, Russia, 1991).
C.C Gonzaga, “Convergence of the large step primal affine-scaling algorithm for primal nondegenerate linear programs,” Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro (Rio de Janeiro, Brazil, 1990).
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
M. Kojima, S. Mizuno and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior-Point and Related Methods (Springer, New York, 1989) pp. 29–47.
M. Kojima, S. Mizuno and A. Yoshise, “A little theorem of the big ℳ in interior point algorithm,”Mathematical Programming 59 (1993) 361–375.
N. Megiddo, “Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior-Point and Related Methods (Springer, New York, 1989) pp. 131–158.
T. Tsuchiya, “Global convergence of the affine scaling methods for degenerate linear programming problems,”Mathematical Programming 52 (1991) 377–404.
T. Tsuchiya and M. Muramatsu, “Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,” Research Memorandum No. 423, The Institute of Statistical Mathematics (Minato-ku, Tokyo, Japan, 1992).
T. Tsuchiya and K. Tanabe, “Local convergence properties of new methods in linear programming,”Journal of the Operations Research Society of Japan 33 (1990) 22–45.
R.J. Vanderbei, “Affine-scaling for linear programs with free variables,”Mathematical Programming 43 (1989) 31–44.
R.J. Vanderbei and J.C. Lagarias, “I.I. Dikin's convergence results for the affine-scaling algorithm,” Preprints, AT&T Bell Laboratories (Murray Hill, NJ, 1988).
R.J. Vanderbei, M.S. Meketon and B.A. Freedman. “A modification of Karmarkar's linear programming algorithm”Algorithmica 1 (1986) 395–407.