Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một Thuật Toán Theo Đường Mới Cho Các Vấn Đề Kết Hợp Không Tuyến Tính P*
Tóm tắt
Dựa trên những kết quả lý thuyết gần đây của Zhao và Li [Math. Oper. Res., 26 (2001), tr. 119—146], chúng tôi trình bày trong bài báo này một phương pháp theo đường mới cho các vấn đề kết hợp không tuyến tính P*. Khác với hầu hết các thuật toán điểm trong hiện tại dựa trên đường trung tâm, thuật toán này theo dõi 'đường trung tâm điều chỉnh' mà tồn tại cho bất kỳ vấn đề P* liên tục nào. Kết quả cho thấy rằng thuật toán này hội tụ toàn cục cho bất kỳ vấn đề P* nào với điều kiện tập nghiệm của nó không rỗng. Bằng cách lựa chọn khác nhau các tham số trong thuật toán, chuỗi lặp có thể tiếp cận đến các loại điểm khác nhau trong tập nghiệm. Hơn nữa, sự hội tụ siêu tuyến tính địa phương của thuật toán này cũng có thể đạt được dưới một số điều kiện nhất định.
Từ khóa
#thuật toán theo đường #vấn đề kết hợp không tuyến tính #hội tụ toàn cục #hội tụ siêu tuyến tínhTài liệu tham khảo
B.H. Ahn, “Iterative methods for linear complementarity problem with uperbounds and lower-bounds,” Math. Programming, vol. 26, pp. 265–315, 1983.
E.D. Andersen and Y. Ye, “On a homogeneous algorithm for the monotone complementarity problem,” Math. Programming, vol. 84, pp. 375–399, 1999.
M. Anitescu, G. Lesaja and F.A. Potra, “An infeasible-interior-point predictor-corrector algorithm for the P*-geometric LCP,” Appl. Math. Optim., vol. 36, pp. 203–228, 1997.
J.V. Burke and S. Xu, “The global linear convergence of a non-interior path-following algorithm for linear complementarity problems,” Math. Oper. Res., vol. 23, pp. 719–734, 1998.
J.V. Burke and S. Xu, “A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem,” Math. Programming, vol. 87, pp. 113–130, 2000.
B. Chen and X. Chen, “A global and local superlinear continuation method for P0 and R 0 and monotone NCP,” SIAM J. Optim., vol. 9, pp. 624–645, 1999.
R.W. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press: Boston, 1992.
R.W. Cottle, J.S. Pang, and V. Venkateswaran, “Sufficient matrices and the linear complementarity problem,” Linear Algebra Appl., vols. 114/115, pp. 231–249, 1989.
F. Facchinei, “Structural and stability properties of P0 nonlinear complementarity problems,” Math. Oper. Res., vol. 23, pp. 735–745, 1998.
F. Facchinei and C. Kanzow, “Beyond monotonicity in regularization methods for nonlinear complementarity problems,” SIAM J. Control Optim., vol. 37, pp. 1150–1161, 1999.
F. Facchinei and J.S. Pang, “Finite-dimensional variational inequalities and complementarity problems,” vols. 1 and 2, Springer-Verlag, New York, 2003.
Y. Fathi, “Computational complexity of LCPs associated with positive definite matrices,” Math. Programming, vol. 17, pp. 335–344, 1979.
T. Hansen and T.C. Koopmans, “On the definition and computation of a capital stock invariant under optimization,” J. Economic Theory, vol. 5, pp. 487–523, 1972.
Z. Huang, J. Han, and Z. Chen, “Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function,” J. Optim. Theory Appl., vol. 117, pp. 39–68, 2003.
Z. Huang, “Locating a maximally complementarity solution of the monotone NCP by using non-interior-point smoothing algorithm,” Mathematical Methods of Operations Research vol. 61, pp. 41–55, 2005.
G. Isac, “Tikhonov’s regularization and the complementarity problem in Hilbert space,” J. Math. Anal. Appl., vol. 174, pp. 53–66, 1991.
B. Jansen, C. Roos, T. Terlaky, and A. Yoshise, “Polynomiality of primal dual affine scaling algorithm for nonlinear complementarity problems,” Math. Programming, vol. 78, pp. 315–345, 1997.
C. Jones and M.S. Gowda, “On the connectedness of solution sets in linear complementarity problems,” Linear Algebra Appl., vol. 272, pp. 33–44, 1998.
M. Kojima, N. Megiddo, and T. Noma, “Homotopy continuation methods for nonlinear complementarity problems,” Math. Oper. Res., vol. 16, pp. 754–774, 1991.
M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, “A unified approach to interior point algorithms for linear complementarity problems,” Lecture Notes in Computer Sciences, 538, Springer-Verlag: New York, 1991.
M. Kojima, M. Mizuno, and T. Noma, “Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems,” Math. Oper. Res., vol. 43, pp. 662–675, 1990.
K.G. Murty, “Linear Complementarity, Linear and Nonlinear Programming,” Sigma Ser. Appl. Math. 3, Heldermann-Verlag: Berlin, 1988.
J.S. Pang and S.A. Gabriel, “NE/SQP: A robust algorithm for the nonlinear complementarity problem,” Math. Programming, vol. 60, pp. 295–338, 1993.
F.A. Potra and R. Sheng, “Predictor-corrector algorithm for solving P*κ-matrix LCP from arbitrary positive starting points,” Math. Programming, vol. 76, pp. 223–244, 1997.
F.A. Potra and R. Sheng, “A large-step infeasible-interior-point method for the P*-matrix LCP,” SIAM J. Optim., vol. 7, pp. 318–335, 1997.
L. Qi, “Convergence analysis of some algorithms for solving nonsmooth equations,” Math. Oper. Res., vol. 18, pp. 227–243, 1993.
G. Ravindran and M.S. Gowda, “Regularization of P0-functions in box variational inequality problems,” SIAM J. Optim., vol. 11, pp. 748–760, 2000.
J. Stoer and M. Wechs, “Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity,” Math. Programming, vol. 83, pp. 407–423, 1998.
J. Stoer, M. Wechs, and S. Mizuno, “High order infeasible-interior-point methods for solving sufficient linear complementarity problems,” Math. Oper. Res., vol. 23, pp. 832–862, 1998.
R. Sznajder and M.S. Gowda, “On the limiting behavior of the trajectory of regularized solutions of P0 complementarity problems,” in Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, and L. Qi (Eds.), Kluwer Academic Publishers, 1998, pp. 371–379.
P. Tseng, “Error Bounds for Regularized Complementarity Problems,” Report, Department of Mathematics, University of Washington, Seattle, 1998.
P. Tseng, “An infeasible path-following method for monotone complementarity problems,” SIAM J. Optim., vol. 7, pp. 386–402, 1997.
L.T. Watson, “Solving the nonlinear complementarity problem by a homotopy method,” SIAM J. Control Optim., vol. 17, pp. 36–46, 1979.
S. Wright and D. Ralph, “Superlinear infeasible-interior-point algorithm for monotone complementarity problems,” Math. Oper. Res., vol. 21, pp. 815–838, 1996.
S. Xu and J.V. Burke, “A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques,” Math. Programming, vol. 86, pp. 91–103, 1999.
Y. Ye, “On homogeneous and self-dual algorithms for LCP,” Math. Programming, vol. 76, pp. 211–222, 1997.
Y. Ye, Interior Point Algorithms Theory and Analysis, John Wiley and Sons: Chichester, UK, 1997.
Y.B. Zhao and G. Isac, “Properties of a multi-valued mapping associated with some nonmonotone complementarity problems,” SIAM J. Control Optim., vol. 39, pp. 571–593, 2000.
Y.B. Zhao and D. Li, “Strict feasibility conditions of complementarity problems,” J. Optim. Theory Appl., vol. 107, pp. 641–664, 2000.
Y.B. Zhao and D. Li, “On a new homotopy continuation trajectory for complementarity problems,” Math. Oper. Res., vol. 26, pp. 119–146, 2001.
Y.B. Zhao and D. Li, “Existence and limiting behavior of a non-interior-point trajectory for complementarity problems without strictly feasible condition,” SIAM J. Control Optim., vol. 40, pp. 898–924, 2001.