一般混合变分不等式的捆集近似算法

数学物理学报 ›› 2011, Vol. 31 ›› Issue (4): 866-879.

一般混合变分不等式的捆集近似算法

夏福全¹|黄南京²

1.四川师范大学数学与软件科学学院成都 610066|2.四川大学数学科学学院成都 610064

收稿日期:2009-09-21 修回日期:2010-10-30 出版日期:2011-08-25 发布日期:2011-08-25
基金资助:
国家自然科学基金(10671135, 70831005)、四川省教育厅重点项目(09ZA091)、四川省应用基础项目(2010JY0121)和教育部博士点基金
(20105134120002)资助

A Bundle Proximal Method for Solving General Mixed Variational Inequalities

XIA Fu-Quan¹, HUANG Na-Jing²

1.College of Mathematics and Software Science, Sichuan Normal University, Chengdu |610066;
2.Department of Mathematics, Sichuan University, Chengdu 610064

Received:2009-09-21 Revised:2010-10-30 Online:2011-08-25 Published:2011-08-25
Supported by:
国家自然科学基金(10671135, 70831005)、四川省教育厅重点项目(09ZA091)、四川省应用基础项目(2010JY0121)和教育部博士点基金
(20105134120002)资助

摘要/Abstract

摘要：

该文研究了一般混合变分不等式解的捆集近似算法. 该方法综合应用Cohen$^{[3]}$所介绍的辅助原理和Kiwiel$^{[11]}$所介绍的关于非光滑凸优化的捆集Bregman近似方法, 构造迭代序列{xⁿ}. 在迭代算法的每一步, 通过求解迭代子问题获得当前迭代点xⁿ. 一方面, xⁿ是迭代子问题的近似极小值点(非精确极小值点); 另一方面, 在迭代的每一子问题中, 根据非光滑凸泛函f 的次梯度, 构造分段光滑的凸泛函f_k用以替代非光滑泛函f, 这两方面使得迭代算法的每个子问题都容易求解, 迭代点xⁿ容易获得. 该文首先介绍如何构造作者的迭代算法, 如何判别当前迭代点的好坏以及算法的终止条件. 其次, 在映象T满足伪Dunn性质的条件下, 证明了迭代算法产生的迭代序列{xⁿ}收敛于一般混合变分不等式的解.

关键词: 迭代算法, 近似方法, 捆集方法, 强凸泛函, 伪Dunn性质

Abstract:

In this paper, the authors consider a bundle proximal method for solving general mixed variational inequalities. The method is based on the auxiliary problem principle due to Cohen and the bundle Bregman proximal method for convex nonsmooth optimization due to Kiwiel. The strategy is to approximate, in the subproblems, the nonsmooth convex function f by a sequence of linear convex piecewise functions f_k, which is constructed from accumulated subgradient linearizations of f. As in the bundle Bregman proximal method for nonsmooth optimization, the method generates a sequence {x^k} by taking x^k to be an approximate minimizer of subproblems. This makes the subproblems more tractable. The authors first explain how to build a new iterative scheme and a stopping criterion to determine whether the current approximation is good enough. This criterion is different from that commonly used in the special case of nonsmooth optimization. The authors also prove that the convergence of the algorithm for the case that the mapping T satisfies the pseudo-Dunn property.

Key words: Iterative schemes, Proximal methods, Bundle methods, Strongly convex function, Pseudo-Dunn property

中图分类号:

90C25

夏福全, 黄南京. 一般混合变分不等式的捆集近似算法[J]. 数学物理学报, 2011, 31(4): 866-879.

XIA Fu-Quan, HUANG Na-Jing. A Bundle Proximal Method for Solving General Mixed Variational Inequalities[J]. Acta mathematica scientia,Series A, 2011, 31(4): 866-879.

参考文献

[1] Aubin J P, Ekeland I. Applied Nonlinear Analysis. Now York: A Wiley Interscience Publication, 1984

[2] Alber Y I, Iusem A N, Solodov M V. On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math Program, 1998, 81: 23--35

[3] Cohen G. Auxiliary problem principle extended to variational inequalities. Journal of Optimization Theory and Applications, 1988, 49: 325--333

[4] Cohen G. Nash equilibria: gradient and decomposition algorithms. Large Scale Systems, 1987, 12: 173--184

[5] Ding X P, Tan K K. A minimax inequality with application th existence of equilibrium point and fixed point theorems. Colloquium Math, 1992,  63: 233--247

[6] Ekeland I, Temam R. Convex Analysis and Variational Inequalities. Amsterdam: North-Holland, 1976

[7] Facchinri F, Pang J S. Finite Dimensional Variational Inequalities and Complementarity Problems. New York: Springer-Verlag, 2003

[8]} Gigola C, Gomez S. A regularization method for solving the finite convex min-max problem. SIAM Journal on Numerical Analysis, 1990, 27: 1621--1634

[9] Hartman P, Stampacchia G. On some nonlinear elliptic differential functional equations. Acta Mathematics, 1966, 115: 271--310

[10] Konnov I. A combined relaxation method for a class of nonlinear variational inequalities. Optimization, 2002, 51: 127--143

[11] Kiwiel K C. A bundle Bregman proximal method for convex nondifferentiable minimization. Math Program, 1999, 85: 241--258

[12] Kiwiel K C. Relaxation methods for strictly convex regularizations of piecewise linear programs. Appl Math Optim, 1998, 38: 239--259

[13] Kothe G. Topological Vector Spaces. Berlin, Germany: Springer-Verlag, 1983

[14] Panagiotopoulos P,  Stavroulakis G. New types of variational principles based on the notion of quasidifferentiablity. Acta Mech, 1994, 94: 171--194

[15] Rockafellar R T. Monotone operators and the proximal point algorith. SIAM J Control Optim, 1976, 14: 877--898

[16] Salmon G. Peturbed Auxiliary Problem Methods to Solve Generalized Variational Inequalities. Namur, Belgium: Presses                   Universitaires de Namur, 2001

[17] Salmon G, Strodiot J, Nguyen V H. A bundle method for solving variational inequalities. SIAM J Optim, 2004, 14(3): 869--893

[18] Solodov M V, Svaiter B F. A new projection method for variational inequality problems. SIAM J Control Optim, 1999, 37: 765--776

[19] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J Control Optim, 1991, 29: 119--138

[20] Wang Y L, Xiu N H, Wang C Y.  Unified framework of extragradient type methods for pseudomonotone variational inequalities. Journal of Optimization Theory and Applications, 2001, 111: 641--656

[21] Xia F Q, Huang N J. Algorithm for solving a new class of general mixed variational inequalities in Banach spaces. Journal              of Computational and Applied Mathematics, 2008, 111: 632--642

[22] Xia F Q, Huang N J. A projected subgradient method for solving generalized mixed variational inequalities. Operations Research
Letters, 2008, 36: 637--642

[23] Zhu D L, Marcotte P. Cocoercivity and its role in the convergence of iterative schemes for solving variational inequalities. SIAM J Optim, 1996, 6: 714--726