Efficient sampling in spectrahedra and volume approximation
DOI10.1016/j.laa.2022.04.002zbMath1489.90105arXiv2010.03817OpenAlexW4225384330WikidataQ114151654 ScholiaQ114151654MaRDI QIDQ2144244
Apostolos Chalkis, Ioannis Z. Emiris, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias P. Tsigaridas
Publication date: 1 June 2022
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.03817
samplingoptimizationMonte Carlorandom walkvolume approximationpolynomial eigenvalue problemsemidefinite-programmingspectahedron
Semidefinite programming (90C22) Monte Carlo methods (65C05) Computational aspects related to convexity (52B55) Eigenvalues, singular values, and eigenvectors (15A18) Complexity and performance of numerical algorithms (65Y20) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17) Numerical approximation and computational geometry (primarily algorithms) (65D99)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A practical volume algorithm
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- The \(D\)-decomposition technique for linear matrix inequalities
- Nearly optimal refinement of real roots of a univariate polynomial
- Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets
- On the complexity of the Lickteig-Roy subresultant algorithm
- On the complexity of computing determinants
- A Monte Carlo approach to the analysis of control system robustness
- Perturbation theory for homogeneous polynomial eigenvalue problems
- Separation bounds for polynomial systems
- Deterministic computation of the characteristic polynomial in the time of matrix multiplication
- Efficient estimation of covariance selection models
- Condition
- Bypassing KLS
- A Randomized Cutting Plane Method with Probabilistic Geometric Convergence
- The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs
- Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
- Approximate Volume and Integration for Basic Semialgebraic Sets
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Random walks and anO*(n5) volume algorithm for convex bodies
- The nonlinear eigenvalue problem
- Practical Polytope Volume Approximation
- Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
- Semidefinite Optimization and Convex Algebraic Geometry
- Sampling the feasible sets of SDPs and volume approximation
- Computing the Volume of Compact Semi-Algebraic Sets
- Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
- Random Spectrahedra
- Compact Rational Krylov Methods for Nonlinear Eigenvalue Problems
- Simulated Annealing for Convex Optimization
- Vector Spaces of Linearizations for Matrix Polynomials
- Symmetric Linearizations for Matrix Polynomials
- A survey of computational complexity results in systems and control
- Sylvester-Habicht sequences and fast Cauchy index computation
This page was built for publication: Efficient sampling in spectrahedra and volume approximation
