Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật Toán Xấp Xỉ Ngoài Dựa Trên Nhánh và Ranh Giới cho Các Chương Trình Phân Số Tổng Tỷ Lệ
Tóm tắt
Trong bài viết này, một thuật toán xấp xỉ ngoài dựa trên nhánh và ranh giới được trình bày nhằm giải quyết toàn cầu một bài toán lập trình phân số tổng tỷ lệ. Để giải quyết vấn đề này, thuật toán giải quyết một bài toán tương đương liên quan đến việc tối thiểu hóa một hàm bậc hai không xác định trên một tập hợp lồi đóng không rỗng. Vấn đề này được giải quyết toàn cầu bằng cách tiếp cận xấp xỉ ngoài dựa trên nhánh và ranh giới, có thể tạo ra nhiều cắt bất phương trình đường thẳng dạng đóng cho mỗi lần lặp. Ngược lại với các kỹ thuật xấp xỉ ngoài thuần túy, thuật toán không yêu cầu tính toán các đỉnh mới được tạo ra khi các cắt này được thêm vào. Về mặt tính toán, công việc chính của thuật toán bao gồm việc giải quyết một chuỗi các bài toán lập trình lồi mà các vùng khả thi là giống nhau ngoại trừ một số ràng buộc tuyến tính nhất định. Do đó, để giải quyết các vấn đề này, một giải pháp tối ưu cho một bài toán có thể được sử dụng hiệu quả làm giải pháp khởi đầu cho bài toán tiếp theo.
Từ khóa
#Thuật toán xấp xỉ ngoài #lập trình phân số #tối thiểu hóa hàm bậc hai #phương pháp nhánh và ranh giới #cắt bất phương trình tuyến tính.Tài liệu tham khảo
Frenk, J.B.G., Scheible, S.: Fractional programming. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, vol. II, pp. 162–172. Kluwer, Dordrecht (2001)
Rao, M.R.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66, 622–626 (1971)
Almogy, Y., Levin, O.: Parametric analysis of a multi-stage stochastic shipping problem. In: Proceedings of the 5th IFORS Conference (IFORS), pp. 359–370 (1964)
Colantoni, C.S., Manes, R.P., Whinston, A.: Programming, profit rates, and pricing decisions. Account. Rev. 44, 467–481 (1969)
Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1989)
Cambini, A., Martein, L., Schaible, S.: On maximizing a sum of ratios. J. Inf. Optim. Sci. 10, 65–79 (1989)
Konno, H., Yajima, Y., Matsui, T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1, 65–81 (1991)
Falk, J.E., Palocsay, S.W.: Image space analysis of generalized fractional programs. J. Glob. Optim. 4, 63–88 (1994)
Konno, H., Fukaishi, K.: A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems. J. Glob. Optim. 18, 283–299 (2000)
Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002)
Konno, H., Yamashita, H.: Minimizing sums and products of linear fractional functions over a polytope. Nav. Res. Logist. 46, 583–596 (1999)
Phuong, N.T.H., Tuy, H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259 (2003)
Konno, H., Kuno, T., Yajima, Y.: Global minimization of a generalized convex multiplicative function. J. Glob. Optim. 4, 47–62 (1994)
Benson, H.P.: Global optimization of nonlinear sums of ratios. J. Math. Anal. Appl. 263, 301–315 (2001)
Benson, H.P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theory Appl. 112, 1–29 (2002)
Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problem. J. Glob. Optim. 22, 343–364 (2002)
Dur, M., Horst, R., Thoai, N.V.: Solving sum-of-ratios fractional programs using efficient points. Optimization 49, 447–466 (2001)
Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)
Schaible, S.: Fractional programming. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 495–608. Kluwer, Dordrecht (1995)
Schaible, S.: Fractional programming with sums of ratios. In: Castagnoli, E., Giorgi, G. (eds.) Scalar and Vector Optimization in Economic and Financial Problems, Proceedings of the Workshop in Milan, 1995, pp. 163–175. Elioprint, Modena (1995)
Benson, H.P.: On the global optimization of sums of linear fractional functions over a convex set. J. Optim. Theory Appl. 121, 19–39 (2004)
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I—convex underestimating problems Math. Program. 10, 147–175 (1976)
Veinott, A.F.: The supporting hyperplane method for unimodal programming. Oper. Res. 15, 147–152 (1967)