Polynomial Solvability of Variants of the Trust-Region Subproblem

DOI10.1137/1.9781611973402.28zbMath1428.90109OpenAlexW4254731324MaRDI QIDQ5383987

Bienstock, Daniel, Alexander Michalka

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.28

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items (20)

On Local Minimizers of Nonconvex Homogeneous Quadratically Constrained Quadratic Optimization with at Most Two Constraints ⋮ On box-constrained total least squares problem ⋮ On Convex Hulls of Epigraphs of QCQPs ⋮ On the tightness of SDP relaxations of QCQPs ⋮ Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem ⋮ A survey of hidden convex optimization ⋮ Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs ⋮ On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem ⋮ KKT-based primal-dual exactness conditions for the Shor relaxation ⋮ (Global) optimization: historical notes and recent developments ⋮ Finding second-order stationary points in constrained minimization: a feasible direction approach ⋮ Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity ⋮ Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem ⋮ The Convex Hull of a Quadratic Constraint over a Polytope ⋮ A Block Lanczos Method for the Extended Trust-Region Subproblem ⋮ A Trust-Region Algorithm for Heterogeneous Multiobjective Optimization ⋮ Chebyshev center of the intersection of balls: complexity, relaxation and approximation ⋮ Some results for quadratic problems with one or two quadratic constraints ⋮ An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem ⋮ Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension

This page was built for publication: Polynomial Solvability of Variants of the Trust-Region Subproblem