[ibexopt] bad optimum bounds (loup<uplo)

[gchabert]

The following run on the attached problem gives loup<uplo (tested on v2.8.7) ./ibexopt -r1e-3 -a1e-30 --eps-h=1e-8 --rigor ~/Tmp/BIOMD0000000272debug.txt BIOMD0000000272debug.txt

and using --kkt fails in debug mode with an assertion violated.

[Glawal]

After some tests, it seems to appear only in rigor mode.

[gchabert]

OK, here are explanations. It took quite a lot of time because your problem is really ill-formed, as you will see.

The first thing is that you cannot ask ibex to certify feasibility when the number of equations exceed the number of variables. In your problem you have 7 equations so the rigor mode is inapplicable. However Ibex had a buggy behavior in this case, I agree. I never tested that so far. So I've just made a fix (see https://github.com/ibex-team/ibex-lib/commit/abdab2d6d2db7bff00ffe5b514b26c8bc3daa5d8 in the develop branch) and now, if you run ibexopt in rigor mode, you will see plenty of warnings:

warning: too many active constraints, cannot prove feasibility -> loup lost!

and the optimizer will never end.... which is fine.

Now, going back to your model: Equations 5 and 6 are redundant and enforce x4=0 so you have to throw one away. But, then, a second problem in your model appears: equation 4 then enforces x3=0 and this value is outside your domain (infeasibility) and the same problem would appear with x2 so I just set all domains to something like [-1e8,1e8].

Then a third problem appears: equations 2 and 3 are redundant and enforce x1x2=0. It is impossible to certify equations numerically in case of redundant constraints, would there be less than the number of variables, as this enforce somehow a permanent singularity. So you need to throw again one of them.

But then, a fourth problem in your model appears. You have an infinity of global minima (x4=0), all reached in the line of points satisfying x5+x6=k13. So ibex is basically running again and again trying to handle all of them. So you need to add an equation, e.g., x5=0;

And then a last problem appears: you are running ibexopt with a goal absolute precision (-a1e-30) which is drastically less than the equation inflation parameter (--eps-h=1e-8). You should never do that!... because filtering with the relaxed equations would not eventually be powerful enough to perform bounding.

So, finally, with the model modified as I've suggested and running ibex as follows:

./ibexopt -r1e-3 -a1e-8 --eps-h=1e-12 --rigor ~/Tmp/BIOMD0000000272debug.txt
BIOMD0000000272debug.txt

it gives an immediate and correct result:

 optimization successful!

 f* in  [-9.99999999999e-09,9.88131291683e-324]
    (best bound)

 x* in  ([75.99999999999997, 76.00000000000003] ; [-1.48219693752374e-323, 1.48219693752374e-323] ; [-9.881312916824931e-324, 9.881312916824931e-324] ; [-9.881312916824931e-324, 9.881312916824931e-324] ; <-0, 0> ; [999.2929999999997, 999.2930000000002])
    (best feasible point)

 relative precision on f*:  1.00000000001
 absolute precision on f*:  1e-08 [passed] 
 cpu time used:         3.00000000001e-06s
 number of cells:       0

Gilles

[gchabert]

edit:

you are running ibexopt with a goal absolute precision (-a1e-30) which is drastically less than the equation inflation parameter (--eps-h=1e-8). You should never do that!... because filtering with the relaxed equations would not eventually be powerful enough to perform bounding.

As noticed by G. Trombettoni, the problem is actual not related to upper bounding (which still occurs) but lower bounding. In rigor mode, the loup does not take into account relaxation and is stuck to the real (non-relaxed) system minimum. On the other hand, the uplo results from contraction and is stuck to the relaxed-system minimum. If eps-h is drastically less than the absolute precision (note: in your problem, relative precision is ineffective because the minimum is 0), then the gap between the loup and the uplo never reaches it.

In non-rigor mode, there is no problem of this kind.