# Using quadratic programming to fit a piecewise linear model plus seasonality

I am reading this paper on fitting an L1TF model to data using quadratic programming. Section 7.4 states how one could add seasonality to the model however it doesn't go very far into it. I am trying to finish this line of thought without much experience in convex optimization.

What they suggest is adding these 's' values as extra parameters which are constrained to be periodic and also have zero mean. Otherwise, the problem won't have a unique solution. Makes sense so far.

But how do you proceed? If you leave these conditions on s as external constraints and try to write down the quadratic form for the combined vector (x,s) you get a singular matrix as I suppose you should since without those constraints the problem is ill-defined. But if the quadratic form is singular, you can't proceed the normal way using the formulas for the dual problem because it involves the inverse of that quadratic form which doesn't not exists if it is singular.

So how should I proceed? Should I move all the constraints on s directly into the calculation of the extended quadratic form? Is there another way to construct the dual problem for this case?

I imagine you would run into this same problem in the simplified case of fitting a single trend with seasonality so I imagine it is well know how to do this.

Update:

Here is my attempt to work the constraints on s directly into the quadratic form. Let's say the size of x is 5 and the seasonality period is 3 for example. That is there are two extra parameters s0, s1. The third s2 = -s1-s2 is eliminated as a parameter but it's effect still show up in the quadratic form as follows.

Call P the 7x7 matrix. It will be symmetric. The first 5x5 block is just the 5x5 identity matrix as none of the x values are dependent on each other. The rows/cols that are =0 mod 3 have a 1 in the 6th row/col and zero in the 7th. The ones = 1 mod 3 have 0 in the 6th, 1 in the 7th. The ones = 2 mod 3 have -1 in both the 6th and 7th rows.

Below are the matrix P and it's inverse P_inv

   In [413]: print P
[ 1.00e+00     0         0         0         0      1.00e+00     0    ]
[    0      1.00e+00     0         0         0         0      1.00e+00]
[    0         0      1.00e+00     0         0     -1.00e+00 -1.00e+00]
[    0         0         0      1.00e+00     0      1.00e+00     0    ]
[    0         0         0         0      1.00e+00     0      1.00e+00]
[ 1.00e+00     0     -1.00e+00  1.00e+00     0     -1.00e+00 -1.00e+00]
[    0      1.00e+00 -1.00e+00     0      1.00e+00 -1.00e+00  0.00e+00]

In [414]: print P_inv
[ 8.33e-01  1.67e-01 -1.67e-01  1.67e-01 -1.67e-01  1.67e-01]
[ 1.67e-01  8.33e-01  1.67e-01 -1.67e-01  1.67e-01 -1.67e-01]
[-1.67e-01  1.67e-01  8.33e-01  1.67e-01 -1.67e-01  1.67e-01]
[ 1.67e-01 -1.67e-01  1.67e-01  8.33e-01  1.67e-01 -1.67e-01]
[-1.67e-01  1.67e-01 -1.67e-01  1.67e-01  8.33e-01  1.67e-01]
[ 1.67e-01 -1.67e-01  1.67e-01 -1.67e-01  1.67e-01 -1.67e-01]


So it is invertible which is good and then I suppose one can proceed as before, using this 7x7 matrix in place of the 5x5 identity matrix. This is easily generalizable to other sizes. Let's see how that works...