Parallelizing a Binary search

[Giancarlo Baldan]

Hi,
I'm trying to solve a Lyapunov-type inequality for a piecewise affine system. The formulation boils down to a quasi-convex SOS problem that can be solved via Bisection on a given variable y.
I'd like to speed up the code using a multicore machine and the parfor paradigm to solve the same SOS problem for different values of y at the same time. The main constraint is that I'd like to evaluate all the SOS constraints only once because they require quite a lot of time (since the system is piecewise affine) and then replace the value of the constant y. The closest (this is clearly not quasi-convex but it does the job!) simple example that I can write here is the following:

sdpvar x;
sdpvar y;
F=sos(-(x^2+1)+y*(x^2+0.1*x+2));
VectorConstants=[0.5, 2];
Results=0*VectorConstants;
parfor i=1:length(VectorConstants)
[sol,V,Q,res]=solvesos(replace(F,y,VectorConstants(i)));
Results(i)=sol.problem;
end

I'm experiencing two different issues:
1) Even with the parfor replaced by a simple for loop, yalmip seems to have issues understanding that y is not longer a variable after I've replaced it with a constant. The problem gets solved but, when computing the factorization, something goes wrong.
2) Even assuming that the optimization problem gets solved correctly, Matlab is unhappy with the fact that yalmip is trying to save some binary file (?). I'm not so sure about this point but I believe it's a different issue that is probably related to my poor skills with parallel coding.

Any help will be greatly appreciated.

[Johan Löfberg]

I don't understand how the code even can run. It crashes on machine due to a bug in the replace command when used in combination with a sos object. Are you really using the most recent version of YALMIP. I had to add

 Z.extra = X.extra;

on line 171 in sdpvar/replace

Having done that, the code runs fine. However, I think you are solving these multiple problems unnecessary. It looks to me as if you simply want to compute the smallest y such that the polynomial is sos. This is a standard parameterized sos problem, i.e, a sos-problem where the polynomial depends on decision variables. Since y enters the polynomial affinely, the parameterized sos-problem will lead to an SDP linear in y, hence not any harder than the sos for fixed coefficients. Look in the section Parameterized problems in http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.SumOfSquares

Hence, finding the smallest possible y would be done using

sdpvar x;
sdpvar y;
F=sos(-(x^2+1)+y*(x^2+0.1*x+2));

[sol,V,Q,res]=solvesdp(F,y);
double(y)

[Giancarlo Baldan]

Thanks a lot for your reply!

First of all, your suggestion of adding the extra line of code in sdpvar/replace solved completely the problem... can I leave that line there or is it just a patch for this particular situation? in other words... will next releases of yalmip include it or not? In any case I'm running Yalmip Version 3 (R2012a) 26-Nov-2012 on Matlab R2010b (WIN 32bit) and, in my case, the code crashed right after the solver was done... when computing the factorization of the solution (not in the replace itself... but it was crashing because it was looking for the .extra information that it couldn't find)

Second, my problem is not that simple... I just provided an example to highlight the issues I'm experiencing. My problem is similar to the DecayRate problem in http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Examples.DecayRate and, hence, it requires Bisection to be solved (or PENBMI whose license I'm still trying to obtain).

Finally, do you have any idea why Matlab complains (and ultimately crashes) if you use a parfor instead of a normal for loop? it seems that yalmip is trying to save some binary files... but I'm really unsure about this.

Giancarlo.

[Johan Löfberg]

The fix is added to the next version.

The file writing issue sounds odd. It does not happen here. I will have to try to find an old matlab installation to try to reproduce. Yalmip never writes to files unless told to (or you use csdp)

[Giancarlo Baldan]

This are the messages that MAtlab spits out... the Warning message is repeated identically  24 times (no idea why...).

Warning: YALMIP objects cannot be saved in binary format. You will run into troubles
if you try to load this file later. You should clear all YALMIP objects first, or
avoid having any YALMIP objects in the list of variables which you save.
> In sdpvar.saveobj at 3
  In distcomp.remoteparfor.remoteparfor at 41
  In parallel_function at 437
  In BoundPiecewiseLyap2DR at 183
??? Error using ==> parallel_function at 598
Error in ==> parallel_function>make_general_channel/channel_general at 879
Undefined function or method 'replace' for input arguments of type 'double'.

Error in ==> BoundPiecewiseLyap2DR at 183
parfor i=1:length(VectorConstants)

Giancarlo.

[Johan Löfberg]

Looks like you are trying to save and load sdpvar/constraInt objects. Not supported any longer.

[Giancarlo Baldan]

I tried also with Matlab R2012a 64bit under linux, and  I have the same issues when I use the parfor paradigm (did you remember to open at least 2 workers using "matlabpool local 2" ? if there is only one worker I don't get the problem since a parfor with one worker is the same as a normal for loop). The message is a little bit different though:

??? Warning: Struct field assignment overwrites a value with class "cell".
 See MATLAB 7.0.4 Release Notes, Assigning Nonstructure Variables As Structures Displays Warning for details.
> In sdpvar.loadobj at 16
  In remoteParallelFunction>iDeserializeByteBuffer at 66
  In remoteParallelFunction at 22
Warning: An error occurred when running a class's loadobj method. The object
that was loaded from the MAT-file was a copy of the object before the loadobj
method was run. The rest of the variables were also loaded from the MAT-file.
The encountered error was:
Error using sdpvar/loadobj (line 32)
Data probably saved in old YALMIP version. Cannot load this...
 
Error using parallel_function (line 589)

Inner matrix dimensions must agree.

Error stack:
recovermonoms.m at 19
replace.m at 117
replace.m at 24

Error in FindMultiPar (line 10)
parfor i=1:length(VectorConstants)
 
Giancarlo.

[Johan Löfberg]

As I said,are you saving/loading yalmip objects? You should not. It is broken and not supported

[Johan Löfberg]

You must be using an old version of yalmip as there is no line 16 in sdpvar/loadobj

[Giancarlo Baldan]

on the machine where I have Matlab 2012a there's Yalmip version 30-AUG-2012 (I don't have access to change that) ... maybe that explains the number of lines in sdpvar/loadobj.

I'm not (Intentionally) try to save any yalmip object.... I'm simply running this script:

clear all;
close all;
clc;

matlabpool size;
if (ans==0)
    matlabpool local 2;
end

sdpvar x;
sdpvar y;
F=sos(-(x^2+1)+y*(x^2+0.1*x+2));

VectorConstants=[0.5, 2];
Results=0*VectorConstants;
parfor i=1:length(VectorConstants)
    [sol,V,Q,res]=solvesos(replace(F,y,VectorConstants(i)));
    Results(i)=sol.problem;
end

I suspect Matlab is trying to save/load some Yalmip object when dealing with the parfor... if that's the case I wouldn't know how to prevent it.
  Giancarlo.

[Johan Löfberg]

After some reading it looks like parfor is based on saving the workbench before issuing parfor, and then loading that data inside each worker. This means that code which looks like

create data
create YALMIP objects
parfor...
 do stuff with YALMIP objects
end

is impossible in YALMIP, since it is unable to save YALMIP objects (previous versions had this functionality but it was broken and could lead to strange phenomena). This will not change in the coming versions of YALMIP, as saving and loading these objects have proved to be problematic, and thus has been disabled.

Code which doesn't carry any objects into the loop should not be any problem

create data
parfor...
 create YALMIP objects
 do stuff with YALMIP objects
end

Sorry for the inconvenience, but that is the current situation.

[Giancarlo Baldan]

Thanks a lot! It's too bad that Yalmip can't be used that way, but at least I know what's going on! You've been very helpful,
  Giancarlo.