Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem

DOI10.1137/16M1058200zbMath1359.49009OpenAlexW2591505158MaRDI QIDQ2967610

Satoru Adachi, Akiko Takeda, Satoru Iwata, Yuji Nakatsukasa

Publication date: 1 March 2017

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

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

zbMATH Keywords

generalized eigenvalue problemtrust-region subproblemhard caseelliptic inner product

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30) Numerical optimization and variational techniques (65K10) Numerical methods based on nonlinear programming (49M37)

Related Items

An efficient algorithm for the extended trust-region subproblem with two linear constraints, An active-set algorithm for norm constrained quadratic problems, A Nested Lanczos Method for the Trust-Region Subproblem, 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, Globally Solving the Trust Region Subproblem Using Simple First-Order Methods, Optimization of triangular networks with spatial constraints, A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants, Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization, Exact two steps SOCP/SDP formulation for a modified conic trust region subproblem, On Local Non-Global Minimizers of Quadratic Optimization Problem with a Single Quadratic Constraint, Solving trust region subproblems using Riemannian optimization, A Block Lanczos Method for Large-Scale Quadratic Minimization Problems with Orthogonality Constraints, Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems, Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem, Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem, Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, A Block Lanczos Method for the Extended Trust-Region Subproblem, On High-Order Multilevel Optimization Strategies, Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem, Local nonglobal minima for solving large-scale extended trust-region subproblems, Integral line-of-sight path following control of magnetic helical microswimmers subject to step-out frequencies, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, QPLIB: a library of quadratic programming instances, An iterative algorithm for the conic trust region subproblem, Error estimates for iterative algorithms for minimizing regularized quadratic subproblems, Solving Generalized CDT Problems via Two-Parameter Eigenvalues, A Newton's method characterization for real eigenvalue problems, Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem, Inertia laws and localization of real eigenvalues for generalized indefinite eigenvalue problems, Error analysis for denoising smooth modulo signals on a graph, A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint, A hybrid algorithm for the two-trust-region subproblem, Quadratic optimization with two ball constraints, On local nonglobal minimum of trust-region subproblem and extension, The Convergence of the Generalized Lanczos Trust-Region Method for the Trust-Region Subproblem, Solving the Cubic Regularization Model by a Nested Restarting Lanczos Method, An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint, \(\rho\)-regularization subproblems: strong duality and an eigensolver-based algorithm

Uses Software

• Matlab
• GALAHAD
• JDQR
• ARPACK
• LSTRS
• JDQZ
• GQTPAR
• mftoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized trust region subproblem
• Obstacle collision detection using best ellipsoid fit
• On solving trust-region and other regularised subproblems in optimization
• A constrained eigenvalue problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem
• Minimizing a Quadratic Over a Sphere
• Solving Generalized CDT Problems via Two-Parameter Eigenvalues
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Computing a Trust Region Step
• Algorithm 873
• Iterative Methods for Finding a Trust-region Step
• A Subspace Minimization Method for the Trust-Region Step
• The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
• Computing Optimal Locally Constrained Steps
• Solution of Sparse Indefinite Systems of Linear Equations
• Numerical Optimization
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• ARPACK Users' Guide
• On Some Properties of Quadratic Programs with a Convex Quadratic Constraint
• A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
• Trust Region Methods
• Templates for the Solution of Algebraic Eigenvalue Problems
• The trust region subproblem and semidefinite programming*
• Solving the Trust-Region Subproblem using the Lanczos Method
• Approximate solutions and eigenvalue bounds from Krylov subspaces
• Second-Order-Cone Constraints for Extended Trust-Region Subproblems
• Functions of Matrices
• GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization
• On the Stationary Values of a Second-Degree Polynomial on the Unit Sphere