search

chkwon / Complementarity.jl

provides a modeling interface for mixed complementarity problems (MCP) and math programs with equilibrium problems (MPEC) via JuMP
Other
75 stars 20 forks source link

Question on return type :StationaryPointFound #60

Open sarkispa opened 2 years ago

sarkispa commented 2 years ago

Hi, I am getting back the :StationaryPointFound message every time I try to solve a particular MCP model with :PATH but I cannot make sense of what this exactly means, and why it is different than a :Solved status for example. Providing a MWE for this issue is going to be relatively complicated but I will try to provide some details.

The problem is an energy dispatch problem from firms to markets, with constraints on supply and market-clearing given a demand function and Cournot competition. A previous iteration of that model was solving when using a 1st-order Taylor approximation on a nonlinear part of the model. We are now trying to solve the model without relying on that approximation. At the stationary point, the residual is greater than the convergence tolerance although not large (~2.5-3.5), the FOCs of the problem are all relatively close to 0 (between ~1e-5 and 0.5) and the variables of interest are believable, but hard to say if optimal. When I try to use :NLsolve instead, I get back three errors:

Again, looking for details on these messages was unfruitful. I have tried to make firms price-taking, remove shipping costs, make all firms identical, use a larger tolerance, etc. but nothing gets me out of the :StationaryPointFound message.

Let me know if I can provide more details, or if you have an idea of what's going on here. Thanks!

chkwon commented 2 years ago

As far as I understand, the PATH solver converts the MCP into an equation, say f(x)=0 and then applies a special Newton's method. The residual is the value of f(x) at the end. I believe :StationaryPointFound happens when the iterative scheme of Newton's method converged to a point, but it is not a solution to the MCP.

The function f(x) in the converted equation does not enjoy good computational properties in general unless your MCP satisfies certain conditions. This explains why your first-order Taylor approximation worked.

You can read about the PATH solver here: http://pages.cs.wisc.edu/~ferris/techreports/cstr1179.pdf