A predictor-corrector interior-point algorithm for \(P_\ast (\kappa )\)-horizontal linear complementarity problem. (English) Zbl 1298.90116
Summary: We present a predictor-corrector path-following interior-point algorithm for \(P_\ast (\kappa )\) horizontal linear complementarity problem based on new search directions. In each iteration, the algorithm performs two kinds of steps: a predictor (damped Newton) step and a corrector (full Newton) step. The full Newton-step is generated from an algebraic reformulation of the centering equation, which defines the central path and seeks directions in a small neighborhood of the central path. While the damped Newton step is used to move in the direction of optimal solution and reduce the duality gap. We derive the complexity for the algorithm, which coincides with the best known iteration bound for \(P_\ast (\kappa )\)-horizontal linear complementarity problems.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C51 | Interior-point methods |
Keywords:
horizontal linear complementarity problem; predictor-corrector algorithm; polynomial complexityReferences:
| [1] | Ai, W.B., Zhang, S.Z.: An O(\sqrt{n}L)\(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems. SIAM J. Optim. 16(2), 400-417 (2005) · Zbl 1122.90078 · doi:10.1137/040604492 |
| [2] | Asadi, S., Mansouri, H.: Polynomial interior-point algorithm for P∗(κ)\(P_*(\kappa )\)-horizontal linear complementarity problems. Numer. Algorithms 63(2), 385-398 (2013) · Zbl 1332.65075 · doi:10.1007/s11075-012-9628-0 |
| [3] | Darvay, Z.: New interior-point algorithms in linear programming. Adv. Model. Optim. 5(1), 51-92 (2003) · Zbl 1136.90509 |
| [4] | Darvay, Z.: A new predictor-corrector algorithm for linear programming. Alkalmazott matematikai lapok 22, 135-161 (2005). In hungarian · Zbl 1136.90391 |
| [5] | Gurtuna, F., Petra, C., Potra, F.A., Shevehenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48, 453-485 (2011) · Zbl 1242.90260 · doi:10.1007/s10589-009-9263-4 |
| [6] | Illés, T., Nagy, M.: A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems. Eur. J. Oper. Res. 181, 1097-1111 (2007) · Zbl 1123.90347 · doi:10.1016/j.ejor.2005.08.031 |
| [7] | Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373-395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150 |
| [8] | Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems Lecture Notes in Computer Science, vol. 538. Springer-Verlag, Berlin (1991) · Zbl 0766.90077 · doi:10.1007/3-540-54509-3 |
| [9] | Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for P∗(κ)\(P_*(\kappa )\)-linear complementarity problems. SIAM J. Optim. 20(6), 3011-3039 (2010) · Zbl 1211.90160 · doi:10.1137/090766735 |
| [10] | Mizuno, S., Todd, M.J., Ye, Y.: On adaptive-step primal-dual interior point algorithms for linear programming. Math. Oper. Res. 18, 964-981 (1993) · Zbl 0810.90091 · doi:10.1287/moor.18.4.964 |
| [11] | Stoer, J., Wechs, M.: Infeasible-interior-point paths for sufficient linear complemetarity problems and their analyticity. Math. Program. 83, 407-423 (1998) · Zbl 0922.90136 |
| [12] | Väliaho, \(H.: P∗P_*\)-matrices are just sufficient. Linear Algebra Appl. 239, 103-108 (1996) · Zbl 0851.15015 |
| [13] | Wang, G.Q., Bai, Y.Q.: Polynomial interior-point algorithm for P∗(κ)\(P_*(\kappa )\) horizontal linear complementarity problem. J. Comput. Appl. Math. 233, 248-263 (2009) · Zbl 1183.65072 · doi:10.1016/j.cam.2009.07.014 |
| [14] | Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1), 208-227 (1994) · Zbl 0803.90092 · doi:10.1137/0804012 |
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.
