IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i10p1099-d553756.html
   My bibliography  Save this article

Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming

Author

Listed:
  • Lakshman S. Thakur

    (Department of Operations and Information Management, School of Business, University of Connecticut, Storrs, CT 06269, USA)

  • Mikhail A. Bragin

    (Department of Electrical and Computer Engineering, School of Engineering, University of Connecticut, Storrs, CT 06269, USA)

Abstract

The problem of obtaining an optimal spline with free knots is tantamount to minimizing derivatives of a nonlinear differentiable function over a Banach space on a compact set. While the problem of data interpolation by quadratic splines has been accomplished, interpolation by splines of higher orders is far more challenging. In this paper, to overcome difficulties associated with the complexity of the interpolation problem, the interval over which data points are defined is discretized and continuous derivatives are replaced by their discrete counterparts. The l ∞ -norm used for maximum r th order curvature (a derivative of order r ) is then linearized, and the problem to obtain a near-optimal spline becomes a linear programming (LP) problem, which is solved in polynomial time by using LP methods, e.g., by using the Simplex method implemented in modern software such as CPLEX. It is shown that, as the mesh of the discretization approaches zero, a resulting near-optimal spline approaches an optimal spline. Splines with the desired accuracy can be obtained by choosing an appropriately fine mesh of the discretization. By using cubic splines as an example, numerical results demonstrate that the linear programming (LP) formulation, resulting from the discretization of the interpolation problem, can be solved by linear solvers with high computational efficiency and the resulting spline provides a good approximation to the sought-for optimal spline.

Suggested Citation

  • Lakshman S. Thakur & Mikhail A. Bragin, 2021. "Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming," Mathematics, MDPI, vol. 9(10), pages 1-12, May.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:10:p:1099-:d:553756
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/10/1099/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/10/1099/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Farid Alizadeh & Jonathan Eckstein & Nilay Noyan & Gábor Rudolf, 2008. "Arrival Rate Approximation by Nonnegative Cubic Splines," Operations Research, INFORMS, vol. 56(1), pages 140-156, February.
    2. Konstantinos Demertzis & Dimitrios Tsiotas & Lykourgos Magafas, 2020. "Modeling and Forecasting the COVID-19 Temporal Spread in Greece: An Exploratory Approach Based on Complex Network Defined Splines," IJERPH, MDPI, vol. 17(13), pages 1-17, June.
    3. Victoria C. P. Chen & David Ruppert & Christine A. Shoemaker, 1999. "Applying Experimental Design and Regression Splines to High-Dimensional Continuous-State Stochastic Dynamic Programming," Operations Research, INFORMS, vol. 47(1), pages 38-53, February.
    4. Daniel Gervini, 2006. "Free‐knot spline smoothing for functional data," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 68(4), pages 671-687, September.
    5. D. P. de Farias & B. Van Roy, 2003. "The Linear Programming Approach to Approximate Dynamic Programming," Operations Research, INFORMS, vol. 51(6), pages 850-865, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Diego Klabjan & Daniel Adelman, 2007. "An Infinite-Dimensional Linear Programming Algorithm for Deterministic Semi-Markov Decision Processes on Borel Spaces," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 528-550, August.
    2. Tetsuo Iida & Paul H. Zipkin, 2006. "Approximate Solutions of a Dynamic Forecast-Inventory Model," Manufacturing & Service Operations Management, INFORMS, vol. 8(4), pages 407-425, October.
    3. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    4. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    5. Chaharborj, Sarkhosh Seddighi & Nabi, Khondoker Nazmoon & Feng, Koo Lee & Chaharborj, Shahriar Seddighi & Phang, Pei See, 2022. "Controlling COVID-19 transmission with isolation of influential nodes," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    6. Ying Chen & Krystel K. Castillo-Villar & Bing Dong, 2021. "Stochastic control of a micro-grid using battery energy storage in solar-powered buildings," Annals of Operations Research, Springer, vol. 303(1), pages 197-216, August.
    7. Matthew S. Maxwell & Mateo Restrepo & Shane G. Henderson & Huseyin Topaloglu, 2010. "Approximate Dynamic Programming for Ambulance Redeployment," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 266-281, May.
    8. Oleksandr Shlakhter & Chi-Guhn Lee, 2013. "Accelerated modified policy iteration algorithms for Markov decision processes," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 78(1), pages 61-76, August.
    9. Sauré, Antoine & Patrick, Jonathan & Tyldesley, Scott & Puterman, Martin L., 2012. "Dynamic multi-appointment patient scheduling for radiation therapy," European Journal of Operational Research, Elsevier, vol. 223(2), pages 573-584.
    10. Cai, Yongyang & Judd, Kenneth L. & Lontzek, Thomas S. & Michelangeli, Valentina & Su, Che-Lin, 2017. "A Nonlinear Programming Method For Dynamic Programming," Macroeconomic Dynamics, Cambridge University Press, vol. 21(2), pages 336-361, March.
    11. Yu, Yugang & Luo, Yifei & Shi, Ye, 2022. "Adoption of blockchain technology in a two-stage supply chain: Spillover effect on workforce," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    12. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    13. Jonathan Patrick & Martin L. Puterman & Maurice Queyranne, 2008. "Dynamic Multipriority Patient Scheduling for a Diagnostic Resource," Operations Research, INFORMS, vol. 56(6), pages 1507-1525, December.
    14. Meissner, Joern & Strauss, Arne, 2012. "Network revenue management with inventory-sensitive bid prices and customer choice," European Journal of Operational Research, Elsevier, vol. 216(2), pages 459-468.
    15. Michael H. Veatch, 2013. "Approximate Linear Programming for Average Cost MDPs," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 535-544, August.
    16. Daniel Adelman & Adam J. Mersereau, 2008. "Relaxations of Weakly Coupled Stochastic Dynamic Programs," Operations Research, INFORMS, vol. 56(3), pages 712-727, June.
    17. Pilla, Venkata L. & Rosenberger, Jay M. & Chen, Victoria & Engsuwan, Narakorn & Siddappa, Sheela, 2012. "A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model," European Journal of Operational Research, Elsevier, vol. 216(1), pages 162-171.
    18. Jin-Kyung Kwak, 2021. "An Order-Up-to Inventory Model with Sustainability Consideration," Sustainability, MDPI, vol. 13(23), pages 1-8, December.
    19. Laura M. Sangalli & Piercesare Secchi & Simone Vantini & Alessandro Veneziani, 2009. "Efficient estimation of three‐dimensional curves and their derivatives by free‐knot regression splines, applied to the analysis of inner carotid artery centrelines," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 58(3), pages 285-306, July.
    20. Oscar Dowson & Lea Kapelevich, 2021. "SDDP.jl : A Julia Package for Stochastic Dual Dynamic Programming," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 27-33, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:10:p:1099-:d:553756. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.