Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization
DOI10.1007/s10107-012-0515-1zbMath1262.90196OpenAlexW2158834326MaRDI QIDQ1949261
Makoto Yamashita, Kojima, Masakazu
Publication date: 6 May 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0515-1
positive semidefinite matrixpolynomial optimization problemsellipsoidal setcompute error boundsconceptual min-max problemexisting SDP relaxationsLasserres hierarchy SDP relaxationsemialgebraic subset of \(\mathbb{R}^m\)sparsity for various optimization
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59) Semialgebraic sets and related spaces (14P10)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving semidefinite-quadratic-linear programs using SDPT3
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Positive definite completions of partial Hermitian matrices
- Minimum-volume enclosing ellipsoids and core sets
- Minimum ellipsoid bounds for solutions of polynomial systems via sum of squares
- Theory of semidefinite programming for sensor network localization
- An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
- A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones
- Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP
- Semidefinite programming relaxation for nonconvex quadratic programs
- Extension of primal-dual interior point algorithms to symmetric cones
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Sparsity in sums of squares of polynomials
- Primal-dual path-following algorithms for determinant maximization problems with linear matrix inequalities
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- On maximization of quadratic form over intersection of ellipsoids with common center
- Incidence matrices and interval graphs
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Global Optimization with Polynomials and the Problem of Moments
- Algorithm 920
- Newton-Type Minimization via the Lanczos Method
- Testing Unconstrained Optimization Software
- Linear Matrix Inequalities in System and Control Theory
- Determinant Maximization with Linear Matrix Inequality Constraints
- A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES
- CSDP 2.3 user's guide
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Rounding of Polytopes in the Real Number Model of Computation
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Computation of Minimum-Volume Covering Ellipsoids
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- On the Minimum Volume Covering Ellipsoid of Ellipsoids
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
