An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
复制标题
DOI：
10.1287/moor.15.3.408
复制
发表时间：
1990-08
期刊：
影响因子：
--
通讯作者：
R. Monteiro;I. Adler
中科院分区：
文献类型：
--
作者：
R. Monteiro;I. Adler
对一类线性约束凸可分规划问题给出了一个原始-对偶内点算法。每次迭代更新一个惩罚参数，并找到一个牛顿步骤与卡鲁什-库恩-塔克方程组，其特征的对数障碍函数问题的解决方案，该参数。它表明，对偶间隙减少在每次迭代的1-I ′/ε n的一个因素，其中I ′是积极的，并依赖于一些参数与目标函数。
We describe a primal-dual interior point algorithm for a class of convex separable programming problems subject to linear constraints. Each iteration updates a penalty parameter and finds a Newton step associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap is reduced at each iteration by a factor of 1-I´/ân, where I´ is positive and depends on some parameters associated with the objective function.