×

zbMATH — the first resource for mathematics

A homogeneous model for monotone mixed horizontal linear complementarity problems. (English) Zbl 1417.90140
Summary: We propose a homogeneous model for the class of mixed horizontal linear complementarity problems. The proposed homogeneous model is always solvable and provides the solution of the original problem if it exists, or a certificate of infeasibility otherwise. Our formulation preserves the sparsity of the original formulation and does not reduce to the homogeneous model of the equivalent standard linear complementarity problem. We study the properties of the model and show that interior-point methods can be used efficiently for the numerical solutions of the homogeneous problem. Numerical experiments show convincingly that it is more efficient to use the proposed homogeneous model for the mixed horizontal linear complementarity problem than to use known homogeneous models for the equivalent standard linear complementarity problem.
MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C51 Interior-point methods
Software:
HOPDM; iOptimize; LIPSOL; OOQP; PCx
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, E.; Ye, Y., A computational study of the homogeneous algorithm for large-scale convex optimization, Comput. Optim. Appl., 10, 243-280, (1998) · Zbl 0914.90212
[2] Andersen, E.; Ye, Y., On a homogeneous algorithm for the monotone complementarity problem, Math. Program., 84, 375-399, (1999) · Zbl 0972.90078
[3] Anitescu, M.; Lesaja, G.; Potra, FA, Equivalence between different formulations of the linear complementarity problem, Optim. Methods Softw., 7, 265-290, (1997) · Zbl 0871.90095
[4] Anstreicher, K., On interior algorithms for linear programming with no regularity assumptions, Oper. Res. Lett., 11, 209-212, (1992) · Zbl 0760.90068
[5] Bonnans, JF; Gonzaga, CC, Convergence of interior point algorithms for the monotone linear complementarity problem, Math. Oper. Res., 21, 1-25, (1996) · Zbl 0846.90109
[6] Czyzyk, J., Mehrotra, S., Wright, S.J.: PCx user guide. Technical Report OTC 96/01. Optimization Technology Center, Argonne National Laboratory and Northwestern University (1996)
[7] Gertz, EM; Wright, SJ, Object-oriented software for quadratic programming, ACM Trans. Math. Softw., 29, 58-81, (2003) · Zbl 1068.90586
[8] Gondzio, J., HOPDM (version 2.12)—a fast LP solver based on a primal-dual interior point method, Eur. J. Oper. Res., 85, 221-225, (1995) · Zbl 0925.90284
[9] Gowda, MS, Reducing a monotone horizontal LCP to an LCP, Appl. Math. Lett., 8, 97-100, (1995) · Zbl 0813.65092
[10] Güler, O., Generalized linear complementarity problems, Math. Oper. Res., 20, 441-448, (1995) · Zbl 0837.90113
[11] Huang, KL; Mehrotra, S., Solution of monotone complementarity and general convex programming problems using a modified potential reduction interior point method, INFORMS J. Comput., 29, 36-53, (2017) · Zbl 1364.90328
[12] Karmarkar, NK, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[13] Lin, Y.; Yoshise, A., A homogeneous model for mixed complementarity problems over symmetric cones, Vietnam J. Math., 35, 541-562, (2007) · Zbl 1213.90192
[14] Lustig, I.; Marsten, RE; Shanno, DF, On implementing Mehrotra’s predictor-corrector interior-point method for linear programming, SIAM J. Optim., 2, 435-449, (1992) · Zbl 0771.90066
[15] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[16] Monteiro, RDC; Pang, JS, Properties of an interior-point mapping for mixed complementarity problems, Math. Oper. Res., 21, 629-654, (1996) · Zbl 0868.90126
[17] Monteiro, RDC; Pang, JS, On two interior-point mappings for nonlinear semidefinite complementarity problems, Math. Oper. Res., 23, 39-60, (1998) · Zbl 0977.90062
[18] Petra, C.G.: Homogenization of mixed horizontal LCPs and applications. Ph.D. thesis, University of Maryland, Baltimore County (2009)
[19] Sznajder, R.; Gowda, MS, Generalizations of P0- and P-properties; extended vertical and horizontal linear complementarity problems, Linear Algebra Appl., 223-224, 695-715, (1995) · Zbl 0835.90104
[20] Ye, Y., On homogeneous and self-dual algorithms for LCP, Math. Program., 76, 211-221, (1997) · Zbl 0881.90116
[21] Ye, Y.; Todd, MJ; Mizuno, S., An \({O}(\sqrt{n}{L})\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 53-67, (1994) · Zbl 0799.90087
[22] Yoshise, A., Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim., 17, 1129-1153, (2006) · Zbl 1136.90039
[23] Yoshise, A., A homogeneous algorithm for monotone complementarity problems over symmetric cones, Front. Sci. Ser., 49, 83, (2007)
[24] Zhang, D.; Zhang, Y., A Mehrotra-type predictor-corrector algorithm with polynomiality and \(Q\)-subquadratic convergence, Ann. Oper. Res., 62, 131-150, (1996) · Zbl 0854.90097
[25] Zhang, Y.: Solving large-scale linear programs by interior-point methods under the MATLAB environment. Technical Report TR96-01. University of Maryland Baltimore County (1996)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.