Chebyshev center of the intersection of balls: complexity, relaxation and approximation

DOI10.1007/S10107-020-01479-0zbMATH Open1465.90120arXiv1901.07645OpenAlexW3008356049MaRDI QIDQ2020607FDOQ2020607

Authors: Yong Xia, Shu Wang, Mei-Jia Yang 

Publication date: 23 April 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We study the n-dimensional problem of finding the smallest ball enclosing the intersection of p given balls, the so-called Chebyshev center problem (CCB). It is a minimax optimization problem and the inner maximization is a uniform quadratic optimization problem (UQ). When p<=n, (UQ) is known to enjoy a strong duality and consequently (CCB) is solved via a standard convex quadratic programming (SQP). In this paper, we first prove that (CCB) is NP-hard and the special case when n = 2 is strongly polynomially solved. With the help of a newly introduced linear programming relaxation (LP), the (SQP) relaxation is reobtained more directly and the first approximation bound for the solution obtained by (SQP) is established for the hard case p>n. Finally, also based on (LP), we show that (CCB) is polynomially solved when either n or p-n(> 0) is fixed.

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

Recommendations

• On Chebyshev center of the intersection of two ellipsoids
• Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
• The problem of a minimal ball enclosing k points
• On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
• Complexity and approximation of the smallest \(k\)-enclosing ball problem

zbMATH Keywords

linear programmingminimaxcomplexitysemidefinite programmingapproximationstrong dualityChebyshev centernonconvex quadratic optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Minimax problems in mathematical programming (90C47)

Cites Work

• Linear Matrix Inequalities in System and Control Theory
• Introductory lectures on convex optimization. A basic course.
• Semidefinite Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
• On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Regularization in Regression with Bounded Noise: A Chebyshev Center Approach
• A Minimax Chebyshev Estimator for Bounded Error Estimation
• Optimal algorithms theory for robust estimation and prediction
• Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
• Title not available (Why is that?)
• Čebyšev sets in the space of convex bodies
• Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
• A new approximate algorithm for the Chebyshev center
• Polynomial Solvability of Variants of the Trust-Region Subproblem
• Convergence of the method of Chebyshev centers and some applications
• The minimum sphere covering a convex polyhedron
• LMI approximations for the radius of the intersection of ellipsoids: Survey.
• Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints
• On Chebyshev Center of the Intersection of Two Ellipsoids
• 10.1007/s11470-008-1002-x

Cited In (8)

• On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
• On Chebyshev Center of the Intersection of Two Ellipsoids
• Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
• An algorithm for finding the Chebyshev center of a convex polyhedron
• Covering a set by a convex compactum: error estimates and computation
• An algorithm for finding the generalized Chebyshev center of sets defined via their support functions
• On global solvability of a class of possibly nonconvex QCQP problems in Hilbert spaces
• Chebyshev center and inscribed balls: properties and calculations

This page was built for publication: Chebyshev center of the intersection of balls: complexity, relaxation and approximation

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