On the branch and bound algorithm for the extended trust-region subproblem

In this paper, by an example we show a defect of the Branch and Bound (BB) algorithm of Beck & Pan (J Glob Optim 69:309–342, 2017) for solving the extended trust-region subproblem ( m -eTRS) when the trust-region subproblem (TRS) is hard case 2. Then, to resolve the defect, we propose to solve a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2022-06, Vol.83 (2), p.221-233
Main Authors: Ansary Karbasy, Saeid, Salahi, Maziar
Format: Article
Language:English
Subjects:
Algorithms
Branch and bound methods
Computer Science
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Real Functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, by an example we show a defect of the Branch and Bound (BB) algorithm of Beck & Pan (J Glob Optim 69:309–342, 2017) for solving the extended trust-region subproblem ( m -eTRS) when the trust-region subproblem (TRS) is hard case 2. Then, to resolve the defect, we propose to solve a subproblem at the root node in order to check whether TRS in the hard case 2 has an optimal that is also feasible and thus optimal for m -eTRS. On several randomly generated test problems, we show that the enhanced algorithm is significantly better than the original BB algorithm in terms of CPU times and fathomed nodes.
ISSN:0925-5001
1573-2916
DOI:10.1007/s10898-021-01104-0