Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một khung phương pháp phân tích hoạt động nguyên thủy-đối ngẫu hội tụ toàn cục cho tối ưu hóa bậc hai lồi quy mô lớn
Tóm tắt
Chúng tôi trình bày một khung phương pháp phân tích hoạt động nguyên thủy-đối ngẫu để giải quyết các bài toán tối ưu hóa bậc hai lồi quy mô lớn (QP). Khác với các phương pháp phân tích hoạt động cổ điển, khung phương pháp của chúng tôi cho phép nhiều thay đổi đồng thời trong ước lượng tập hợp hoạt động, điều này thường dẫn đến việc xác định nhanh chóng tập hợp hoạt động tối ưu mà không phụ thuộc vào ước lượng ban đầu. Các giá trị lặp của khung phương pháp của chúng tôi chính là những ước lượng tập hợp hoạt động, trong đó cho mỗi ước lượng, một phương pháp giải nguyên thủy-đối ngẫu được xác định duy nhất thông qua một bài toán con rút gọn. Thông qua việc giới thiệu một tập hợp chỉ số phụ trợ cho ước lượng tập hợp hoạt động, cách tiếp cận của chúng tôi kiểm soát toàn cục cho các bài toán QP lồi nghiêm ngặt. Hơn nữa, chi phí tính toán cho mỗi lần lặp thường chỉ cao hơn một chút so với chi phí giải một hệ phương trình tuyến tính rút gọn. Các kết quả số được cung cấp, minh họa rằng hai trường hợp mà chúng tôi đề xuất trong khung phương pháp của chúng tôi là hiệu quả trong thực tế, ngay cả trong các bài toán có điều kiện kém. Chúng tôi quy kết những lợi ích sau này cho mối quan hệ giữa khung phương pháp của chúng tôi và kỹ thuật Newton nửa nhẵn.
Từ khóa
#tối ưu hóa bậc hai lồi #phương pháp phân tích hoạt động #hội tụ toàn cục #phương pháp Newton nửa nhẵnTài liệu tham khảo
Aganagić, M.: Newton’s method for linear complementarity problems. Math. Program. 28(3), 349–362 (1984)
Bergounioux, M., Ito, K., Kunisch, K.: Primal-dual strategy for constrained optimal control problems. SIAM J. Control Optim. 37(4), 1176–1194 (1999)
Bergounioux, M., Kunisch, K.: Primal-dual strategy for state-constrained optimal control problems. Comput. Optim. Appl. 22(2), 193–224 (2002)
Birgin, E.G., Floudas, C.A., Martínez, J.M.: Global minimization using an augmented Lagrangian method with variable lower-level constraints. Math. Program. 125(1), 139–162 (2010)
Byrd, R.H., Chin, G.M., Nocedal, J., Oztoprak, F.: A family of second-order methods for convex \(\ell _1\)-regularized optimization. Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (2012)
Chen, L., Wang, Y., He, G.: A feasible active set QP-free method for nonlinear programming. SIAM J. Optim. 17(2), 401–429 (2006)
Ciarlet, P.G.: The Finite Element Method for Elliptic Problems. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, PA (2002)
Conn, A.R., Gould, N.I.M., Toint, PhL: A globally convergent augmented lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28(2), 545–572 (1991)
Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)
Cryer, C.W.: The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control 9(3), 385–392 (1971)
Feng, L., Linetsky, V., Morales, J.L., Nocedal, J.: On the solution of complementarity problems arising in American options pricing. Optim. Method. Softw. 26(4–5), 813–825 (2011)
Ferreau, H.J., Kirches, C., Potschka, A., Bock, H.G., Diehl, M.: qpOASES: a parametric active-set algorithm for quadratic programming. Math. Program. Comput., 1–37 (2014)
Gharbia, I.B., Gilbert, J.C.: Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix. Math. Program. 134(2), 349–364 (2012)
Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47(1), 99–131 (2005)
Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for SQOPT version 7: software for largescale linear and quadratic programming. Systems Optimization Laboratory, Stanford University, Palo Alto, CA (2006)
Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization. Emerald Group Publishing Limited, Bingley (1982)
Gill, P.E., Robinson, D.P.: Regularized sequential quadratic programming methods. Technical report, Department of Mathematics, University of California, San Diego, La Jolla, CA (2011)
Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: global convergence. SIAM J. Optim. 20(4), 2023–2048 (2010)
Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: local convergence and practical issues. SIAM J. Optim. 20(4), 2049–2079 (2010)
Gould, N.I.M., Robinson, D.P.: A second-derivative SQP method with a “trust-region-free” predictor step. IMA J. Numer. Anal. 32(2), 580–601 (2011)
Gould, N.I.M., Toint, PhL: An iterative working-set method for large-scale nonconvex quadratic programming. Appl. Numer. Math. 43(1), 109–128 (2002)
Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23(4), 707–716 (1986)
Hager, W.W.: The dual active set algorithm. In: Pardalos, P.M. (ed.) Advances in Optimization and Parallel Computing, pp. 137–142. North Holland, Amsterdam (1992)
Hager, W.W., Hearn, D.W.: Application of the dual active set algorithm to quadratic network optimization. Comput. Optim. Appl. 1(4), 349–373 (1993)
Hintermüller, M., Ito, K., Kunisch, K.: The primal-dual active set strategy as a semismooth Newton method. SIAM J. Optim. 13(3), 865–888 (2003)
Kostreva, M.M.: Block pivot methods for solving the complementarity problem. Linear Algebra Appl. 21(3), 207–215 (1978)
Kočvara, M., Zowe, J.: An iterative two-step algorithm for linear complementarity problems. Numerische Mathematik 68(1), 95–106 (1994)
Kunisch, K., Rendl, F.: An infeasible active set method for quadratic problems with simple bounds. SIAM J. Optim. 14(1), 35–52 (2003)
Maros, I., Mészáros, C.: A repository of convex quadratic programming problems. Optim. Method. Softw. 11(1–4), 671–681 (1999)
Moré, J., Toraldo, G.: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1(1), 93–113 (1991)
Nocedal, J., Wright, S.J.: Numerical Optimization 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)
Portugal, L.F., Júdice, J.J., Vicente, L.N.: A comparison of block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables. Math. Comput. 63(208), 625–643 (1994)
Robinson, D.P., Feng, L., Nocedal, J., Pang, J.S.: Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems. SIAM J. Optim. 23(3), 1371–1397 (2013)
Toint, PhL: Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints. Math. Program. 77(3), 69–94 (1997)
Ulbrich, M., Ulbrich, S.: Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function. Math. Program. 95(1), 103–135 (2003)
Vapnik, V., Cortes, C.: Support vector networks. Mach. Learn. 20(3), 273–297 (1995)
Vardi, Y., Shepp, L.A., Kaufman, L.: A statistical model for positron emission tomography. J. Am. Statist. Assoc. 80(389), 8–20 (1985)