Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán cắt trung tâm tăng tốc cho lập trình bán vô hạn tuyến tính
Tóm tắt
Bài báo này trình bày một thuật toán cho lập trình bán vô hạn tuyến tính, nhằm tăng tốc độ hội tụ của thuật toán cắt trung tâm được đề xuất lần đầu tiên trong [4]. So với các thuật toán khác, thuật toán trong [4] có lợi thế là có thể áp dụng dưới các điều kiện nhẹ nhàng và cung cấp các nghiệm khả thi. Tuy nhiên, tốc độ hội tụ của nó đã được chứng minh là tương đối chậm trong các trường hợp thực tế. Thuật toán được đề xuất trong bài báo này giới thiệu một sơ đồ tăng tốc đơn giản mang lại sự hội tụ nhanh hơn, như đã được xác nhận bằng một số ví dụ, cùng với một khoảng của độ dài đã định chứa giá trị tối ưu. Bài báo cũng chỉ ra rằng thuật toán cung cấp một nghiệm cho bài toán đối ngẫu và có thể được sử dụng cho lập trình bán vô hạn lồi.
Từ khóa
#thuật toán cắt trung tâm #lập trình bán vô hạn #hội tụ #nghiệm khả thi #bài toán đối ngẫuTài liệu tham khảo
Bahn, O., Goffin J.L., Vial, J.Ph., Du Merle, O.: Experimental behavior of an interior point cutting plane algorithm for convex programming: an application to geometric programming. Disc. Appl. Math. 49, 3–23 (1994)
Betrò, B., Guglielmi, A.: Methods for global prior robustness under generalized moment conditions. In: Ríos Insua, D., Ruggeri, F. (eds.), Robust Bayesian Analysis, Springer-Verlag, New York, 2000, pp. 273–293
den Hertog, D., Kaliski, J., Roos, C., Terlaky, T.: A logarithmic barrier cutting plane method for convex programming. Ann. Oper. Res. 58, 69–98 (1995)
Elzinga, J., Moore, Th.: A central cutting plane algorithm for the convex programming problem. Math. Program. 8, 134–145 (1975)
Glashoff, K., Gustafson, S.A.: Linear Optimization and Approximation. Springer-Verlag, Berlin, 1983
Goberna, M.A., López, M.A.: Linear Semi-Infinite Optimization. Wiley, New York, 1998
Hu, H.: A one-phase algorithm for semi-infinite linear programming. Math. Program. 46, 85–103 (1990)
Knüppel, O.: A PROFIL/BIAS implementation of a global minimization algorithm. Berichte des Forschungsschwerpunktes Informations- und Kommunikationstechnik 95.4, TU Hamburg-Harburg, 1995
Kortanek, K.O., Moulin P.: Semi-infinite programming in orthogonal wavelet filter design. In: Reemsten, R., Rückmann, J.J. (eds.), Semi-Infinite Programming, Kluwer Academic Publishers, Dordrecht, 1998, pp. 323–360
Kortanek, K.O., No, H.: A central cutting plane for convex semi-infinite programming problems. SIAM J. Optim. 3, 901–918 (1993)
Leon, T., Vercher E.: A purification algorithm for semi-infinite programming. Eur. J. Oper. Res. 57, 412–420 (1992)
Moulin, P., Anitescu M., Kortanek K.O., Potra F.A.: The role of linear semi-infinite programming in signal-adapted QMF bank design. IEEE Trans. Signal Processing 45, 2160–2174 (1997)
Potchinkov, A.W.: Design of optimal linear phase FIR filters by a semi-infinite programming technique. Signal Processing 58, 165–180 (1997)
Reemsten, R., Görner, S.: Numerical methods for semi-infinite programming: a survey. In: Reemsten, R., Rückmann, J.J. (eds.), Semi-Infinite Programming, Kluwer Academic Publishers, Dordrecht, 1998, pp. 195–275
Vial, J.P.: Computational experience with a primal-dual interior point method for smooth convex programming. Optim. Methods Softw. 3, 285–316 (1994)