A Full-Newton step infeasible-interior-point algorithm for P*(k)-horizontal linear complementarity problems
DOI:
https://doi.org/10.2298/YJOR130515034AKeywords:
horizontal linear complementarity problem (HLCP), infeasible-interior point method, central pathAbstract
In this paper we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problem (HLCP). This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by suitable perturbation in HLCP problem. Then, we use so-called feasibility steps that serves to generate strictly feasible iterates for the next perturbed problem. After accomplishing a few centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration complexity for infeasible interior-point methods.References
Anitescu, M., Lesaja, G., Potra, F.A., Equivalence between different formulations of the linear complementarity problem, Optimization Methods and Software, 7(3) (1997) 265-290.
Karmarkar, N. K., A new polynomial-time algorithm for linear programming, Combinatorica, 4(4) (1984) 373-395.
Ai, W.B., Zhang, S.Z., An O(nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems, SIAM Journal on Optimization, 16(2) (2005) 400-417.
Potra, F.A., Wright, S.J., Interior-point methods, Journal of Computational and Applied Mathematics, 124(1-2) (2000) 281-302.
Gonzaga, C., Bonnans, J., Fast convergence of the simplified largest step path following algorithm, Mathematical Programming, 76(1) (1997) 95-115.
Huang, Z.H., Polynomiality of high-order feasible interior point method for solving the horizontal linear complementarity problems, Journal of System Science and Mathematical Sciences, 20(4) (2000) 432-438.
Mansouri, H., Asadi, S., A quadratically convergent O(n) interior-point algorithm for the P(•)-matrix horizontal linear complementarity problem, Journal of Sciences, Islamic Republic of Iran, 23(3) (2012) 237-244.
Asadi, S., Mansouri, H., Polynomial interior-point algorithm for P(•) horizontal linear complementarity problem, Numerical Algorithms, 63(2) (2012) 385-398.
Zhang, Y., On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization, 4(1) (1994) 208-227.
Stoer, J., Wechs, M., Mizuno, S., High order infeasible-interior-point methods for solving sufficient linear complementarity problems, Mathematics of Operations Research, 23(4) (1998) 832-862.
Stoer, J., Wechs, M., The complexity of high-order predictor-corrector methods for solving sufficient linear complementarity problems, Optimization Methods and Software, 10(2) (1998) 393-417.
Roos, C., A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM Journal on Optimization, 16(4) (2006) 1110-1136.
Mansouri, H., Roos, C., A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization, Numerical Algorithms, 52(2) (2009) 225-255.
Mansouri, H., Zangiabadi, M., Pirhaji, M., A full-Newton step O(n) infeasible interior-point algorithm for linear complementarity problems, Nonlinear Analysis: Real World Applications, 12(1) (2011) 545-561.
Stoer, J., Wechs, M., Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity, Mathematical Programming, 83(1-3) (1998) 407-423.
Gurtuna, F., Petra, C., Potra, F.A., Shevehenko, O., Vancea, A., Corrector-predictor methods for sufficient linear complementarity problems, Computational Optimization and Applications, 48(3) (2011) 453-485.
Roos, C., Terlaky, T., Vial, J.-Ph., Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, UK, 1997 (2nd Edition, Springer, 2006).
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
