Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân tích hội tụ của một thuật toán phạt cho tối ưu hóa không mượt mà và hiệu suất của nó trong việc giải quyết các bài toán hình cầu khó
Tóm tắt
Công trình này xây dựng dựa trên các kết quả lý thuyết và số liệu của Thuật toán Phạt cho Tối ưu hóa Không mượt mà có Ràng buộc (PACNO) được đề xuất gần đây. Đóng góp của chúng tôi là ba điểm chính. Thay vì chỉ dựa trên các điểm dừng gần đúng của các bài toán con, chúng tôi giả định rằng các điểm tối thiểu cục bộ gần đúng đã được tính toán. Do đó, một kết quả hội tụ mạnh mẽ hơn được đạt được, dựa trên một điều kiện tối ưu liên tiếp mới. Hơn nữa, bằng cách sử dụng một khung tối thiểu hóa hộp đen và các trường hợp hình cầu cứng, các tham số nội tại của PACNO đã được điều chỉnh, cải thiện kết quả từ tài liệu cho bài toán hôn nhau, bao gồm xác định số lượng tối đa các hình cầu không chồng chéo và bằng nhau có thể chạm vào cùng một hình cầu cùng kích thước. Cuối cùng, bài toán hôn nhau đôi được mô hình hóa: hai hình cầu bằng nhau và tiếp xúc được đưa ra, và mục tiêu là tìm số lượng tối đa các hình cầu không chồng chéo, có cùng bán kính với cặp hình cầu đã cho, có thể được sắp xếp sao cho mỗi hình cầu chạm ít nhất một trong số các hình cầu đã nêu. Một công thức không mượt cho bài toán hôn nhau đôi đã được thiết kế, và các giải pháp cho các trường hợp hai, ba và bốn chiều đã được đạt được thành công.
Từ khóa
#Tối ưu hóa không mượt mà #thuật toán phạt #hội tụ #bài toán hôn nhau #hình cầu cứng.Tài liệu tham khảo
Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization 60(5), 627–641 (2011)
Andreani, R., Martínez, J.M., Svaiter, B.F.: A new sequential optimality condition for constrained optimization and algorithmic consequences. SIAM J. Optim. 20(6), 3533–3554 (2010)
Andreani, R., Martínez, J.M., Ramos, A., Silva, P.J.: Strict constraint qualifications and sequential optimality conditions for constrained optimization. Math. Oper. Res. 43(3), 693–717 (2018)
Audet, C., Béchard, V., Le Digabel, S.: Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J. Glob. Optim. 41(2), 299–318 (2008)
Audet, C., Dennis, J.E. Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188–217 (2006)
Audet, C., Dennis, J.E. Jr., Le Digabel, S.: Globalization strategies for mesh adaptive direct search. Comput. Optim. Appl. 46(2), 193–215 (2010)
Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer, Cham (2017)
Audet, C., Le Digabel, S., Tribes, C., Montplaisir, V.R.: The nomad project. software available at https://www.gerad.ca/nomad. Last access in September 11 (2019)
Audet, C., Orban, D.: Finding optimal algorithmic parameters using derivative-free optimization. SIAM J. Optim. 17(3), 642–664 (2006)
Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2014). https://doi.org/10.1137/1.9781611973365
Bourguignon, J.P., Jeltsch, R., Pinto, A., Viana, M. (eds.): Mathematics of Energy and Climate Change (International Conference and Advanced School Planet Earth, Portugal March 21–28. CIM Series in Mathematical Sciences, vol. 2013. Springer, Switzerland (2015)
Boyvalenkov, P.G., Danev, D.P., Bumova, S.P.: Upper bounds on the minimum distance of spherical codes. IEEE Trans. Informatuoi Theory 42(5), 1576–1581 (1996)
Burachik, R., Kaya, Y.: An augmented penalty function method with penalty parameter updates for nonconvex optimization. Nonlinear Anal. 75(3), 1158–1167 (2012)
Burke, J.: Calmness and exact penalization. SIAM J. Control. Optim. 29(2), 493–497 (1991)
Burke, J.V.: An exact penalization viewpoint of constrained optimization. SIAM J. Control. Optim. 29(4), 968–998 (1991)
Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., Simões, L.E.A.: Gradient sampling methods for nonsmooth optimization ArXiv e-prints (2018)
Burke, J.V., Lewis, A.S., Overton, M.L.: Approximating subdifferentials by random sampling of gradients. Math. Oper. Res. 27(3), 567–584 (2002)
Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15 (3), 751–779 (2005)
Castelani, E.V., Martinez, A.L.M., Martínez, J.M., Svaiter, B.F.: Addressing the greediness phenomenon in nonlinear programming by means of proximal augmented Lagrangians. Comput. Optim. Applic. 46(2), 229–245 (2010)
Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)
Conn, A., Gould, G., Toint, P.: LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A). Springer, Berlin (1992)
Conway, J.H., Sloane, N.J.C.: Sphere Packings, Lattices and Groups. Springer, New York (1988)
Curtis, F.E., Mitchell, T., Overton, M.L.: A BFGS-SQP method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles. Optim. Methods Softw. 32(1), 148–181 (2017)
Curtis, F.E., Overton, M.L.: A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM J. Optim. 22(2), 474–500 (2012)
Dutta, J., Deb, K., Tulshyan, R., Arora, R.: Approximate KKT points and a proximity measure for termination. J. Glob. Optim. 56(4), 1463–1499 (2013)
Flatley, L.C., Theil, F.: Face-centered cubic crystallization of atomisitc configurations. Arch. Ration. Mech. Anal. 218, 363–416 (2015)
Gill, P.E., Kungurtsev, V., Robinson, D.P.: A stabilized SQP method: Global convergence. IMA J. Numer. Anal. 37(1), 407–443 (2017)
Gill, P.E., Kungurtsev, V., Robinson, D.P.: A shifted primal-dual interior method for nonlinear optimization. (Optimization Online) (2018)
Goldstein, A.A.: Optimization of Lipschitz continuous functions. Math. Program. 13(1), 14–22 (1977)
Gomes-Ruggiero, M.A., Martínez, J.M., Santos, S.A.: Spectral projected gradient method with inexact restoration for minimization with nonconvex constraints. SIAM J. Sci. Comput. 31(3), 1628–1652 (2009)
Helou, E.S., Santos, S.A., Simões, L. E. A.: On the differentiability check in gradient sampling methods. Optim. Methods Softw. 31(5), 983–1007 (2016)
Helou, E.S., Santos, S.A., Simões, L. E. A.: A new sequential optimality condition for constrained nonsmooth optimization. SIAM J. Optim. 30 (2), 1610–1637 (2020)
Jenssen, M., Joos, F., Perkins, W.: On kissing numbers and spherical codes in high dimensions. Adv. Math. 335, 307–321 (2018)
Kappel, F., Kuntsevich, A.V.: An implementation of Shor’s r-Algorithm. Comput. Optim. Appl. 15(2), 193–205 (2000)
Karas, E.W., Pilotta, E.A., Ribeiro, A.A.: Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems. Comput. Optim. Appl. 44, 427–441 (2009)
Kiwiel, K.C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18(2), 379–388 (2007)
Kovacevic, R.M., Pflug, G.C., Vespucci, M.T. (eds.): Handbook of Risk Management in Energy Production and Trading International Series in Operations Research & Management Science, vol. 199. Springer, New York (2013)
Krejiċ, N., Martínez, J.M., Mello, M.P., Pilotta, E.A.: Validation of an augmented Lagrangian algorithm with a Gauss-N,ewton Hessian approximation using a set of hard-spheres problems. Comput. Optim. Applic. 16(3), 247–263 (2000)
Kucherenko, S., Belotti, P., Liberti, L., Maculan, N.: New formulations for the kissing number problem. Discret. Appl. Math. 155, 1837–1841 (2007)
Le Digabel, S.: Algorithm 909: Nomad: Nonlinear optimization with the mads algorithm. ACM Trans. Math. Softw. 37(4), 44:1–44:15 (2011)
Loucks, D., Stedinger, J., Haith, D.: Water Resource Systems Planning and Analysis. Englewood Cliffs, New Jersey (1981)
Machado, F.C., de Oliveira Filho, F.M.: Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry. Exp. Math., 1–8. https://doi.org/10.1080/10586458.2017.1286273 (2017)
Martínez, L., Andrade, R., Birgin, E.G., Martínez, J.M.: Packmol: A package for building initial configurations for molecular dynamics simulations. J. Comput. Chem. 30(13), 2157–2164 (2009)
Sagastizábal, C.: Divide to conquer: Decomposition methods for energy optimization. Math. Program. 134(1), 187–222 (2012)
Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106, 25–57 (2006)