pith. sign in

arxiv: 2605.03711 · v1 · submitted 2026-05-05 · 🧮 math.OC · cs.NA· eess.SP· math.NA

One-Dimensional Nonnegative Spline Smoothing via Convex Semi-Infinite Programming with a Cutting-Plane Method

Hiroki Arai , Daichi Kitahara This is my paper

Pith reviewed 2026-05-07 15:31 UTC · model grok-4.3

classification 🧮 math.OC cs.NAeess.SPmath.NA
keywords nonnegative spline smoothingconvex semi-infinite programmingcutting-plane methodquadratic programmingone-dimensional splinesnonnegativity constraintsoptimization algorithms
0
0 comments X

The pith

A cutting-plane algorithm solves one-dimensional nonnegative spline smoothing to exact optimality by enforcing nonnegativity only at the violating points.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reformulates nonnegative spline smoothing as a convex semi-infinite program whose constraints are the infinite family of linear inequalities needed for nonnegativity at every point. It then replaces the conventional sufficient-condition quadratic program with a cutting-plane procedure that starts from an unconstrained spline fit, locates the minimum of each polynomial piece, and adds any negative locations as new equality constraints before re-solving. The loop repeats until every piece stays nonnegative. This removes the small sub-optimality introduced by sufficient conditions while retaining the speed of quadratic programming. The method is shown to converge to the true solution of the semi-infinite program.

Core claim

The central claim is that the one-dimensional nonnegative spline smoothing problem, previously solved approximately via sufficient conditions inside a quadratic program, can be solved exactly by casting it as a convex semi-infinite program and applying an iterative cutting-plane procedure that adds only the most negative point of each spline segment as a new linear constraint before re-solving the quadratic program.

What carries the argument

The cutting-plane loop for the convex semi-infinite program: locate the minimizer of each polynomial piece (closed-form for low degree, numerical otherwise), add any negative location as a constraint, and resolve the quadratic program until no negative values remain.

If this is right

  • The returned spline is the exact minimizer of the original semi-infinite program rather than an approximation.
  • The procedure converges to the global optimum of the convex semi-infinite program.
  • Numerical comparisons show faster and more reliable performance than the MATLAB LRSQP solver on the same formulation.
  • The solution improves on the conventional sufficient-condition quadratic program by removing the conservatism of that sufficient condition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same cutting-plane idea could be tried on other smoothing problems whose nonnegativity or positivity constraints are infinite families of linear inequalities.
  • The method's success depends on being able to locate polynomial minima quickly; extensions to higher-degree splines would require more robust numerical minimization.
  • Because each iteration only adds a handful of constraints, the approach may scale better than general-purpose semi-infinite solvers when the number of spline pieces is moderate.

Load-bearing premise

That the minimum value of each polynomial piece can be found accurately enough that every location where the spline would go negative is eventually added as a constraint.

What would settle it

A concrete spline of degree three or higher on which the algorithm terminates yet the final spline dips below zero at some point not added during the process.

Figures

Figures reproduced from arXiv: 2605.03711 by Daichi Kitahara, Hiroki Arai.

Figure 2
Figure 2. Figure 2: As mentioned above, the result of the QP method lies view at source ↗
read the original abstract

Spline functions are smooth piecewise polynomials widely used for interpolation and smoothing, and nonnegative spline smoothing is also studied for nonnegative data. Previous research used sufficient conditions for the nonnegativity of spline functions because necessary and sufficient conditions for the nonnegativity are infinitely many linear inequalities, which are difficult to handle in optimization algorithms. This conventional method quickly computes a nonnegative spline function via quadratic programming (QP), but the optimal solution may be slightly degraded by using the sufficient condition. In this paper, we express 1D nonnegative spline smoothing as a convex semi-infinite programming (CSIP) problem that directly deals with infinite inequality constraints. As optimization algorithms for general SIP problems, local-reduction-based sequential quadratic programming (LRSQP) methods are used, but their convergence performance deteriorates for certain problems due to multiple approximations during updates. To quickly solve the CSIP problem, we propose a cutting-plane (CP) method. In the proposed method, after giving an initial solution by the standard spline smoothing, we find the minimizer of each polynomial piece by using the closed-form solution for a low-degree polynomial or a numerical solution for a high-degree polynomial. If the minimum value is negative, then such minimizer is added into the constraint of the problem to guarantee the nonnegativity. This constrained problem is quickly solved via QP, and we find the minimizer of each polynomial piece again. We repeat these procedures until there are no negative minimum values. The proposed method guarantees convergence to the original CSIP solution, and its effectiveness is demonstrated in numerical experiments by comparison to the conventional methods, QP under the sufficient condition and CSIP using the MATLAB LRSQP algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper formulates one-dimensional nonnegative spline smoothing as a convex semi-infinite program (CSIP) whose infinite nonnegativity constraints are handled exactly rather than via sufficient conditions. It proposes a cutting-plane algorithm that starts from an unconstrained spline, repeatedly solves a QP with the current finite set of pointwise constraints, locates the global minimizer of each resulting polynomial piece (closed-form for low degree, numerical for high degree), and adds any violating points as new linear inequalities until no negative values remain. The abstract asserts that the procedure converges to the original CSIP optimum and that numerical experiments show it outperforms both the conventional sufficient-condition QP and MATLAB’s LRSQP solver for CSIP.

Significance. If the convergence claim holds and the numerical results are reproducible, the method supplies a practical, exact alternative to conservative sufficient-condition approaches for nonnegative spline smoothing. This could improve solution quality in applications such as density estimation or signal processing where nonnegativity is required, while retaining the computational advantages of QP solves. The paper’s emphasis on a simple, implementable cutting-plane loop without multiple nested approximations is a clear strength relative to general LRSQP schemes.

major comments (3)
  1. [Abstract / Method] Abstract and method description: the claim that the cutting-plane iteration “guarantees convergence to the original CSIP solution” is stated without a formal proof or even a sketched argument. Convergence hinges on the per-piece global minimization step locating every negative excursion; the manuscript supplies no analysis of the numerical solver’s completeness (tolerance settings, handling of multiple local minima for high-degree pieces, or interval-arithmetic guarantees), leaving the central correctness claim unverified.
  2. [Numerical experiments] Numerical experiments section: the abstract asserts experimental superiority over QP (sufficient condition) and LRSQP, yet the provided text contains no tables, quantitative metrics, problem dimensions, or termination criteria. Without these data or an error analysis comparing the final spline’s violation of the infinite constraint set, the performance claim cannot be assessed.
  3. [Algorithm description] Termination criterion: the algorithm stops when all per-piece minima are nonnegative, but no discussion is given of how floating-point precision, knot-interval partitioning, or the choice of numerical minimizer affects whether a small negative dip could be missed, potentially allowing the reported solution to violate the original CSIP constraints.
minor comments (2)
  1. [Abstract] The abstract refers to “the minimizer of each polynomial piece” without specifying the knot-interval partitioning or how the spline is represented between knots; a brief clarification of the piecewise-polynomial basis would improve readability.
  2. [Introduction / Preliminaries] Notation for the spline degree, knot vector, and the finite constraint index set is introduced only informally; consistent symbols and a short preliminary section would aid readers unfamiliar with spline smoothing.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We address each major comment below and will revise the manuscript to incorporate the suggested improvements for clarity, rigor, and completeness.

read point-by-point responses

  1. Referee: [Abstract / Method] Abstract and method description: the claim that the cutting-plane iteration “guarantees convergence to the original CSIP solution” is stated without a formal proof or even a sketched argument. Convergence hinges on the per-piece global minimization step locating every negative excursion; the manuscript supplies no analysis of the numerical solver’s completeness (tolerance settings, handling of multiple local minima for high-degree pieces, or interval-arithmetic guarantees), leaving the central correctness claim unverified.

    Authors: We agree that the current manuscript lacks a sketched convergence argument and numerical robustness details. In the revised version we will add a brief convergence subsection arguing that the sequence of QP objectives is monotonically nondecreasing and bounded above by the CSIP optimum; because each added linear constraint is generated at a globally detected violation and the feasible set remains convex and closed, the limit satisfies the entire infinite constraint set. We will also specify the numerical tolerances (10^{-12}), note that closed-form solutions are used for degrees ≤3 (exact), and describe a multi-start global optimizer for higher degrees to address local-minima concerns. revision: yes

  2. Referee: [Numerical experiments] Numerical experiments section: the abstract asserts experimental superiority over QP (sufficient condition) and LRSQP, yet the provided text contains no tables, quantitative metrics, problem dimensions, or termination criteria. Without these data or an error analysis comparing the final spline’s violation of the infinite constraint set, the performance claim cannot be assessed.

    Authors: The referee is correct that the current draft omits the quantitative details. We will expand the numerical section with tables reporting data sizes, spline degrees, knot counts, CPU times, objective values, and maximum constraint violations for all three methods. We will also include an error analysis confirming that final CP solutions violate the infinite nonnegativity constraints by at most machine epsilon. revision: yes

  3. Referee: [Algorithm description] Termination criterion: the algorithm stops when all per-piece minima are nonnegative, but no discussion is given of how floating-point precision, knot-interval partitioning, or the choice of numerical minimizer affects whether a small negative dip could be missed, potentially allowing the reported solution to violate the original CSIP constraints.

    Authors: We will augment the algorithm description with a numerical-stability paragraph. It will explain the uniform knot partitioning, the use of a small negative threshold (-10^{-10}) to trigger constraint addition, and the specific global minimizer (multi-start derivative-free search) together with its convergence tolerance, thereby ensuring that floating-point or partitioning artifacts do not leave undetected violations. revision: yes

Circularity Check

0 steps flagged

No circularity: standard cutting-plane algorithm for CSIP with independent convergence property

full rationale

The paper formulates nonnegative spline smoothing as a convex semi-infinite program and proposes an iterative cutting-plane procedure that solves successive QPs while adding linear constraints at detected negative minimizers of each polynomial piece. Convergence to the original CSIP solution follows from the standard property that the process continues until the finite constraint set enforces nonnegativity everywhere (a direct consequence of the convexity and the exhaustive search for violations on each compact interval), without any reduction of the claimed result to a fitted parameter, self-defined quantity, or self-citation chain. No ansatz is smuggled, no known result is merely renamed, and the numerical experiments serve only as validation rather than as the source of the guarantee. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard convex optimization and spline theory; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the domain assumption that nonnegativity of a spline can be expressed via infinitely many linear inequalities.

axioms (1)
  • domain assumption Nonnegativity of a spline function is equivalent to an infinite set of linear inequalities on its coefficients.
    Invoked to justify the CSIP formulation; standard in spline literature but central to moving from sufficient conditions to exact constraints.

pith-pipeline@v0.9.0 · 5615 in / 1248 out tokens · 45014 ms · 2026-05-07T15:31:29.939739+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Smoothing by spline functions,

    C.H. Reinsch, “Smoothing by spline functions,” Numerische Math- ematik, vol.10, no.3, pp.177–183, 1967

    work page 1967

  2. [2]

    Wahba, Spline Models for Observational Data, SIAM, Philadel- phia, PA, 1990

    G. Wahba, Spline Models for Observational Data, SIAM, Philadel- phia, PA, 1990

    work page 1990

  3. [3]

    Ramsay and B.W

    J.O. Ramsay and B.W. Silverman, Functional Data Analysis, 2nd ed., Springer, New York, NY, 2005

    work page 2005

  4. [4]

    Schumaker, Spline Functions: Basic Theory, 3rd ed., Cambridge University Press, UK, 2007

    L. Schumaker, Spline Functions: Basic Theory, 3rd ed., Cambridge University Press, UK, 2007

    work page 2007

  5. [5]

    Chui, Multivariate Splines, SIAM, Philadelphia, PA, 1988

    C.K. Chui, Multivariate Splines, SIAM, Philadelphia, PA, 1988

    work page 1988

  6. [6]

    On estimation of a probability density function and mode,

    E. Parzen, “On estimation of a probability density function and mode,” The Annals of Mathematical Statistics, vol.33, no.3, pp.1065–1076, 1962

    work page 1962

  7. [7]

    Percival and A.T

    D.B. Percival and A.T. Walden, Spectral Analysis for Physical Ap- plications, Cambridge University Press, UK, 1993

    work page 1993

  8. [8]

    Probability density function esti- mation by positive quartic 𝐶2-spline functions,

    D. Kitahara and I. Yamada, “Probability density function esti- mation by positive quartic 𝐶2-spline functions,” Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Brisbane, Aus- tralia, pp.3556–3560, 2015

    work page 2015

  9. [9]

    Two-dimensional positive spline smoothing and its application to probability density estimation,

    D. Kitahara and I. Yamada, “Two-dimensional positive spline smoothing and its application to probability density estimation,” Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Shanghai, China, pp.4219–4223, 2016

    work page 2016

  10. [10]

    Kitahara, A Study of Algebraic Phase Unwrapping and Spline Smoothing for Signal Processing Applications, Doctoral Thesis, Tokyo Institute of Technology, 2016

    D. Kitahara, A Study of Algebraic Phase Unwrapping and Spline Smoothing for Signal Processing Applications, Doctoral Thesis, Tokyo Institute of Technology, 2016

    work page 2016

  11. [11]

    Symmetric indefinite systems for interior point methods,

    R.J. Vanderbei and T.J. Carpenter, “Symmetric indefinite systems for interior point methods,” Math. Program., vol.58, no.1–3, pp.1–32, 1993

    work page 1993

  12. [12]

    Regularized symmetric indefinite sys- tems in interior point methods for linear and quadratic optimization,

    A. Altman and J. Gondzio, “Regularized symmetric indefinite sys- tems in interior point methods for linear and quadratic optimization,” Optim. Methods Softw., vol.11, no.1–4, pp.275–302, 1999

    work page 1999

  13. [13]

    Semi-infinite programming: Theory, methods, and applications,

    R. Hettich and K.O. Kortanek, “Semi-infinite programming: Theory, methods, and applications,” SIAM Review, vol.35, no.3, pp.380–429, 1993

    work page 1993

  14. [14]

    Reemtsen and J.J

    R. Reemtsen and J.J. R¨ uckmann, eds., Semi-Infinite Programming, Nonconvex Optimization and Its Applications, vol.25, Kluwer Aca- demic Publishers, The Netherlands, 1998

    work page 1998

  15. [15]

    M. ´A. Goberna and M.A. L ´opez, eds., Semi-Infinite Programming: Recent Advances, Nonconvex Optimization and Its Applications, vol.57, Kluwer Academic Publishers, The Netherlands, 2001

    work page 2001

  16. [16]

    Semi-infinite programming,

    M.A. L ´opez and G. Still, “Semi-infinite programming,” European Journal of Operational Research, vol.180, no.2, pp.491–518, 2007

    work page 2007

  17. [17]

    Infinitely constrained optimization problems,

    J.W. Blankenship and J.E. Falk, “Infinitely constrained optimization problems,” Journal of Optimization Theory and Applications, vol.19, no.2, pp.261–281, 1976

    work page 1976

  18. [18]

    Discretization methods for the solution of semi- infinite programming problems,

    R. Reemtsen, “Discretization methods for the solution of semi- infinite programming problems,” Journal of Optimization Theory and Applications, vol.71, no.1, pp.85–103, 1991

    work page 1991

  19. [19]

    Local reduction based SQP-type method for semi-infinite programs with an infinite number of second- order cone constraints,

    T. Okuno and M. Fukushima, “Local reduction based SQP-type method for semi-infinite programs with an infinite number of second- order cone constraints,” Journal of Global Optimization, vol.60, no.1, pp.25–48, 2014

    work page 2014

  20. [20]

    A transformation-based discretization method for solving general semi-infinite optimization problems,

    J. Schwientek, T. Seidel, and K.H. K¨ ufer, “A transformation-based discretization method for solving general semi-infinite optimization problems,” Mathematical Methods of Operations Research, vol.93, pp.83–114, 2021

    work page 2021

  21. [21]

    Convex semi-infinite programming algo- rithms with inexact separation oracles,

    A. Oustry and M. Cerulli, “Convex semi-infinite programming algo- rithms with inexact separation oracles,” Optimization Letters, vol.19, no.3, pp.437–462, 2025

    work page 2025

  22. [22]

    Cutting planes in integer and mixed integer programming,

    H. Marchand, A. Martin, R. Weismantel, and L. Wolsey, “Cutting planes in integer and mixed integer programming,” Discrete Applied Mathematics, vol.123, no.1–3, pp.397–446, 2002

    work page 2002

  23. [23]

    The minimization of lower subdifferentiable functions under nonlinear constraints: An all feasible cutting plane algo- rithm,

    F. Plastria, “The minimization of lower subdifferentiable functions under nonlinear constraints: An all feasible cutting plane algo- rithm,” Journal of Optimization Theory and Applications, vol.57, no.3, pp.463–484, 1988

    work page 1988

  24. [24]

    Modal interval regression based on spline quantile regression,

    S. Yao, D. Kitahara, H. Kuroda, and A. Hirabayashi, “Modal interval regression based on spline quantile regression,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.106-A, no.2, pp.106–123, 2023

    work page 2023

  25. [25]

    MATLAB, fseminf Algorithm, https://www.mathworks.com/help/ optim/ug/fseminf.html, accessed Apr. 1, 2026

    work page 2026

  26. [26]

    A perfect example for the BFGS method,

    Y.H. Dai, “A perfect example for the BFGS method,” Mathematical 10 ARAI and KITAHARA: 1D NONNEGATIVE SPLINE SMOOTHING VIA CSIP WITH A CP METHOD Programming, vol.138, pp.501–530, 2013

    work page 2013

  27. [27]

    qpOASES: a parametric active-set algorithm for quadratic program- ming

    H.J. Ferreau, C. Kirches, A. Potschka, H.G. Bock, and M. Diehl, “qpOASES: a parametric active-set algorithm for quadratic program- ming”, Mathematical Programming Computation, vol.6, pp.327– 363, 2014

    work page 2014

  28. [28]

    Boumal, An Introduction to Optimization on Smooth Manifolds, Cambridge University Press, UK, 2023

    N. Boumal, An Introduction to Optimization on Smooth Manifolds, Cambridge University Press, UK, 2023. Appendix A: Strong Convexity of the Cost Function For QP in (3), its cost function𝑓 (𝒃) = ∥ 𝒚 − 𝑨𝒃 ∥2 2 +𝜆𝒃T𝑸𝒃 = 𝒃T ( 𝑨T 𝑨+𝜆𝑸)𝒃−2𝒚T 𝑨𝒃 +𝒚T 𝒚 is twice differentiable. Thus, the cost function 𝑓 is 𝛾-strongly convexon the constraint set N𝑯 = {𝒃 ∈ R𝑑𝑚+1 | 𝑯𝒃 ...

    work page 2023