A feasible primal-dual interior point method for linear semidefinite programming

详细信息    查看全文

• 作者：Imene Touil^a ; ^{i_touil@yahoo.fr" class="auth_mail" title="E-mail the corresponding author} ; Djamel Benterki^b ; Adnan Yassine^c ; ^d ; ^e
• 关键词：90C22 ; 90C51
• 刊名：Journal of Computational and Applied Mathematics
• 出版年：2017
• 出版时间：1 March 2017
• 年：2017
• 卷：312
• 期：Complete
• 页码：216-230
• 全文大小：465 K

文摘

In this paper, we consider a feasible primal–dual interior point method for linear semidefinite programming problem method=retrieve&_eid=1-s2.0-S0377042716302254&_mathId=si1.gif&_user=111111111&_pii=S0377042716302254&_rdoc=1&_issn=03770427&md5=a9d860af925bdb94da8bbd95618e36a9" title="Click to view the MathML source">(SDP)$\left(SDP\right)$ based on Alizadeh–Haeberly–Overton (AHO) direction (Monteiro, 1997). Firstly, and by a new and simple technique, we establish the existence and uniqueness of optimal solution of the perturbed problem method=retrieve&_eid=1-s2.0-S0377042716302254&_mathId=si2.gif&_user=111111111&_pii=S0377042716302254&_rdoc=1&_issn=03770427&md5=63a215222196463013d69bc08131b583" title="Click to view the MathML source">(SDP)_μ${\left(SDP\right)}_{\mu }$ and its convergence to optimal solution of method=retrieve&_eid=1-s2.0-S0377042716302254&_mathId=si1.gif&_user=111111111&_pii=S0377042716302254&_rdoc=1&_issn=03770427&md5=a9d860af925bdb94da8bbd95618e36a9" title="Click to view the MathML source">(SDP)$\left(SDP\right)$. Next, we present new different alternatives to calculate the displacement step. After, we establish the convergence of the obtained algorithm and we show that its complexity is method=retrieve&_eid=1-s2.0-S0377042716302254&_mathId=si4.gif&_user=111111111&_pii=S0377042716302254&_rdoc=1&_issn=03770427&md5=5eb89b208226c49f10c23fc9151a54eb">$\mathcal{O}(\sqrt{n}ln\left[{\epsilon }^{-1}\left(〈X^0,S^0〉\right)\right])$. Finally, we present some numerical simulations which show the effectiveness of the algorithm developed in this work.