ad icon indicating copy to clipboard operation
ad copied to clipboard

Feasibility finder often loops on Newton constrainedDescent

Open identicalsnowflake opened this issue 5 years ago • 0 comments

import Data.Functor.Identity
import Numeric.AD (auto)
import Numeric.AD.Newton

ex :: [ (Double , Identity Double) ]
ex = constrainedDescent (const (auto 1)) cs (Identity 18.5)
  where
    cs = [ CC \(Identity x) -> auto 0.0 - x
         , CC \(Identity x) -> x - auto 10.0
         ]

The above is simply trying to find a feasible value between 0 and 10, with a starting guess of 18.5.

It works for starting values below 18.4, but as soon as I try anything 18.5 or above, it just loops indefinitely.

I tried digging through the code some, and if I change that nrSteps = [take 20 | _ <- [1..length tValues]] ++ [id] line in constrainedConvex' to take 60 steps instead of 20, I have some more success, but I can still get failures just by increasing my starting guess a bit further.

I'm not entirely familiar with what's going on, but it looks like the search attempts often converge on infeasible solutions. I think it's because the earlier attempts try smaller steps, but bail out if a solution is not found quickly, while later attempts are taking such large steps that they converge on something outside the bounds entirely. Perhaps it would make sense to re-try smaller steps if the big steps converge, starting from that point?

identicalsnowflake avatar May 12 '19 19:05 identicalsnowflake