Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sự bình tĩnh của các hệ thống ràng buộc tuyến tính dưới các nhiễu cấu trúc với ứng dụng vào sơ đồ theo dõi đường đi
Tóm tắt
Chúng tôi quan tâm đến các hệ thống ràng buộc tuyến tính hữu hạn trong một khuôn khổ tham số, trong đó hệ số bên phải là một hàm đồng tuyến tính của tham số nhiễu. Những nhiễu có cấu trúc như vậy cung cấp một khuôn khổ thống nhất cho các mô hình tham số khác nhau trong tài liệu, chẳng hạn như nhiễu khối, nhiễu định hướng và/hoặc nhiễu một phần của cả bất đẳng thức và đẳng thức. Chúng tôi mở rộng một số kết quả gần đây về tính bình tĩnh của ánh xạ tập hợp khả thi và cung cấp một ứng dụng cho sự hội tụ của một sơ đồ thuật toán theo dõi đường đi nhất định. Chúng tôi nhấn mạnh rằng công thức của chúng tôi cho mô đun tính bình tĩnh chỉ phụ thuộc vào dữ liệu danh nghĩa, điều này khiến nó có thể tính toán trong thực tế.
Từ khóa
#hệ thống ràng buộc tuyến tính; nhiễu cấu trúc; tính bình tĩnh; sàng lọc đường đi; thuật toán hội tụTài liệu tham khảo
Al-Jeiroudi, G., Gondzio, J., Hall, J.: Preconditioning indefinite systems in interior point methods for large scale linear optimization. Optim. Methods Softw. 23, 345–363 (2008)
Bai, K., Ye, J.J., Zhang, J.: Directional quasi/pseudo-normality as sufficient conditions for metric subregularity. SIAM J. Optim. 29, 2625–2649 (2019)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (1993)
Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization, Athena Scientific, Dynamic Ideas, Belmont, Massachusetts (1997)
Cánovas, M.J., Gómez-Senent, F.J., Parra, J.: Regularity modulus of intersection mappings. Application to the stability of squations via splitting into inequalities. J. Convex Anal. 19, 913–926 (2012)
Cánovas, M. J., Hall, J.A.J., López, M. A., Parra, J.: Calmness of partially perturbed linear systems with an application to the central path. Optimization 68, 465–483 (2019)
Cánovas, M.J., Henrion, R., López, M.A., Parra, J.: Outer limits of subdifferentials and calmness moduli in linear and nonlinear programming. J. Optim. Theory Appl. 169, 925–952 (2016)
Cánovas, M.J., Klatte, D., López, M.A., Parra, J.: Metric regularity in convex semi-infinite optimization under canonical perturbations. SIAM J. Optim. 18, 717–732 (2007)
Cánovas, M.J., López, M.A., Mordukhovich, B.S., Parra, J.: Quantitative stability of linear inequality systems under block perturbations with applications to convex systems. Top 20, 310–327 (2012)
Cánovas, M.J., López, M.A., Mordukhovich, B.S., Parra, J.: Subdifferentials and stability analysis of feasible set and Pareto front mappings in linear multiobjective optimization. Vietnam J. Math 48, 315–334 (2020)
Cánovas, M.J., López, M.A., Parra, J., Toledo, F.J.: Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 22, 375–389 (2014)
Cánovas, M.J., Parra, J., Rückmann, J.-J., Toledo, F.J.: Point-based neighborhoods for sharp calmness constants in linear programming. Set-Valued Var. Anal. 25, 757–772 (2017)
Dontchev, A.L., Rockafellar, R.T.: Implicit Functions Mappings, Solution: A View from Variational Analysis. Springer, New York (2009)
Facchinei, F., Fischer, A., Herrich, M.: An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions. Math. Program, Ser. A 146, 1–36 (2014)
Goberna, M.A., López, M. A.: Linear Semi-Infinite Optimization. John Wiley & Sons, Chichester (UK) (1998)
Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)
Hu, H.: Characterizations of the strong basic constraint qualifications. Math Oper Res. 30, 956–965 (2005)
Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49, 263–265 (1952)
Ioffe, A.D.: Variational Analysis of Regular Mappings. Springer, Cham (2017)
Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984)
Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications, Nonconvex Optim Appl, vol. 60. Kluwer Academic, Dordrecht, The Netherlands (2002)
Klatte, D., Kummer, B.: Optimization methods stability of inclusions in Banach spaces. Math Program. B 117, 305–330 (2009)
Klatte, D., Kummer, B.: Approximations and generalized Newton methods. Math. Program. Ser. B 168, 673–716 (2018)
Kruger, A., Ngai, H.V.A.N., Théra, M.: Stability of error bounds for convex constraint systems in Banach spaces. SIAM J. Optim. 20, 3280–3296 (2010)
Li, M.H., Meng, K.W., Yang, X.Q.: On error bound moduli for locally Lipschitz and regular functions. Math. Program. Ser. A 171, 463–487 (2018)
Mangasarian, O.L., Fromovitz, S.: The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints. J. Math. Anal. Appl. 17, 37–47 (1967)
Megiddo, N. In: Megiddo, N. (ed.) : Pathways to the Optimal Set in Linear Programming, in Progress in Mathematical Programming, pp 131–158. Springer-Verlag, New York (1989)
Monteiro, R.D.C., Adler, I.: Interior path following primal-dual algorithms. Part I: Linear programming. Math. Program 44, 27–41 (1989)
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory. Springer, Berlin (2006)
Potra, F.A., Wright, S.J., Interior-point methods: J. Comput. Appl. Math. 124, 281–302 (2000)
Potra, F.A.: Q-superlinear convergence of the iterates in primal-dual interior-point methods. Math. Program., Ser. A 91, 99–115 (2001)
Renegar, J.: A polynomial time algorithm based on Newton’s method for linear programming. Math. Program 40, 59–93 (1988)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, N.J. (1970)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Wang, X., Ye, J.J., Yuan, X., Zeng, S., Zhang, J.: Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis. Set-Valued Var. Anal. https://doi.org/10.1007/s11228-020-00570-0(2021)
Zhang, Y., Tapia, R.A., Dennis, J.E.: On the superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms. SIAM J. Optim. 2, 304–324 (1992)