咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >A LINEAR-TIME ALGORITHM FOR GE... 收藏

A LINEAR-TIME ALGORITHM FOR GENERALIZED TRUST REGION SUBPROBLEMS

为概括信任区域 Subproblems 的一个线性时间的算法

作     者:Jiang, Rujun Li, Duan 

作者机构:Fudan Univ Sch Data Sci Shanghai Peoples R China City Univ Hong Kong Sch Data Sci Hong Kong Peoples R China 

出 版 物:《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期:2020年第30卷第1期

页      面:915-932页

核心收录:

学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基  金:Shanghai Sailing Program [18YF1401700] Natural Science Foundation of China (NSFC) Science and Technology Commission of Shanghai Municipality Project Hong Kong Research Grants Council [14213716, 14202017] 

主  题:generalized trust region subproblem semidefinite programming linear-time complexity approximation algorithms 

摘      要:In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363-381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分