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

DOI10.1007/S10898-020-00985-XMaRDI QIDQ2045012zbMATH OpenOpenAlexFDO

Authors Zhuoyi Xu, Yong Xia, Jiulin Wang

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 programmingapproximation algorithmquadratic optimizationChebyshev center

Mathematics Subject Classification ID

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

Recommendations

• Faster, but weaker, relaxations for quadratically constrained quadratic programs
• scientific article; zbMATH DE number 169307
• Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
• A relaxation method for nonconvex quadratically constrained quadratic programs
• A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
• On convex relaxations for quadratically constrained quadratic programming
• Improved approximation bound for quadratic optimization problems with orthogonality constraints
• A new convex relaxation for quadratically constrained quadratic programming
• Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints.
• scientific article; zbMATH DE number 6474937

Cites work

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

Cited in

(4)

• Covering a set by a convex compactum: error estimates and computation
• Chebyshev center of the intersection of balls: complexity, relaxation and approximation
• Chebyshev center and inscribed balls: properties and calculations
• On Chebyshev center of the intersection of two ellipsoids

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

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