Three-Monotone Interpolation

详细信息    查看全文

• 作者：Josef Cibulka ; Ji?í Matou?ek ; Pavel Paták
• 关键词：$$k$$ k ; Monotone interpolation ; 3 ; Monotonicity ; Semidefinite programming ; 26B25 ; 90C22 ; 52A99
• 刊名：Discrete and Computational Geometry
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：54
• 期：1
• 页码：3-21
• 全文大小：555 KB
• 参考文献：1.Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987-006 (2009)View Article MATH
  2.Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization. Springer, New York (2012)MATH
  3.Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2003)View Article
  4.Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2001)View Article MATH
  5.Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)View Article MATH
  6.Bukh, B., Matou?ek, J.: Erd?s–Szekeres-type statements: Ramsey function and decidability in dimension 1. Duke Math. J. 163(12), 2243-270 (2014)View Article MATH MathSciNet
  7.Conlon, D., Fox, J., Pach, J., Sudakov, B., Suk, A.: Ramsey-type results for semi-algebraic relations. Trans. Am. Math. Soc. 366, 5043-065 (2013)View Article MathSciNet
  8.Eliá?, M., Matou?ek, J.: Higher-order Erd?s–Szekeres theorems. Adv. Math. 244, 1-5 (2013)View Article MATH MathSciNet
  9.Eliá?, M., Matou?ek, J., Roldán-Pensado, E., Safernová Z.: Lower bounds on geometric Ramsey functions. Extended Abstract in: Proceedings of the 30th Annual Symposium on Computational Geometry (2014, preprint). arXiv:-307.-157
  10.Erd?s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463-70 (1935)
  11.Fox, J., Pach, J., Sudakov, B., Suk, A.: Erd?s–Szekeres-type theorem for monotone paths and convex bodies. Proc. Lond. Math. Soc. 105(5), 953-82 (2012)View Article MATH MathSciNet
  12.G?rtner, B., Matou?ek, J.: Approximation Algorithms and Semidefinite Programming. Springer, Heidelberg (2012)View Article MATH
  13.Gr?tschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Berlin (1988)
  14.Kopotun, K., Shadrin, A.: On \(k\) -monotone approximation by free knot splines. SIAM J. Math. Anal. 34(4), 901-24 (2003)View Article MATH MathSciNet
  15.Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2010)MATH
  16.Morris, W., Soltan, V.: The Erd?s–Szekeres problem on points in convex position—a survey. Bull. Am. Math. Soc. New Ser. 37(4), 437-58 (2000)View Article MATH MathSciNet
  17.Pe?ari?, J.E., Proschan, F., Tong, Y.L.: Convex Functions, Partial Orderings, and Statistical Applications. Mathematics in Science and Engineering, vol. 187. Academic Press, Boston (1992)MATH
  18.Porkolab, L., Khachiyan, L.: On the complexity of semidefinite programs. J. Global Optim. 10, 351-65 (1997)View Article MATH MathSciNet
  19.Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77(2B), 129-62 (1997)MATH MathSciNet
  20.Roberts, A.W., Varberg, D.E.: Convex Functions. Pure and Applied Mathematics, vol. 57. Academic Press, New York (1973)MATH
  21.Schoenberg, I.J.: On integral representations of completely monotone and related functions (abstract). Bull. Am. Math. Soc. 47, 208 (1941)
  22.Steele, M.J.: Variations on the monotone subsequence theme of Erd?s and Szekeres. In: Aldous, D., et al. (eds.) Discrete Probability and Algorithms. IMA Volumes in Mathematics and Its Applications, vol. 72, pp. 111-31. Springer, Berlin (1995)View Article
  23.Suk, A.: A note on order-type homogeneous point sets. Mathematika 60(1), 37-2 (2014)View Article MATH MathSciNet
  24.Tarasov, S.P., Vyalyi, M.N.: Semidefinite programming and arithmetic circuit evaluation. Discrete Appl. Math. 156(11), 2070-078 (2008)View Article MATH MathSciNet
  25.Williamson, R.E.: Multiply monotone functions and their Laplace transforms. Duke Math. J. 23, 189-07 (1956)View Article MATH MathSciNet
  26.Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht (2000)
  
• 作者单位：Josef Cibulka (1) (2)
  Ji?í Matou?ek (1) (3)
  Pavel Paták (4)
  
  1. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Prague 1, Czech Republic
  2. Institute of Physics of the ASCR, v.v.i., Za Slovankou 1782/3, 182 00, Prague 8, Czech Republic
  3. Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland
  4. Department of Algebra, Charles University, Sokolovská 83, 186 75, Prague 8, Czech Republic
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444

文摘

A function \(f:{\mathbb {R}}\rightarrow {\mathbb {R}}\) is called \(k\)-monotone if it is \((k-2)\)-times differentiable and its \((k-2)\)nd derivative is convex. A point set \(P\subset {\mathbb {R}}^2\) is \(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 nonlocal: 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 Erd?s and Szekeres, while the cases with \(k\ge 4\) 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.