A linear-time algorithm for the trust region subproblem based on hidden convexity

Jiulin Wang; Yong Xia

doi:10.1007/s11590-016-1070-0

A linear-time algorithm for the trust region subproblem based on hidden convexity

Jiulin Wang
, Yong Xia^*

^*此作品的通讯作者

数学科学学院

Beihang University

科研成果: 期刊稿件 › 文章 › 同行评审

20 引用（Scopus）

摘要

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

源语言	英语
页（从-至）	1639-1646
页数	8
期刊	Optimization Letters
卷	11
期	8
DOI	https://doi.org/10.1007/s11590-016-1070-0
出版状态	已出版 - 1 12月 2017

访问文件

10.1007/s11590-016-1070-0

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{9875aedc5b4f40e691ecdccc0e9b3588,

title = "A linear-time algorithm for the trust region subproblem based on hidden convexity",

abstract = "We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov{\textquoteright}s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.",

keywords = "Hidden convexity, Linear time complexity, Proximal gradient algorithm, Trust region subproblem",

author = "Jiulin Wang and Yong Xia",

note = "Publisher Copyright: {\textcopyright} 2016, Springer-Verlag Berlin Heidelberg.",

year = "2017",

month = dec,

day = "1",

doi = "10.1007/s11590-016-1070-0",

language = "英语",

volume = "11",

pages = "1639--1646",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "8",

}

TY - JOUR

T1 - A linear-time algorithm for the trust region subproblem based on hidden convexity

AU - Wang, Jiulin

AU - Xia, Yong

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

AB - We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

KW - Hidden convexity

KW - Linear time complexity

KW - Proximal gradient algorithm

KW - Trust region subproblem

UR - https://www.scopus.com/pages/publications/84982296465

U2 - 10.1007/s11590-016-1070-0

DO - 10.1007/s11590-016-1070-0

M3 - 文章

AN - SCOPUS:84982296465

SN - 1862-4472

VL - 11

SP - 1639

EP - 1646

JO - Optimization Letters

JF - Optimization Letters

IS - 8

ER -

A linear-time algorithm for the trust region subproblem based on hidden convexity

摘要

访问文件

其它文件与链接

指纹

引用此