Fix integration with Multi-Parametric Toolbox

[GoogleCodeExporter]

Some methods of ellipsoid, hyperplane, reach classes depend on classes from 
Multi-Parametric Toolbox (available from 
http://control.ee.ethz.ch/~mpt/downloads/). One of such classes is polytope 
class (you can run a search for 'polytope' string within all ellipsoid toolbox 
m-files.

You need to 
1) Download MTP and put it into mtp folder next to cvx. Please do not commit it 
to svn.
2) Write the tests that cover all functionality of ellipsoid toolbox related to 
MPT. If you encounter a bug - fix it. 

Original issue reported on code.google.com by heartofm...@gmail.com on 24 Feb 2013 at 3:53

[GoogleCodeExporter]

I've faced some troubles in using arrayfun with polytopes. I'm not  
entirely sure, but I think this is because of realisation .size() function for 
polytopes. So, I'll use for loops instead of arrayfun with polytopes.

Original comment by justente...@gmail.com on 25 Feb 2013 at 11:21

[GoogleCodeExporter]

Original comment by justente...@gmail.com on 3 Mar 2013 at 7:35

• Changed state: Started

[GoogleCodeExporter]

I think we need to talk about intersection_ea. The algorithm it uses to compute 
minimum volume ellipsoid, containig intersection of ellipsoid and polytope, is 
wrong, as i think, and I don't know how to fix it.

Original comment by justente...@gmail.com on 5 Mar 2013 at 3:22

[GoogleCodeExporter]

And in intersection_ia algorithm is wrong too. I think, that i know how to fix 
it using cvx, but if i'll do it, then how to verify the result, without using 
the same algorithm.

Original comment by justente...@gmail.com on 5 Mar 2013 at 5:23

[GoogleCodeExporter]

I have an idea - what if you build a polytope EP that is an ellipsoid 
triangulation for some ellipsoid E(use gras.geom.tri.spheretri function to 
build a triangulation of a sphere triangulation and then multiply the vertex 
coordinates by sqrtm(Q) to get an ellipsoid triangulation).

Then compare the approximation of intersection(E,P) with intersection (E,EP) 
and make sure that they are close with some level of precision.

Original comment by heartofm...@gmail.com on 14 Mar 2013 at 1:14

[GoogleCodeExporter]

Please have a look at this article - 
http://www.iri.upc.edu/people/ros/WebEllipsoids/pdfs-ellipsoids/ICRA1991.pdf

The article covers the implemented algorithm of external approximation of 
ellipsoid and a stripe intersection. When applied to polytops the algorithm 
won't give the minimum volume ellipsod, that is for sure. In this case we can 
talk about SOME external estimate that is neither tight nor minimal-volume. 
This estimate is better than nothing. 

Thus I suggest that you check that when you intersect an ellipsoid and a 
polytope you get a minimum-volume ellipsoid in certain simple cases. One of 
such cases would be an intersection of a unit-ball with a such polytope that 
makes the optimal external approximation of the intersection equal to the same 
unit-ball i.e. intersection_ia(unitBall,somePolytope)=unitBall. To build a 
polytope that satisfies this equality you need just get a piece of paper and 
find the coordinates of politope edges. I suggest that you start with 
2-dimensional case and a stripe.

After you are done with the unit-ball case just apply some affine 
transformation to both the unit-ball and the polytope and apply 
intersection_ea. The result should still coincide with the transformed unit 
ball.

Original comment by heartofm...@gmail.com on 18 Mar 2013 at 5:13

[GoogleCodeExporter]

Answering your question whether to make a presence of MPT obligatory... I think 
the answer should be "yes", at least for now as it is the most simple and 
robust approach. Later we can make it optional if we want. 

See  init() method in elltool.conf.Properties class - it is called from 
s_install (via ellipsoids_init) and performs initialization of the toolbox. In 
particular it uses  elltool.cvx.CVXController class to set up CVX. I suggest we 
create a similar class for MPT (elltool.mpt.MPTController) with similar 
methods. To make the approach generic I'd suggest to create an interface for 
these methods and place it into elltool.external.IExtTBXController and make 
both  elltool.cvx.CVXController and elltool.mpt.MPTController inherit it. in 
Properties.init() we need to use MPTController in the same way as CVXController 
for initialization. Finally instead of copying-pasting the calls like 

elltool.cvx.CVXController.setUpIfNot();
elltool.mpt.MPTController.setUpIfNot();

I think we need to create a list of controllers and just call their methods in 
a loop. This way we will be able to add integration with other external 
toolboxes if necessary just by writing a controller and placing it into the 
list in Properties class.

Finally, we need to make sure that make MPT tests run as part of our test 
coverage.

Original comment by heartofm...@gmail.com on 25 Mar 2013 at 4:17

[GoogleCodeExporter]

Original comment by heartofm...@gmail.com on 26 Mar 2013 at 9:29

• Added labels: Priority-Critical

[GoogleCodeExporter]

i've got some problems with cvx today. it throws an exeption during 
initialization:
"Error using cvx_global (line 144)
All solvers were disabled due to errors or license issues.
Please re-run CVX_SETUP and, if necessary, contact CVX Research for support."

Original comment by justente...@gmail.com on 26 Mar 2013 at 9:31

[GoogleCodeExporter]

i've got some problems with cvx today. it throws an exeption during 
initialization:
"Error using cvx_global (line 144)
All solvers were disabled due to errors or license issues.
Please re-run CVX_SETUP and, if necessary, contact CVX Research for support."

Original comment by justente...@gmail.com on 26 Mar 2013 at 9:31

[GoogleCodeExporter]

Please let me know if the following sequence helps

1) close matlab, remove cvx
2) type prefdir, go to the displayed folder and manually delete cvxprefs.mat
3) download and install cvx from 
http://ellipsoids.googlecode.com/files/cvx_2_0_build890.zip
4) start matlab and make sure that s_install finishes correctly

Original comment by heartofm...@gmail.com on 26 Mar 2013 at 9:36

[GoogleCodeExporter]

Yes, it helped.

Original comment by justente...@gmail.com on 26 Mar 2013 at 9:52

[GoogleCodeExporter]

Original comment by justente...@gmail.com on 26 Mar 2013 at 1:09

• Changed state: ReadyForReview

[GoogleCodeExporter]

Am I correct that you've completed the first part of the ticket so that we can 
reintegrate and then work on the second part?

Original comment by heartofm...@gmail.com on 26 Mar 2013 at 2:21

[GoogleCodeExporter]

I  think yes.

Original comment by justente...@gmail.com on 26 Mar 2013 at 3:15

[GoogleCodeExporter]

Original comment by heartofm...@gmail.com on 26 Mar 2013 at 6:02

• Changed state: ReadyForReintegration

[GoogleCodeExporter]

So, what about reintegration? I'm waiting now, until current errors in the 
trunk will be fixed, am i right?

Original comment by justente...@gmail.com on 28 Mar 2013 at 8:37

• Changed state: ReadyForReview

[GoogleCodeExporter]

I think Irina has just fixed them but let us wait and see the test results to 
make sure that all the tests pass. Once they do - go ahead and reintegrate. 
Also, which version of MTP should I use. And should I just put it next cvx?

Original comment by heartofm...@gmail.com on 28 Mar 2013 at 12:04

• Changed state: ReadyForReintegration

[GoogleCodeExporter]

I use MPT 2.6.3 version. After putting it nex to cvx you need to add mtp to 
path and initialize it
>> addpath(genpath('/path/to/mpt/'));
>> mpt_init;

Original comment by justente...@gmail.com on 28 Mar 2013 at 12:08

[GoogleCodeExporter]

Hm, then I think we need to hold on a bit. We need to have an automatic 
initialization as with CVX (see comment #7), i.e. mpt_init should be called 
from Properties.init 

Please implement this functionality and then we will re-integrate

Original comment by heartofm...@gmail.com on 28 Mar 2013 at 2:26

• Changed state: New

[GoogleCodeExporter]

I've implemented this functionality. 

Original comment by justente...@gmail.com on 30 Mar 2013 at 8:21

• Changed state: ReadyForReview

[GoogleCodeExporter]

Please fix a few problems I found (see my comment to your last commit)

Original comment by heartofm...@gmail.com on 30 Mar 2013 at 12:19

• Changed state: ReviewFailed

[GoogleCodeExporter]

Please provide a self-contained piece of Matlab code that reproduced the 
performance problem you mentioned on the 1st of April on the seminar. If you 
already have a test - please specify its name.

Original comment by heartofm...@gmail.com on 1 Apr 2013 at 4:19

[GoogleCodeExporter]

The problem is that this code:

nDims = 20;
ell20D = ellipsoid(eye(nDims ));
poly20D = 
polytope(struct('H',[eye(nDims);-eye(nDims)],'K',(1/sqrt(nDims))*ones(nDims*2,1)
);
isInside = isinside(ell20D ,poly20D);

will work really long. Longer than 15 minutes on my computer.

Original comment by justente...@gmail.com on 1 Apr 2013 at 9:34

[GoogleCodeExporter]

Please do the following - completely remove MPT (and make sure that all the 
preferences file that might exist are also deleted). Then unzip it next to cvx 
and run Matlab using the special shortcut for toolbox. If MPT is installed and 
ready for use - please reintegrate.

Original comment by heartofm...@gmail.com on 2 Apr 2013 at 2:28

• Changed state: ReadyForReintegration

[GoogleCodeExporter]

I found a problem - please have it fixed prior to reintegration. In 
Properties.init()

in setUpToolbox function you use switch operator. Please 
1) define SETUP_METHOD_NAME_VEC = 
{'elltool.cvx.CVXController','elltool.mpt.MPTController'};
2) Instead of switch use the following approach
obj=feval(className);
3) Why do you return res=0 from setEllToolbox? Please have it removed.

Original comment by heartofm...@gmail.com on 2 Apr 2013 at 3:23

• Changed state: ReviewFailed

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Please rename elltool.controllers into elltool.exttbx and then reintegrate

Original comment by heartofm...@gmail.com on 2 Apr 2013 at 7:22

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Regarding the performance problem - I had an idea.

To detect that polytope P belongs to Ellipsoid E it is sufficient (please 
check) to verify that a polar of P contains a polar of E.

You can read about polar sets in Rockafellar. Wets "Variational Analysis" or 
somewhere else in the internet. The good thing is that a polar of an ellipsoid 
is also an ellipsoid. The same is true for polytope (see 
http://www.inf.ethz.ch/personal/fukudak/polyfaq/node7.html)

But unfortunately finding a polar of a polytope requires finding its vertices 
i.e. we still require extreme method.

Another idea I have is to apply an affine transformation that shapes the 
ellipsoid into a ball and a polytope - into a different polytope. Then to check 
that the polytope is contained within a ball you need to solve a linear 
optimization problem of finding a single vertex with maximum distance from 
ellipsoid center. Please check if it computationally easier than finding all 
the vertices.

If not - let us keep it as is BUT just make sure you vectorize the code in 
isinside for polytopes (arrayfun instead of loops).

And please reintegrate MPTController changes ASAP.

http://www.inf.ethz.ch/personal/fukudak/polyfaq/node7.html

Original comment by heartofm...@gmail.com on 4 Apr 2013 at 3:04

[GoogleCodeExporter]

I was ready for reintegrate about half an hour ago, but now, after vetaliy 
reintegrated i should run tests again. So, probably, i can reintegrate only on 
saturday.

Original comment by justente...@gmail.com on 4 Apr 2013 at 7:37

[GoogleCodeExporter]

Also, as i said, arrayfun does not work with polytopes. That's why i'm using 
loops with polytopes.

Original comment by justente...@gmail.com on 4 Apr 2013 at 7:50

[GoogleCodeExporter]

Second method, that you described in comment 30 require ellipsoid to be 
nondegenerate. We can regularise  ellipsoid matrix, but if  ellipsoid and 
polytope are both degenerate, I'm not sure, that after regularization we will 
get right answer.

Original comment by justente...@gmail.com on 5 Apr 2013 at 9:52

[GoogleCodeExporter]

Right, at least please see if we can get a speedup for non-degenerate 
ellipsoids...
And please describe what else remains to be done for this ticket (tests, 
functionality changes etc). Thanks.

Original comment by heartofm...@gmail.com on 6 Apr 2013 at 10:43

• Changed state: New

[GoogleCodeExporter]

I need to speed up isinide method and make tests for method of ellipsoid 
intersection_ea, and method of reach intersect.

Original comment by justente...@gmail.com on 7 Apr 2013 at 9:19

[GoogleCodeExporter]

Please do not forget that you need to re-create the branch for the ticket and 
the current one is useless after merge.

Original comment by heartofm...@gmail.com on 7 Apr 2013 at 1:03

[GoogleCodeExporter]

I've improved a unification of MPTController and CVXController a bit (in 
trunk), please provide a real implementation for checkSettings method in 
MPTController.

Original comment by heartofm...@gmail.com on 8 Apr 2013 at 9:33

[GoogleCodeExporter]

Original comment by justente...@gmail.com on 9 Apr 2013 at 4:34

• Changed state: Started

[GoogleCodeExporter]

Will your implementation of checkSettings work after clear global?

Original comment by heartofm...@gmail.com on 9 Apr 2013 at 9:20

[GoogleCodeExporter]

No, it wont. So, if global is cleared, should we throw an error, or initialize 
mpt again?

Original comment by justente...@gmail.com on 12 Apr 2013 at 6:45

[GoogleCodeExporter]

Let's throw an exception.

Original comment by heartofm...@gmail.com on 12 Apr 2013 at 6:48

[GoogleCodeExporter]

Original comment by justente...@gmail.com on 13 Apr 2013 at 6:14

• Changed state: ReadyForReview

[GoogleCodeExporter]

A few things still need to be done (see my comments to your last commit).

Original comment by heartofm...@gmail.com on 14 Apr 2013 at 12:39

• Changed state: ReviewFailed

[GoogleCodeExporter]

Original comment by justente...@gmail.com on 15 Apr 2013 at 3:09

• Changed state: Started

[GoogleCodeExporter]

The discription of contains(firstEllArr, secondEllArr):
% CONTAINS - checks if one ellipsoid contains the other.
%            The condition for E1 = firstEllArr to contain
%            E2 = secondEllArr is
%            min(rho(l | E1) - rho(l | E2)) > 0, subject to <l, l> = 1.
%
You can see, that here we checking if firstEllArr contains secondEllArr.
Description of isinside(fstEllArr, secObjArr, mode):
% ISINSIDE - checks if the intersection of ellipsoids contains the
%            union or intersection of given ellipsoids or polytopes.
%
%   res = ISINSIDE(fstEllArr, secEllArr, mode) Checks if the union
%       (mode = 'u') or intersection (mode = 'i') of ellipsoids in
%       secEllArr lies inside the intersection of ellipsoids in
%       fstEllArr...
Isinside can do the same things as contains, and more. But they are using 
different algorithms.

Original comment by justente...@gmail.com on 15 Apr 2013 at 3:17

[GoogleCodeExporter]

Or, at least, their code looks different.

Original comment by justente...@gmail.com on 15 Apr 2013 at 3:27

[GoogleCodeExporter]

isinside seem to call contains but I think that "isinside" is a bad name for 
this method. I suggest to do the following:

1) Rename isinside into isIntersectContains in all the tests and let Irina know 
about this

2) Implement a normal isinside method that could accept both ellipsoid and 
polytop as a second input (in case of ellipsoid you just call 
secEll.contains(self));

As of course, we need tests for this new method.

Original comment by heartofm...@gmail.com on 15 Apr 2013 at 5:10

[GoogleCodeExporter]

Also, i found, that you can call
ell(27) = ellipsoid();
ell2 = reshape(ell,[3,3,3]);
display(ell2);
and result will be "3x9 array of ellipsoids", while size(ell2) is [3,3,3]. Is 
it a bug?

Original comment by justente...@gmail.com on 15 Apr 2013 at 5:10

[GoogleCodeExporter]

I think so, we already have issue 66 to fix this, added this as a comment there.

Original comment by heartofm...@gmail.com on 15 Apr 2013 at 5:19

[GoogleCodeExporter]

[deleted comment]