An Example of Nondecomposition in Data Fitting by Piecewise Monotonic Divided Differences of Order Higher Than Two

I. C. Demetriou ()
Additional contact information
I. C. Demetriou: National and Kapodistrian University of Athens

A chapter in Open Problems in Optimization and Data Analysis, 2018, pp 319-330 from Springer

Abstract: Abstract Let n measurements of values of a real function of one variable be given, but the measurements include random errors. For given integers m and σ, we consider the problem of making the least sum of squares change to the data such that the sequence of the divided differences of order m of the fit changes sign at most σ times. The main difficulty in these calculations is that there are about O(n σ) combinations of positions of sign changes, so that it is impracticable to test each one separately. Since this minimization calculation has local minima, a general optimization algorithm can stop at a local minimum that need not be a global one. It is an open question whether there is an efficient algorithm that can compute a global solution to this important problem for general m and σ. It has been proved that the calculations when m = 1, which gives a piecewise monotonic fit to the data, and m = 2, which gives a piecewise convex/concave fit to the data, reduce to separating the data into σ + 1 disjoint sets of adjacent data and solving a structured quadratic programming problem for each set. Separation allows the development of some dynamic programming procedures that solve the particular problems in O(n 2 + σnlog2 n) and about O(σn 3) computer operations, respectively. We present an example which shows that the minimization calculation when m ≥ 3 and σ ≥ 1 may not be decomposed into separate calculations on subranges of adjacent data such that the associated divided differences of order m are either non-negative or non-positive. Therefore, the example rules out the possibility of solving the general problem by a similar dynamic programming calculation.

Keywords: Approximation; Combinatorics; Data fitting; Decomposition; Divided differences; Dynamic programming; Least squares; Piecewise convexity/concavity; Piecewise monotonicity; Smoothing (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-99142-9_17

Ordering information: This item can be ordered from
http://www.springer.com/9783319991429

DOI: 10.1007/978-3-319-99142-9_17

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().