最优化与变分不等式的可行解序列的有限终止性

摘要/Abstract

摘要：

为了在更弱的条件下, 给出最优化问题 (OP) 与变分不等式问题 (VIP) 的可行解序列的有限终止性, 在这类问题的解集上引进了一个增广映射, 分别建立了解集关于可行解序列广义弱尖锐性的概念. 这个新概念是传统的弱尖锐性与强非退化概念的扩充与推广, 其克服了最优化与变分不等式在许多情况下解集不具有弱尖锐性或强非退化性的缺陷. 在这些问题的解集满足广义弱尖锐性的条件下, 提供其可行解序列有限终止于解集的充分与必要条件. 这些结果是现有相关文献中在弱尖锐或强非退化条件下相应结果的推广, 同时也为许多最优化算法的有限终止性提供了更弱的充分条件.

关键词: 最优化问题, 变分不等式问题, 可行解序列, 广义弱尖锐性, 有限终止性

Abstract:

To provide a finite characterization of feasible solution sequences for optimization problems (OP) and variational inequality problems (VIP), an augmented set value map is introduced for the solution sets of these problems. Additionally, the concepts of augmented weak sharpness with respect to feasible solution sequences are established. These novel notions extend the traditional concepts of weak sharpness and strongly non-degeneracy relative to feasible solution sequences, addressing the limitation that solution sets often lack weak sharpness or strongly non-degeneracy in many cases. When the feasible solution sets of optimization problems and variational inequality problems exhibit augmented weak sharpness, the necessary and sufficient conditions for the finite termination of feasible solution sequences are provided for each problem. These conditions extend the corresponding results found in existing literature, where solution sets are weak sharp or strongly non-degenerate. Furthermore, sufficient conditions with fewer restrictions are provided for the finite termination of various optimization algorithms.

Key words: Optimization problem, Variational inequality problem, Feasible solution sequence, Augmented weak sharpness, Finite termination

中图分类号:

O224

王茹钰, 赵文玲, 宋道金. 最优化与变分不等式的可行解序列的有限终止性[J]. 数学物理学报, 2024, 44(4): 1037-1051.

Wang Ruyu, Zhao Wenling, Song Daojin. The Finite Termination of Feasible Solution Sequence for Optimization and Variational Inequality[J]. Acta mathematica scientia,Series A, 2024, 44(4): 1037-1051.

参考文献 38

[1]	Rockafellar R T, Wets R J B. Variational Analysis. New York: Springer Science & Business Media, 2009
[2]	Rockafellar R T. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 1976, 14(5): 877-898
[3]	Polyak B T. Introduction to Optimization. New York: Optimization Software, 1987: 1-32
[4]	Ferris M C. Weak Sharp Minima and Penalty Functions in Mathematical Programming. Cambridge: University of Cambridge, 1988
[5]	Ansari Q H, Babu F, Yao J C. Regularization of proximal point algorithms in Hadamard manifolds. Journal of Fixed Point Theory and Applications, 2019, 21: 1-23
[6]	Dinis B, Pinto P. Metastability of the proximal point algorithm with multi-parameters. Portugaliae Mathematica, 2020, 77(3): 345-381
[7]	Ferris M C. Finite termination of the proximal point algorithm. Mathematical Programming, 1991, 50: 359-366
[8]	Kim J L, Toulis P, Kyrillidis A. Convergence and stability of the stochastic proximal point algorithm with momentum. Proc Machine Learn Res, 2022, 168: 1034-1047
[9]	Matsushita S, Xu L. Finite termination of the proximal point algorithm in Banach spaces. Journal of Mathematical Analysis and Applications, 2012, 387(2): 765-769
[10]	Mokhtari A, Ozdaglar A, Pattathil S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. Proc Machine Learn Res, 2020, 108: 1497-1507
[11]	Nemirovski A. Prox-method with rate of convergence $ \mathcal{O}(1/t) $ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 2004, 15(1): 229-251
[12]	Xiu N, Zhang J. On finite convergence of proximal point algorithms for variational inequalities. Journal of Mathematical Analysis and Applications, 2005, 312(1): 148-158
[13]	Al-Khayyal F, Kyparisis J. Finite convergence of algorithms for nonlinear programs and variational inequalities. Journal of Optimization Theory and Applications, 1991, 70(2): 319-332
[14]	Burke J V, Moré J J. On the identification of active constraints. SIAM Journal on Numerical Analysis, 1988, 25(5): 1197-1211
[15]	Carmona R, Laurière M. Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games: II—the finite horizon case. The Annals of Applied Probability, 2022, 32(6): 4065-4105
[16]	Fischer A, Kanzow C. On finite termination of an iterative method for linear complementarity problems. Mathematical Programming, 1996, 74: 279-292
[17]	Griewank A, Walther A. Finite convergence of an active signature method to local minima of piecewise linear functions. Optimization Methods and Software, 2019, 34(5): 1035-1055
[18]	Nguyen L V, Qin X L. Weak sharpness and finite convergence for mixed variational inequalities. Journal of Applied & Numerical Optimization, 2019, 1(1): 77-90
[19]	Solodov M V, Tseng P. Some methods based on the D-gap function for solving monotone variational inequalities. Computational Optimization and Applications, 2000, 17: 255-277
[20]	Wang C, Liu Q, Yang X. Convergence properties of nonmonotone spectral projected gradient methods. Journal of Computational and Applied Mathematics, 2005, 182(1): 51-66
[21]	Wang C, Zhao W, Zhou J, et al. Global convergence and finite termination of a class of smooth penalty function algorithms. Optimization Methods and Software, 2013, 28(1): 1-25
[22]	Xiu N, Zhang J. Some recent advances in projection-type methods for variational inequalities. Journal of Computational and Applied Mathematics, 2003, 152(1/2): 559-585
[23]	Zhao Z, Liu Z. Finite-time convergence disturbance rejection control for a flexible Timoshenko manipulator. IEEE/CAA Journal of Automatica Sinica, 2020, 8(1): 157-168
[24]	Burke J V, Deng S. Weak sharp minima revisited, part II: Application to linear regularity and error bounds. Mathematical Programming, 2005, 104: 235-261
[25]	Burke J V, Deng S. Weak sharp minima revisited, Part III: Error bounds for differentiable convex inclusions. Mathematical Programming, 2009, 116(1/2): 37-56
[26]	Bonnans J F, Shapiro A. Perturbation Analysis of Optimization Problems. New York: Springer Science & Business Media, 2013
[27]	Fong R, Patrick M, Vedaldi A. Understanding deep networks via extremal perturbations and smooth masks//Proceedings of the IEEE/CVF International Conference on Computer Vision. 2019: 2950-2958
[28]	Jourani A. Hoffman's error bound, local controllability, and sensitivity analysis. SIAM Journal on Control and Optimization, 2000, 38(3): 947-970
[29]	Tirer T, Huang H, Niles-Weed J. Perturbation analysis of neural collapse//International Conference on Machine Learning. 2023: 34301-34329
[30]	Wang C Y, Zhang J Z, Zhao W L. Two error bounds for constrained optimization problems and their applications. Applied Mathematics and Optimization, 2008, 57: 307-328
[31]	Xu K, Shi Z, Zhang H, et al. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 2020, 33: 1129-1141
[32]	Zheng X Y, Yang X Q. Weak sharp minima for semi-infinite optimization problems with applications. SIAM Journal on Optimization, 2007, 18(2): 573-588
[33]	Burke J V, Ferris M C. Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization, 1993, 31(5): 1340-1359
[34]	Marcotte P, Zhu D. Weak sharp solutions of variational inequalities. SIAM Journal on Optimization, 1998, 9(1): 179-189
[35]	Zhou J, Wang C. New characterizations of weak sharp minima. Optimization Letters, 2012, 6: 1773-1785
[36]	Burke J V, Ferris M C. Characterization of solution sets of convex programs. Operations Research Letters, 1991, 10(1): 57-60
[37]	Rockafellar R T. Convex Analysis. Princeton: Princeton Univ Press, 1970
[38]	Calamai P H, Moré J J. Projected gradient methods for linearly constrained problems. Mathematical Programming, 1987, 39(1): 93-116