A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem

Xiaoni Chi; Zhongping Wan; Zijun Hao

doi:10.3934/jimo.2021082

Article Contents

2022, Volume 18, Issue 4: 2579-2598. Doi: 10.3934/jimo.2021082

This issue Previous Article Due-window assignment scheduling with learning and deterioration effects Next Article Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities

A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem

1.
School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China
2.
School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China
3.
School of Mathematics and Information Science, North Minzu University, Yinchuan 750021, China

^* Corresponding author: Zhongping Wan
^* Corresponding author: Zhongping Wan

Received: August 31, 2020

Revised: January 31, 2021

Published: July 2022

Abstract Full Text(HTML) Figure(4) / Table(1) Related Papers Cited by

Abstract

The weighted complementarity problem (wCP) can be applied to a large variety of equilibrium problems in science, economics and engineering. Since formulating an equilibrium problem as a wCP may lead to highly efficient algorithms for its numerical solution, wCP is a nontrivial generalization of the complementarity problem. In this paper we consider a special weighted linear complementarity problem (wLCP), which is the more general optimization of the Fisher market equilibrium problem. A full-modified-Newton infeasible interior-point method (IIPM) for the special wLCP is proposed. The algorithm reformulates the central path of the perturbed problem as an equivalent system of equations, and uses only full-Newton steps at each iteration, so-called a feasibility step (i.e., a full-modified-Newton step) and several usual centering steps. The polynomial complexity of the algorithm is as good as the best known iteration bound for these types of IIPMs in linear optimization.

Keywords:

Weighted linear complementarity problem,
infeasible interior-point method,
full-modified-Newton step,
polynomial complexity.

Mathematics Subject Classification: Primary: 90C33; Secondary: 90C51.

Citation:

Full Text(HTML)

Figure 1. The value of $ rb: = \|b-Ax\| $

Download: Full-size image PowerPoint slide

Figure 2. The value of $ rc:=\|c-A^{T}y-s\| $

Download: Full-size image PowerPoint slide

Figure 3. The value of $ rw: = \|\omega(t)-\omega\| $

Download: Full-size image PowerPoint slide

Figure 4. The value of $ rv: = \delta(v) $

Download: Full-size image PowerPoint slide

Table 1. Numerical results for the special wLCPs

Time(s)	Iter	$ t $	$ \delta(v) $
0.027	156	4.3155e-05	1.1389e-11
0.032	172	8.8496e-06	1.7788e-13
0.019	109	1.3410e-05	7.6732e-13
0.105	206	3.9157e-06	3.3555e-14
0.084	97	6.7376e-05	1.0484e-11
0.081	118	3.1367e-06	1.9156e-14
0.128	218	2.7493e-05	2.0044e-12
0.096	168	2.1576e-05	4.5414e-12

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	K. M. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centring, Optim. Methods Softw., 27 (2012), 605-612. doi: 10.1080/10556788.2011.644791.
[2]	Y. Bai, P. Ma and J. Zhang, A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Ind. Manag. Optim., 12 (2016), 739-756. doi: 10.3934/jimo.2016.12.739.
[3]	J. -S. Chen, SOC Functions and their Applications, Springer, Singapore, 2019. doi: 10.1007/978-981-13-4077-2.
[4]	X. Chi, M. S. Gowda and J. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Global Optim., 73 (2019), 153-169. doi: 10.1007/s10898-018-0689-z.
[5]	R. W. Cottle, J.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992. doi: 10.1137/1.9780898719000.
[6]	S.-C. Fang and W. X. Xing, Linear Conic Programming: Theory and Applications, Science Press, Beijing, 2013.
[7]	M. Fukushima, Z.-Q. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim., 12 (2002), 436-460. doi: 10.1137/S1052623400380365.
[8]	G. Gu, H. Mansouri, M. Zangiabadi, Y. Q. Bai and C. Roos, Improved full-Newton step $O(nL)$ infeasible interior-point method for linear optimization, J. Optim. Theory Appl., 145 (2010), 271-288. doi: 10.1007/s10957-009-9634-0.
[9]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395. doi: 10.1007/BF02579150.
[10]	M. Kojima, S. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res., 15 (1990), 662-675. doi: 10.1287/moor.15.4.662.
[11]	L. Kong, N. Xiu and J. Han, The solution set structure of monotone linear complementarity problems over second-order cone, Oper. Res. Lett., 36 (2008), 71-76. doi: 10.1016/j.orl.2007.03.009.
[12]	H. Liu, X. Yang and C. Liu, A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming, J. Optim. Theory Appl., 158 (2013), 796-815. doi: 10.1007/s10957-013-0303-y.
[13]	N. Lu and Z.-H. Huang, A smoothing Newton algorithm for a class of non-monotonic symmetric cone linear complementarity problems, J. Optim. Theory Appl., 161 (2014), 446-464. doi: 10.1007/s10957-013-0436-z.
[14]	F. A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634-1654. doi: 10.1137/110837310.
[15]	F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467-488. doi: 10.1007/s10589-015-9811-z.
[16]	L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87 (2000), 1-35. doi: 10.1007/s101079900127.
[17]	C. Roos, A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16 (2006), 1110-1136. doi: 10.1137/050623917.
[18]	C. Roos, T. Terlaky and J. -Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, 1997.
[19]	J. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927-3936. doi: 10.1007/s40314-017-0554-6.
[20]	G. Q. Wang, C. J. Yu and K. L. Teo, A full-Newton step feasible interior-point algorithm for $P_{}(\kappa)$-linear complementarity problems, J. Global Optim.*, 59 (2014), 81-99. doi: 10.1007/s10898-013-0090-x.
[21]	J. Wu, L. Zhang and Y. Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, J. Glob. Optim., 55 (2013), 359-385. doi: 10.1007/s10898-012-9880-9.
[22]	Y. Xu, L. Zhang and J. Zhang, A full-modified-Newton step infeasible interior-point algorithm for linear optimization, J. Ind. Manag. Optim., 12 (2016), 103-116. doi: 10.3934/jimo.2016.12.103.
[23]	Y. Ye, Inteior Point Algorithms, Theory and Analysis, John Wiley & Sons, New York, 1997. doi: 10.1002/9781118032701.
[24]	Y. Ye, A path to the Arrow-Debreu competitive market equilibrium, Math. Program., 111 (2008), 315-348. doi: 10.1007/s10107-006-0065-5.
[25]	J. Zhang, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett., 10 (2016), 499-509. doi: 10.1007/s11590-015-0877-4.
[26]	L. Zhang and Y. Xu, A full-Newton step interior-point algorithm based on modified Newton direction, Oper. Res. Lett., 39 (2011), 318-322. doi: 10.1016/j.orl.2011.06.006.