A Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems
- PDF / 395,625 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 168 Views
A Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems Soodabeh Asadi1,2 · Zsolt Darvay3 · Goran Lesaja4,5 · Nezam Mahdavi-Amiri1 · Florian Potra6 Received: 9 March 2020 / Accepted: 20 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, a full-Newton step Interior-Point Method for solving monotone Weighted Linear Complementarity Problem is designed and analyzed. This problem has been introduced recently as a generalization of the Linear Complementarity Problem with modified complementarity equation, where zero on the right-hand side is replaced with the nonnegative weight vector. With a zero weight vector, the problem reduces to a linear complementarity problem. The importance of Weighted Linear Complementarity Problem lies in the fact that it can be used for modelling a large class of problems from science, engineering and economics. Because the algorithm takes only full-Newton steps, the calculation of the step size is avoided. Under a suitable condition, the algorithm has a quadratic rate of convergence to the target point on the central path. The iteration bound for the algorithm coincides with the best iteration bound obtained for these types of problems. Keywords Weighted complementarity · Interior-point · Path-following · Full-Newton step Mathematics Subject Classification 90C33 · 90C51
1 Introduction The Weighted Linear Complementarity Problem (WLCP) has recently been introduced by Potra [1]. Many equilibrium problems in economics can be formulated as a skewsymmetric WLCP. Likewise, the linear programming and weighted centering (LPWC) problem, proposed by Anstreicher [2], can be formulated as a skew-symmetric WLCP.
Communicated by Nobuo Yamashita.
B
Goran Lesaja [email protected]
Extended author information available on the last page of the article
123
Journal of Optimization Theory and Applications
In [1], Potra showed that the Fisher problem [3] reduces to a skew-symmetric WLCP. He generalized the LPWC by introducing a quadratic programming and weighted centering (QPWC) problem, and showed that the QPWC and its dual lead to a monotone WLCP. He defined a smooth central path for WLCP being different from the one considered for the Fisher equilibrium problem of Ye [3]. The starting point belongs by construction to the central path. This is not the case with the modified central path of Ye [3]. In fact, Ye used a potential reduction method to produce a point in a certain neighborhood of the modified central path. Furthermore, Potra [1] proposed two interior-point methods (IPMs) for solving the monotone WLCP both of which follow the aforementioned smooth central path. The first IPM of [1] is as an extension of the largest-step path-following method of McShane [4]. The algorithm requires one matrix factorization per iteration and has the same computational complexity as the short-step algorithm, but it is more efficient in practice, because it works directly with the starting point on the central path, w
Data Loading...
