Predicting errors while using sossolve with the penbmi solver

[Yannick Zakowski]

Hello,

Here's a bit of general context : I am a (french) computer scientist (student actually) interested in invariant inference. I happen to be confronted with quite wild constraints : non-linear polynomials, with bi-linear parametrization. Auxiliary, I'm trying to use the objective function in order to "guide" the solver toward a meaningful invariant.

Now here's a practical example I'm experiencing :

clear all; yalmip ('clear');
sdpvar x y a b c l l1 l2 l3 l4;
I = a*x^2+b*y^2+c;
F = [sos(I - l1*x -l2*(1-x) -l3*y -l4*(1-y)), l1>=0, l2>=0, l3>=0, l4>=0]; % Precondition
F = F + [sos(a*(3/4*x-1/8*y)^2+b*(3/4*x-1/8*y)+c-l*I), l>=0] % Consecution
sol = solvesos(F, a^2+b^2+c^2, sdpsettings('solver','penbmi'), [a;b;c;l;l1;l2;l3;l4])
disp(sprintf('%+g*x^2 %+g*y^2 %+g >= 0', double(a)*10000, double(b)*10000, double(c)*10000));

It's an exampe among others, just to illustrate precisely the kind of stuff I'm doing.

And here comes my problem: from one example to another, or simply by tweaking my objective function, I regularly (actually, in most cases) two different errors:

"PENBMI Error:
Stopped by linesearch failure. Result may be wrong.

PENBMI failed."

"PENBMI Error:
Stopped by iterations counter. Result may be wrong.

PENBMI failed."

I digged a bit both through the basics of optimization theory and the specific papers dedicated to penbmi, but am still far from an expert. I therefore don't manage to understand either how to avoid these errors, or how to configure penbmi in order to dodge these. I might even be doing a more fundamental error through the way I formulate my problem that I would not be aware of?

I'm sorry for how vague can my question be, but any indication or pointers toward relevant documentation would be of great help.

Thanks a lot,
Best,

Yannick.

[Johan Löfberg]

I would say it is essentially unpredictable  You are trying to solve bilinear SDPs, which simply is very hard. PENBMI is the only publically available solver, and it just doesn't perform better than this on generic models. Either dig deep into the details on what the resulting SDP look like and try to improve that, or device your on SDP solver for these problems (or come up with a better SOS model)

[Johan Löfberg]

To begin with,

sos(a*(3/4*x-1/8*y)^2+b*(3/4*x-1/8*y)+c-l*I)

You are squaring I (talk about variable set up for bugs, is it 1,l or I?) which contains parametric variables, so you introduce parametric nonlinearities. However, you essentially have f(x)-L^2>=0. This is equivalent to 

[f(x) L;L 1]>=0

I.e., a matrix condition. This is linear in L. Apply matrix-sos on this instead.

...just an examples on things you might want to investigate

[Johan Löfberg]

ha ha. Tried it, and when I copied it to matlab it turned out that the poor variable name indeed struck. In Chrome, l*I looks like the same two letters, in MATLAB it was clear you multiplied (small L times capital i).

So, the matrix sos approach won't work. 

[Yannick Zakowski]

Well actually my poor choice of variable name is missleading : i am not squaring l, but writing "lambda * parametric_Invariant". This pattern comes from a Lagrangian relaxation of the property: Inv => Inv(after affectations)

[Yannick Zakowski]

I think that the bilinear aspect is inherent to my approach. Therefore, when you said that penbmi simply don't handle well such generic problems, do you suggest that some specific subclass of bmi problems are better handle? If so, would you know which they are so that I could see if I manage to fit my framework into it ?

By the way, thank a lot for your time!

[Johan Löfberg]

So are you working in Cousouts group?

Anyway, what I am saying is that if you want to be able to solve these problems robustly, it will require a significant effort, be it development of special solvers, or a deep analysis of the generated SDPs in order to see if they have some feature which can be exploited/removed etc to help the solver (SOS problems often have problems that the solution doesn't have any strict interior due to monomials in the decomposition which simply cannot be in there, and this can easily lead to problems for the solver. YALMIP spends some effort to improve this (Newton polytope, symmetry reductions etc) but it might be that you have to do these things manually to get an even better model).

Progress on modelling and applications of LMIs has been vast and is a pretty mature field. On the BMI side, I would say essentially nothing has happened since the late 90s when they started to appear. The lack of public general solver is a clear symptom of this. A theory and model based on LMIs is highly useful since we actually can solve these relatively robustly (problem => LMI => case closed), while one the BMI side, going from a generic problem description to a BMI formulation takes us a very short distance closer to an actual solution (problem => BMI => hmm...)

Adding to that, BMIs are from a computational complexity point of view intractable, hence one could never expect to much.

[Yannick Zakowski]

Actually no, but we're trying to follow their work, coupled with other ideas :)

My hope were/are that despite being an hard problem, the reasonable size of our problems (degree usually lower than 4, no more than 5 variables, hence less than 150 parameters in the worst case, amount which can be highly reduced) would still allow it to work. But it seems like it's even already hard with two variables, at degree 2.

Thanks again for your answers, I'll try to investigate this to see if we have a chance or not. I'm quite disappointed that Cousot did not mention any of this in his papers and rather seemed optimistic.

Best,
Yannick.

[Johan Löfberg]

Don't lose your faith completely. There might be useful schemes to attack this, looks like a fun challenge.

BTW, isn't the problem ill-posed as a=b=c=l1=l2=l3=0 is optimal, isn't it?

[Yannick Zakowski]

Yeah you're definitely right, the trivial invariant is always true here. I can easily exclude it, but it didn't popped here when I launched the solver on this example.

[Johan Löfberg]

Maybe stating the obvious: This problem is most easily solved by simply fixing l to a constant value, which yields a linear SOS problem.