期刊
SIAM JOURNAL ON OPTIMIZATION
卷 29, 期 2, 页码 1603-1633出版社
SIAM PUBLICATIONS
DOI: 10.1137/18M1174313
关键词
generalized trust region subproblem; convex reformulation; minimax problems; large-scale problems; Kurdyka-Lojasiewicz inequality
资金
- Shanghai Sailing Program [18YF1401700]
- National Natural Science Foundation of China (NSFC) [11801087]
- Hong Kong Research Grants Council [14213716, 14202017]
We present a new solution framework to solve the generalized trust region subproblem (GTRS) of minimizing a quadratic objective over a quadratic constraint. More specifically, we derive a convex quadratic reformulation (CQR) via minimizing a linear objective over two convex quadratic constraints for the GTRS. We show that an optimal solution of the GTRS can be recovered from an optimal solution of the CQR. We further prove that this CQR is equivalent to minimizing the maximum of the two convex quadratic functions derived from the CQR for the case under investigation. Although the latter minimax problem is nonsmooth, it is well structured and convex. We thus develop two steepest descent algorithms corresponding to two different line search rules. We prove global sublinear convergence rates for both algorithms. We also obtain a local linear convergence rate of the first algorithm by estimating the Kurdyka-Lojasiewicz exponent at any optimal solution under mild conditions. We finally demonstrate the efficiency of our algorithms with numerical experiments.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据