Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật Toán Cải Thiện Và Phân Nhánh Để Tối Ưu Toàn Cầu Các Bài Toán NLP Phi ĐConvex
Tóm tắt
Bài báo này trình bày một thuật toán mới để giải quyết các bài toán lập kế hoạch phi toàn cục (NLP) không lồi. Thuật toán này dựa trên việc giải quyết hai bài toán. Bài toán định hình lại (RP) là một định hình lại thích hợp của bài toán gốc và liên quan đến các thuật ngữ lồi và các thuật ngữ đơn biến lồi. Bài toán chính (MP) là một bài toán NLP không lồi mà xấp xỉ bên ngoài vùng khả thi và đánh giá thấp hàm mục tiêu. MP bao gồm các thuật ngữ lồi và các thuật ngữ là các sản phẩm của các hàm đơn biến lồi và các biến mới. Bằng cách cố định các biến trong các thuật ngữ lồi, một bài toán NLP lồi mà đánh giá cao vùng khả thi và đánh giá thấp hàm mục tiêu được nhận được từ MP. Giống như hầu hết các thuật toán tối ưu hóa toàn cầu xác định, cần phải cung cấp giới hạn cho tất cả các biến trong các thuật ngữ không lồi. MP ép buộc giá trị mục tiêu phải cải thiện và giảm thiểu sự khác biệt giữa giới hạn trên và giới hạn dưới của tất cả các biến đến không hoặc một giá trị dương. Trong trường hợp đầu tiên, một giải pháp khả thi của bài toán gốc được đạt được và hàm mục tiêu được cải thiện. Về cơ bản, trường hợp thứ hai tương ứng với một giải pháp không khả thi của bài toán gốc do sự tồn tại của khoảng trống trong một số biến. Một quy trình phân nhánh được thực hiện để chứng minh rằng không có giải pháp tốt hơn hoặc giảm miền, loại bỏ giải pháp địa phương của MP đã được tìm thấy. Giải pháp MP chỉ ra một điểm khóa để thực hiện việc phân nhánh. Một kỹ thuật giảm giới hạn được thực hiện để tăng tốc độ hội tụ. Kết quả tính toán cho thấy rằng thuật toán này so sánh rất thuận lợi với các phương pháp khác khi áp dụng cho các bài toán thử nghiệm và các bài toán thiết kế quy trình. Nó thường nhanh hơn và có kết quả rất chính xác.
Từ khóa
#Tối ưu hóa toàn cầu #NLP không lồi #thuật toán cải thiện và phân nhánhTài liệu tham khảo
C.S. Adjiman I.P. Androulakis C.A. Floudas (2000) ArticleTitleGlobal optimization of mixed-integer nonlinear problems AIChE Journal 46 IssueID9 1769–1797 Occurrence Handle10.1002/aic.690460908
I. Androulakis C.D. Maranas C.A. Floudas (1995) ArticleTitleαBB: A global optimization method for general constrained nonconvex problems Journal of Global Optimization 7 337–363 Occurrence Handle10.1007/BF01099647
Brooke, A., Kendrick, D., Meeraus, A. and Raman, R., (1997), GAMS Language Guide, Release 2.25, Version 92. GAMS Development Corporation, 1997.
Dixon, L.C.W. and Szegö, G.P. (1978), The global optimisation problem: an introduction, In: Dixon L.C.W. and Szagö P.G.(eds.), Towards Global Optimization 2, North-Holland, Amsterdam.
C.A. Floudas A. Aggarwal R. Ciric (1989) ArticleTitleGlobal optimum search for nonconvex NLP and MINLP problems Computational Chemical Engineering 13 1117–1132
C.A. Floudas R. Ciric (1989) ArticleTitleStrategies for overcoming uncertainties in heat exchanger network synthesis Computational Chemical Engineering 13 1133–1152
C.A. Floudas V. Visweswaran (1993) ArticleTitleA primal-relaxed dual global optimization approach Journal of Optimization Theory and Applications 78 IssueID2 187 Occurrence Handle10.1007/BF00939667
P. Hansen B. Jaumard S.H. Lu (1991) ArticleTitleAn analytical approach to global optimization Mathematical Programming 52 227–254
D.M. Himmelblau (1972) Applied Nonlinear Programming McGraw-Hill New York
Levy, A.V. and Gómez, S. (1985), The tunneling method applied to global optimization, Numerical Optimization, SIAM: 213–244.
C.D. Maranas C.A. Floudas (1994) ArticleTitleA deterministic global optimization approach for molecular structure determination Journal of Chemical Physics 100 IssueID2 1247–1261 Occurrence Handle10.1063/1.467236
C.D. Maranas C.A. Floudas (1995) ArticleTitleFinding all solutions of nonlinearly constrained systems of equations Journal of Global Optimization 7 143–182 Occurrence Handle10.1007/BF01097059
C.D. Maranas C.A. Floudas (1997) ArticleTitleGlobal optimization in generalized geometric programming Computational Chemical Engineering 21 IssueID4 351–369
G.P. McCormick (1972) Converting general nonlinear programming problems to separable nonlinear programming problems The George Washington University Washington D.C.
G.P. McCormick (1976) ArticleTitleComputability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems Mathematical Programming 10 147–175 Occurrence Handle10.1007/BF01580665
I. Quesada I.E. Grossmann (1995) ArticleTitleA Global Optimization algorithm for linear fractional and bilinear programs Journal of Global Optimization 6 39–76 Occurrence Handle10.1007/BF01106605
H.S. Ryoo N.V. Sahinidis (1995) ArticleTitleGlobal optimization of nonconvex NLPs and MINLPs with applications in process design Computational Chemical Engineering 19 IssueID5 551–566
H.S. Ryoo N.V. Sahinidis (1996) ArticleTitleA branch-and-reduce approach for global optimization Journal of Global Optimization 8 107–138 Occurrence Handle10.1007/BF00138689
H.D. Sherali A. Alameddine (1992) ArticleTitleA new reformulation-linearization technique for bilinear programming problems Journal of Global Optimization 2 379–410
E.M.B. Smith C.C. Pantelides (1999) ArticleTitleA symbolic reformulation/spatial branch-and-bound algorithm for the global optimization of nonconvex MINLPs Computational Chemical Engineering 23 457–478
M. Tawarmalani N.V. Sahinidis (2001) ArticleTitleSemidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions Journal of Global Optimization 20 137–158 Occurrence Handle10.1023/A:1011233805045
M. Türkay I.E. Grossmann (1996) ArticleTitleDisjunctive programming techniques for the optimization of process systems with discontinuous investment costs-multiple size regions Industrial Engineering Chemical Research 35 2611–2623
V. Visweswaran C.A. Floudas (1996) New Formulations and Branching Strategies for the GOP Algorithm I.E. Grossmann (Eds) Global Optimization in Engineering Design Kluwer Academic Publishers The Netherlands
T. Westerlund F. Pettersson (1995) ArticleTitleAn extended cutting plane method for solving convex MINLP problems Computational Chemical Engineering 19 131–136
J.M. Zamora I.E. Grossmann (1999) ArticleTitleA branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms Journal of Global Optimization 14 217–249 Occurrence Handle10.1023/A:1008312714792