Abstract: In this paper, we present a primal-dual interior point algorithm for a class of convex programming problem with linear and box constrains. The algorithm can be started at any primal-dual feasible interior point and admits the global convergence. When the initial point is close to the central path, it becomes a central path-following algorithm. Numerical experiments show the proposed algorithm is effective for the large scale problems.

Key words: convex programming, interior point algorithm, primal-dual, path-following

摘要： 本文对一类具有线性和框式约束的凸规划问题给出了一个原始-对偶内点算法, 该算法可在任一原始-对偶可行内点启动, 并且全局收敛,当初始点靠近中心路径时, 算法成为中心路径跟踪算法。 数值实验表明, 算法对求解大型的这类问题是有效的。

关键词: 凸规划, 内点算法, 原始-对偶, 路径跟踪