一类高阶牛顿迭代法及其在线性互补问题中的应用
|
摘要
通过等价转换,把线性互补问题转化为一个不可微的非线性方程组,进而采用光滑函数处理,得到一个光滑非线性方程组,利用高阶牛顿迭代法进行求解.该方法不再区分线性互补问题是否单调,因此扩大了线性互补问题的求解范围.计算结果表明,方法计算速度快,对线性互补问题求解较为有效.
Through the equivalent transformation,linear complementary problem(LCP)is transformed into a nonsmooth nonlinear equation.After smoothing by a smooth function,a smooth nonlinear equation is reformed,which can be solved by high-order Newton's iteration method.This method no longer requires whether linear complementary problem is monotone or not,which expand the scope of solvable linear complementarity problem.The results show that this method is fast in computing speed,and is more effective for solving linear complementary problem.
Through the equivalent transformation,linear complementary problem(LCP)is transformed into a nonsmooth nonlinear equation.After smoothing by a smooth function,a smooth nonlinear equation is reformed,which can be solved by high-order Newton's iteration method.This method no longer requires whether linear complementary problem is monotone or not,which expand the scope of solvable linear complementarity problem.The results show that this method is fast in computing speed,and is more effective for solving linear complementary problem.
引文
[1]王超.线性互补问题[D].成都:电子科技大学,2010.
[2]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M].上海:上海科学技术出版社,2006.
[3]屈彪,王长钰,张树霞.一种求解非线性互补问题的方法及其收敛性[J].计算数学,2006,28(3):247-258.
[4]Chen X,Xiang S.Computation of Error Bounds for P-matrix Linear Complementarity Problems[J].Mathematical Programming,2006,106(3):513-525.
[5]Jein-shan Chen.On some NCP-functions based on the generalized Fischer-burmeister function[J].Asia-Pacific Journal of Operational Research,2007,24(3):401-420.
[6]郑华.线性互补问题的误差分析和模基方法[D].华南师范大学,2015.
[7]Gao L,Wang Y,Li C.New error bounds for the linear complementarity problem of QN-matrices[J].Numerical Algorithms,2017,77(2):1-14.
[8]王峰,孙德淑. B-矩阵线性互补问题的误差界估计[J].数学的实践与认识,2017,47(8):253-260.
[9]甘梦婷,杨绍蓉,李朝迁. B-Nekrasov矩阵线性互补问题的最优误差界[J].吉林大学学报(理学版),2018,56(2):263-267.
[10]Dai P F.Error bounds for linear complementarity problems of DB-matrices[J].Linear Algebra&Its Applications,2016,53(4):647-657.
[11]黎稳,郑华.线性互补问题的数值分析[J].华南师范大学学报(自然科学版),2015,47(3):1-9.
[12]Bai Y Q,Lesaja G,Roos C.A new class of polynomial interior-point algorithms for P*(κ)-linear complementary problems[J].Pacific Journal of Optimization,2008,4(1):248-263.
[13]雍龙泉,邓方安,陈涛.单调线性互补问题的一种内点算法[J].数学杂志,2009,29(5):681-686.
[14]Mansouri H,Pirhaji M.A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems[J].Journal of Optimization Theory&Applications,2013,157(2):451-461.
[15]雍龙泉.一种改进的全局和声搜索算法求解线性互补问题[J].黑龙江大学自然科学学报,20.14,31(5):589-596.
[16]Jein-shan Chen,Chun-Hsu Ko,Shaohua Pan.A neural network based on the generalized FischerBurmeister function for nonlinear complementarity problems[J].Information Sciences,2010,180(5):697-711.
[17]Chen Y J,Zhang M W.A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function[J].Journal of Shandong University,2012,47(10):81-88.
[18]张丽丽,任志茹.M-矩阵线性互补问题模系多分裂迭代方法的收敛性[J]·数学学报,2017,60(4):547-556.
[19]Dai P F,Li J C,Li Y T,et al.A general preconditioner for linear complementarity problem with an M-matrix[J].Journal of Computational&Applied Mathematics,2017,317:100-112.
[20]Kheirfam,Behrouz et al..An infeasible interior-point method for the P_*-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step[J].Communications in Combinatorics and Optimization,2018,3(1):51-70.
[21]Behrouz Kheirfam,Maryam Chitsaz.Polynomial convergence of two higher order interior-point methods for P_*(κ)-LCP in a wide neighborhood of the central path[J].Period.Math.Hungar.,2018,76(2):243-264.
[22]刘志敏,杜守强,王瑞莹.求解线性互补问题的Levenberg-Maxquardt型算法[J].应用数学学报,2018,41(3)403-419.
[23]张汇实,张天四,薛文娟. Anderson加速外梯度法求解非线性互补问题[J].应用数学,2018,31(1):229-236.
[24]郑华,罗静.一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J].计算数学,2018,40(1):24-32.
[25]Zhang C,Chen X.Smoothing projected gradient method and its application to stochastic linear complementarity problems[J].SIAM Journal on Optimization,2009,20(2):627-649.
[26]王英晓,杜守强·求解一类广义随机线性互补问题的投影Levenberg-Marquardt方法[J].上海工程技术大学学报,2017,31(4):326-331.
[27]王国强,白延琴.对称锥互补问题的内点法:理论分析和算法实现[M].哈尔滨:哈尔滨工业大学出版社,2014.
[28]索云阳.张量互补问题解的存在性[D].天津:天津大学,2017.
[29]Xiao B.The linear complementarity problem with a parametric input[J].European Journal of Operational Research,1995,81(2):420-429.
[30]Adelgren N,Wiecek M M.A two-phase algorithm for the multiparametric linear complementarity problem[J].European Journal of Operational Research,2016,254(3):715-738.
[31]张杰,单文柏,石楠等.求解一类特殊随机广义垂直线性互补间题的光滑化SAA方法[J].辽宁师范大学学报(自然科学版),2017,40(3):301-306.
[32]Shang M,Zhang C,Xiu N.Minimal zero norm solutions of linear complementarity problems[J].Journal of Optimization Theory&Applications,2014,163(3):795-814.
[33]Chen Xiaojun,Xiang Shuhuang.Sparse solutions of linear complementarity problems[J].Mathematical Programming:Series A,2015,159(1):539-556.
[34]雍龙泉.一致光滑逼近函数及其性质[J].陕西理工大学学报(自然科学版),2018,34(1):74-79.
[35]张旭,檀结庆,艾列富.一种求解非线性方程组的3p阶迭代方法[J].计算数学,2017,39(1):14-22.
[36]Sharma J R,Gupta P.An efficient fifth order method for solving systems of nonlinear equations[J].Computers&Mathematics with Applications,2014,67(3):591-601.
[37]Foutayeni Y E,Bouanani H E,Khaladi M.An efficient fifth-order method for linear optimization[J].Journal of Optimization Theory and Applications,2016,170(1):189-204.
[38]雍龙泉,刘三阳,史加荣等.几类特殊矩阵及性质[J].兰州大学学报(自然科学版),2016,52(3):385-389.
[39]雍龙泉.广义正定矩阵的判别及相应线性方程组的求解[J].吉林大学学报(理学版),2017,55(1):74-78.
[40]Yong Longquan,Tuo Shouheng,Shi Jiarong.Sparse solution of some special optimization problems[J].Journal of Interdisciplinary Mathematics,2017,20(2):595-602.
[2]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M].上海:上海科学技术出版社,2006.
[3]屈彪,王长钰,张树霞.一种求解非线性互补问题的方法及其收敛性[J].计算数学,2006,28(3):247-258.
[4]Chen X,Xiang S.Computation of Error Bounds for P-matrix Linear Complementarity Problems[J].Mathematical Programming,2006,106(3):513-525.
[5]Jein-shan Chen.On some NCP-functions based on the generalized Fischer-burmeister function[J].Asia-Pacific Journal of Operational Research,2007,24(3):401-420.
[6]郑华.线性互补问题的误差分析和模基方法[D].华南师范大学,2015.
[7]Gao L,Wang Y,Li C.New error bounds for the linear complementarity problem of QN-matrices[J].Numerical Algorithms,2017,77(2):1-14.
[8]王峰,孙德淑. B-矩阵线性互补问题的误差界估计[J].数学的实践与认识,2017,47(8):253-260.
[9]甘梦婷,杨绍蓉,李朝迁. B-Nekrasov矩阵线性互补问题的最优误差界[J].吉林大学学报(理学版),2018,56(2):263-267.
[10]Dai P F.Error bounds for linear complementarity problems of DB-matrices[J].Linear Algebra&Its Applications,2016,53(4):647-657.
[11]黎稳,郑华.线性互补问题的数值分析[J].华南师范大学学报(自然科学版),2015,47(3):1-9.
[12]Bai Y Q,Lesaja G,Roos C.A new class of polynomial interior-point algorithms for P*(κ)-linear complementary problems[J].Pacific Journal of Optimization,2008,4(1):248-263.
[13]雍龙泉,邓方安,陈涛.单调线性互补问题的一种内点算法[J].数学杂志,2009,29(5):681-686.
[14]Mansouri H,Pirhaji M.A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems[J].Journal of Optimization Theory&Applications,2013,157(2):451-461.
[15]雍龙泉.一种改进的全局和声搜索算法求解线性互补问题[J].黑龙江大学自然科学学报,20.14,31(5):589-596.
[16]Jein-shan Chen,Chun-Hsu Ko,Shaohua Pan.A neural network based on the generalized FischerBurmeister function for nonlinear complementarity problems[J].Information Sciences,2010,180(5):697-711.
[17]Chen Y J,Zhang M W.A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function[J].Journal of Shandong University,2012,47(10):81-88.
[18]张丽丽,任志茹.M-矩阵线性互补问题模系多分裂迭代方法的收敛性[J]·数学学报,2017,60(4):547-556.
[19]Dai P F,Li J C,Li Y T,et al.A general preconditioner for linear complementarity problem with an M-matrix[J].Journal of Computational&Applied Mathematics,2017,317:100-112.
[20]Kheirfam,Behrouz et al..An infeasible interior-point method for the P_*-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step[J].Communications in Combinatorics and Optimization,2018,3(1):51-70.
[21]Behrouz Kheirfam,Maryam Chitsaz.Polynomial convergence of two higher order interior-point methods for P_*(κ)-LCP in a wide neighborhood of the central path[J].Period.Math.Hungar.,2018,76(2):243-264.
[22]刘志敏,杜守强,王瑞莹.求解线性互补问题的Levenberg-Maxquardt型算法[J].应用数学学报,2018,41(3)403-419.
[23]张汇实,张天四,薛文娟. Anderson加速外梯度法求解非线性互补问题[J].应用数学,2018,31(1):229-236.
[24]郑华,罗静.一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J].计算数学,2018,40(1):24-32.
[25]Zhang C,Chen X.Smoothing projected gradient method and its application to stochastic linear complementarity problems[J].SIAM Journal on Optimization,2009,20(2):627-649.
[26]王英晓,杜守强·求解一类广义随机线性互补问题的投影Levenberg-Marquardt方法[J].上海工程技术大学学报,2017,31(4):326-331.
[27]王国强,白延琴.对称锥互补问题的内点法:理论分析和算法实现[M].哈尔滨:哈尔滨工业大学出版社,2014.
[28]索云阳.张量互补问题解的存在性[D].天津:天津大学,2017.
[29]Xiao B.The linear complementarity problem with a parametric input[J].European Journal of Operational Research,1995,81(2):420-429.
[30]Adelgren N,Wiecek M M.A two-phase algorithm for the multiparametric linear complementarity problem[J].European Journal of Operational Research,2016,254(3):715-738.
[31]张杰,单文柏,石楠等.求解一类特殊随机广义垂直线性互补间题的光滑化SAA方法[J].辽宁师范大学学报(自然科学版),2017,40(3):301-306.
[32]Shang M,Zhang C,Xiu N.Minimal zero norm solutions of linear complementarity problems[J].Journal of Optimization Theory&Applications,2014,163(3):795-814.
[33]Chen Xiaojun,Xiang Shuhuang.Sparse solutions of linear complementarity problems[J].Mathematical Programming:Series A,2015,159(1):539-556.
[34]雍龙泉.一致光滑逼近函数及其性质[J].陕西理工大学学报(自然科学版),2018,34(1):74-79.
[35]张旭,檀结庆,艾列富.一种求解非线性方程组的3p阶迭代方法[J].计算数学,2017,39(1):14-22.
[36]Sharma J R,Gupta P.An efficient fifth order method for solving systems of nonlinear equations[J].Computers&Mathematics with Applications,2014,67(3):591-601.
[37]Foutayeni Y E,Bouanani H E,Khaladi M.An efficient fifth-order method for linear optimization[J].Journal of Optimization Theory and Applications,2016,170(1):189-204.
[38]雍龙泉,刘三阳,史加荣等.几类特殊矩阵及性质[J].兰州大学学报(自然科学版),2016,52(3):385-389.
[39]雍龙泉.广义正定矩阵的判别及相应线性方程组的求解[J].吉林大学学报(理学版),2017,55(1):74-78.
[40]Yong Longquan,Tuo Shouheng,Shi Jiarong.Sparse solution of some special optimization problems[J].Journal of Interdisciplinary Mathematics,2017,20(2):595-602.