Article Contents
Article Contents

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

• * Corresponding author: Zhongping Wan
• 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.

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

 Citation:

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

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

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

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

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
•  [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.

Figures(4)

Tables(1)