拟变分不等式问题的算法研究
|
摘要
本文主要研究拟变分不等式问题的算法.针对这类问题,我们给出了三种算法并对其进行了研究.全文共分为四章.
第一章是绪论,主要介绍了拟变分不等式问题的研究现状以及本文的主要研究工作.
第二章主要在文献[25]第三部分的基础上对其提出的求解拟变分不等式问题的投影算法做了进一步的研究,并且在一些合适的前提条件下,给出了该投影算法Q-线性收敛速度的证明.
第三章利用广义正则gap函数的方向导数,构造了一种迭代方向,提出了一类求解拟变分不等式问题的算法.此算法不需关心目标函数的梯度计算问题,与相关文献比较,该算法的适用范围更加广泛.在某些假设条件下,证明了算法的收敛性.
第四章在文献[26]的基础上,构造了一种严格下降方向,提出了求解拟变分不等式问题的另一类下降算法.在理论上,此算法避免了涉及最优化问题的目标函数的梯度问题.与第三章相比较,本章中的假设条件由正定减弱为半正定.同时在一些合理的假设下,保证了该算法的有效性和收敛性.
In this dissertation, we mainly investigate the algorithms for quasi-variational inequality problem. We design three methods for solving quasi-variational in-equality problem. Four chapters are included in this thesis.
Chapter 1 is the introduction. We describe the research situations of quasi-variational inequality problem. The main contributions of this paper are also stated briefly.
In Chapter 2, based on the third section of [25], we do further research on the projection method for quasi-variational inequality problem. Under some appropriate conditions, we prove the Q-linear convergence rate of the related projection method.
In Chapter 3, constructing a descent direction obtained from the direc-tional differentiability of the (generalized) regularized gap function, we present a derivative-free descent method for solving the quasi-variational inequality prob-lem. We do not need consider the gradient problem of the objective function. Compared with the ones in the related references, the method of this paper has the superiority that the application is more wider. Under some reasonable con-ditions, the convergence of the algorithm is proved.
In Chapter 4, by constructing a strictly descent direction in the spirit of [26], we present another descent algorithm for solving the quasi-variational in-equality problem. We still do not need consider the gradient problem of the objective function. Compared with Chapter 3, the assumption that the▽F(·) is semi-positive definite is weaker than the one that▽F(·) is positive-definite. In addition, the effectiveness and convergence of this algorithm is guaranteed under some reasonable conditions.
第一章是绪论,主要介绍了拟变分不等式问题的研究现状以及本文的主要研究工作.
第二章主要在文献[25]第三部分的基础上对其提出的求解拟变分不等式问题的投影算法做了进一步的研究,并且在一些合适的前提条件下,给出了该投影算法Q-线性收敛速度的证明.
第三章利用广义正则gap函数的方向导数,构造了一种迭代方向,提出了一类求解拟变分不等式问题的算法.此算法不需关心目标函数的梯度计算问题,与相关文献比较,该算法的适用范围更加广泛.在某些假设条件下,证明了算法的收敛性.
第四章在文献[26]的基础上,构造了一种严格下降方向,提出了求解拟变分不等式问题的另一类下降算法.在理论上,此算法避免了涉及最优化问题的目标函数的梯度问题.与第三章相比较,本章中的假设条件由正定减弱为半正定.同时在一些合理的假设下,保证了该算法的有效性和收敛性.
In this dissertation, we mainly investigate the algorithms for quasi-variational inequality problem. We design three methods for solving quasi-variational in-equality problem. Four chapters are included in this thesis.
Chapter 1 is the introduction. We describe the research situations of quasi-variational inequality problem. The main contributions of this paper are also stated briefly.
In Chapter 2, based on the third section of [25], we do further research on the projection method for quasi-variational inequality problem. Under some appropriate conditions, we prove the Q-linear convergence rate of the related projection method.
In Chapter 3, constructing a descent direction obtained from the direc-tional differentiability of the (generalized) regularized gap function, we present a derivative-free descent method for solving the quasi-variational inequality prob-lem. We do not need consider the gradient problem of the objective function. Compared with the ones in the related references, the method of this paper has the superiority that the application is more wider. Under some reasonable con-ditions, the convergence of the algorithm is proved.
In Chapter 4, by constructing a strictly descent direction in the spirit of [26], we present another descent algorithm for solving the quasi-variational in-equality problem. We still do not need consider the gradient problem of the objective function. Compared with Chapter 3, the assumption that the▽F(·) is semi-positive definite is weaker than the one that▽F(·) is positive-definite. In addition, the effectiveness and convergence of this algorithm is guaranteed under some reasonable conditions.
引文
[1]G.Stampacchia. Formes bilineaires coercivites sur les ensembles convexes[J]. C. R. Acad. Sci. Paris,1964,258:4413-4416.
[2]Muhammad Aslam Noor. An iterative scheme for a class of quasi variational in-equalities [J]. J. Math. Anal. Appl.,1985,110:463-468.
[3]Muhammad Aslam Noor. Sensitivity analysis for quasi-variational inequalities [J]. J. Optim. Theory Appl,1997,95(2):399-407.
[4]M.Kocvara and J.V.Outrata. On a class of quasi-variational inequalities[J]. Opti-mization methods and Software,1995,5:275-295.
[5]M.A.Noor. On merit functions for quasi-variational inequalities[J]. Journal of Mathematical Inequalities,2007, 1(2):259-268.
[6]M.A.Noor. Implicit dynamical systems for quasi-variational inequalities[J]. Appl. Math. Comput,2002,134:69-81.
[7]M.Fukushima. A class of gap functions for quasi-variational inequality problems[J]. Journal of Operational Industrial and Management Optimization,2007,3(2):165-171.
[8]Kouichi Taji. On gap functions for quasi-variational inequalities[J]. Abstract and Applied Analysis, doi:10.1155/2008/531361.
[9]C.Baiocchi, A.Capelo. Variational and quasi-variational inequalities[M]. J.Wiley and Sons, New York,1984.
[10]F.Facchinei, J.S.Pang. Finite-dimensional variational inequalities and complemen-tarity problems[M]. Springer-Verlag, New York,2003.
[11]M.Fukushima. Equivalent differentiable optimization problems and desent meth-ods for asymmetric variational inequality problems [J]. Mathematical Programming, 1992,53:99-110.
[12]J.M.Peng and M.Fukushima. A hybrid newton methods for solving variational inequality problem via the D-gap function[J]. Mathematical Programming,1999,
86:367-386.
[13]J.H.Wu, M.Floriam and P.Marcotte. A. general descent framework for the mono-tone variational,inequality problem[J]. Mathematical Programming,1993,61:281-300.
[14]M. Fukushima. Merit functions for variational inequality and complementarity problems[M]. Nonlinear Optimization and Applications, New York,1996,155-170.
[15]B.Qu, C.Y.Wang and J.Z.Wang. Convergence and error bound of a method for solving variational inequality problems via the generalized D-gap function [J]. Jour-nal of Optimization Theroy and Applications,2003,119:535-552.
[16]. D.L.Zhu and P.Marcotte. Modified descent methods for solving the monotone vari-ational inequality problem[J]. Operations Research Letters,1993,14(2):111-120.
[17]N. Yamashita and M. Fukushima. Equivalent unconstraint minimization and global error bounds for variational inequality problems[J]. SIAM Journal on Con-trol and Optimization,1997,35:273-284.
[18]J.M. Peng. Equivalence of variational inequality problems to unconstrained mini-mization[J]. Mathematical Programming,1997,78:347-356.
[19]B.Xiao and B.T.Harker. A nonsmooth method for variational inequalities [J]. Math-ematical Programming,1994,65(2):139-216.
[20]J.Z.Zhang, B.Qu, N.H.Xiu. Some projection-like methods for the generalized Nash equilibria[J]. Comput.Optim.Appl., doi:10.1007/s10589-008-9173-x.
[21]J.S.Pang, M.Fukushima. Quasi-variational inequalities, generalized Nash equilib-rium problems and multi-leader-follower games[J]. Computational Management Science,2005,2:21-56.
[22]A.Bensousan and J.Lions. Applications des inequations variationelles en controle stochastique[M]. Dunod, Paris,1978.
[23]王宜举,修乃华.非线性规划理论与算法[M].陕西科学技术出版社,2008.
[24]N.Yamashita, K.Taji, M.Fukushima. Unconstrained optimization reformulations of variational inequality problems[J]. Journal of Optimization Theroy and Appli-cations,1997,92(3):439-456.
[25]李靖.广义Nash均衡问题的算法及应用研究.曲阜师范大学硕士毕业论文,2008.
[26]Barbara Panicucci, Massimo Pappalardo, Mauro Passacantando. A globally con-vergent descent method for nonsmooth variational inequalities [J]. Comput. Optim. Appl., doi:10.1007/s10589-007-9132-y.
[27]F.H.Clarke. Optimization and nonsmooth analysis[M]. Wiley, New York,1983.
[28]H.Xu. Regularized gap function and D-gap function for nonsmooth variational in-equalities [M]. In:Rubinov, A., Glover, B.(eds.) Optimization and Related Topics, Kluwer Academic, Dordrecht,2001,153-176.
[29]L.Qi and J.Sun. A nonsmooth version of Newton's method[J]. Mathematical Pro-gramming,1993,58:353-368.
[30]Lili Huan, Biao Qu, Jin-guang Jiang. Merit functions for general mixed quasi-variational inequalities[J]. Journal of Applied Mathematics and Computing,2010, 33(1):411-421.
[2]Muhammad Aslam Noor. An iterative scheme for a class of quasi variational in-equalities [J]. J. Math. Anal. Appl.,1985,110:463-468.
[3]Muhammad Aslam Noor. Sensitivity analysis for quasi-variational inequalities [J]. J. Optim. Theory Appl,1997,95(2):399-407.
[4]M.Kocvara and J.V.Outrata. On a class of quasi-variational inequalities[J]. Opti-mization methods and Software,1995,5:275-295.
[5]M.A.Noor. On merit functions for quasi-variational inequalities[J]. Journal of Mathematical Inequalities,2007, 1(2):259-268.
[6]M.A.Noor. Implicit dynamical systems for quasi-variational inequalities[J]. Appl. Math. Comput,2002,134:69-81.
[7]M.Fukushima. A class of gap functions for quasi-variational inequality problems[J]. Journal of Operational Industrial and Management Optimization,2007,3(2):165-171.
[8]Kouichi Taji. On gap functions for quasi-variational inequalities[J]. Abstract and Applied Analysis, doi:10.1155/2008/531361.
[9]C.Baiocchi, A.Capelo. Variational and quasi-variational inequalities[M]. J.Wiley and Sons, New York,1984.
[10]F.Facchinei, J.S.Pang. Finite-dimensional variational inequalities and complemen-tarity problems[M]. Springer-Verlag, New York,2003.
[11]M.Fukushima. Equivalent differentiable optimization problems and desent meth-ods for asymmetric variational inequality problems [J]. Mathematical Programming, 1992,53:99-110.
[12]J.M.Peng and M.Fukushima. A hybrid newton methods for solving variational inequality problem via the D-gap function[J]. Mathematical Programming,1999,
86:367-386.
[13]J.H.Wu, M.Floriam and P.Marcotte. A. general descent framework for the mono-tone variational,inequality problem[J]. Mathematical Programming,1993,61:281-300.
[14]M. Fukushima. Merit functions for variational inequality and complementarity problems[M]. Nonlinear Optimization and Applications, New York,1996,155-170.
[15]B.Qu, C.Y.Wang and J.Z.Wang. Convergence and error bound of a method for solving variational inequality problems via the generalized D-gap function [J]. Jour-nal of Optimization Theroy and Applications,2003,119:535-552.
[16]. D.L.Zhu and P.Marcotte. Modified descent methods for solving the monotone vari-ational inequality problem[J]. Operations Research Letters,1993,14(2):111-120.
[17]N. Yamashita and M. Fukushima. Equivalent unconstraint minimization and global error bounds for variational inequality problems[J]. SIAM Journal on Con-trol and Optimization,1997,35:273-284.
[18]J.M. Peng. Equivalence of variational inequality problems to unconstrained mini-mization[J]. Mathematical Programming,1997,78:347-356.
[19]B.Xiao and B.T.Harker. A nonsmooth method for variational inequalities [J]. Math-ematical Programming,1994,65(2):139-216.
[20]J.Z.Zhang, B.Qu, N.H.Xiu. Some projection-like methods for the generalized Nash equilibria[J]. Comput.Optim.Appl., doi:10.1007/s10589-008-9173-x.
[21]J.S.Pang, M.Fukushima. Quasi-variational inequalities, generalized Nash equilib-rium problems and multi-leader-follower games[J]. Computational Management Science,2005,2:21-56.
[22]A.Bensousan and J.Lions. Applications des inequations variationelles en controle stochastique[M]. Dunod, Paris,1978.
[23]王宜举,修乃华.非线性规划理论与算法[M].陕西科学技术出版社,2008.
[24]N.Yamashita, K.Taji, M.Fukushima. Unconstrained optimization reformulations of variational inequality problems[J]. Journal of Optimization Theroy and Appli-cations,1997,92(3):439-456.
[25]李靖.广义Nash均衡问题的算法及应用研究.曲阜师范大学硕士毕业论文,2008.
[26]Barbara Panicucci, Massimo Pappalardo, Mauro Passacantando. A globally con-vergent descent method for nonsmooth variational inequalities [J]. Comput. Optim. Appl., doi:10.1007/s10589-007-9132-y.
[27]F.H.Clarke. Optimization and nonsmooth analysis[M]. Wiley, New York,1983.
[28]H.Xu. Regularized gap function and D-gap function for nonsmooth variational in-equalities [M]. In:Rubinov, A., Glover, B.(eds.) Optimization and Related Topics, Kluwer Academic, Dordrecht,2001,153-176.
[29]L.Qi and J.Sun. A nonsmooth version of Newton's method[J]. Mathematical Pro-gramming,1993,58:353-368.
[30]Lili Huan, Biao Qu, Jin-guang Jiang. Merit functions for general mixed quasi-variational inequalities[J]. Journal of Applied Mathematics and Computing,2010, 33(1):411-421.