Three-monotone interpolation

DOI10.1007/S00454-015-9695-9MaRDI QIDQ2354672zbMATH OpenOpenAlexFDO

Authors Josef Cibulka, Pavel Paták, Jiří Matoušek

Publication date 20 July 2015

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4731

zbMATH Keywords

3-monotonicity\(k\)-monotone interpolationsemidefinite programmingunivariate quadratic polynomials

Mathematics Subject Classification ID

Convexity of real functions of several variables, generalizations (26B25) General convexity (52A99) Semidefinite programming (90C22)

Abstract: A function $fcolonmathbbRomathbbR$ is called emph{$k$-monotone} if it is $(k-2)$-times differentiable and its $(k-2)$nd derivative is convex. A point set $Psubsetmathbb{R}^2$ is emph{$k$-monotone interpolable} if it lies on a graph of a $k$-monotone function. These notions have been studied in analysis, approximation theory etc. since the 1940s. We show that 3-monotone interpolability is very non-local: we exhibit an arbitrarily large finite $P$ for which every proper subset is $3$-monotone interpolable but $P$ itself is not. On the other hand, we prove a Ramsey-type result: for every $n$ there exists $N$ such that every $N$-point $P$ with distinct $x$-coordinates contains an $n$-point $Q$ such that $Q$ or its vertical mirror reflection are $3$-monotone interpolable. The analogs for $k$-monotone interpolability with $k=1$ and $k=2$ are classical theorems of ErdH{o}s and Szekeres, while the cases with $kge4$ remain open. We also investigate the computational complexity of deciding $3$-monotone interpolability of a given point set. Using a known characterization, this decision problem can be stated as an instance of polynomial optimization and reformulated as a semidefinite program. We exhibit an example for which this semidefinite program has only doubly exponentially large feasible solutions, and thus known algorithms cannot solve it in polynomial time. While such phenomena have been well known for semidefinite programming in general, ours seems to be the first such example in polynomial optimization, and it involves only univariate quadratic polynomials.

Review text

Inspired by the classical results on \(k\)-monotone interpolability for \(k = 1\) and \(k = 2\) due to \textit{P. Erdős} and \textit{G. Szekeres} from [Compos. Math. 2, 463--470 (1935; JFM 61.0651.04)], the authors investigate the \(3\)-monotone interpolability, showing for instance that it is very nonlocal, by providing an arbitrarily large and finite two-dimensional set \(P\) which is not \(3\)-monotone interpolable, but all its proper subsets are. Moreover, a Ramsey-type result is also proven, namely that for every positive integer \(n\) there exists another positive integer \(N\) such that every \(N\)-point with distinct \(x\)-coordinates contains an \(n\)-point that is \(3\)-monotone interpolable or its vertical mirror reflection has this property. The computational complexity of the problem of deciding the \(3\)-monotone interpolability of a given point set, stated as an instance of polynomial optimization and reformulated as a semidefinite program, is discussed, too. An example where this semidefinite program has only doubly exponentially large feasible solutions and thus known algorithms cannot solve it in polynomial time is provided, being arguably the first of its kind in polynomial optimization in the literature.

Recommendations

• scientific article; zbMATH DE number 1823893
• scientific article; zbMATH DE number 2127842
• The complexity of interpolating given data in three space with a convex function of two variables
• On \(k\)-convex point sets
• scientific article; zbMATH DE number 3975510
• Covering a Simple Polygon by Monotone Directions
• Approximating optimal point configurations for multivariate polynomial interpolation
• Shape-preserving interpolation by cubic splines
• scientific article; zbMATH DE number 878854
• Characterization of \(n\)-independent sets with no more than \(3n\) points

Cites work

• A note on order-type homogeneous point sets
• Algorithms in real algebraic geometry
• An exact duality theory for semidefinite programming and its complexity implications
• Approximation algorithms and semidefinite programming.
• Convex functions, partial orderings, and statistical applications
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Geometric algorithms and combinatorial optimization
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Handbook on semidefinite, conic and polynomial optimization
• Higher-order Erdős-Szekeres theorems
• scientific article; zbMATH DE number 3425889 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Moments, positive polynomials and their applications
• Multiply monotone functions and their Laplace transforms
• On k-Monotone Approximation by Free Knot Splines
• On the Complexity of Numerical Analysis
• On the complexity of semidefinite programs
• Ramsey-type results for semi-algebraic relations
• Semidefinite programming and arithmetic circuit evaluation
• The Erdos-Szekeres problem on points in convex position – a survey

Cited in

(2)

• scientific article; zbMATH DE number 903868 (Why is no real title available?)
• Three-monotone spline approximation

This page was built for publication: Three-monotone interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354672)