×

A sub-additive DC approach to the complementarity problem. (English) Zbl 1414.90364

Summary: In this article, we study a merit function based on sub-additive functions for solving the non-linear complementarity problem (NCP). This leads to consider an optimization problem that is equivalent to the NCP. In the case of a concave NCP this optimization problem is a Difference of Convex (DC) program and we can therefore use DC Algorithm to locally solve it. We prove that in the case of a concave monotone NCP, it is sufficient to compute a stationary point of the optimization problem to obtain a solution of the complementarity problem. In the case of a general NCP, assuming that a DC decomposition of the complementarity problem is known, we propose a penalization technique to reformulate the optimization problem as a DC program and prove that local minima of this penalized problem are also local minima of the merit problem. Numerical results on linear complementarity problems, absolute value equations and non-linear complementarity problems show that our method is promising.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
49M20 Numerical methods of relaxation type

Software:

CVX
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Abdallah, L., Haddou, M., Migot, T.: Solving absolute value equation using complementarity and smoothing functions. J. Comput. Appl. Math. 327, 196-207 (2018) · Zbl 1370.90297
[2] An, L.T.H., Tao, P.D.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133(1), 23-46 (2005) · Zbl 1116.90122
[3] Chen, C., Mangasarian, O.L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Program. 71(1), 51-69 (1995) · Zbl 0855.90124
[4] Chen, C., Mangasarian, O.L.: A class of smoothing functions for nonlinear and mixed complementarity problems. Comput. Optim. Appl. 5(2), 97-138 (1996) · Zbl 0859.90112
[5] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009) · Zbl 1192.90001
[6] De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75(3), 407-439 (1996) · Zbl 0874.90185
[7] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2007) · Zbl 1062.90001
[8] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7(1), 225-247 (1997) · Zbl 0873.90096
[9] Fischer, A.: Solution of monotone complementarity problems with locally lipschitzian functions. Math. Program. 76(3), 513-532 (1997) · Zbl 0871.90097
[10] Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33. Springer, Berlin (2013) · Zbl 0943.90001
[11] Fukushima, M.: Merit Functions for Variational Inequality and Complementarity Problems, pp. 155-170. Springer, USA (1996) · Zbl 0996.90082
[12] Grant, M., Boyd, S., Ye, Y.: CVX: Matlab Software for Disciplined Convex Programming (2008)
[13] Haddou, M., Maheux, P.: Smoothing methods for nonlinear complementarity problems. J. Optim. Theory Appl. 160(3), 711-729 (2014) · Zbl 1396.90085
[14] Huang, C., Wang, S.: A power penalty approach to a nonlinear complementarity problem. Oper. Res. Lett. 38(1), 72-76 (2010) · Zbl 1182.90090
[15] Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17(4), 851-868 (1996) · Zbl 0868.90123
[16] Kojima, M., Shindoh, S.: Extensions of Newton and quasi-Newton methods to systems of PC 1 equations. Institute of Technology, Department of Information Sciences (1986)
[17] Le Thi, H.A., Dinh, T.P.: On solving linear complementarity problems by DC programming and DCA. Comput. Optim. Appl. 50(3), 507-524 (2011) · Zbl 1237.90234
[18] Mangasarian, O.L.: Absolute value equation solution via concave minimization. Optim. Lett. 1(1), 3-8 (2007) · Zbl 1149.90098
[19] Mangasarian, O.L.: Absolute value equation solution via linear programming. J. Optim. Theory Appl. 161(3), 870-876 (2014) · Zbl 1293.90041
[20] Migot, T., Haddou, M.: A smoothing method for sparse optimization over polyhedral sets. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, pp 369-379. Springer, Berlin (2015) · Zbl 1370.90177
[21] Qi, L., Sun, D., Zhou, G.: A new look at smoothing newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87(1), 1-35 (2000) · Zbl 0989.90124
[22] Solodov, M.V.: Constraint qualifications. Wiley Encyclopedia of Operations Research and Management Science. Wiley, New York (2010)
[23] Tao, P.D., Bernoussi, S.E.: Duality in D.C. (Difference of Convex functions) Optimization. Subgradient Methods, pp. 277-293. Birkhäuser Basel, Basel (1988)
[24] Tao, P.D., An, L.T.H.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289-355 (1997) · Zbl 0895.90152
[25] Tao, P.D., An, L.T.H.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476-505 (1998) · Zbl 0913.65054
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.