Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension

DOI10.1007/s10898-020-00985-xzbMath1473.90108OpenAlexW3118587179MaRDI QIDQ2045012

Publication date: 11 August 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-020-00985-x

zbMATH Keywords

semidefinite programming approximation algorithm quadratic optimization Chebyshev center

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonlinear programming (90C30) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (2)

Chebyshev center and inscribed balls: properties and calculations ⋮ Covering a set by a convex compactum: error estimates and computation

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
A generalization of Löwner-John's ellipsoid theorem
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
Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
On affine scaling algorithms for nonconvex quadratic programming
Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
On the solution of a two ball trust region subproblem
A semidefinite framework for trust region subproblems with applications to large scale minimization
Approximation algorithms for quadratic programming
Approximating quadratic programming with bound and quadratic constraints
Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints
The complexity of approximating a nonlinear program
On maximization of quadratic form over intersection of ellipsoids with common center
Chebyshev center of the intersection of balls: complexity, relaxation and approximation
A survey of hidden convex optimization
Recent advances in trust region algorithms
Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Semidefinite relaxation and nonconvex quadratic optimization
New Results on Quadratic Minimization
Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
Polynomial Solvability of Variants of the Trust-Region Subproblem

This page was built for publication: Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension