Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Khung Josephy–Newton không chính xác cho các phương trình tổng quát và ứng dụng của nó trong phân tích cục bộ các phương pháp Newton cho tối ưu hóa có ràng buộc
Tóm tắt
Chúng tôi đề xuất và phân tích một phiên bản có ngẫu nhiên của phương pháp Josephy–Newton cổ điển để giải quyết các phương trình tổng quát. Khung có ngẫu nhiên này thuận tiện để xử lý một cách thống nhất lập trình bậc hai tuần tự tiêu chuẩn, phiên bản ổn định của nó, lập trình bậc hai có ràng buộc tuần tự và các phương pháp Lagrange có ràng buộc tuyến tính. Đặc biệt cho các phương pháp Lagrange có ràng buộc tuyến tính, chúng tôi đạt được sự hội tụ siêu tuyến tính dưới điều kiện tối ưu đủ bậc hai và điều kiện đủ ràng buộc Mangasarian–Fromovitz nghiêm ngặt, trong khi các kết quả trước đó trong tài liệu giả định (ngoài tính đủ bậc hai) điều kiện đủ ràng buộc độc lập tuyến tính mạnh hơn cũng như điều kiện bổ sung nghiêm ngặt. Đối với các phương pháp lập trình bậc hai có ràng buộc tuần tự, chúng tôi chứng minh sự hội tụ siêu tuyến tính/quadratic theo dạng nguyên - đối ngẫu dưới cùng các giả định như trên, điều này cũng mang đến một kết quả mới.
Từ khóa
#Josephy–Newton #phương trình tổng quát #tối ưu hóa có ràng buộc #hội tụ siêu tuyến tính #lập trình bậc hai tuần tựTài liệu tham khảo
An, L.T.H.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Math. Program. 87, 401–426 (2000)
Anitescu, M.: A superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming. SIAM J. Optim. 12, 949–978 (2002)
Arutyunov, A.V., Izmailov, A.F.: Sensitivity analysis for cone-constrained optimization problems under the relaxed constraint qualifications. Math. Oper. Res. 30, 333–353 (2005)
Audet, C., Hansen, P., Jaumard, B., Savard, G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87, 131–152 (2000)
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)
Boggs, B.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1996)
Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006)
Dennis, J.E., Moré, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28, 549–560 (1974)
Fernández, D., Solodov, M.: On local convergence of sequential quadratically-constrained quadratic-programming type methods, with an extension to variational problems. Comput. Optim. Appl. 39, 143–160 (2008)
Fernández, D., Solodov, M.: Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems. Math. Program. (2009). DOI 10.1007/s10107-008-0255-4
Fischer, A.: Local behavior of an iterative framework for generalized equations with nonisolated solutions. Math. Program. 94, 91–124 (2002)
Friedlander, M.P., Saunders, M.A.: A globally convergent linearly constrained Lagrangian method for nonlinear optimization. SIAM J. Optim. 15, 863–897 (2005)
Fukushima, M., Luo, Z.-Q., Tseng, P.: A sequential quadratically constrained quadratic programming method for differentiable convex minimization. SIAM J. Optim. 13, 1098–1119 (2003)
Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12, 253–273 (1999)
Huang, Z.-H., Sun, D., Zhao, G.: A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput. Optim. Appl. 35, 199–237 (2006)
Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report no. 1965, Mathematics Research Center, University of Wisconsin, Madison (1979)
Josephy, N.H.: Quasi-Newton methods for generalized equations. Technical Summary Report no. 1966, Mathematics Research Center, University of Wisconsin, Madison (1979)
Kantorovich, L.V., Akilov, G.P.: Functional Analysis, 2nd edn. Pergamon, Oxford (1982)
Kruk, S., Wolkowicz, H.: Sequential, quadratically constrained, quadratic programming for general nonlinear programming. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, pp. 563–575. Kluwer Academic, Dordrecht (2000)
Li, D.-H., Qi, L.: Stabilized SQP method via linear equations. Appl. Math. Techn. Rept. AMR00/5, Univ. New South Wales, Sydney (2000)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
Murtagh, B.A., Saunders, M.A.: A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints. Math. Program. Study 16, 84–117 (1982)
Nesterov, Y.E., Nemirovskii, A.S.: Interior Point Polynomial Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia (1993)
Panin, V.M.: A second-order method for discrete min-max problem. USSR Comput. Math. Math. Phys. 19, 90–100 (1979)
Robinson, S.M.: A quadratically convergent algorithm for general nonlinear programming problems. Math. Program. 3, 145–156 (1972)
Robinson, S.M.: Perturbed Kuhn–Tucker points and rates of convergence for a class of nonlinear-programming algorithms. Math. Program. 7, 1–16 (1974)
Robinson, S.M.: Stability theorems for systems of inequalities, Part II: Differentiable nonlinear systems. SIAM J. Numer. Anal. 13, 497–513 (1976)
Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43–62 (1980)
Solodov, M.V.: On the sequential quadratically constrained quadratic programming methods. Math. Oper. Res. 29, 64–79 (2004)
Wiest, E.J., Polak, E.: A generalized quadratic programming-based phase-I–phase-II method for inequality-constrained optimization. Appl. Math. Optim. 26, 223–252 (1992)
Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11, 253–275 (1998)
Wright, S.J.: Modifying SQP for degenerate problems. SIAM J. Optim. 13, 470–497 (2002)
Wright, S.J.: Constraint identification and algorithm stabilization for degenerate nonlinear programs. Math. Program. 95, 137–160 (2003)