Complexity analysis of interior-point methods yielding the best known iteration bound for semidefinite optimization
Publish Year: 1402
نوع سند: مقاله ژورنالی
زبان: English
View: 50
This Paper With 15 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJNAA-14-5_027
تاریخ نمایه سازی: 5 شهریور 1402
Abstract:
The purpose of this paper is to obtain new complexity results for solving the semidefinite optimization (SDO) problem. We define a new proximity function for the SDO by a new kernel function with an efficient logarithmic barrier term. Furthermore, we formulate an algorithm for the large and small-update primal-dual interior-point method (IPM) for the SDO. It is shown that the best result of iteration bounds for large-update methods and small-update methods can be achieved, namely \mathcal{O}\left(qn^{\frac{q+۱}{۲q}}\log \frac{n}{\epsilon }\right) \ for large-update and \mathcal{O}(q^{۲}\sqrt{n}\log \frac{n}{\epsilon }) for small-update methods, where q>۱. The analysis in this paper is new and different from the one using for LO. Several new tools and techniques are derived in this paper. Furthermore, numerical tests to investigate the behavior of the algorithm so as to be compared with other approaches.
Keywords:
Authors
Derbal Louiza
LMFN, Fundamental and Numerical Mathematics Laboratory, Department of Mathematics, Faculty of Science, Ferhat Abbas University, Setif, Algeria
Kebbiche Zakia
LMFN, Fundamental and Numerical Mathematics Laboratory, Department of Mathematics, Faculty of Science, Ferhat Abbas University, Setif, Algeria
Bouafia Mousaab
LMAH, FR-CNRS-۳۳۳۵, ISCN, ۷۶۰۰ Le Havre, France, University of ۸ May ۱۹۴۵ Guelma. BP ۴۰۱, ۲۴۰۰۰ Guelma, Algeria