# Optimization problem with two-step discontinuous function

imagine my function as a staircase with two steps. This function is to be fitted to some empirical data and I'm searching for an algorithm which minimizes the Root Mean Squared Error between this function and the data. The decision variables are L1 and L2 (for the level of the steps on the y-axis) and C (for the cut-off-point between the steps on the x-axis). The possible values for C on the x-axis are discreete and finite. Can you point me to algorithms or even possible solutions in Excel (VBA), Matlab or C++? The standard Excel solver is unable to solve this problem, because it requires a smooth function, but the (expensive) Premium solver seems able to do it.

My suggestion for an algorithm would be following 2-step method: Given the finite set of values for C, for each C, optimize L1 and L2. Then, optimum C* would the C with the lowest RMSE given L1* and L2*. Would that be correct? Or is there a more elegant way to it?

-
When you say "imagine my function as a staircase with two steps", I imagine a function with three different values and two steps between them, but then you only have two variables for the "level of the steps" and only once position on the $x$ axis. So it seems you actually mean just a function that changes from one value to another just once? This would usually be referred to as a "step function", not a "two-step function". –  joriki Apr 5 '11 at 7:07
Note that your problem has a discrete aspect and a continuous aspect. The decision for $C$ is discrete, since it doesn't matter where between two consecutive data points you put it. The decision for $L_1$ and $L_2$ is continuous. The continuous part is easy: Once you know where the step is, $L_1$ and $L_2$ are just the averages of the data on each side of the step. So your problem is basically to find the best split point. –  joriki Apr 5 '11 at 7:16
It helps if you mark edits as edits in the text; then people who have already read the question know that they need to reread parts of it to be up to date. My comments above referred to the original question. –  joriki Apr 5 '11 at 7:27
Your algorithm is correct. I was hoping one might be able to show that the RMSE is convex in $C$, which would have meant you don't have to try all values for $C$, but there are counterexamples for that, with several local minima for $C$, so I think you do have to try them all. When you say "optimize $L_1$ and $L_2$", note that in this case that just means "take the average of the data on each side of $C$". –  joriki Apr 5 '11 at 7:47
with respect to your 1st comment: You are right, only one change of value, sorry for the confusion. 2nd comment: correct. 3d comment: sorry again. 4th comment: I realize that for a given C, I can evaluate L1* and L2* independently from one another. That's what I meant. –  Steve06 Apr 5 '11 at 17:34

The example $\{(-1,-1),(-\epsilon,-\epsilon),(\epsilon,\epsilon),(1,1)\}$ shows that there can be more than one local minimum with respect to $C$: Splitting 1 & 3 either way is better than splitting 2 & 2. So it seems you can't avoid trying out every position for the step.

To find the optimal $C$ efficiently, note that the optimal $L_1$ and $L_2$ given $C$ will be the average of the data on each side of $C$, so that what you're trying to minimize is

$$\begin{eqnarray} && \sum_{x_i<C}\left(f_i-\frac{\sum_{x_i<C}f_i}{N_<}\right)^2 + \sum_{x_i\ge C}\left(f_i-\frac{\sum_{x_i\ge C}f_i}{N_\ge}\right)^2 \\ &=& \sum_{x_i<C}f_i^2 - \frac{\left(\sum_{x_i<C}f_i\right)^2}{N_<} + \sum_{x_i\ge C}f_i^2 - \frac{\left(\sum_{x_i\ge C}f_i\right)^2}{N_\ge} \\ &=& \sum f_i^2 - \left( \frac{\left(\sum_{x_i<C}f_i\right)^2}{N_<} + \frac{\left(\sum_{x_i\ge C}f_i\right)^2}{N_\ge} \right)\;, \end{eqnarray}$$

where $N_<$ and $N_\ge$ are the numbers of points to the left and right of $C$, respectively. The first term is constant, so you can ignore it, so all you need to do is sweep through from left to right, in each step adding one function value to the left-hand sum and subtracting it from the right-hand sum and evaluating the expression in parentheses.

-
i implemented an algorithm that checks every possible split point, but due to the no. of possibilities (around 1000) it's a bit slow. I consider starting with a large net of inspecting first every 100th possible split point, then, within the range of the 2 nearby solutions with the lowest average error, I would tighten the net to every 20th possible split point, and finally loop through every possibility of the best 20-point range. Would that make sense? –  Steve06 Apr 6 '11 at 14:58
@Steve: I'm not sure how good your chances to get close to the optimal solution would be with such an approach. I think it would depend on the clustering of the values and might differ quite a bit from the optimal result in some cases. If you have 1000 split points, you should be able to try them in almost no time, so I suspect you might be doing it inefficiently -- did you use the approach in my answer to avoid having to sum function values for each possible split? –  joriki Apr 6 '11 at 15:57
it takes long because (a) because L1, L2 are each fitted to the data iteratively, (b) I use Excel VBA which as a scripting language is of course a lot slower than some C code and (c) the whole procedure has to be repeated for 500 different companies in my sample. At the moment, one company takes about half an hour on average to be optimized. –  Steve06 Apr 6 '11 at 17:51
@Steve: Your last comment makes we wonder whether you've understood my answer. This should be a matter of milliseconds, not hours. Most importantly, $L1$ and $L2$ should not be fitted to the data iteratively -- as I wrote in the answer, they are simply the averages of the function values to the left and to the right of the split point, respectively, and even these averages don't have to be recalculated for each potential split point. I recommend that you try to implement my answer; I'll be happy to help if you have questions about it. –  joriki Apr 6 '11 at 17:59