×

zbMATH — the first resource for mathematics

Feasibility problems with complementarity constraints. (English) Zbl 1346.90762
Summary: A Projected-Gradient Underdetermined Newton-like algorithm will be introduced for finding a solution of a Horizontal Nonlinear Complementarity Problem (HNCP) corresponding to a feasible solution of a Mathematical Programming Problem with Complementarity Constraints (MPCC). The algorithm employs a combination of Interior-Point Newton-like and Projected-Gradient directions with a line-search procedure that guarantees global convergence to a solution of HNCP or, at least, a stationary point of the natural merit function associated to this problem. Fast local convergence will be established under reasonable assumptions. The new algorithm can be applied to the computation of a feasible solution of MPCC with a target objective function value. Computational experience on test problems from well-known sources will illustrate the efficiency of the algorithm to find feasible solutions of MPCC in practice.

MSC:
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
HSL; levmar; MacMPEC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreani, R.; Dunder, C.; Martínez, J. M., Nonlinear-programming reformulation of the order-value optimization problem, Mathematical Methods of Operations Research, 61, 3, 365-384, (2005) · Zbl 1114.90464
[2] Andreani, R.; Júdice, J. J.; Martínez, J. M.; Patrício, J., On the natural merit function for solving complementarity problems, Mathematical Programming, 130, 1, 211-223, (2011) · Zbl 1236.90127
[3] Andreani, R.; Júdice, J. J.; Martínez, J. M.; Patrício, J., A projected-gradient interior-point algorithm for complementarity problems, Numerical Algorithms, 57, 4, 457-485, (2011) · Zbl 1229.65097
[4] Anitescu, M., On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints, SIAM Journal on Optimization, 15, 4, 1203-1236, (2005) · Zbl 1097.90050
[5] Anitescu, M.; Tseng, P.; Wright, S. J., Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties, Mathematical Programming, 110, 2, 337-371, (2007) · Zbl 1119.90050
[6] Benson, H. Y.; Sen, A.; Shanno, D. F.; Vanderbei, J., Interior-point algorithms, penalty methods and equilibrium problems, Computational Optimization and Applications, 34, 2, 155-182, (2006) · Zbl 1121.90124
[7] Bomze, I. M., Copositive optimization-recent developments and applications, European Journal of Operational Research, 216, 3, 509-520, (2012) · Zbl 1262.90129
[8] Chen, X., Smoothing methods for complementarity problems and their applications: a survey, Journal of the Operations Research Society of Japan, 43, 32-47, (2000) · Zbl 0998.90078
[9] Chen, X.; Yamamoto, T., Newton-like methods for solving underdetermined nonlinear equations with nondifferentiable terms, Journal of Computational and Applied Mathematics, 55, 3, 311-324, (1994) · Zbl 0823.65048
[10] Ehrenmann, A.; Neuhoff, K., A comparison of electricity market designs in networks, Operations research, 57, 2, 274-286, (2009) · Zbl 1181.90177
[11] Fang, H.; Leyffer, S.; Munson, T., A pivoting algorithm for linear programming with linear complementarity constraints, Optimization Methods and Software, 27, 1, 89-114, (2012) · Zbl 1311.90152
[12] Fernandes, L.; Friedlander, A.; Guedes, M.; Júdice, J. J., Solution of a general linear complementarity problem using smooth optimization and its application to bilinear programming and lcp, Applied Mathematics & Optimization, 43, 1, 1-19, (2001) · Zbl 1033.90132
[13] Ferris, M. C.; Pang, J. S., Engineering and economic applications of complementarity problems, Siam Review, 39, 4, 669-713, (1997) · Zbl 0891.90158
[14] Fletcher, R.; Leyffer, S., Solving mathematical programs with complementarity constraints as nonlinear programs, Optimization Methods and Software, 19, 1, 15-40, (2004) · Zbl 1074.90044
[15] Fukushima, M.; Luo, Z. Q.; Pang, J. S., A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Computational Optimization and Applications, 10, 1, 5-34, (1998) · Zbl 0904.90153
[16] Fukushima, M.; Tseng, P., An implementable active-set algorithm for computing a b-stationary point of a mathematical program with linear complementarity constraints, SIAM Journal on Optimization, 12, 3, 724-739, (2002) · Zbl 1005.65064
[17] García-Rodenas, R.; Verastegui-Rayo, D., A column generation algorithm for the estimation of origin-destination matrices in congested traffic networks, European Journal of Operational Research, 184, 3, 860-878, (2008) · Zbl 1141.90013
[18] Gowda, M. S., Reducing a monotone horizontal lcp to an lcp, Applied Mathematics Letters, 8, 1, 97-100, (1995) · Zbl 0813.65092
[19] Guo, L.; Lin, G.-H.; Zhang, D.; Zhu, D., An mpec reformulation of an epec model for electricity markets, Operations Research Letters, 43, 3, 262-267, (2015)
[20] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Mathematical Programming, 137, 1-2, 257-288, (2013) · Zbl 1262.65065
[21] HSL, A collection of fortran codes for large scale scientific computation, (2013)
[22] Hu, X.; Ralph, D., Using epecs to model bilevel games in restructured electricity markets with locational prices, Operations research, 55, 5, 809-827, (2007) · Zbl 1167.91357
[23] Hu, X. M.; Ralph, D., Convergence of a penalty method for mathematical programming with complementarity constraints, Journal of Optimization Theory and Applications, 123, 2, 365-390, (2004)
[24] Jiang, H.; Ralph, D., Extension of quasi-Newton methods to mathematical programs with complementarity constraints, Computational Optimization and Applications, 25, 1-3, 123-150, (2003) · Zbl 1038.90100
[25] Júdice, J. J., Optimization with linear complementarity constraints, Pesquisa Operacional, 34, 3, 559-584, (2014)
[26] Júdice, J. J.; Sherali, H. D.; Ribeiro, I. M.; Faustino, A. M., Complementarity active-set algorithm for mathematical programming problems with equilibrium constraints, Journal of Optimization Theory and Applications, 134, 3, 467-481, (2007) · Zbl 1145.90075
[27] Kanzow, C.; Yamashita, N.; Fukushima, M., Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics, 173, 2, 321-343, (2005) · Zbl 1065.65070
[28] Kovacevic, R. M.; Pflug., C. G., Electricity swing option pricing by stochastic bilevel optimization: a survey and new approaches, European Journal of Operational Research, 237, 2, 389-403, (2014) · Zbl 1304.91218
[29] Leyffer, S., Macmpec: ampl collection of mpecs, Argonne National Laboratory, (2000)
[30] Leyffer, S.; López-Calva, G.; Nocedal, J., Interior methods for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 17, 1, 52-77, (2006) · Zbl 1112.90095
[31] Li, D. H.; Fukushima, M., A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optimization Methods and Software, 13, 3, 181-201, (2000) · Zbl 0960.65076
[32] Lin, G.-H.; Fukushima, M., Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: a survey, Pacific Journal of Optimization, 6, 3, 455-482, (2010) · Zbl 1200.65052
[33] Lin, G.-H.; Zhang, D.; Liang, Y.-C., Stochastic multiobjective problems with complementarity constraints and applications in healthcare, European Journal of Operational Research, 226, 3, 461-470, (2013) · Zbl 1292.90218
[34] Luo, Z. Q.; Pang, J. S.; Ralph, D., Mathematical programs with equilibrium constraints, (1996), Cambridge University Press
[35] Murty, K. G., Linear complementarity, (1988), Linear and Nonlinear Programming, Heldermann, Berlin · Zbl 0634.90037
[36] Outrata, J.; Kocvara, M.; Zowe, J., Nonsmooth approach to optimization problems with equilibrium constraints: theory, applications and numerical results, 28, (1998), Springer Science & Business Media · Zbl 0947.90093
[37] Pang, J. S., Partially b-regular optimization and equilibrium problems, Mathematics of Operations Research, 32, 3, 687-699, (2007) · Zbl 1341.90145
[38] Ralph, D., Nonlinear programming advances in mathematical programming with complementarity constraints, Royal Society, (2007)
[39] Ralph, D.; Stein, O., The c-index: a new stability concept for quadratic programs with complementarity constraints, Mathematics of Operations Research, 36, 3, 504-526, (2011) · Zbl 1243.90219
[40] Scheel, H.; Scholtes, S., Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity, Mathematics of Operations Research, 25, 1, 1-22, (2000) · Zbl 1073.90557
[41] Toyasaki, F.; Daniele, P.; Wakolbinger, T., A variational inequality formulation of equilibrium models for end-of-life products with nonlinear constraints, European Journal of Operational Research, 236, 1, 340-350, (2014) · Zbl 1338.90415
[42] Walpen, J.; Mancinelli, M. E.; Lotito, P. A., A heuristic for the od matrix adjustment problem in a congested transport network, European Journal of Operational Research, 242, 3, 807-819, (2015) · Zbl 1341.90028
[43] Wu, D.; Yin, Y.; Lawphongpanich, S., Pareto-improving congestion pricing on multimodal transportation networks, European Journal of Operational Research, 210, 3, 660-669, (2011) · Zbl 1213.90068
[44] Yao, J.; Adler, I.; Oren, S. S., Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network, Operations Research, 56, 1, 34-47, (2008) · Zbl 1167.90408
[45] Yao, J.; Oren, S. S.; Adler, I., Two-settlement electricity markets with price caps and Cournot generation firms, European Journal of Operational Research, 181, 3, 1279-1296, (2007) · Zbl 1123.90333
[46] Ye, J. J., Necessary optimality conditions for multiobjective bilevel programs, Mathematics of Operations Research, 36, 1, 165-184, (2011) · Zbl 1218.90180
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.