Implement tests of certain ellipsoid class methods, part1

[GoogleCodeExporter]

The following methods of @ellipsoid class need to be covered with the unit 
tests:

%  isinternal         - Checks if given vector belongs to the union or 
intersection
%                       of given ellipsoids.

%  polar              - Computes the polar ellipsoid to an ellipsoid that 
contains
%                       the origin.

%  intersect          - Checks if the union or intersection of ellipsoids 
intersects
%                       with given ellipsoid, hyperplane, or polytope.
%  intersection_ea    - Computes the minimal volume ellipsoid containing 
intersection
%                       of two ellipsoids, ellipsoid and halfspace, or ellipsoid
%                       and polytope.
%  intersection_ia    - Computes the maximal ellipsoid contained inside the
%                       intersection of two ellipsoids, ellipsoid and halfspace
%                       or ellipsoid and polytope.
%  ellintersection_ia - Computes maximum volume ellipsoid that is contained
%                       in the intersection of given ellipsoids (can be more 
than 2).
%  ellunion_ea        - Computes minimum volume ellipsoid that contains
%                       the union of given ellipsoids.
%  hpintersection     - Computes the intersection of ellipsoid with hyperplane.

Original issue reported on code.google.com by heartofm...@gmail.com on 11 Oct 2012 at 7:14

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

The tests should be implemented within
elltool.core.test.mlunit.EllipsoidTestCase class 
(elltool in r25 of trunk is located within 
[https://ellipsoids.googlecode.com/svn/trunk/products/+elltool]

run_tests function should be in elltool.core.test package. 

[https://ellipsoids.googlecode.com/svn/trunk/products/+elltool/+test/run_tests] 
function should call your function.

Please read [MLUNITEXT_unit_testing_framework_description], 
[Toolbox_installation_instructions], [Issues_workflow_and_branching_policy]
wiki pages before you start.

Original comment by heartofm...@gmail.com on 12 Oct 2012 at 9:09

[GoogleCodeExporter]

Original comment by vkaushanskiy on 14 Oct 2012 at 3:36

• Changed state: Started

[GoogleCodeExporter]

I haven't found any information where I should write my code. Should I create 
special folder "tests" or use "ellipsoid" folder?

Original comment by vkaushanskiy on 14 Oct 2012 at 5:15

[GoogleCodeExporter]

As written in the comment 5 above you should crete elltool.core.test.mlunit 
package, it would be located in 
<YourWorkingCopy>\products\+elltool\+core\+test\+mlunit. 

In this packet you should create EllipsoidTestCase MLUNITEXT test class, the 
name of the file would be  
<YourWorkingCopy>\products\+elltool\+core\+test\+mlunit\EllipsoidTestCase.m

Along with this class you should 
 # create run_tests function in <YourWorkingCopy>\products\+elltool\+core\+test folder which would put it into elltool.core.test packet
 # Modify elltool.test.run_tests function so that it calls your newly created elltool.core.test.run_tests function in the way described item 3 on http://code.google.com/p/ellipsoids/wiki/MLUNITEXT_unit_testing_framework_description Wiki page

Original comment by heartofm...@gmail.com on 14 Oct 2012 at 5:38

[GoogleCodeExporter]

Please note that old classes (@-classes) and new classes are not compatible, we 
create a new package structure from scratch. This means that you should not pay 
attention to the location of old classes in the folder hierarchy. The location 
of new clases is \products\+elltool and everything you write should be put 
there. Of course you code will reference old classes which are not in this 
package structure but it is not a problem because the whole working copy is in 
Matlab path (of course if you followed 
http://code.google.com/p/ellipsoids/wiki/Toolbox_installation_instructions) so 
those classes will be found and called without any problems.

Original comment by heartofm...@gmail.com on 14 Oct 2012 at 5:46

[GoogleCodeExporter]

I have a question about polars. I'm trying to test singular cases.
My test example is:
q = [0, 0, 0]'
Q - zero matrix.

As I understand, the answer is R^n.
Toolbox function polar gives the empty ellipsoid.

Is it ok? And should I include this test to my test cases?

Original comment by vkaushanskiy on 16 Oct 2012 at 7:19

[GoogleCodeExporter]

The first bug is found, congratulations! Please
1) Keep the test, better - enhance it by considering a degenerated ellipsoid (a 
disk in 3d space)

2) Fix polar function so that it checks for boundeness of the resulting 
ellipsoid. If the result is not bounded - throw an exception using throwerror 
function. Example:
throwerror('degenerateEllipsoid','The resulting ellipsoid is not bounded')

3) Make the test negative by introducing a check that in the case of 
not-boundeness the proper exception is thrown. To do such checks mlunitext has 
a  special method of mlunitext.test_case class. The name of method is 
runAndCheckError. Example:

inpEll=...
self.runAndCheckError('resEll=polar(inpEll)','degenerateEllipsoid');

or

self.runAndCheckError(@doMyStuff,'degenerateEllipsoid');

where doMyStuff is a subfunction whithin a test method that looks like this:

function doMyStuff()
resEll=polar(inpEll);
end

Original comment by heartofm...@gmail.com on 16 Oct 2012 at 7:55

[GoogleCodeExporter]

I have some problems with applying assert_equal function to ellipsoids.

I have an error, when I use this function directly for ellipsoids.
Also I tried to do following: to get center and shape and to compare matrixes. 
But I haven't found any way to get ellipsoid's center and matrix in ellipsoid 
class.

Could you advise me what to do?

Original comment by vkaushanskiy on 16 Oct 2012 at 5:23

[GoogleCodeExporter]

Sure, that's easy - ellipsoids have the method that compares them and returns 1 
or 0. That is incorrect by itself and it should return a logical type but 
that's another story... So, I suggest to use the following command:

mlunitext.assert_equals(1,eq(ellExp,ellRes))

or 

mlunitext.assert_equals(true,eq(ellExp,ellRes)==1)

Original comment by heartofm...@gmail.com on 16 Oct 2012 at 5:30

[GoogleCodeExporter]

Please commit your code to your branch by the end of today so that I can have a 
look. It is not a problem if I is not finished - I just need to be able to see 
your progress. No merges back to the trunk!

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 9:03

[GoogleCodeExporter]

I've found that for checking that a point is in a degenerate ellipsoid, we use 
regularization. Should we change it or it's ok?

Original comment by vkaushanskiy on 17 Oct 2012 at 2:47

[GoogleCodeExporter]

Can you please point me to the specific place (file URL, line number)?

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 2:58

[GoogleCodeExporter]

Yes, class: ellipsoid, file: isinternal.m, line number: 118

Original comment by vkaushanskiy on 17 Oct 2012 at 2:59

[GoogleCodeExporter]

I decided to make the following test:
center = [0, 0, 0]', matrix = [1, 0, 0; 0, 2, 0; 0, 0, 0].

Let's consider the point [0.3, -0.8, eps]'.

I've found that if eps > 1e-3 than this point is not internal else it's 
internal point.

Original comment by vkaushanskiy on 17 Oct 2012 at 3:24

[GoogleCodeExporter]

There is something wrong here. eps in your example is too large - I would 
understand that [0.3, -0.8, 1e-12] would belong to the ellipsoid but not 1e-3. 
Absolute tolerance specified in ellipsoid_init is 1e-7. Do we get 1e-3 because 
we take a matrix square root? If so - we need to fix regularize so that it uses 
abs_tol^2 (absolute tolerance squared) and not just absolute tolerance. Also, 
point that you take in your test should be based on ellOptions.abs_tol i.e. you 
should make the point dependent on the global tolerance level. Please let me 
know if my explanation is unclear.

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 3:54

[GoogleCodeExporter]

I think that it's clear. I'll try to do this. Let's discuss this, if I have 
some problems.

Original comment by vkaushanskiy on 17 Oct 2012 at 4:10

[GoogleCodeExporter]

I've noticed a bug in intersect function(class ellipsoid, file: intersect.m, 
line: 302.

Test example: 
            nDim = 2;
            testEllipsoid(1) = ellipsoid(eye(nDim));
            testEllipsoid(2) = ellipsoid([2, 2]', eye(nDim));
            testHyperplane = hyperplane([1, 0]', 10);
            testRes = intersect(testEllipsoid, testHyperplane, 'i');

Undefined function 'sdpvar' for input arguments of type 'double'.

Error in ellipsoid/intersect>lqcqp (line 302)
  x         = sdpvar(size(v, 1), 1);

Original comment by vkaushanskiy on 17 Oct 2012 at 5:30

[GoogleCodeExporter]

Have you installed Yalmip? If not - just download it and unzip to YALMIP folder 
next to product folder. s_install script will take care of the rest.

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 6:10

[GoogleCodeExporter]

Ok, now it works.

Original comment by vkaushanskiy on 17 Oct 2012 at 6:16

[GoogleCodeExporter]

I'm trying simple test for intersect function:

            nDim = 2;
            testEllipsoid_1 = ellipsoid(eye(nDim));
            testEllipsoid_2 = ellipsoid([1000, -1000]', eye(nDim));
            testRes = intersect(testEllipsoid_1, testEllipsoid_2, 'i');

The answer is 1, but expected answer is 0.

As I understand, the problem is in l_elldist function(which is in distance.m 
ellipsoid class).
Could you check it?

Original comment by vkaushanskiy on 17 Oct 2012 at 8:01

[GoogleCodeExporter]

Sure, I'll do that but tomorrow after seminar. Before that I won't have any 
access to computer and won't be able to look at you code. If you have something 
 - please commit it right now (within next 10 minutes). It doesn't matter if 
your code is not finished - just show me what you have. 

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 8:07

[GoogleCodeExporter]

Ok, I've done.

Original comment by vkaushanskiy on 17 Oct 2012 at 8:12

[GoogleCodeExporter]

Could you please always write a proper commit message - it is all in the policy 
here: 
http://code.google.com/p/ellipsoids/wiki/Issues_workflow_and_branching_policy?ts
=1350504699&updated=Issues_workflow_and_branching_policy
Thanks.

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 8:16

[GoogleCodeExporter]

I don't see any tests, just some changes to polar method. Hm, I thought that 
you have at least some tests... Maybe you missted them when making a commit? To 
incldue your files into commit you need to ADD them first.

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 8:18

[GoogleCodeExporter]

I've recommited by our policy. I've done tests for 3 functions.

Original comment by vkaushanskiy on 17 Oct 2012 at 8:23

[GoogleCodeExporter]

I don't see anything, strange... 

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 8:25

[GoogleCodeExporter]

You can check by yourself whether you have commited anything or not, just right 
click your working copy, TortoiseSVN->ShowLog. If you see your commit with all 
the changes - only then it is ok.

Original comment by heartofm...@gmail.com on 17 Oct 2012 at 8:30

[GoogleCodeExporter]

Is it ok now? I had some problems with my client for Mac.

Original comment by vkaushanskiy on 17 Oct 2012 at 8:34

[GoogleCodeExporter]

Yes, now I can see your commit. thanks.

Original comment by heartofm...@gmail.com on 18 Oct 2012 at 4:51

[GoogleCodeExporter]

I've considered the question that I told you on Thusday(about intersection 
ellipsoids). I decided to download the previous version of yalmip, so, as a 
result I have the following warning:

Warning: Options LargeScale = 'off' and Algorithm = 'trust-region-reflective'
conflict.
Ignoring Algorithm and running active-set algorithm. To run 
trust-region-reflective,
set
LargeScale = 'on'. To run active-set without this warning, use Algorithm =
'active-set'. 
> In fmincon at 454
  In callfmincon at 168
  In solvesdp at 249
  In ellipsoid.distance>l_elldist at 383
  In ellipsoid.distance at 93
  In ellipsoid.intersect at 121 
Warning: Your current settings will produce an error in a future release. 
> In fmincon at 471
  In callfmincon at 168
  In solvesdp at 249
  In ellipsoid.distance>l_elldist at 383
  In ellipsoid.distance at 93
  In ellipsoid.intersect at 121 

As I understand, I should change some options, don't I?

Original comment by vkaushanskiy on 20 Oct 2012 at 7:11

[GoogleCodeExporter]

Why did you have to download the previous version? I tought we agreed that you 
compare against cvx, no?

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 7:22

[GoogleCodeExporter]

Yes, I remember it, but I've noticed that ellipsoidal toolbox, which I used 
before our project, used the previous version of yalmip, so I decided to check.
I think that this warning  "Warning: Your current settings will produce an 
error in a future release" is the best description of this problem.

Original comment by vkaushanskiy on 20 Oct 2012 at 7:27

[GoogleCodeExporter]

Btw - we can communicate via google chat if you want...

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 7:27

[GoogleCodeExporter]

Do you have this warning when using the latest version Release 20120926? If not 
- I think we need to fix Yalmip version as well so that everyone uses the same 
development platform.

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 7:31

[GoogleCodeExporter]

I did test for ellunion_ea function, but in some test cases the tolerance 
between ellunion_ea result and cvx is more then 1e-5. Is it ok and what should 
I do?

Original comment by vkaushanskiy on 20 Oct 2012 at 2:28

[GoogleCodeExporter]

I suppose that it could be connected with different ellipsoid's format, which 
used in cvx and ellunion_ea. A^(-2) must be used for converting from one format 
to another. It could be the main reason.

Original comment by vkaushanskiy on 20 Oct 2012 at 2:45

[GoogleCodeExporter]

The difference should not be greater than absolute tolerance specified in 
ellOptions structure (1e-7 at the moment). I suggest we use realizedTol<=absTol 
as the test success criteria. Have you tried to 
1) switch solver in CVX via cvx_solver command?
2) increase precision of calculations in both cvx and yalmip (the required 
precision in yalmip should be derived from abs_tol via some constant multiplier 
that should be found empirically).

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 3:07

[GoogleCodeExporter]

I use sedumi in cvx and yalmip. I also increased precision as max as possible. 
As a result, dim = 2 is OK, but dim = 3 is not.

Original comment by vkaushanskiy on 20 Oct 2012 at 5:14

[GoogleCodeExporter]

Can you write the problem in cvx using the same notation as in yalmip, i.e via 
making A^{-2} conversion? Once the optimization problems are written using 
exactly the same notation they should be easier to compare. Also, I would 
compare different notations of the same tasks in both cvx and yalmip to get a 
complete picture. ellipsoid_ea is a very important function and we need it 
polished... That is why I want to find a source of the problem.

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 5:54

[GoogleCodeExporter]

btw - much big the difference is for dim=3?

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 6:05

[GoogleCodeExporter]

No, it's about 1e-6

Original comment by vkaushanskiy on 20 Oct 2012 at 6:21

[GoogleCodeExporter]

while you are looking at the difference between the task notations can you 
please commit the test so that I have a look? I'm particularly interested in 
the way you regulate the precision of Sedumi solver depending on abs_tol...

Original comment by heartofm...@gmail.com on 20 Oct 2012 at 6:27

[GoogleCodeExporter]

I regulate sedumi solver precision using this line:
ellOptions.sdpsettings = sdpsettings('solver','sedumi','sedumi.eps',1e-18);

Original comment by vkaushanskiy on 20 Oct 2012 at 7:13

[GoogleCodeExporter]

I've noticed that the difference between ellunion_ea and cvx example is just 
only in convertation before and after the main calculation in ellunion_ea. When 
I deleted this part, the result had become the same. So, in my opinion, the my 
problem of loosing precision is invert and square matrix operations.

In addition, ellunion_ea uses quite strange regularization:
  B = sqrtm(A);
  P = ell_inv(B'*B);
  P = (1+ellOptions.abs_tol)*0.5*(P + P');

Original comment by vkaushanskiy on 20 Oct 2012 at 8:54

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I've found a bug in hpintersection. When hyperplane doesn't intersect 
ellipsoid, the function return empty ellipsoid? Should I do an exception?

Original comment by vkaushanskiy on 21 Oct 2012 at 4:01

[GoogleCodeExporter]

1) Regarding the union -  let us replace
B = sqrtm(A);
P = ell_inv(B'*B);
P = (1+ellOptions.abs_tol)*0.5*(P + P');

with 

B=inv(A);
P=0.5*(B+B.');

2) In all the union tests the test verify that the resulting ellipsoid actually 
DOES contain all the input ellipsoids with abs_tol level of tolerance. In all 
the intersection tests verify that the resulting ellipsoid is contained within 
the input ellipsoids.

3) Complement your tests with the non-trivial high-dimensional examples. You 
can use rand to generate data once but you shouldn't use rand directly in the 
tests. Instead use mat-files to store the input data. Use 
modgen.struct.test.mlunit_test_mixed, testStrucDispRegress test as an example. 
In this test the files with the data are stored in the subfolder of mlunit 
folder and loaded as follows

            inpFileName=[self.testDataRootDir,filesep,[methodName,'_inp.mat']];
            SData=load(inpFileName);

where testDataRootDir is a field of test_case class

4) As for hpintersection - let us introduce the second output argument called 
isnIntersectedMat and introduce the following check within a body of 
hpintersection:
if the function is called with a single output argument and for one of the 
input ellipsoids the result is empty - throw an exception. However if the 
second argument is requested as well - return true at the corresponding 
position and do not throw an exception.

5) I've noticed that most of the functions can accept 2-dimensional arrays of 
ellipsoids. But what will happen if you try to call with with 
higher-dimensional arrays? in hpintersect I see that size of the input array is 
requested in the following way [n,m]=size(E); For the multi-dimensional array 
inpArray like 2x3x4 [n,m]=size(inpArray) would return 2x12 which would lead to 
the size of the result being different from the size of input array. I'd 
suggest to verify that the input array is 2-dimensional and throw an exception 
(though of course the correct way to fix that would be just allowing for the 
input arrays of any size and processing them correctly).

5)  

Original comment by heartofm...@gmail.com on 21 Oct 2012 at 5:44