L1 filtering - GoldfarbIdnani

[NorthwoodCapitalManagement]

Hi,

I am trying to solve a particular optimization problem. It is a trend filtering technique called L1 which you can find here for more details: http://web.stanford.edu/~boyd/papers/pdf/l1_trend_filter.pdf.

I have attached a screenshot of the original problem (y is the signal and x is the trend which we are trying to compute).

This dual problem is QP and I thought of using your GoldfarbIdnani algorithm to solve it. Please see the second screenshot.

I have attached a rather simple/not-optimized (in any sense) code sample (in a word format ...).

code_sample.docx

I have also attached a graph showing the input data, the output of the attached code sample and the same problem resolved by an R package (https://github.com/hadley/l1tf). As you can see, the ouput I get from Accord is far from what it should/could be.

I was wondering if you were able to identify any issue: am I mis-specifying the problem in Accord? Are there any limitations for which this solver wouldn't work? I am surprised to see only 5 iterations steps, is there a way to increase the number of iterations? Do you have any other suggestions?

Many thanks for your help. I am not sure it is even the right place to ask this kind of questions. Feel free to redirect me.

Kind regards, Charles

Ps: I have created the same issue on StackOverflow if that's the right place for such a question: http://stackoverflow.com/questions/43364539/accord-net-l1-trend-filtering-goldfarbidnani

Help Topic: http://accord-framework.net/docs/html/M_Accord_Math_Optimization_GoldfarbIdnani__ctor_3.htm

[NorthwoodCapitalManagement]

Changing the subtraction into an addition in GetResult: res[i] = input[i] + adjustment[i]; actually makes Accord.Net and R match. I don't really get why so if someone has an explanation I would gladly hear it, but I understand it might be off topic.

[blaisexen]

Hello,,

Do you mean to say that there was a bug in the framework? that the subtraction was wrong, the addition is right?

[NorthwoodCapitalManagement]

Hi, Many thanks for your response. I wouldn't go as far as to say that there is a bug in the framework. However, equation (14) in the above screenshot (which I have checked from a mathematical point of view) shows that it should be a subtraction, not an addition. I see two possibilities so far: 1) I have wrongly set-up the problem in Accord (very likely) 2) Accord returns the solution with the wrong sign (which I seriously doubt). I am happy to help if you think there might be a bug down the line.

[blaisexen]

Hi,

cesarsouza is not here, lets wait for him, I hope he comes in.

thank you

[cesarsouza]

Hello Charles,

Many thanks for the interest in the framework and for opening the issue! The Goldfarb Idnani implementation in the framework should produce roughly the same results as R's solve.QP function from the package 'quadprog'. However, one difference in the implementations is that sign of the 'd' vector is inverted in respect to solve.QP. In case you are not accounting for this difference, they this might explain the inversion of results you are getting.

To illustrate how to get equivalent results in R and Accord.NET, please consider the following example. Let's say we have a QP problem expressed in R as:

solve.QP(matrix(c(10, -3,  1, -3, 11, -2, 1, -2, 12), 3, 3), c(1,5,3), 
               t(matrix(c(-4, 2, 1, -3, 1, -2, 0, -1, 2), 3,3)), c(-8,4,-1))

Then, in order to express this in Accord we would need:

double[,] D =
{
    { 10, -3,  1 },
    { -3, 11, -2 },
    {  1, -2, 12 },
};

double[] d = { 1, 5, 3 };

double[,] A = 
{
    { -4,  2,  1 },
    { -3,  1, -2 },
    {  0, -1,  2 },
};

double[] b = { -8, 4, -1 };

var qp = new GoldfarbIdnani(D, d.Multiply(-1), A.Transpose(), b);

Please note that instead of passing d, the method is passing d.Multiply(-1) as the linear parameter of the Goldfarb Idnani constructor.

I hope it helps,

Cesar

[NorthwoodCapitalManagement]

Many thanks Cesar for your detailed explanation. Re-reading your very interesting post (http://crsouza.com/2012/04/05/quadratic-programming-in-c/) I should have figured that out myself! Congratulations on a very powerful framework which I will continue to use and explore. Charles