求解张量随机互补问题的光滑牛顿算法

doi:10.15960/j.cnki.issn.1007-6093.2022.02.011

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 128-136.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.011

求解张量随机互补问题的光滑牛顿算法

单锡泉¹^,*(), 李梅霞², 刘瑾瑜³

1. 潍坊职业学院, 山东潍坊 262737
2. 潍坊学院, 山东潍坊 261061
3. 山东信息职业技术学院, 山东潍坊 261061

收稿日期:2020-01-21 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 单锡泉 E-mail:shanxiquan123@163.com
作者简介:单锡泉 E-mail: shanxiquan123@163.com

Smoothing Newton method for the tensor stochastic complementarity problem

Xiquan SHAN¹^,*(), Meixia LI², Jinyu LIU³

1. Weifang Vocational College, Weifang 262737, Shandong, China
2. Weifang University, Weifang 261061, Shandong, China
3. Shandong University of Information Technology, Weifang 261061, Shandong, China

Received:2020-01-21 Online:2022-06-15 Published:2022-05-27
Contact: Xiquan SHAN E-mail:shanxiquan123@163.com

摘要/Abstract

摘要：

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。

关键词: 张量随机互补问题, 光滑牛顿算法, 全局收敛性

Abstract:

In recent years, more and more people realize that stochastic complementarity problem plays an important role in economic management. Some scholars have extended the stochastic complementarity problem from matrices to tensors and proposed the stochastic complementarity problem of tensors. In this paper, we introduce a class of smooth functions, propose a smooth Newton algorithm, and prove the global and local convergence of the algorithm. Finally, the effectiveness of the algorithm is verified by numerical experiments.

Key words: tensor stochastic complementarity problem, smoothing Newton algorithm, global convergence

中图分类号:

O221.2

单锡泉, 李梅霞, 刘瑾瑜. 求解张量随机互补问题的光滑牛顿算法[J]. 运筹学学报, 2022, 26(2): 128-136.

Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem[J]. Operations Research Transactions, 2022, 26(2): 128-136.

图/表 2

表1

表2

参考文献 14

1	Song Yisheng , Qi Liqun . Tensor complementarity problem and semi-positive tensors[J]. Journal of Optimization Theory and Applications, 2016, 169 (3): 1069- 1078. doi: 10.1007/s10957-015-0800-2
2	Song Yisheng, Qi Liqun. Property of tensor complementarity problem and some classes of structured tensors[J]. arXiv: 1412.0113, 2014.
3	Che Maolin , Qi Liqun , Wei Yimin . Positive definite tensors to nonlinear complementarity problems[J]. Journal of Optimization Theory and Applications, 2016, 168 (2): 475- 487. doi: 10.1007/s10957-015-0773-1
4	Zhang Jian . A smoothing newton algorithm for weighted linear complementarity problem[J]. Optimization Letters, 2016, 10 (3): 499- 509. doi: 10.1007/s11590-015-0877-4
5	Luo Ziyan , Qi Liqun , Xiu Naihua . The sparsest solutions to Z-tensor complementarity problems[J]. Optimization Letters, 2017, 11 (3): 471- 482. doi: 10.1007/s11590-016-1013-9
6	Song Yisheng , Yu Gaohang . Properties of solution set of tensor complementarity problem[J]. Journal of Optimization Theory and Applications, 2016, 170 (1): 85- 96. doi: 10.1007/s10957-016-0907-0
7	Ling Chen , He Hongjin , Qi Liqun . Higher-degree eigenvalue complementarity problems for tensors[J]. Computational Optimization and Applications, 2016, 64 (1): 149- 176. doi: 10.1007/s10589-015-9805-x
8	Qi Liqun . Eigenvalues of a real supersymmetric tensor[J]. Journal of Symbolic Computation, 2005, 40 (6): 1302- 1324. doi: 10.1016/j.jsc.2005.05.007
9	Chen Jeinshan , Pan Shaohua . A family of NCP-functions and a descent method for the nonlinear complementarity problem[J]. Computational Optimization and Applications, 2008, 40 (3): 389- 404. doi: 10.1007/s10589-007-9086-0
10	Che Maolin , Qi Liqun , Wei Yimin . Stochastic R₀ tensors to stochastic tensor complementarity problems[J]. Optimization Letters, 2019, 13 (3): 261- 279.
11	Du Shouqiang , Che Maolin , Wei Yimin . Stochastic structured tensors to stochastic complementarity problems[J]. Computational Optimization and Applications, 2020, 75 (3): 649- 668. doi: 10.1007/s10589-019-00144-3
12	韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法[M]. 上海: 上海科学技术出版社, 2006.
13	Chen B T , Patrick T H . A non-interior-point continuation method for linear complementarity problems[J]. SIAM Journal on Matrix Analysis and Applications, 1993, 14 (4): 1168- 1190. doi: 10.1137/0614081
14	Tang Jingyong , Li Dong , Zhou Jinchuan , et al. A smoothing Newton method for nonlinear complementarity problems[J]. Computational and Applied Mathematics, 2013, 32 (1): 107- 118. doi: 10.1007/s40314-013-0015-9

初始点	牛顿步次数	解	$\\|H(w^{k})\\|$	时间/s
$(10, 10, 10, 10)^{\rm T}$	11	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	8.283 7$\times 10^{-9}$	0.031
$(5, 5, 5, 5)^{\rm T}$	9	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	2.033 9$\times 10^{-7}$	0.029
$(3, 3, 3, 3)^{\rm T}$	8	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	9.515 0$\times 10^{-9}$	0.034
$(2, 2, 2, 2)^{\rm T}$	7	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	6.510 4$\times 10^{-9}$	0.033
$(1, 1, 1, 1)^{\rm T}$	5	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	3.135 3$\times 10^{-9}$	0.024
$(1, 1, 2, 2)^{\rm T}$	6	$(0.000\, 0, 0.793\, 7, 0.000\, 1, 1.442\, 2)^{\rm T}$	1.593 8$\times 10^{-10}$	0.025
$(0, 0, 1, 1)^{\rm T}$	4	$10^{-7}\times(0.062\, 5, 0.062\, 5, 0.125\, 2, 0.187\, 9)^{\rm T}$	2.424 8$\times 10^{-8}$	0.023
$(0, 0, 0.5, 0.5)^{\rm T}$	3	$10^{-6}\times(0.098\, 8, 0.098\, 8, 0.192\, 0, 0.297\, 3)^{\rm T}$	3.805 2$\times 10^{-7}$	0.026

初始点	牛顿步次数	解	$\\|H(w^{k})\\|$	时间/s
$(10, 10, 10)^{\rm T}$	8	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$9.882\, 5\times 10^{-11}$	0.016
$(5, 5, 5)^{\rm T}$	7	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$5.365\, 0\times 10^{-11}$	0.015
$(3, 3, 3)^{\rm T}$	6	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$5.518\, 0\times 10^{-10}$	0.016
$(2, 2, 2)^{\rm T}$	5	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$1.927\, 6\times 10^{-8}$	0.015
$(1, 1, 1)^{\rm T}$	5	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$4.541\, 5\times 10^{-9}$	0.019
$(1.5, 1.5, 1.5)^{\rm T}$	5	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$5.359\, 2\times 10^{-10}$	0.015
$(-1, 1, 5)^{\rm T}$	7	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$5.365\, 1\times 10^{-11}$	0.015
$(-2, 2, 2)^{\rm T}$	5	$(0.000\, 0, 1.000\, 0, 1.000\, 0)^{\rm T}$	$2.675\, 1\times 10^{-8}$	0.015

[1]	张慧玲, 赛闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.
[2]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[3]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[4]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[5]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[6]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[7]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[8]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[9]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[10]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.

求解张量随机互补问题的光滑牛顿算法

Smoothing Newton method for the tensor stochastic complementarity problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 14

相关文章 10

编辑推荐

Metrics

本文评价