A small model that stress the QP solver with zero as start values

[Programmer-Magnus]

I hope this discussion can be used to improve ActiveSetSolver, IterativeRefinementSolver and IterativeRefinementSolver2.

The test testZECEVIC2 was run using 56.0.0-SNAPSHOT.

I think that the testZECEVIC2 with a zero vector as start guess might be fruitful to debug. Its a small model that trigger the
"Break cycle on redundant constraints because step length..." in ActiveSetSolver, and then it believe it is done, which is not true, returning a bad solution. (Note: Using the default LP start guess, ActiveSetSolver and IterativeRefinementSolver1/2 finds the optimal solution.) But I think this test can be used to understand+improve the ActiveSetSolver.

Details:
Several excluded constraints get the same stepLength at the last iteration and the same is always found because they are searched in the same order.
Would it be possible to start looking for an excluded constraint to include, on the index after the getLastExcluded() constraint, if getLastExcluded() is set.
This way all constraints with best stepLength would be included-then-excluded before trying something else.

Using testZECEVIC2 as a test for the IterativeRefinementSolver2 solver (modifying the initial start guess to also be a zero vector). It will believe it converged, but it will return the wrong solution.
a.
This might indicate that computing the zoom factor by multiplying the last zoom factor with the present error is not perfect.
b.
It also seems like neither IterativeRefinementSolver or IterativeRefinementSolver2 change active set during their iterations.

Finding:
If reverting the order in which the excluded constraints are compared it will succeed with zero as start vector.
(ActiveSetSolver.java, L:125)

If above can be solved remember this:
If using "extendedPrecision(true)" (IterativeRefinementSolver) for this model it will fail.
This is because it will then be given a start guess being the zero vector.

[apete]

Yes, interesting case.

The key fix I found is to not record the "history" of last included/excluded when setting up the initial set of active inequalities. Doesn't really make sense to that, and it caused a problem in this case.

I liked the idea (on how) to cycle through the excluded constraints. Not sure it solved any problems, but didn't cause any either (at least not with the "reset history" thing already applied). Think I'll keep this change.

You can test the changes I made in the refinement branch.

[Programmer-Magnus]

Great that you found a fix for this.
Debugging your change using this test, I found a bug in the IterativeRefinementSolver for when there is no equilibrium conditions. Then the relative residual got to large because magnitude of inequalities was not considered. I fixed this and refactored the code slightly. Its included in the IterativeRefinment one parameter branch.

Regarding the ActiveSetSolver, something similar to this might be a useful optimization with many excluded constraints:

After fraction becomes ZERO, stepLength can no longer change and the loop can be aborted. This will avoid the computation of .dot products earlier in the loop, at the cost of one comparison when stepLength is changed.

if (ZERO <= fraction && fraction < stepLength) { stepLength = fraction; this.setConstraintToInclude(excluded[i]); if (this.isLogDebug()) { this.log(1, "Best so far: {} @ {} ({}) ––– {} / {}.", stepLength, i, excluded[i], currentSlack, slackChange); } if (stepLength == ZERO) { break; } }