Globally solving extended trust region subproblems with two intersecting cuts
- PDF / 348,259 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 173 Views
Globally solving extended trust region subproblems with two intersecting cuts Zhibin Deng1,2
· Cheng Lu3 · Ye Tian4 · Jian Luo5
Received: 21 May 2018 / Accepted: 19 September 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract In this paper, we propose an algorithm to globally solve the extended trust-region subproblem with two linear intersecting cuts. Based on the tightness of the linear cuts at optimal solution, we can resolve the original problem by solving either a traditional trust-region subproblem over a sphere or a semidefinite programming relaxation with second-order cone constraints. Two examples from literature and numerical experiment on randomly generated instances are used to demonstrate how the proposed algorithm works. Keywords Extended trust region subproblem · Intersecting cuts · Semidefinite programming relaxation · Second-order cone constraints
1 Introduction Consider the extended trust-region subproblem (ETRS) with linear cuts as follows: min x T Qx + 2q T x s.t. x ≤ 1,
B
(ETRSm )
Jian Luo [email protected]
1
School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190, China
2
Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China
3
School of Economics and Management, North China Electric Power University, Beijing 102206, China
4
School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China
5
School of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025, China
123
Z. Deng et al.
a1T x ≤ b1 , .. . amT x ≤ bm , where x ∈ n is the decision variable, x is the Euclidean norm of x, Q is an n × n symmetric real matrix, q, a1 , . . . , am ∈ n , and b1 , . . . , bm are constants. In particular, we assume Q is not positive semidefinite. Otherwise, (ETRSm ) is a tractable convex program, which can be solved in polynomial time to any given precision by interior-point methods [1]. Problem (ETRSm ) arises from the trust-region method for constrained optimization problems (ref. [18]). When m = 1, i.e., there is only one linear cut in (ETRSm ), Sturm and Zhang [14] showed that (ETRSm ) can be reformulated to an equivalent semi-definite programming (SDP) problem with second-order cone (SOC) constraints. Therefore, (ETRSm ) is polynomial-time solvable within any given precision for m = 1. Locatelli also established the exactness conditions for an SDP relaxations of this problem in [8]. For large-scale instances, Salahi and Taati proposed a fast eigenvalue approach in [13]. For m ≥ 3, Jeyakumar and Li [6] show that the classical SDP relaxation is tight as long as a dimensional condition holds. Burer and Yang proved in [3] that the SDP relaxation with additional SOC reformulation (SDPR-SOCR) is exact when any two of the linear cuts are nonintersecting in the unit ball. For solving (ETRSm ) in a general case, we refer the readers [4,9] and [10] for conic approximation methods. We point
Data Loading...
