Algorithm for Solving Symmetric Cone Complementarity Problems

Abstract

Abstract: A monotonic trust region algorithm for symmetric cone complementarity problems was proposed based on a smoothing function. The problem was transformed into unconstrained optimization problem and the trust region subproblem was constructed. The problem was solved by using trust region algorithm combined with nonmonotonic strategies, and the global convergence of the algorithm was proved. Numerical experimental results demonstrate that the algorithm is effective for symmetric cone complementarity problems.

Key words: symmetric cone complementarity problems, trust region algorithms, nonmonotonic strategies, Newton method, smooth function

CLC Number:

O2224

Gao Leifu, Yu Dongmei. Algorithm for Solving Symmetric Cone Complementarity Problems[J]. Journal of System Simulation, 2015, 27(5): 1050-1056.

References

[1] 修乃华, 韩继业. 对称锥互补问题[J]. 数学进展, 2007, 36(1): 1-12.
[2] Faraut J, Koranyi A.Analysis on Symmetric cones [M]. USA: Oxford University Press, 1994.
[3] Nesterov Y, Nemirovski A.Interior point polynomial methods in convex programming: heory and applications[M]. Philadelphia, USA: P Society for Industrial unapplied Mathematics (SIAM), 1994.
[4] Faybusovich L.Euclidean Jordan algebras and interior-point algorithms[J]. Positivity (S1385-1292), 1997, 1(3): 331-357.
[5] Faybusovich L.Linear systems in Jordan algebras and primal-dual interior-point algorithms[J]. J Comput Appl Math (S0377-0427), 1997, 86(3): 149-175.
[6] Schmieta S H, Alizadeh F.Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones[J]. Mathematics of Operations Research (S1432-2994), 2001, 26(03): 543-564.
[7] Schmieta S H, Alizadeh F.Extension of primal-dual interior point algorithms to symmetric cones[J]. Mathematics Programming Series A (S0025-5610), 2003, 96(03): 409-438.
[8] C B Chua, P Yi.A continuation method for nonlinear complementarity problems over symmetric cones[J]. SIAM Journal on Optimization (S0363-0129), 2010, 20(5): 2560-2583.
[9] L Fang, G P He, Y H Hu.A new smoothing Newton-type method for second-order cone programming problems[J]. Applied Mathematics and Computation (S0096-3003), 2009, 215(3): 1020-1029.
[10] Z H Huang, T Ni.Smoothing algorithms for complementarity problems over symmetric cones[J]. Comput Optim Appl (S0926-6003), 2010, 45(3): 557-579.
[11] L C Kong, J Sun, N H Xiu.A regularized smoothing Newton method for symmetric cone complementarity problems[J]. SIAM Journal on Optimization (S0363-0129), 2008, 19(3): 1028-1047.
[12] 刘长河, 刘红卫, 尚有林. 对称锥规划的邻域跟踪算法[J]. 中国科学: 数学, 2013, 43(7): 691-702.
[13] 袁亚湘, 孙文渝. 最优化理论与方法[M]. 北京: 科学出版社, 2006: 324-330.
[14] 柯小伍, 韩继业. 一类新的信赖域算法的全局收敛性[J]. 应用数学学报, 1995, 18(4): 608-615.
[15] Francisco Facchinei Christian Kanzow. A nonsmooth inexact Newton method for the solution of large-scale nonlinear Complementarity problems[J]. Mathematical Programming (S0025-5610), 1997, 76(3): 493-512.
[16] T Ni, W Z Gu.Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions[J]. Journal of Applied Mathematics and Computing. DOI 10.1007/s12190-009-0341-7, 2009.
[17] S P Rui, C X Xu.A smoothing inexact Newton method for nonlinear complementarity problems[J]. Journal of Computational and Applied Mathematics (S0377-0427), 2010, 233(6): 2332-2338.
[18] 张运胜, 高雷阜. 对称锥互补问题的一个惩罚NR函数的水平有界性[J]. 应用泛函分析学报, 2013, 15(4): 337-341.
[19] D Sun, J Sun.Strong semismoothness of Fischer- Burmeister SDC and SOC Methods complementarity functions[J]. Mathematical Programming (S0025-5610), 2005, 103(3): 575-581.
[20] Huang Z H, Ni T.Smoothing algorithms for complemen-
tarity problems over symmetric cones[J]. Computational Optimization and Applications (S0926-6003), 2010, 45(3): 557-579.
[21] 李改弟. 一个自动确定信赖域半径的信赖域方法[J]. 工程数学学报, 2006, 23(5): 843-848.
[22] Cottle R W, Pang J S, Stone R E.The linear complementarity problem [M]. Boston, USA: Academic Press, 1992.
[23] 王剑平, 吕毅斌, 张晓鹏. 无约束优化的一类新的非单调信赖域算法[J].科学技术与工程, 2012, 12(14): 291-294.
[24] Sturma J F.Using Sedumi 1.02, A Matlab toolbox for optimization over symmetric cones[J]. Optimization Methods and Software (S1055-6788), 1999, 11(1): 625-653.
[25] X H Liu, Z H Huang.A smoothing Newton algorithms based on one-parametric class of smoothing functions for linear programming over symmetric cones[J]. Mathematical Methods of Operations Research (S1432-2994), 2009, 70(3): 385-404.