关键词: 半定规划, 宽邻域, 可行内点算法, 多项式复杂性

Abstract:

For interior-point algorithms in semidefinte programming,it is well-known that the selection of the center parameter is crucial for proving polynomility and for efficiency,However,for the previous semidefinte programming paper,the center parameter is fixed,so that this increase largely the complexity of the algorithms and reduce the effectiveness of the algorithms.In the paper,we propose an effective feasible interior point algorithm based on wide neighborhood,with a polynomial relationship between the centering parameter and search step size,and thus in each iteration,the center parameter not only changes with step size but also the optimal is found.It is also proven that the complexity and the effectiveness of the algorithm is optimal based on NT direction in the theory.

Key words: semidefinite programming;wide neighborhood;feasible-interior-point algorithm;polynomial algorithm