SpringerLink
Log in

Regularity and well-posedness of a dual program for convex best C 1-spline interpolation

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

An efficient approach to computing the convex best C 1-spline interpolant to a given set of data is to solve an associated dual program by standard numerical methods (e.g., Newton’s method). We study regularity and well-posedness of the dual program: two important issues that have been not yet well-addressed in the literature. Our regularity results characterize the case when the generalized Hessian of the objective function is positive definite. We also give sufficient conditions for the coerciveness of the objective function. These results together specify conditions when the dual program is well-posed and hence justify why Newton’s method is likely to be successful in practice. Examples are given to illustrate the obtained results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Burmeister, W., Hess, W., Schmidt, J.W.: Convex spline interpolants with minimal curvature. Computing 35, 219–229 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  2. Deutsch, F.: Best Approximation in Inner Product Spaces. CMS Books in Mathematics, vol. 7. Springer, New York (2001)

    MATH  Google Scholar 

  3. Dietze, S., Schmidt, J.W.: Determination of shape preserving spline interpolants with minimal curvature via dual programs. J. Approx. Theory 52, 43–57 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  4. Dontchev, A.L., Kalchev, B.D.: Duality and well-posedness in convex interpolation. Numer. Funct. Anal. Optim. 10, 673–689 (1989)

    MathSciNet  MATH  Google Scholar 

  5. Dontchev, A.L., Qi, H.-D., Qi, L.: Convergence of Newton’s method for convex best interpolation. Numer. Math. 87, 435–456 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  6. Dontchev, A.L., Qi, H.-D., Qi, L., Yin, H.: A Newton method for shape-preserving spline interpolation. SIAM J. Optim. 13, 588–602 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  7. Dontchev, A.L., Zolezzi, T.: Well-posed Optimization Problems. Lecture Notes in Mathematics, vol. 1543. Springer, Berlin (1993)

    MATH  Google Scholar 

  8. Facchinei, F., Fischer, A., Kanzow, C.: Regularity properties of a new equation reformulation of variational inequalities. SIAM J. Optim. 8, 850–869 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  9. Fischer, A., Kanzow, C.: On finite termination of an iterative method for linear complementarity problems. Math. Program. 74, 279–292 (1996)

    MathSciNet  Google Scholar 

  10. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993)

    Google Scholar 

  11. Kanzow, C., Qi, H.-D., Qi, L.: On the minimum norm solution of linear programs. J. Optim. Theory Appl. 116, 333–345 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  12. Kojima, M., Shindo, S.: Extension of Newton and quasi-Newton methods for systems of PC 1 equations. J. Oper. Res. Soc. Jpn. 29, 352–373 (1986)

    MATH  MathSciNet  Google Scholar 

  13. Mangasarian, O.L.: Finite Newton method for classification problems. Optim. Methods Softw. 17, 913–929 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  14. Neuman, E.: Uniform approximation by some Hermite interpolation splines. J. Comput. Appl. Math. 4, 7–9 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  15. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (1999)

    MATH  Google Scholar 

  16. Qi, H.-D., Qi, L.: Finite termination of a dual Newton method for convex best C 1 interpolation and smoothing. Numer. Math. 96, 317–337 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  17. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  18. Schmidt, J.W.: An unconstrained dual program for computing convex C 1-spline approximants. Computing 39, 133–140 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  19. Schmidt, J.W.: On tridiagonal linear complementarity problems. Numer. Math. 51, 11–21 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  20. Schmidt, J.W.: Dual algorithms for solving convex partially separable optimization problems. Jahresber. Deutsch. Math.-Verein. 94, 40–62 (1992)

    MATH  MathSciNet  Google Scholar 

  21. Schmidt, J.W., Hess, W.: Spline interpolation under two-sided restrictions on the derivatives. Z. Angew. Math. Mech. 69, 353–365 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  22. Sun, D., Han, J., Zhao, Y.: The finite termination of the damped Newton algorithm for linear complementarity problems. Acta Math. Appl. Sinica 21, 148–154 (1998) (in Chinese)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, University of Southampton, Highfield, Southampton, SO17 1BJ, UK

    Houduo Qi

  2. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China

    **aoqi Yang

Authors
  1. Houduo Qi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. **aoqi Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Houduo Qi.

Additional information

The work was supported by EPSRC grant EP/D502535/1 for the first author and by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU 5141/01E) for the second author.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Qi, H., Yang, X. Regularity and well-posedness of a dual program for convex best C 1-spline interpolation. Comput Optim Appl 37, 409–425 (2007). https://doi.org/10.1007/s10589-007-9027-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-007-9027-y

Keywords

Search

Navigation