Optimize linear fit with variable range

Hello,

I've been trying to adress my problem in several ways but so far, none really satisfied me. Here it is:

I have a set of curves in which a linear behavior appears. This linear behavior doesnt necessarily appear at the same positions in my different curves and is not necessarily made of the same number of points.

I want to find the range that gives the best linear fit to this linear behavior, not knowing precisely where it begins and ends.

By best, I mean the linear fit with the R^2 parameter closest to 1 with the longest range possible.

My current unsatisfying solution:

1) Calculate the second derivative of my curves and find the positions where it is the closest to zero. This gives me a rough estimate as to where the linear behavior starts and ends.

2) Given the estimate range, I change starting and ending points of the range forward or backward and calculate a linear regression (using polyfit and polyval) with the R^2 parameter as my criterion for finding the best linear fit (R^2 gets closer to 1).

This is thus a two variables (start and end points) optimization non-linear problem where variables are integers. I tried using optimization solvers and routines from https://inverseproblem.co.nz/OPTI/ with constraints on the limits of variables and length of the range but it didnt really satisfy me as it was taking too long and often for a non-optimal result.

To limit the number of iterations, I'm now using a simple while loop: I vary the starting point say for 1000 points, find the position of max of R^2, update the range, then vary ending point for 1000 points and find the position of max of R^2 and then back to starting point and so forth until the positions of starting and ending points converge. But this solution is not elegant and still time-consuming.

So, my questions are: do you know of any functions, Matlab tools, routines, solvers that would help with my problem to make it fast (5 mins max per curve ?) and reliable? Would you have different strategies that I'm using right now to address this problem?

Thank for reading and your help.

Best regards,

David P.

Answer 1

[Alan Weiss]

This sounds to me like a multiobjective optimization problem. You want the biggest range possible, and at the same time you want the closest adherence of the best-fitting line to the curve. There is a tradeoff between large range and small deviation.

I suggest that you formulate your problem with two objectives to minimize: the negative of the length of the line, and the sum of squares of the deviation between points on the curve and the best-fitting straight line. If you have a Global Optimization Toolbox license, you can use gamultiobj to calculate a Pareto set showing the best set of tradeoffs between the objectives.

Alan Weiss

MATLAB mathematical toolbox documentation

[David Petiteau]

Thank you for your help.

I didn't know about multi-objective optimization and it sounds like what I need.

Unfortunately, my variables are integers because they are used to update the range (or line) on which I'm calculating the linear fit, and gamultiobj doesn't have integers constraints option, apparently.

I will look more into it, but it seems I may have to use a different program than Matlab for that.

Thanks again!