Globally Solving the Trust Region Subproblem Using Simple First-Order Methods

DOI10.1137/16M1150281zbMath1455.90104OpenAlexW2809818748MaRDI QIDQ4571045

Amir Beck, Yakov Vaisbourd

Publication date: 6 July 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

optimality conditionsglobal optimumfirst-order methodstrust region subproblem

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26) Optimality conditions and duality in mathematical programming (90C46)

Related Items

An efficient algorithm for the extended trust-region subproblem with two linear constraints, An active-set algorithm for norm constrained quadratic problems, On the branch and bound algorithm for the extended trust-region subproblem, Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem, Solving trust region subproblems using Riemannian optimization, A variable metric and Nesterov extrapolated proximal DCA with backtracking for a composite DC program, First-Order Methods for Nonconvex Quadratic Minimization, Error estimates for iterative algorithms for minimizing regularized quadratic subproblems, Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step, Tilt stability for quadratic programs with one or two quadratic inequality constraints, An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint, Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem

Uses Software

• GQTPAR
• HSL-VF05

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for trust region problems
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• A constrained eigenvalue problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem
• Minimizing a Quadratic Over a Sphere
• Introduction to Nonlinear Optimization
• Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem
• Accelerating the LSTRS Algorithm
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Computing a Trust Region Step
• Iterative Methods for Finding a Trust-region Step
• The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
• Computing Optimal Locally Constrained Steps
• Newton’s Method with a Model Trust Region Modification
• A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
• Trust Region Methods
• First-Order Methods in Optimization
• Solving the Trust-Region Subproblem using the Lanczos Method
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants