Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp khoảng toàn cục cho tối ưu hóa không mịn cục bộ
Tóm tắt
Bài viết thảo luận về một phương pháp khoảng để xác định các nghiệm cục bộ của các bài toán tối ưu hóa không ràng buộc không mịn. Hàm mục tiêu được giả định là địa phương Lipschitz và có các bao gồm khoảng thích hợp. Phương pháp bao gồm hai phần: tìm kiếm cục bộ và tiếp tục toàn cục cùng với việc kết thúc. Tìm kiếm cục bộ sử dụng một thuật toán giảm giá hội tụ toàn cầu cho thấy sự tương đồng với các phương pháp ε-bundle. Trong khi các phương pháp ε-bundle sử dụng đa diện như là các xấp xỉ bên trong của các ε-vi phân, vốn là công cụ chính của hầu hết tất cả các khái niệm bundle, phương pháp của chúng tôi sử dụng các hộp song song với các trục như là các xấp xỉ bên ngoài của các ε-vi phân. Các hộp này được xác định gần như tự động thông qua các kỹ thuật bao gồm của số học khoảng. Kích thước của các hộp bằng với kích thước của bài toán và giữ nguyên trong suốt quá trình tính toán. Việc ứng dụng các hộp không gặp khó khăn từ nhu cầu đầu tư nỗ lực phương pháp và tính toán để điều chỉnh các đa diện theo trạng thái mới nhất của việc tính toán cũng như để đơn giản hóa chúng khi số lượng đỉnh trở nên quá lớn, như trường hợp với các đa diện. Phần thứ hai của phương pháp áp dụng các kỹ thuật khoảng của tối ưu hóa toàn cục cho nghiệm cục bộ gần đúng nhận được từ tìm kiếm ở phần đầu tiên để xác định các giới hạn sai số đảm bảo hoặc cải thiện nghiệm nếu cần thiết. Chúng tôi trình bày các thuật toán nguyên mẫu cho cả hai phần của phương pháp, cũng như lý thuyết hội tụ hoàn chỉnh cho chúng và chứng minh cách mà các xấp xỉ bên ngoài có thể được thu được.
Từ khóa
#tối ưu hóa không mịn #phương pháp khoảng #hội tụ toàn cầu #thuật toán giảm giá #xấp xỉ bên ngoàiTài liệu tham khảo
Androulakis, I.P., Maranas, C.D. and Floudas, C.A. (1995), BB: A global optimization method for general constrained nonconvex problems, Journal of Global Optimization 7: 337–363.
Auslender, A., et al. (eds.) (1981), Lecture Notes in Control and Information Sciences, Vol. 30. Springer Verlag, Berlin.
Berner, S. (1995), Ein paralleles Verfahren zur verifizierten globalen Optimierung. Ph.D. Thesis, Wuppertal.
Clarke, F.H. (1983), Optimization and Nonsmooth Analysis, SIAM. New York.
Evtushenko, Y.G. and Potapov, M.A. (1994), Deterministic Global Optimization, in [50], pp. 481–500.
Goldstein, A.A. (1977), Optimization of Lipschitz continuous functions, Mathematical Programming 13: 14–22.
Giannessi, F. (ed.) (1992), Nonsmooth Optimization: Methods and Applications. Gordon and Breach, Philadelphia.
Hansen, E. (1992), Global Optimization Using Interval Analysis. Dekker, New York.
Hansen, P., Jaumard, B. and Lu, Ski-Hin (1991), An analytical approach to global optimization, Mathematical Programming 52: 227–254.
Hansen, P., Jaumard, B. and Xiong, J. (1993), Decomposition and interval arithmetic applied to the global minimization of polynomial and rational functions, Journal of Global Optimization 3: 421–437.
Hansen, P. and Jaumard, B. (1995), Lipschitz optimization, in [15], pp. 407–493.
Herzberger, H. (ed.) (1994), Topics in Validated Computations. Elsevier, Amsterdam.
Hiriart-Urruty, J.-B. and Lemaréchal, C. (1993), Convex Analysis and Minimization Algorithms I. Springer Verlag, Berlin.
Hiriart-Urruty, J.-B. and Lemaréchal, C. (1993), Convex Analysis and Minimization Algorithms II. Springer Verlag, Berlin.
Horst, R. and Pardalos, P.M. (eds.) (1995), Handbook of Global Optimization. Kluwer, Dordrecht.
Horst, R., Pardalos, P.M. and Thoai, N.V. (1995), Introduction to Global Optimization. Kluwer, Dordrecht.
Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches. Springer Verlag, Berlin.
Jansson, C. (1994), On self-validating methods for optimization problems, in [12], pp. 381–438.
Jansson, C. and Knüppel, O. (1995), A branch and bound algorithm for bound constrained optimization problems without derivatives, Journal of Global Optimization 7: 297–331.
Kearfott, R.B. (1996), A review of techniques in the verified solution of constrained global optimization problems, in [22], pp. 23–59.
Kearfott, R.B. (1996), Interval extensions of non-smooth functions for global optimization and nonlinear systems solvers, Computing 57: 149–162.
Kearfott, R.B. and V. Kreinovich, (eds.) (1996), Applications of Interval Computations. Kluwer, Dordrecht.
Kiwiel, K.C. (1985), Methods of Descent in Nonsmooth Optimization. Springer Verlag, Berlin.
Kiwiel, K.C. (1992), A restricted step proximal bundle method for nonconvex nondifferentiable optimization, in [7], pp. 175–188.
Lemaréchal, C. (1981), A view of line-searches, in [2], pp. 59–78.
Lemaréchal, C. (1989), Nondifferentiable optimization, in [37], pp. 529–572.
Lemaréchal, C. (1992), Langrangian decomposition and nonsmooth optimization: Bundle algorithm, prox iteration, augmented langrangian, in [7], pp. 201–216.
Lemaréchal, C. and Zowe, J. (1994), A condensened introduction to bundle methods in nonsmooth optimization, in [50], pp. 357–382.
McCormick, G.P. (1983), Nonlinear Programming. Wiley, New York.
Mäkelä, M. and Neittaanmäki, P. (1992), Nonsmooth Optimization-Analysis and Algorithms with Applications to Optimal Control. World Scientific, Singapore.
Mayne, D.Q. and Polak, E. (1984), Outer approximation algorithm for nondifferentiable optimization problems, Journal of Optimization Theory and Applications 42: 19–30.
Mayne, D.Q., Polak, E. and Wardi, Y. (1983), On the extension of constrained optimization algorithms from differentiable to nondifferentiable problems, SIAM Journal of Control and Optimization 21: 179–203.
Mifflin, R. (1982), A Modification and an extension of Lemaréchal's algorithm for nonsmooth minimization, Mathematical Programming Study 17: 77–90.
Mifflin, R. (1992), Ideas for developing a rapidly convergent algorithm for nonsmooth minimization, in [7], pp. 228–239.
Moore, R.E. (1966), Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J.
Moore, R.E. (ed.) (1988), Reliability in Computing: The Role of Interval Mathematics. Academic Press, San Diego.
Nemhauser, et al. (1989), Handbooks in Operation Research & Management Science, Vol. I: Optimization. Elsevier Science Publishers, Amsterdam.
Pintér, J.D. (1996), Global Optimization in Action. Kluwer, Dordrecht.
Ratschek, H. (1988), Some recent aspects of interval algorithms for global optimization, in [36], pp. 325–339.
Ratschek, H. and Rokne, J. (1984), Computer Methods for the Range of Functions. Horwood, Chichester.
Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global Optimization. Horwood, Chichester.
Ratschek, H. and Rokne, J. (1995), Interval methods, in [15], pp. 751–828.
Ratschek, H. and Voller, R. (1990), Unconstrained optimization over unbounded domains, SIAM Journal of Control and Optimization 28: 528–539.
Ratz, D. (1992), Automatische Ergebnisverifikation bei globalen Optimierungsproblemen. Ph.D. thesis, Karlsruhe.
Ratz, D. and Csendes, T. (1995), On the selection of subdivision directions in interval branchand-bound methods for global optimization, Journal of Global Optimization 7: 183–207.
Robinson, S.M. (1973), Computable error bounds for nonlinear programming, Mathematical Programming 5: 235–242.
Schittkowski, K. (ed.) (1985), Computational Mathematical Programming. Springer Verlag, Berlin.
Schramm, H. and Zowe, J. (1992), A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM Journal of Optimization 2: 121–152.
Shor, N.Z. (1985), Minimization Methods for Nondifferentiable Functions. Springer Verlag, Berlin.
Spedicato, E. (ed.) (1994), Algorithms for Continuous Optimization: The State of Art. Kluwer, Dordrecht.
Stahl, V. (1995), Interval Methods for Bounding the Range of Polynomials and Solving Systems of Linear Equations. Ph.D. thesis, Linz.
Törn, A.A. and Žilinkas, A. (1989), Global Optimization. Springer Verlag, Berlin.
Wolfe, M.A. and Zhang, L.S. (1994), An interval algorithm for nondifferentiable global optimization, Applied Mathematics and Computation 63: 101–122.
Zowe, J. (1985), Nondifferentiable optimization, in [47], pp. 323–356.