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

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

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

CLC Number:

O221.2

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

Figures/Tables 2

References 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]	Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization [J]. Operations Research Transactions, 2022, 26(2): 64-72.
[2]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[3]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[4]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[5]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[6]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[7]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[8]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[9]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[10]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.
[11]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[12]	DU Shouqiang. Global convergence of the Levenberg-Marquardt method with Goldstein line search [J]. Operations Research Transactions, 2012, 16(4): 105-111.
[13]	ZHAO Qi, ZHANG Yan. A Nonmonotoe Filter Method For Minimax Problems [J]. Operations Research Transactions, 2012, 16(2): 91-104.
[14]	ZHANG Yu-Nong, LI Xue-Zhong, ZHANG Zhi-Jun, LI Jun. An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems [J]. Operations Research Transactions, 2012, 16(1): 21-30.
[15]	WANG Hua. A Nonmonotone Feasible SQP Method for Nonlinear Complementarity Problem [J]. Operations Research Transactions, 2011, 15(2): 85-94.

Smoothing Newton method for the tensor stochastic complementarity problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 14

Related Articles 15

Recommended Articles

Metrics

Comments