Complexity analysis and numerical implementation of a new interior-point algorithm for semidefinite optimization

被引：0

作者：

Zaoui, Billel ^{[1
]}

Benterki, Djamel ^{[1
]}

Khelladi, Samia ^{[1
]}

机构：

[1] Setif Univ Ferhat Abbas, Fac Sci, Dept Math, Lab Fundamental & Numer Math, Setif 19000, Algeria

来源：

OPERATIONS RESEARCH LETTERS | 2024年 / 57卷

关键词：

Semidefinite optimization; Interior-point method; Descent direction; Primal-dual algorithm; SEARCH DIRECTIONS; CONVERGENCE; PATH;

D O I：

10.1016/j.orl.2024.107192

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We generalize Zhang and Xu's (2011) [22] interior point algorithm for linear optimization to semidefinite optimization problems in order to define a new search direction. The symmetrization of the search direction is based on the full Nesterov-Todd scaling scheme. Moreover, we show that the obtained algorithm solves the studied problem in polynomial time and that the short-step algorithm has the best-known iteration bound, namely O(root nlogn/epsilon)-iterations. Finally, we report a comparative numerical study to show the efficiency of our proposed algorithm.

引用

页数：7

共 23 条

[1] Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J].

Alizadeh, F ;

Haeberly, JPA ;

Overton, ML .

SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) :746-768

[2]

[Anonymous], 2005, J. Math. Modelling Algo.

[3]

Benterki D, 2021, B MATH SOC SCI MATH, V64, P3

[4] New method for determining search directions for interior-point algorithms in linear optimization [J].

Darvay, Zsolt ;

Takacs, Petra-Renata .

OPTIMIZATION LETTERS, 2018, 12 (05) :1099-1116

[5]

De Klerk E., 2004, ASPECTS SEMIDEFINITE

[6]

De Klerk E., 1997, Interior-Point Methods for Semidefinite Programming

[7] A class of new search directions for full-NT step feasible interior point method in semidefinite optimization [J].

Guerra, Loubna .

RAIRO-OPERATIONS RESEARCH, 2022, 56 (06) :3955-3971

[8] On the convergence of the central path in semidefinite optimization [J].

Halická, M ;

de Klerk, E ;

Roos, C .

SIAM JOURNAL ON OPTIMIZATION, 2002, 12 (04) :1090-1099

[9] An interior-point method for semidefinite programming [J].

Helmberg, C ;

Rendl, F ;

Vanderbei, RJ ;

Wolkowicz, H .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :342-361

[10] A New Search Direction for Full-Newton Step Interior-Point Method in -HLCP [J].

Kheirfam, B. .

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION, 2019, 40 (10) :1169-1181

← 1 2 3 →