Primal-Dual Interior Point Methods for Semidefinite Programming Based on a New Type of Kernel Functions

被引：8
作者：
Touil, Imene [1 ]
Chikouche, Wided [1 ]
机构：
[1] Mohamed Seddik Ben Yahia Univ, LMPA, Jijel, Algeria
来源：
FILOMAT | 2020年 / 34卷 / 12期
关键词：
Linear semidefinite programming; Primal-dual interior point methods; Hyperbolic-logarithmic kernel function; Complexity analysis; Large- and small-update methods; COMPLEXITY; ALGORITHM;
D O I：
10.2298/FIL2012957T
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we propose the first hyperbolic-logarithmic kernel function for Semidefinite programming problems. By simple analysis tools, several properties of this kernel function are used to compute the total number of iterations. We show that the worst-case iteration complexity of our algorithm for large-update methods improves the obtained iteration bounds based on hyperbolic [24] as well as classic kernel functions. For small-update methods, we derive the best known iteration bound.
引用
收藏
页码：3957 / 3969
页数：13
相关论文
共 26 条
[1]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[2]  
Alizadeh F., 1991, THESIS U MINNESOTA
[3]  
Bai Y.Q., 2002, P IND OPT S OPT DAY
[4]   A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms [J].
Bai, Yan Qin ;
Guo, Jin Li ;
Roos, Cornelis .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2009, 25 (12) :2169-2178
[5]   A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization [J].
Bai, YQ ;
El Ghami, M ;
Roos, C .
SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) :101-128
[6]   A new efficient large-update primal-dual interior-point method based on a finite barrier [J].
Bai, YQ ;
El Ghami, M ;
Roos, C .
SIAM JOURNAL ON OPTIMIZATION, 2003, 13 (03) :766-782
[7]   An Efficient Primal-Dual Interior Point Method for Linear Programming Problems Based on a New Kernel Function with a Trigonometric Barrier Term [J].
Bouafia, Mousaab ;
Benterki, Djamel ;
Yassine, Adnan .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2016, 170 (02) :528-545
[8]   Complexity Analysis of Primal-Dual Interior-Point Methods for Linear Optimization Based on a New Parametric Kernel Function with a Trigonometric Barrier Term [J].
Cai, X. Z. ;
Wang, G. Q. ;
El Ghami, M. ;
Yue, Y. J. .
ABSTRACT AND APPLIED ANALYSIS, 2014,
[9]   On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function [J].
Choi, Bo Kyung ;
Lee, Gue Myung .
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 2009, 71 (12) :E2628-E2640
[10]   Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term [J].
El Ghami, M. ;
Guennoun, Z. A. ;
Bouali, S. ;
Steihaug, T. .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2012, 236 (15) :3613-3623
123