Very High-Dimensional Slope Change Detection with Guarantees

We study the problem of detecting a common slope change across high-dimensional time series, in both sparse and non-sparse settings, using continuous piecewise-linear fitting. An exact formulation of the shared-breakpoint problem yields a nonconvex mixed-integer nonlinear program (MINLP), whose computational cost grows rapidly with the number of time-series dimensions. We develop a scalable domain-reduction framework that constructs lower bounds for candidate breakpoint intervals using Lagrangian relaxation, allowing intervals that cannot contain a globally optimal breakpoint to be safely eliminated and thereby tightening the McCormick envelope over the remaining domain. We show that for each dimension and candidate interval, the resulting Lagrangian dual admits a closed-form solution computable through low-dimensional matrix operations. Consequently, the computational effort required to evaluate the bounds scales linearly with the number of dimensions. Computational experiments demonstrate tight lower bounds, substantial reductions in the breakpoint search domain, and scalability to time series with up to $100{,}000$ dimensions, with optimality gaps ranging from $0.43$\% to $0.93$\%.