An efficient algorithm for large-scale extended trust-region subproblems with non-intersecting linear constraints
Author | Karbasy, S.A. |
Author | Hamdi, A. |
Author | Salahi, M. |
Author | Taati, A. |
Available date | 2023-09-24T07:55:31Z |
Publication Date | 2021 |
Publication Name | Optimization Letters |
Resource | Scopus |
Abstract | In this paper, we study the extended trust-region subproblem in which the trust-region intersects the ball with m linear inequality constraints (m-eTRS). We assume that the linear constraints do not intersect inside the ball. We show that the optimal solution of m-eTRS can be found by solving one TRS, computing the local non-global minimizer of TRS if it exists and solving at most two TRSs with an additional linear equality constraint (1-eqTRS). Both TRS and (1-eqTRS) are polynomially and efficiently solvable, thus the new algorithm significantly improves over the SOCP/SDP relaxation of Burer and Yang [Math Program 149(1-2):253-264, 2015]. on two classes of test problems, the efficiency of the proposed approach is compared with the SOCP/SDP relaxation and branch and bound algorithm of Beck and Pan [J Global Optim 69(2):309-342, 2017]. 2021, Springer-Verlag GmbH Germany, part of Springer Nature. |
Language | en |
Publisher | Springer Science and Business Media Deutschland GmbH |
Subject | Extended trust-region sub-problems SOCP/SDP relaxation Trust-region methods |
Type | Article |
Pagination | 1425-1446 |
Issue Number | 4 |
Volume Number | 15 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
-
Mathematics, Statistics & Physics [722 items ]