Closed GoogleCodeExporter closed 9 years ago
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
[deleted comment]
[deleted comment]
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
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
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
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
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
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
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:
Thanks Sri, this is definitively going to help!
Original comment by cesarso...@gmail.com
on 10 Nov 2014 at 9:49
[deleted comment]
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
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
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
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:
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
[deleted comment]
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
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
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
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:
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
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
Original comment by cesarso...@gmail.com
on 8 Dec 2014 at 9:13
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
Original issue reported on code.google.com by
Chanchik...@gmail.com
on 24 Jan 2013 at 7:24