Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10–16, 2022. (English) Zbl 1519.00018
Summary: From a mathematical perspective, optimization is the science of proving inequalities. In this sense, computational optimization is a method for computer-assisted proofs.
Conic (linear) optimization is the problem of minimizing a linear functional over the intersection of a convex cone with an affine subspace of a topological vector space. For many cones this problem is computationally tractable, and as a result there is a growing number of computer-assisted proofs using conic optimization in discrete geometry, (extremal) graph theory, numerical analysis, and other fields, the most famous example perhaps being the proof of the Kepler Conjecture.
The aim of this workshop was to bring researchers from these diverse fields together to work towards expanding the current scope of conic optimization as a method of generating proofs, and to identify problems and challenges to work on together.
Conic (linear) optimization is the problem of minimizing a linear functional over the intersection of a convex cone with an affine subspace of a topological vector space. For many cones this problem is computationally tractable, and as a result there is a growing number of computer-assisted proofs using conic optimization in discrete geometry, (extremal) graph theory, numerical analysis, and other fields, the most famous example perhaps being the proof of the Kepler Conjecture.
The aim of this workshop was to bring researchers from these diverse fields together to work towards expanding the current scope of conic optimization as a method of generating proofs, and to identify problems and challenges to work on together.
MSC:
| 00B05 | Collections of abstracts of lectures |
| 00B25 | Proceedings of conferences of miscellaneous specific interest |
| 90-06 | Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming |
| 68-06 | Proceedings, conferences, collections, etc. pertaining to computer science |
| 90Cxx | Mathematical programming |
| 90C22 | Semidefinite programming |
| 14Pxx | Real algebraic and real-analytic geometry |
| 68V05 | Computer assisted proofs of proofs-by-exhaustion type |
| 05Cxx | Graph theory |
References:
| [1] | L. Baldi and B. Mourrain. On Moment Approximation and the Effective Putinar’s Posi-tivstellensatz, arXiv:2111.11258 (2021). · Zbl 1518.14080 |
| [2] | K. Fang and Fawzi. The sum-of-squares hierarchy on the sphere, and applications in quan-tum information theory. Mathematical Programming, 2020. |
| [3] | E. de Klerk and M. Laurent. Worst-case examples for Lasserre’s measure-based hierarchy for polynomial optimization on the hypercube, Mathematics of Operations Research, 45(1) (2020) 86-98. · Zbl 1442.90141 |
| [4] | E. de Klerk and M. Laurent. Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Mathematical Programming (2020). |
| [5] | J.B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11 (2001) 796-817. · Zbl 1010.90061 |
| [6] | J.B. Lasserre. A New Look at Nonnegativity on Closed Sets and Polynomial Optimization, SIAM Journal on Optimization, 21(3) (2010), 864-885. · Zbl 1242.90176 |
| [7] | M. Laurent and L. Slot. An effective version of Schmüdgen’s Positivstellensatz for the hy-percube. arXiv:2109.09528 (2020). · Zbl 1515.90093 |
| [8] | J. Nie and M. Schweighofer. On the complexity of Putinar?s Positivstellensatz. Journal of Complexity 23(1) (2007) 135-150. · Zbl 1143.13028 |
| [9] | L. Slot. Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel. arXiv:2111.04610 (2021). |
| [10] | L. Blum, F. Cucker, M. Shub, S. Smale. Complexity and Real Computation, Springer-Verlag New York Inc. (1998). |
| [11] | J.M. Borwein, H. Wolkowicz. Facial reduction for a cone-convex programming problem, J. Aust. Math. Soc. 30:3 (1981). · Zbl 0464.90086 |
| [12] | E. de Klerk, Aspects of semidefinite programming, Springer (2010). |
| [13] | E. de Klerk, C. Roos, T. Terlaky Initialization in semidefinite programming via a self-dual, skew-symmetric embedding, Op. Res. Lett. 20 (1997), 213-221. · Zbl 0881.90096 |
| [14] | I. Klep, M. Schweighofer. An exact duality theory for semidefinite programming based on sums of squares, Math. Oper. Res. 38:3 (2013), 569-590. · Zbl 1309.13031 |
| [15] | M.V. Ramana. An exact duality theory for semidefinite programming and its complexity implications, Math. Prog. Serie B 77:2 (1997), 129-162. · Zbl 0890.90144 |
| [16] | S. Naldi, R. Sinn. Conic programming: Infeasibility certificates and projective geometry, Journal of Pure and Applied Algebra 225:7 (2021), 106606. · Zbl 1461.90100 |
| [17] | G. Pataki, Bad semidefinite programs: they all look the same, SIAM J. Optim. 27:1 (2017), 146-172. · Zbl 1366.90158 |
| [18] | C. Scheiderer, Sums of squares of polynomials with rational coefficients, J. Eur. Math. Soc. (2016), 1495-1513. · Zbl 1354.14036 |
| [19] | H. Waki, How to generate weakly infeasible semidefinite programs via Lasserre relaxations for polynomial optimization, Optim. Lett. 6:8 (2012), 1883-1896. · Zbl 1257.90069 |
| [20] | Y. Ye, M.J. Todd, S. Mizuno An O( √ nL)-iteration homogeneous and self-dual linear pro-gramming algorithm, Math. Oper. Res. 19:1 (1994), 53-67. · Zbl 0799.90087 |
| [21] | I.M. Bomze, M. Dür, E. de Klerk, C. Roos, A.J. Quist and T. Terlaky, On Copositive Programming and Standard Quadratic Optimization Problems, J. Global Optim. 18 (2000), 301-320. · Zbl 0970.90057 |
| [22] | M. Dutour Sikirić, A. Schürmann and F. Vallentin, Rational factorizations of completely positive matrices, Linear Algebra Appl. 523 (2017), 46-51. · Zbl 1369.90121 |
| [23] | M. Dutour Sikirić, A. Schürmann and F. Vallentin, A simplex algorithm for rational cp-factorization, Math. Prog. 187 (2021), 25-45. · Zbl 1465.90059 |
| [24] | A. Schürmann, Computational geometry of positive definite quadratic forms, Amer. Math. Soc. (2009). · Zbl 1185.52016 |
| [25] | A. Schürmann and V. Dannenberg, Perfect Copositive Matrices, in preparation. · Zbl 07902975 |
| [26] | N. Shaked-Monderer, M. Dür and A. Berman, Complete positivity over the rationals, Pure and Appl. Func. Anal 3 (2018), 681 -691 · Zbl 1474.15085 |
| [27] | C. Bachoc, G. Nebe, F. M. de Oliveira Filho, and F. Vallentin, Lower bounds for measurable chromatic numbers, Geom. Funct. Anal. 19 (2009), no. 3, 645-661. MR 2563765 · Zbl 1214.05022 |
| [28] | C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite pro-gramming, J. Amer. Math. Soc. 21 (2008), no. 3, 909-924. MR 2393433 · Zbl 1223.90039 |
| [29] | C. Bachoc and F. Vallentin, Optimality and uniqueness of the (4, 10, 1/6) spherical code, J. Combin. Theory Ser. A 116 (2009), no. 1, 195-204. MR 2469257 · Zbl 1160.94018 |
| [30] | S. Bochner, Hilbert distances and positive definite functions, Ann. of Math. (2) 42 (1941), 647-656. MR 0005782 · JFM 67.0691.02 |
| [31] | D. de Laat, Moment methods in extremal geometry, Ph.D. thesis, Delft University of Tech-nology, 2017. |
| [32] | D. de Laat and N. Leijenhorst, Solving clustered low-rank semidefinite programs arising from polynomial optimization, 2022. |
| [33] | M. Dostert, D. de Laat, and P. Moustrou, Exact Semidefinite Programming Bounds for Packing Problems, SIAM Journal on Optimization 31 (2021), no. 2, 1433-1458, Publisher: Society for Industrial and Applied Mathematics. · Zbl 1527.90147 |
| [34] | K. Gatermann and P. A. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra 192 (2004), no. 1-3, 95-128. MR 2067190 · Zbl 1108.13021 |
| [35] | F. C. Machado and F. M. de Oliveira Filho, Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry, Aceito em Experiment. Math. (2017), arXiv:1609.05167. |
| [36] | M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969-984. MR 1254128 · Zbl 0796.12002 |
| [37] | I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96-108. MR 0005922 · Zbl 0063.06808 |
| [38] | V. Chandrasekaran and P. Shah. Relative entropy relaxations for signomial optimization. SIAM J. Optim., 26(2):1147-1173, 2016. · Zbl 1345.90066 |
| [39] | V. Chandrasekaran and P. Shah. Relative entropy optimization and its applications. Math. Program., Ser. A, 161(1-2):1-32, 2017. · Zbl 1357.81037 |
| [40] | K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. J. Pure & Applied Algebra, 192(1-3):95-128, 2004. · Zbl 1108.13021 |
| [41] | S. Iliman and T. de Wolff. Amoebas, nonnegative polynomials and sums of squares supported on circuits. Res. Math. Sci., 3(paper no. 9), 2016. · Zbl 1415.11071 |
| [42] | S. Iliman and T. de Wolff. Lower bounds for polynomials with simplex Newton polytopes based on geometric programming. SIAM J. Optim., 26(2):1128-1146, 2016. · Zbl 1380.12001 |
| [43] | L. Katthän, H. Naumann, and T. Theobald. A unified framework of SAGE and SONC polynomials and its duality theory. Math. Comput., 90:1297-1322, 2021. · Zbl 1466.14062 |
| [44] | J. B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim., 17:822-843, 2006 · Zbl 1119.90036 |
| [45] | R. Murray, V. Chandrasekaran, and A. Wierman. Newton polytopes and relative entropy optimization. Found. Comput. Math., 21:1703-1737, 2021. · Zbl 1483.90121 |
| [46] | R. Murray, V. Chandrasekaran, and A. Wierman. Signomial and polynomial optimization via relative entropy and partial dualization. Math. Program. Comput., 13:257-295, 2021. · Zbl 1530.90071 |
| [47] | C. Pantea, H. Koeppl, and G. Craciun. Global injectivity and multiple equilibria in uni-and bi-molecular reaction networks. Discrete and Continuous Dynamical Systems -Series B, 17(6):2153-2170, May 2012. · Zbl 1253.80023 |
| [48] | B. Reznick. Forms derived from the arithmetic-geometric inequality. Math. Annalen, 283(3):431-464, 1989. · Zbl 0637.10015 |
| [49] | C. Riener, T. Theobald, L. Jansson-Andrén, and J. B. Lasserre. Exploiting symmetries in SDP-relaxations for polynomial optimization. Math. Oper. Res., 38(1):122-141, 2013. · Zbl 1291.90167 |
| [50] | H. Waki, S. Kim, M. Kojima, and M. Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim., 17:218-242, 2006 · Zbl 1109.65058 |
| [51] | J. Wang, V. Magron, and J. B. Lasserre. Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim., 31:114-141, 2021. · Zbl 1457.90106 |
| [52] | J. Wang, V. Magron, and J. B. Lasserre. TSSOS: a moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim., 31:1-29, 2021. · Zbl 1506.90202 |
| [53] | Christine Bachoc, Dion C. Gijswijt, Alexander Schrijver, and Frank Vallentin, Invariant semidefinite programs,Handbook on semidefinite, conic and polynomial optimization, Inter-nat. Ser. Oper. Res. Management Sci., vol. 166, Springer, New York, 2012, pp. 219-269. · Zbl 1334.90097 |
| [54] | The GAP Group, GAP -Groups, Algorithms, and Programming, Version 4.11.1, 2021 |
| [55] | Kaashif Hymabaccus and Dmitrii V. Pasechnik, RepnDecomp: A GAP package for decom-posing linear representations of finite groups, Journal of Open Source Software 5 (2020), no. 50, 1835-1836. |
| [56] | Dmitrii Pasechnik, Splitting fields of real irreducible representations of finite groups, Rep-resent. Theory 25 (2021), 897-902. MR 4324950 · Zbl 1510.20013 |
| [57] | Jean-Pierre Serre, Conducteurs d’Artin des caractères réels, Invent. Math. 14 (1971), 173-183. MR 321908 · Zbl 0229.13006 |
| [58] | Frank Vallentin, Symmetry in semidefinite programs, Linear Algebra Appl. 430 (2009), no. 1, 360-369. MR 2460523 · Zbl 1165.90017 |
| [59] | E. Gaar, D. Krenn, S. Margulies, and A. Wiegele, An Optimization-Based Sum-of-Squares Approach to Vizing’s Conjecture, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC ’19), July 15-18, 2019, Beijing, China. · Zbl 1444.68303 |
| [60] | E. Gaar, D. Krenn, S. Margulies, and A. Wiegele. Towards a computational proof of vizing’s conjecture using semidefinite programming and sums-of-squares, J. Symb. Comput., 107:67-105, 2021. · Zbl 1465.05128 |
| [61] | E. Gaar and M. Siebenhofer. Sum-of-squares certificates for Vizing’s conjecture via deter-mining Gröbner bases, https://arxiv.org/abs/2112.04007, December 2021. · Zbl 1519.05190 |
| [62] | M. Siebenhofer. Establishing new sum-of-squares certificates for vizing’s conjecture, Mas-ter’s thesis, University of Klagenfurt, 2021. |
| [63] | V. G. Vizing. Some unsolved problems in graph theory, Uspehi Mat. Nauk, 23(6 (144)):117-134, 1968. · Zbl 0177.52301 |
| [64] | V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math. 4 (1973), 305-337. · Zbl 0253.05131 |
| [65] | R.E. Gomory, Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc. 64 (1958), 275-278. · Zbl 0085.35807 |
| [66] | Frank de Meijer, Renata Sotirov, The Chvátal-Gomory Procedure for Integer SDPs with Ap-plications in Combinatorial Optimization, Preprint, 2022, https://arxiv.org/abs/2201.10224 |
| [67] | Christine Bachoc, Anna Gundert, and Alberto Passuello, The theta number of simplicial complexes, Israel Journal of Mathematics 232 (2019), no. 1, 443-481. · Zbl 1419.90109 |
| [68] | Phillippe Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973), no. 10, vi+97. · Zbl 1075.05606 |
| [69] | David Ellis, Yuval Filmus, and Ehud Friedgut, Triangle-intersecting families of graphs, Journal of the European Mathematical Society 14 (2012), 841-885. · Zbl 1238.05143 |
| [70] | David Ellis, Ehud Friedgut, and Haran Pilpel, Intersecting families of permutations, Journal of the American Mathematical Society 24 (2011), no. 3, 649-682. · Zbl 1285.05171 |
| [71] | Péter Frankl, On Sperner families satisfying an additional condition, Journal of Combina-torial Theory, Series A 20 (1976), no. 1, 1-11. · Zbl 0328.05002 |
| [72] | Yuval Filmus, Konstantin Golubev, Noam Lifshitz, High dimensional Hoffman bound and applications in extremal combinatorics, Algebraic Combinatorics 4, no. 6 (2021): 1005-1026. · Zbl 1511.05177 |
| [73] | Chris Godsil and Karen Meagher, Erdős-Ko-Rado theorems: algebraic approaches, Cam-bridge Studies in Advanced Mathematics, vol. 149, Cambridge University Press, Cambridge, 2016. · Zbl 1343.05002 |
| [74] | Konstantin Golubev, On the chromatic number of a simplicial complex, Combinatorica (2016), 1-12. |
| [75] | Willem Haemers, A generalization of the Higman-Sims technique, Nederl. Akad. Wetensch. Indag. Math. 40 (1978), no. 4, 445-447. · Zbl 0415.15004 |
| [76] | Alan J. Hoffman, On eigenvalues and colorings of graphs, in Selected Papers of Alan J. Hoffman -with Commentary, World Scientific, 2003, pp. 407-419. · Zbl 1041.01013 |
| [77] | László Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information theory 25 (1979), no. 1, 1-7. · Zbl 0395.94021 |
| [78] | M.K. de Carli Silva, F.M. de Oliveira Filho, and C.M. Sato, Flag algebras: a first glance, Nieuw Archief voor Wiskunde 5/17 (2016) 193-199. · Zbl 1364.05090 |
| [79] | A. Razborov, Flag algebras, Journal of Symbolic Logic 72 (2007) 1239-1282. References · Zbl 1146.03013 |
| [80] | M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packing, Journal of Com-binatorial Theory, Series B 40 (1986) 330-343. · Zbl 0596.05052 |
| [81] | D. Castro-Silva, F.M. de Oliveira Filho, L. Slot, and F. Vallentin, A recursive Lovász theta number for simplex-avoiding sets, to appear in Proceedings of the American Mathematical Society, 2021, 13pp, arXiv:2106.09360. |
| [82] | A. Razborov, Flag algebras, Journal Of Symbolic Logic 72 (2007), 1239-1282. · Zbl 1146.03013 |
| [83] | A. Raymond, J. Saunderson, M. Singh and R. Thomas, Symmetric sums-of-squares over k-subset hypercubes, Mathematical Programming 2 (2018), 315-354. · Zbl 1383.05306 |
| [84] | Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex min-imization: a novel approach. Mathematical Programming, 145(1):451-482, 2014. · Zbl 1300.90068 |
| [85] | Yurii Nesterov. A method of solving a convex programming problem with convergence rate O(1/k 2 ). Soviet Mathematics Doklady, 27(2):372-376, 1983. · Zbl 0535.90071 |
| [86] | Boris T. Polyak. Introduction to optimization. Optimization Software New York, 1987. · Zbl 0625.62093 |
| [87] | Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Pro-gramming, 161(1-2):307-345, 2017. · Zbl 1359.90098 |
| [88] | Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27(3):1283-1313, 2017. · Zbl 1371.90108 |
| [89] | Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016. · Zbl 1329.90103 |
| [90] | Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Performance estimation tool-box (PESTO): automated worst-case analysis of first-order optimization methods. In Pro-ceedings of the 56th Conference on Decision and Control (CDC), 2017. · Zbl 1371.90108 |
| [91] | Baptiste Goujaud, Céline Moucer, François Glineur, Julien Hendrickx, Adrien Taylor, and Aymeric Dieuleveut. PEPit: computer-assisted worst-case analyses of first-order optimiza-tion methods in python. preprint arXiv:2201.04040, 2022. |
| [92] | Felix Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):405-418, 2021. · Zbl 1466.90067 |
| [93] | Guoyong Gu and Junfeng Yang. Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems. SIAM Journal on Optimization, 30(3):1905-1921, 2020. · Zbl 1468.90083 |
| [94] | Hadi Abbaszadehpeivasti, Etienne de Klerk, and Moslem Zamani. The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions. Optimization Letters, 2021. · Zbl 1493.90138 |
| [95] | Teodor Rotaru, François Glineur, and Panagiotis Patrinos. Tight convergence rates of the gradient method on hypoconvex functions. preprint arXiv:2203.00775, 2022. |
| [96] | Donghwan Kim and Jeffrey A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1-2):81-107, 2016. · Zbl 1345.90113 |
| [97] | Bryan Van Scoy, Randy A. Freeman, and Kevin M. Lynch. The fastest known globally con-vergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2017. |
| [98] | Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, pages 1-31, 2021. · Zbl 1478.90089 |
| [99] | Donghwan Kim and Jeffrey A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1):192-219, 2021. · Zbl 1468.90085 |
| [100] | Etienne De Klerk, François Glineur, and Adrien B Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimiza-tion Letters, 11(7):1185-1199, 2017. · Zbl 1381.90067 |
| [101] | Yoel Drori and Adrien B Taylor. Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming, 184(1):183-220, 2020. · Zbl 1451.90118 |
| [102] | Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimization. arXiv:2101.09741, 2021. · Zbl 1518.90071 |
| [103] | Arkadi Nemirovski. Information-based complexity of convex programming. Lecture notes, http://www2.isye.gatech.edu/ñemirovs/Lec EMCO.pdf, 1994. References · Zbl 1135.90379 |
| [104] | Sergei Bernstein. Sur l’ordre de la meilleure approximation des fonctions continues par des polynômes de degré donné.émoire couronné, Brussels, 1912. · JFM 45.0633.03 |
| [105] | Felix Kirschner and Etienne de Klerk, “Construction of multivariate polynomial approxi-mation kernels via semidefinite programming,” 2022, arXiv:2203.05892. · Zbl 1519.90155 |
| [106] | Alexander Weiße, Gerhard Wellein, Andreas Alvermann, and Holger Fehske. The kernel polynomial method. Rev. Mod. Phys., 78:275-306, Mar 2006. · Zbl 1205.81090 |
| [107] | Bogdan Dumitrescu. Positive Trigonometric Polynomials and Signal Processing Applica-tions. Signals and Communication Technology. Springer, Dordrecht, 2007. References · Zbl 1126.93005 |
| [108] | L. Lovàsz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1979), 1-7. · Zbl 0395.94021 |
| [109] | Semidefinite programming bounds for the average kissing number Maria Dostert (joint work with Alexander Kolpakov, Fernando Mário de Oliveira Filho) set of interior-disjoint closed balls. Furthermore, the contact graph of a packing P is the graph with vertex set P in which two balls are adjacent if they intersect, that is, if they are tangent to each other. Contact graphs of packings of disks on the plane are characterized by the Koebe-Andreev-Thurston theorem [7]: they are precisely the (simple) planar graphs. In higher dimensions, no such simple characterization is known (see the paper by |
| [110] | J.H. Conway and N.J.A. Sloane, Sphere Packings, Lattices, and Groups, Grundlehren der mathematischen Wissenschaften 290, Springer-Verlag, New York, 1988. · Zbl 0634.52002 |
| [111] | M. Dostert, A. Kolpakov and F.M. de Oliveira Filho, Semidefinite programming bounds for the average kissing number , Israel Journal of Mathematics TBD (2022), 1-25. · Zbl 1493.90158 |
| [112] | D. Eppstein, G. Kuperberg, and G.M. Ziegler, Fat 4-polytopes and fatter 3-spheres, in: Discrete geometry, Monographs and Textbooks in Pure and Applied Mathematics 253, Dekker, New York, 2003, pp. 239-265. · Zbl 1045.52006 |
| [113] | A. Glazyrin, Contact graphs of ball packings, arXiv:1707.02526, 2017, 15pp. |
| [114] | G. Kuperberg and O. Schramm, Average kissing numbers for non-congruent sphere packings, Mathematical Research Letters 1 (1994) 339-344. · Zbl 0836.52007 |
| [115] | F.C. Machado and F.M. de Oliveira Filho, Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry, Experimental Mathematics 27 (2018) 362-369. · Zbl 1401.52028 |
| [116] | K. Stephenson, Introduction to Circle Packing: The Theory of Discrete Analytic Functions, Cambridge University Press, Cambridge, 2005. · Zbl 1074.52008 |
| [117] | N. Afkhami-Jeddi, H. Cohn, T. Hartman, D. de Laat, and A. Tajdini, High-dimensional sphere packing and the modular bootstrap, Journal of High Energy Physics 2020 (2020), no. 12, 66. · Zbl 1457.81095 |
| [118] | C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite pro-gramming, J. Amer. Math. Soc. 21 (2008), no. 3, 909-924. arXiv:math/0608426 MR 2393433 · Zbl 1223.90039 |
| [119] | H. Cohn and N. Elkies, New upper bounds on sphere packings I, Ann. of Math. (2) 157 (2003), no. 2, 689-714. arXiv:math.MG/0110009 MR 1973059 · Zbl 1041.52011 |
| [120] | H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, and M. Viazovska, The sphere packing problem in dimension 24, Ann. of Math. (2) 185 (2017), no. 3, 1017-1033. arXiv:1603.06518 MR 3664817 · Zbl 1370.52037 |
| [121] | H. Cohn, D. de Laat, and A. Salmon, Three-point bounds for sphere packing, in preparation, 2022. |
| [122] | H. Cohn and Y. Zhao, Sphere packing bounds via spherical codes, Duke Math. J. 163 (2014), no. 10, 1965-2002. arXiv:1212.5966 MR 3229046 · Zbl 1296.05046 |
| [123] | D. de Laat, F. M. de Oliveira Filho, and F. Vallentin, Upper bounds for packings of spheres of several radii, Forum of Mathematics, Sigma 2 (2014), e23 (en). · Zbl 1310.52022 |
| [124] | T. C. Hales, A proof of the Kepler conjecture, Ann. of Math. (2) 162 (2005), no. 3, 1065-1185. MR 2179728 · Zbl 1096.52010 |
| [125] | G. A. Kabatyanskii and V. I. Levenshtein, Bounds for packings on a sphere and in space, Problemy Peredachi Informatsii 14 (1978), no. 1, 3-25, English translation in Problems of Information Transmission 14, 1-17, 1978. · Zbl 0407.52005 |
| [126] | M. S. Viazovska, The sphere packing problem in dimension 8, Ann. of Math. (2) 185 (2017), no. 3, 991-1015. arXiv:1603.04246 MR 3664816 · Zbl 1373.52025 |
| [127] | J. Miller and M. Sznaier, “Bounding the Distance to Unsafe Sets with Convex Optimization,” 2021, arXiv:2110.14047. |
| [128] | S. Prajna and A. Jadbabaie, “Safety Verification of Hybrid Systems Using Barrier Certifi-cates,” in International Workshop on Hybrid Systems: Computation and Control. Springer, 2004, pp. 477-492. · Zbl 1135.93317 |
| [129] | R. Lewis and R. Vinter, “Relaxation of optimal control problems to equivalent convex pro-grams,” Journal of Mathematical Analysis and Applications, vol. 74, no. 2, pp. 475-493, 1980. · Zbl 0443.49015 |
| [130] | M. J. Cho and R. H. Stockbridge, “Linear Programming Formulation for Optimal Stopping Problems,” SIAM J. Control Optim., vol. 40, no. 6, pp. 1965-1982, 2002. · Zbl 1010.60037 |
| [131] | C. Villani, Optimal Transport: Old and New. Springer Science & Business Media, 2008, vol. 338. · Zbl 1158.53036 |
| [132] | J. B. Lasserre, Moments, Positive Polynomials And Their Applications, ser. Imperial Col-lege Press Optimization Series. World Scientific Publishing Company, 2009. |
| [133] | H. Waki, S. Kim, M. Kojima, and M. Muramatsu, “Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity,” SIOPT, vol. 17, no. 1, pp. 218-242, 2006. · Zbl 1109.65058 |
| [134] | J. Miller, D. Henrion, and M. Sznaier, “Peak Estimation Recovery and Safety Analysis,” IEEE Control Systems Letters, vol. 5, no. 6, pp. 1982-1987, 2020. |
| [135] | J. Miller, D. Henrion, M. Sznaier, and M. Korda, “Peak Estimation for Uncertain and Switched Systems,” 2021. |
| [136] | M. Yannakakis, “Expressing combinatorial optimization problems by Linear Programs,” Journal of Computer and System Sciences, vol. 43, no. 3, pp. 441-466, 1991. References · Zbl 0748.90074 |
| [137] | Korda, Milan. Stability and performance verification of dynamical systems controlled by neural networks: algorithms and complexity. arXiv preprint arXiv:2102.02273 (2021). |
| [138] | Korda, Milan, and Colin N. Jones. Stability and performance verification of optimization-based controllers. Automatica 78 (2017): 34-45. Reporter: Felix Kirschner · Zbl 1357.93075 |
| [139] | Prof. Dr. Angelika Wiegele Institut für Mathematik Alpen-Adria-Universität Klagenfurt Universitätsstraße 65-67 9020 Klagenfurt AUSTRIA |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
