GoldfarbIdnaniQuadraticSolver class failed to give correct answer

[GoogleCodeExporter]

What steps will reproduce the problem?
1. create the GoldfarbIdnaniQuadraticSolver with the following constraints

A   B   C   D   Op  Val
0.0732  0.0799  0.1926  0.0047  =   0.098
1   1   1   1   =   1
1   0   0   0   >=  0
0   1   0   0   >=  0
0   0   1   0   >=  0
0   0   0   1   >=  0
1   0   0   0   >=  0.5

2. minimize with
Q:
0.12264004  0.011579293 0.103326825 0.064073439
0.011579293 0.033856    0.014311947 0.014732381
0.103326825 0.014311947 0.17715681  0.067615114
0.064073439 0.014732381 0.067615114 0.11539609
and 
d:
0   0   0   0

What is the expected output? What do you see instead?
the expected results are
A   B   C   D
0.5 0.336259542 0.163740458 0

The output are
A   B   C   D
0.5 0.3996  0.1543  -0.0539

What version of the product are you using? On what operating system?
the version is 2.8.1.0 Last Published on 12/21/2012
OS is Window XP

Please provide any additional information below.
development Tools is Visual Studio 2010 Professional
more Properties from the solver:
Deletions: 2
Iterations: 7
Lagrangian[0]: 0.47610163141385442
Lagrangian[1]: 0.018357076997984511
Lagrangian[2]: 0.0
Lagrangian[3]: 0.0
Lagrangian[4]: 0.0
Lagrangian[5]: 0.057217556502738381
Lagrangian[6]: 0.057966723535120945
Solution[0]: 0.5
Solution[1]: 0.39959370168854663
Solution[2]: 0.15434219180400793
Solution[3]: -0.053935893492554586
Value: 0.03092710642619409

Original issue reported on code.google.com by Chanchik...@gmail.com on 24 Jan 2013 at 7:24

[GoogleCodeExporter]

There are some cases in which the Goldfarb-Idnani really fails to provide a 
correct answer. For future reference, in case anyone is interested, to solve 
this issue, it would be needed to setup more test cases, then check against the 
original FORTRAN [1] implementation by Berwin A. Turlach to see if it produces 
the same results. If it does not, then it would be possible to pinpoint the 
issue by checking the execution of the two programs.

[1]: http://school.maths.uwa.edu.au/~berwin/software/quadprog.html

Original comment by cesarso...@gmail.com on 1 Jun 2013 at 10:48

• Changed state: Accepted
• Added labels: Priority-High
• Removed labels: Priority-Medium

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Hi Chanchik...@gmail.com

Your answer to the question:
"
What is the expected output? What do you see instead?"
namely:
"the expected results are
A   B   C   D
0.5 0.336259542 0.163740458 0"

is not correct.

The product of your expected result and the first constraint row does not meet 
the   right-hand-side ( 0.098 ) . Instead it only equals 0.095.

Incidentally both R and Matlab arrive at the correct expected result namely:

R:
$solution
0.50000000000000 0.30967169476486 0.19032830523514 0.00000000000000

Matlab:

X =

   0.50000000000000
   0.30967169476486
   0.19032830523514
                  0

I did confirm that the Accord.Net.Math.Optimization.GoldfarbIdnani solver gives 
the error you describe above. So the port from Fortran to C# has not been 
perfect.

I wish I could get a Fortran test set up to look at both simultaneously !

Original comment by janakisr...@gmail.com on 7 Nov 2014 at 9:43

[GoogleCodeExporter]

Hi janakisri1964!

Thanks for taking a look at this issue! Regarding your last remark, it is 
actually possible to look at both at the same time. I did the same to test 
against LibLBFGS, Lbfgsb3 and Quadpack. The solution has a project named 
"Accord.Tests.Math.Cpp" which contains all C++ code that is called from the 
unit tests in order to compare results. What is needed to be done to finally 
solve this issue is to convert the Quadrprog code to C++ using a reliable 
automatic tool, and then follow both the C++ and the Accord.NET port using the 
test case posted here.

I will try to set up at least the C++ code in the test project.

Thanks and best regards,
Cesar

Original comment by cesarso...@gmail.com on 8 Nov 2014 at 8:47

[GoogleCodeExporter]

I just added an automated C++ translation of the original Fortran code into the 
unit tests project.

 https://github.com/accord-net/framework/commit/9dbc466a961f53a76cae478dcd14b36abae7f65c

Original comment by cesarso...@gmail.com on 8 Nov 2014 at 8:36

[GoogleCodeExporter]

Hi janakisri1964,

Actually, thanks a lot for posting the corrected expected values. I had tried 
to isolate this particular bug in the past, but since I could never match the 
values reported here, I ended up postergating the issue. It never occurred to 
me the reported expected values could have been wrong.

I think I might have found the issue, I will update shortly.

Original comment by cesarso...@gmail.com on 9 Nov 2014 at 4:26

[GoogleCodeExporter]

A potential fix has been committed to the GitHub repository.

https://github.com/accord-net/framework/commit/c7103f3f889d86d6e95a045bae3ab9a03
9038780

Original comment by cesarso...@gmail.com on 9 Nov 2014 at 5:20

• Changed state: Started

[GoogleCodeExporter]

Thank You Cesar!

The issue is now fixed with the above sample.

I'm going to try another project where I've been using Accord.Math to check if 
the errors there are now fixed

Appreciate your jumping and finding the correction so fast,

Sri

Original comment by janakisr...@gmail.com on 10 Nov 2014 at 2:20

[GoogleCodeExporter]

Dear Cesar , I do see another bug and I 'm attaching a .cs file which should 
illustrate the problem . ( plus 3 data files for the hessian , the constraints 
and the rhs for the constraints)

The expected value is :

variable 2  = 0.74083116998144
variable 13 = 0.14799651298617
variable 14 = 0.11117231703249

rest of variable are zero at the solution.

value of the optimization at the optimum = 0.049316494677822

GoldfarbIdnani.cs actually gives :

variable 2  = 0.74218827871682258
variable 13 = 0.19509631681640696
variable 14 = 0.064354801771370068

Rest of variables are zero in GoldfarbIdnani as well.

value of the optimization at the optimum in GoldfarbIdnani  = 
0.049320902704394452

which is slightly higher than the optimum value of 0.049316494677822( I ran it 
in R)

FYI: the problem is overspecified with lower and upper bounds  on each variable 
, plus 2  global bounds ( equalities ) 

When I eliminate all the variables except the 3 that either solution picks , 
then they both give exactly the same result:
variable 1 = 0.740831373
variable 2 = 0.14799639709
variable 3 = 0.111172230143

So the R solution gives the same result when there are more variables that are 
not used in the final solution , but the Accord.Math solution changes the 
solution depending on the other variables ( even when they are not used in its 
final solution ).

I have not gotten into debugging using the c++ test project . Some hints on 
what to look for might help!

Thanks

Sri

Original comment by janakisr...@gmail.com on 10 Nov 2014 at 9:25

Attachments:

• CTest.cs
• dmatFull.csv
• constraintMatrix11_15.csv
• constraints11_14.csv

[GoogleCodeExporter]

Thanks Sri, this is definitively going to help!

Original comment by cesarso...@gmail.com on 10 Nov 2014 at 9:49

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Thanks again! Apparently, this was again being caused by off-by-one errors that 
originated from the fact that Fortran's arrays are 1-based instead of 0-based. 
However, I couldn't still obtain the _exact_ same results as R. They are 
similar only up to 5 decimal places.

The potential fix has been committed in
https://github.com/accord-net/framework/commit/7fcadedce2b580edbe85b1375b1104155
0c33248

If you have more test cases, please let me know!

Original comment by cesarso...@gmail.com on 11 Nov 2014 at 1:45

[GoogleCodeExporter]

This definitely has fixed the earlier issue. I have a 100-point test just to 
see if there are results at each point over an array of r-h-s for 1st 
constraint row. Previous versions failed to find a solution at stretches of 
points (   they seemed to be clustered around a few pivots). This version 
worked flawlessly through each of the 100-point test .

I am going to do more tests with various hessians and equality constraints to 
test further .Its looking good right now.

Thanks a ton , Cesar!

Original comment by janakisr...@gmail.com on 11 Nov 2014 at 2:45

[GoogleCodeExporter]

Incidentally , the results ( optimization value) differ in 9th or 10th decimal 
place in my testing with Accord.Math and R :

R gets                0.049316494677822
Accord.Math gets      0.049316495006437963

Could it be that it is stopping slightly earlier than optimal ( 
Constants.DoubleEpsilon ) ?

To me it doesn't matter . Its as close as zero difference

Thanks

Sri

Original comment by janakisr...@gmail.com on 11 Nov 2014 at 3:42

[GoogleCodeExporter]

Hi Cesar !

The problem is not fully resolved yet. I am enclosing a slightly different 
constraint set and RHS , with the same hessian as before ( post #10 in this 
issue , #33). The revised code( your post #13 ) fails with no possible solution 
, but R succeeds .

R value at optimum = 0.048224950997808 
Accord.Math        NoPossibleSolution

R:
$solution
variable 2 =0.41144782323407
variable 13=0.27310552838116
variable 14=0.31544664838498

Accord.Math =
Iterations=21
Deletions=13

I can send any other info you need.

Original comment by janakisr...@gmail.com on 12 Nov 2014 at 5:11

Attachments:

• constraintMatrix11_15.csv
• constraints11_14.csv

[GoogleCodeExporter]

Hi Sri,

It _seems_ that this is related to the fact that the results differs slightly. 
Actually, the Accord solutions seems to converge to the same answer, but it 
can't approximate it with sufficient precision, thus it gives up and says the 
problem is not solvable. However, if you take a look on the Solution property 
of the GoldfarbIdnani object, it will be already quite close, up to 5 decimal 
places.

In any case, I am still investigating the issue.

Original comment by cesarso...@gmail.com on 13 Nov 2014 at 9:50

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Thanks Cesar for this insight. 

I also realized that some pruning of the constraint matrix might be in order . 
For example the two constraint rows left-hand-side at the very end ( 
inequalities ) are the same as the second constraint row left-hand-side ( 
equality ).

(Well the very last one has all the signs reversed but is essentially the same 
as the second equality row)

If this is the only problem , I might as well pre-process the constraint matrix 
to remove inequality rows which are already represented in equalities 

Today I will investigate if that has anything to do with it.

Sri

Original comment by janakisr...@gmail.com on 13 Nov 2014 at 1:51

[GoogleCodeExporter]

There is another problem . It goes into an infinite loop under certain 
combinations of constraints. I found that it had already converged  as you 
pointed out  , so I added a check if the Iteration count exceeded a large 
number , and just declared it solved at that point , which seems to work fine.( 
no actual constraints seemed to have been violated in the solution)

 L50: // start a new iteration 

     Iterations++;
     if (Iterations > 1000)
     {
            return;
     }

Original comment by janakisr...@gmail.com on 17 Nov 2014 at 2:06

[GoogleCodeExporter]

Thanks! Can you please give me an example that results in the infinite loop 
issue? I will be adding support for specifying tolerance threshold for each 
constraints. This will hopefully help mitigate the issue as well!

Regards,
Cesar

Original comment by cesarso...@gmail.com on 17 Nov 2014 at 2:09

[GoogleCodeExporter]

I'm attaching the constraint lhs and rhs files . The other files are same as 
originally. the solution in Accord.Math pretty much converges to the one found 
in R.  

R Solution
Variable 2    : 0.4                      (0.4 , same in Accord)
variable 4    : 0.0016271524831373       (0.0016274211014407616 in Accord)
variable 19   : 0.59837284751686         (0.59837257889855644 in Accord)

All the rest are ~ zero at the solution in both.

value in R           : 0.052870914138455
value in Accord.Math : 0.052870912320705628 ( i.e. very slightly better than R )
However the Iteration count in Accord is 1001 and would go much higher          
    ( ~ Infinite) but for the exit on Iteration count

Original comment by lakshma...@gmail.com on 17 Nov 2014 at 7:49

Attachments:

• constraints11_14.csv
• constraintMatrix11_15.csv

[GoogleCodeExporter]

Dear Cesar ,
Were you able to use the files to see the problem?

I have some time off end of December and I can devote some to studying this 
issue and plan to

Sri

Original comment by lakshma...@gmail.com on 4 Dec 2014 at 2:19

[GoogleCodeExporter]

Hi Sri,

It seems like the last modification that I made, to introduce tolerance values 
in the constraints, also solved the infinite loop problem you were 
experiencing. I am incorporating your files in the automatic testing framework, 
and I will make a new release soon.

Thanks again for all the help! If you notice further problems, please let me 
know.

The latest sources are available at GitHub, but if you wish here are some of 
the updated binaries:

  - https://dl.dropboxusercontent.com/u/32601472/accord/releases/git-05-12-2014.rar

Best regards,
Cesar

Original comment by cesarso...@gmail.com on 6 Dec 2014 at 2:37

[GoogleCodeExporter]

Original comment by cesarso...@gmail.com on 8 Dec 2014 at 9:13

• Changed state: Fixed

[GoogleCodeExporter]

Thanks for the updates. Indeed the problem seems to be fixed with respect to 
the loop and I don't see any new ones .I will be testing more intensively in 
the next few days and let you know how it goes

Appreciate your help a lot

Sri

Original comment by lakshma...@gmail.com on 9 Dec 2014 at 3:05