A wide neighbourhood primal-dual second-order corrector interior point algorithm for semidefinite optimization

被引：1

作者：

Yang, Chong ^{[1
,2
]}

Duan, Fujian ^{[1
,2
]}

Li, Xiangli ^{[1
,2
]}

机构：

[1] Guilin Univ Elect Technol, Sch Math & Comp Sci, Guilin, Peoples R China

[2] Guilin Univ Elect Technol, Guangxi Coll & Univ Key Lab Data Anal & Computat, Guilin, Guangxi, Peoples R China

来源：

OPTIMIZATION | 2024年 / 73卷 / 03期

基金：

中国国家自然科学基金;

关键词：

Semidefinite optimization; wide neighbourhood; interior-point methods; second-order methods; polynomial complexity;

D O I：

10.1080/02331934.2022.2126283

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we proposed a new primal-dual second-order corrector interior-point algorithm for semidefinite optimization. The algorithm is based on Darvay-Takacs neighbourhood of the central path. In the new algorithm, the search directions are determined by the Darvay-Takacs's direction and a second-order corrector direction in each iteration. The iteration complexity bound is O(root nL) for the Nesterov-Todd scaling direction, which coincides with the best-known complexity results for semidefinite optimization. Finally, numerical experiments show that the proposed algorithm is promising.

引用

页码：875 / 895

页数：21

共 26 条

[1] An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J].

Ai, WB ;

Zhang, SZ .

SIAM JOURNAL ON OPTIMIZATION, 2005, 16 (02) :400-417

[2]

[Anonymous], 1991, THESIS U MINNESOTA M

[3]

Darvay Z., 2003, ADV MODELING OPTIMIZ, V5, P51

[4] A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization [J].

Darvay, Zsolt ;

Kheirfam, Behrouz ;

Rigo, Petra Renata .

OPTIMIZATION LETTERS, 2020, 14 (07) :1747-1763

[5] Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood [J].

Darvay, Zsolt ;

Takacs, Petra Renata .

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2018, 26 (03) :551-563

[6]

de Klerk E, 2002, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications

[7]

[冯增哲 Feng Zengzhe], 2014, [运筹学学报, Operations Research Transaction], V18, P49

[8] A new O(√nL)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming [J].

Feng, Zengzhe ;

Fang, Liang .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2014, 256 :65-76

[9] A wide neighbourhood interior-point method with [image omitted] iteration-complexity bound for semidefinite programming [J].

Feng, Zengzhe ;

Fang, Liang .

OPTIMIZATION, 2010, 59 (08) :1235-1246

[10] A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization [J].

Kheirfam, B. .

OPTIMIZATION, 2019, 68 (12) :2243-2263

← 1 2 3 →