A note on polynomial solvability of the CDT problem
From MaRDI portal
Abstract: We describe a simple polynomial-time algorithm for the CDT problem that relies on a construction of Barvinok.
Recommendations
- On the complexity of quadratic programming with two quadratic constraints
- Polynomial Solvability of Variants of the Trust-Region Subproblem
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- New Results on Quadratic Minimization
- Solving generalized CDT problems via two-parameter eigenvalues
Cites work
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- A Survey of the S-Lemma
- A two-variable approach to the two-trust-region subproblem
- Algorithms in real algebraic geometry
- Alternative theorems for quadratic inequality systems and global quadratic optimization
- Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Estimating \(L^\infty\) norms by \(L^{2k}\) norms for functions on orbits.
- Feasibility testing for systems of real quadratic equations
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- New Results on Quadratic Minimization
- On a subproblem of trust region algorithms for constrained optimization
- On Local Solutions of the Celis--Dennis--Tapia Subproblem
- On maxima of dual function of the CDT subproblem
- Optimality Conditions for the Minimization of a Quadratic with Two Quadratic Constraints
- Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
- Second-order-cone constraints for extended trust-region subproblems
- Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
- The trust region subproblem with non-intersecting linear constraints
- Trust Region Methods
- Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
Cited in
(45)- A computational study of global optimization solvers on two trust region subproblems
- Numerical experience with a polyhedral-norm CDT trust-region algorithm
- Efficient local search procedures for quadratic fractional programming problems
- An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
- When a system of real quadratic equations has a solution
- Comment on: ``Approximation algorithms for quadratic programming
- A survey of hidden convex optimization
- Finding second-order stationary points in constrained minimization: a feasible direction approach
- A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
- A hybrid algorithm for the two-trust-region subproblem
- A gentle, geometric introduction to copositive optimization
- Recent advances in trust region algorithms
- On the complexity of quadratic programming with two quadratic constraints
- A polynomial case of the cardinality-constrained quadratic optimization problem
- Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow
- A two-variable approach to the two-trust-region subproblem
- Solving generalized CDT problems via two-parameter eigenvalues
- Kronecker product constraints with an application to the two-trust-region subproblem
- Computing the signed distance between overlapping ellipsoids
- The solution of Euclidean norm trust region SQP subproblems via second-order cone programs: an overview and elementary introduction
- On obtaining the convex hull of quadratic inequalities via aggregations
- On Chebyshev center of the intersection of two ellipsoids
- A linear-time algorithm for globally maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere
- A second-order cone based approach for solving the trust-region subproblem and its variants
- New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem
- On Local Minimizers of Nonconvex Homogeneous Quadratically Constrained Quadratic Optimization with at Most Two Constraints
- Complexity, exactness, and rationality in polynomial optimization
- Complexity, exactness, and rationality in polynomial optimization
- On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
- A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
- KKT-based primal-dual exactness conditions for the Shor relaxation
- Optimization under uncertainty and risk: quadratic and copositive approaches
- (Global) optimization: historical notes and recent developments
- Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem
- How Do Exponential Size Solutions Arise in Semidefinite Programming?
- An efficient splitting algorithm for solving the CDT subproblem
- Solving two-trust-region subproblems using semidefinite optimization with eigenvector branching
- The mixed integer trust region problem
- On convergence of the block Lanczos method for the CDT subproblem
- A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
- On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints
- On spectral and nuclear norms of order three tensors with one fixed dimension
- Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
- A fast and cheap approach for strengthening Lagrangian bound for the generalized Celis-Dennis-Tapia subproblem
- Tilt stability for quadratic programs with one or two quadratic inequality constraints
This page was built for publication: A note on polynomial solvability of the CDT problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789609)
