Interior path following primal-dual algorithms

摘要: We describe a primal-dual interior point algorithm for linear programming and convex quadratic problems which requires total of O(n$\sp3$L) arithmetic operations. Each iteration updates penalty parameter finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system equations characterizes solution logarithm barrier function problem. The is based on path following idea. show that duality gap reduced at each by factor (1 $-$ $\delta$/$\sqrt{n}$) where 0.1 $\leq$ $\delta$ $<$ 1. As consequence, optimal our problem can be found in most O($\sqrt{n}$L) iterations. We also how extended to solve class separable subject constraints. In this case, it shown $\delta$/$\sqrt{n}$), positive depends some parameters objective function.