×

A non-monotone inexact non-interior continuation method based on a parametric smoothing function for LWCP. (English) Zbl 1390.90534

Summary: This paper considers the linear weighted complementarity problem (denoted by LWCP). We introduce a parametric smoothing function which is a broad class of smoothing functions for the LWCP and enjoys some favourable properties. Based on this function, we propose a new non-interior continuation method for solving the LWCP. In general, the non-interior continuation method consists of finding an exact solution of a system of equations at each iteration, which may be cumbersome if one is solving a large-scale problem. To overcome this difficulty, our method uses an inexact Newton method to solve the corresponding linear system approximately and adopts a non-monotone line search to obtain a step size. Under suitable assumptions, we show that the proposed method is globally and locally quadratically convergent. Preliminary numerical results are also reported.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods

Software:

SCCP
Full Text: DOI

References:

[1] K. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centering, Optim. Methods Softw. 27 (2012), pp. 605-612. doi: 10.1080/10556788.2011.644791 · Zbl 1254.90106
[2] X. Chen and P. Tseng, Non-interior continuation methods for solving semidefinite complementarity problems, Math. Program. 95 (2003), pp. 431-474. doi: 10.1007/s10107-002-0306-1 · Zbl 1023.90046
[3] X.N. Chi and S.Y. Liu, Analysis of a non-interior continuation method for second-order cone programming, J. Appl. Math. Comput. 27 (2008), pp. 47-61. doi: 10.1007/s12190-008-0057-0 · Zbl 1193.90169
[4] F.H. Clarke, Optimization, Nonsmooth Analysis, John Wiley, Sons, New York, 1983. · Zbl 0582.49001
[5] Z.H. Huang, The global linear, local quadratic convergence of a non-interior continuation algorithm for the LCP, IMA J. Numer. Anal. 25 (2005), pp. 670-684. doi: 10.1093/imanum/dri008 · Zbl 1084.65061
[6] Z.H. Huang and J.Y. Han, Non-interior continuation method for solving the monotone semidefinite complementarity problem, Appl. Math. Optim. 47 (2003), pp. 195-211. doi: 10.1007/s00245-003-0765-7 · Zbl 1030.65069
[7] Z. Jian, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett. 10 (2016), pp. 499-509. doi: 10.1007/s11590-015-0877-4 · Zbl 1346.90778
[8] L.Y. Lu and W.Z. Gu, A non-interior continuation algorithm for the CP based on a generalized smoothing function, J. Comput. Appl. Math. 235 (2011), pp. 2300-2313. doi: 10.1016/j.cam.2010.10.027 · Zbl 1211.65073
[9] N. Lu and Z.H. Huang, Convergence of a non-interior continuation algorithm for the monotone SCCP, Acta Math. Appl. Sin. 26(4) (2010), pp. 543-556. doi: 10.1007/s10255-010-0024-z · Zbl 1225.90135
[10] N. Lu, F. Ma, and S.Y. Liu, A non-interior continuation algorithm for solving the convex feasibility problem, Appl. Math. Model. 38 (2014), pp. 5421-5430. doi: 10.1016/j.apm.2014.04.030 · Zbl 1428.90122
[11] F.A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim. 22(4) (2012), pp. 1634-1654. doi: 10.1137/110837310 · Zbl 1273.90217
[12] F.A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl. 23 (2015), pp. 1-22.
[13] S.P. Rui and C.X. Xu, Inexact non-interior continuation method for monotone semidefinite complementarity problems, Optim. Lett. 6 (2012), pp. 1411-1424. doi: 10.1007/s11590-011-0337-8 · Zbl 1282.90199
[14] N.H. Xiu, One-step quadratic convergence of non-interior continuation method for NCP, Chinese Sci. Bull. 44 (1999), pp. 1483-1488. doi: 10.1007/BF02886340 · Zbl 1041.90534
[15] J.X. Zhao and Y. Wang, A full-Newton step non-interior continuation algorithm for a class of complementarity problems, J. Comput. Appl. Math. 236 (2012), pp. 2728-2739. doi: 10.1016/j.cam.2012.01.016 · Zbl 1241.65060
[16] J.G. Zhu and B.B. Hao, A new noninterior continuation method for solving a system of equalities and inequalities, J. Appl. Math. (2014). doi:10.1155/2014/592540. · Zbl 1442.65107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.