一个求解半正定规划问题的新原始-对偶内点算法

A New Primal-dual Interior-point Algorithm for Semidefinite Optimization

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(n^(1/2)log n log n/∈)和O(n^(1/2)log n/∈),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性.

The barrier function plays an important role in designing and analyzing primal-dual interior-point methods. In this paper we present a primal-dual interior-point algorithm based on a barrier function determined by the kernel function for semidefinite optimization problems. The barrier determined by kernel function is not only to define the search direction for the algorithm, but also to measures the distance between the iterations and the central path. We compute the iteration bounds and derive the iteration bounds：O（√n log n log n/c） for large- and O（√n log n/ε） for small-update methods, respectively, where n is the dimension of the problem considered. The numerical example shows that the algorithm is efficient and is related with the parameter in kernel function.