The trust region subproblem with non-intersecting linear constraints
From MaRDI portal
Publication:2515041
The authors consider an extended trust region subproblem (eTRS) in which the trust region is formed by the intersection of the unit ball and the solution set of \(m\) linear inequality constraints, and they study the relation of the optimal value of the eTRS to that of a particular convex relaxation of this problem which is solvable in polynomial time. As was shown earlier, both optimal values are identical for \(m\leq 2\) when the linear constraints are parallel and the optimal value of the relaxation problem is strictly smaller than that of the eTRS for \(m\geq 2\) when at least two of the linear constraints intersect within the unit ball, i.e., are satisfied with equality for some feasible point of the eTRS. In this paper it is proved that in fact for each \(m\) there is no gap between both optimal values as long as the \(m\) linear constraints do not intersect or, more generally, as long as they do not intersect in the interior of the unit ball.
Recommendations
- Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints
- Trust region subproblem with an additional linear inequality constraint
- Second-order-cone constraints for extended trust-region subproblems
- A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts
- An efficient algorithm for the extended trust-region subproblem with two linear constraints
Cites work
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Approximation algorithms for quadratic programming
- Computing a Trust Region Step
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- New Results on Quadratic Minimization
- On Cones of Nonnegative Quadratic Functions
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Problems of distance geometry and convex properties of quadratic maps
- Second-order-cone constraints for extended trust-region subproblems
- Solving the Trust-Region Subproblem using the Lanczos Method
- The generalized trust region subproblem
- Trust Region Methods
Cited in
(50)- An efficient algorithm for solving the generalized trust region subproblem
- Quadratic programs with hollows
- A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
- Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
- Coderivatives related to parametric extended trust region subproblem and their applications
- Parametric approach for solving quadratic fractional optimization with a linear and a quadratic constraint
- An efficient algorithm for the extended trust-region subproblem with two linear constraints
- 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
- Finding second-order stationary points in constrained minimization: a feasible direction approach
- Globally solving extended trust region subproblems with two intersecting cuts
- A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
- Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming
- Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints
- A hybrid algorithm for the two-trust-region subproblem
- A gentle, geometric introduction to copositive optimization
- A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts
- On globally solving the extended trust-region subproblems
- Interplay of non-convex quadratically constrained problems with adjustable robust optimization
- On indefinite quadratic optimization over the intersection of balls and linear constraints
- Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow
- Trust region subproblem with an additional linear inequality constraint
- A note on polynomial solvability of the CDT problem
- A two-variable approach to the two-trust-region subproblem
- Exactness conditions for an SDP relaxation of the extended trust region problem
- Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems
- A block Lanczos method for the extended trust-region subproblem
- Solving trust-region subproblem augmented with linear inequality constraints
- On Convex Hulls of Epigraphs of QCQPs
- On obtaining the convex hull of quadratic inequalities via aggregations
- 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
- On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
- Connectivity of quadratic hypersurfaces and its applications in optimization. I: General theory
- Second-order-cone constraints for extended trust-region subproblems
- A second-order cone based approach for solving the trust-region subproblem and its variants
- Polynomial Solvability of Variants of the Trust-Region Subproblem
- New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem
- A linear-time algorithm for generalized trust region subproblems
- KKT-based primal-dual exactness conditions for the Shor relaxation
- (Global) optimization: historical notes and recent developments
- Convex hull results on quadratic programs with non-intersecting constraints
- Semidefinite representable reformulations for two variants of the trust-region subproblem
- New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
- Accelerated first-order methods for a class of semidefinite programs
- Convexification techniques for fractional programs
- A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
- Accelerating the branch and bound algorithm for solving the extended trust-region subproblems
- Quadratic optimization with two ball constraints
This page was built for publication: The trust region subproblem with non-intersecting linear constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515041)
