A linear-time algorithm for the trust region subproblem based on hidden convexity

DOI10.1007/S11590-016-1070-0MaRDI QIDQ1686552zbMATH OpenOpenAlexFDO

Authors Jiulin Wang, Yong Xia

Publication date 15 December 2017

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-016-1070-0

zbMATH Keywords

hidden convexitylinear time complexityproximal gradient algorithmtrust region subproblem

Mathematics Subject Classification ID

Quadratic programming (90C20)

Recommendations

• A linear-time algorithm for generalized trust region subproblems
• A linear-time algorithm for trust region problems
• The generalized trust region subproblem: solution complexity and convex hull results
• Trust region subproblem with an additional linear inequality constraint
• An efficient algorithm for the extended trust-region subproblem with two linear constraints

Cites work

• A linear-time algorithm for trust region problems
• Computing a Trust Region Step
• Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• Recent advances in trust region algorithms
• Solving the Trust-Region Subproblem using the Lanczos Method
• Strong duality for generalized trust region subproblem: S-lemma with interval bounds
• The generalized trust region subproblem
• Trust Region Methods

Cited in

(19)

• An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
• The generalized trust region subproblem: solution complexity and convex hull results
• On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint
• A survey of hidden convex optimization
• Globally solving extended trust region subproblems with two intersecting cuts
• A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• A linear-time algorithm for trust region problems
• Globally solving the trust region subproblem using simple first-order methods
• Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
• Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• 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
• Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
• A linear-time algorithm for generalized trust region subproblems
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• A Convex Approximation for a PDE Constrained Fractional Optimization Problem with an Application to Photonic Crystal Design

Describes a project that uses

Uses Software

• HSL-VF05
• GQTPAR

This page was built for publication: A linear-time algorithm for the trust region subproblem based on hidden convexity

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