.png){kind=icon}
.png){kind=icon}
Return
A Heuristic for Complementarity Problems Using Difference of Convex Functions
.png){kind=icon}
PRE
AI
DOI：10.1287/ijoc.2024.0822.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a new difference of convex functions algorithm (DCA) for solving linear and nonlinear mixed complementarity problems (MCPs). The approach is based on the reformulation of bilinear complementarity constraints as difference of convex (DC) functions, more specifically, the difference of scalar, convex quadratic terms. This reformulation gives rise to a DC program, which is solved via sequential linear approximations of the concave term using standard DCA techniques. The reformulation is based on a generalization of earlier results on recasting bilinearities and leads to a novel algorithmic framework for MCPs. Through extensive numerical experimentation, the proposed approach, referred to as DCA-BL, proves to be an efficient heuristic for complementarity problems. For linear complementarity problems (LCPs), we test the approach on a number of randomly generated instances by varying the size, the density, and the eigenvalue distribution of the LCP matrix, providing insights into the numerical properties of DCA-BL. In addition, we apply the framework to a market equilibrium problem and find that DCA-BL scales well on realistic LCP instances. Also, through experimentation, we find that that DCA-BL performs particularly well compared with other DC-based complementarity approaches in the literature if the LCP is highly dense, asymmetric, or indefinite. Lastly, the method is successfully applied to a set of equilibrium problems with second-order cone constraints, which give rise to nonlinear complementarity problems, with applications to stochastic equilibrium problems in water infrastructure and finance.
Keywords:
DC programming
complementarity problems
equilibrium problems
infrastructure modeling
portfolio selection
Journal
I
IF:
2.1
Papers:
86
Citations:
3.2K
Organization
View more organizations