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

DOI10.1007/s11590-016-1070-0zbMath1410.90145OpenAlexW2508878802MaRDI QIDQ1686552

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 complexitytrust region subproblemproximal gradient algorithm

Mathematics Subject Classification ID

Quadratic programming (90C20)

Related Items (18)

Globally Solving the Trust Region Subproblem Using Simple First-Order Methods ⋮ On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint ⋮ A survey of hidden convex optimization ⋮ A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants ⋮ Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation ⋮ 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 ⋮ Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem ⋮ 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 ⋮ Error estimates for iterative algorithms for minimizing regularized quadratic subproblems ⋮ An accelerated first-order method with complexity analysis for solving cubic regularization 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 ⋮ 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 ⋮ The generalized trust region subproblem: solution complexity and convex hull results

Uses Software

• GQTPAR
• HSL-VF05

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for trust region problems
• The generalized trust region subproblem
• Strong duality for generalized trust region subproblem: S-lemma with interval bounds
• Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• Recent advances in trust region algorithms
• Computing a Trust Region Step
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Trust Region Methods
• Solving the Trust-Region Subproblem using the Lanczos Method
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations

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