A Convergence Analysis for a Convex Version of Dikin's Algorithm

Jie Sun

A version of Dikin's algorithm is studied in which a quadratic merit function is minimized at each iteration together with an affine transformation of the variables. It is shown that the sequence generated by the algorithm globally converges to a point at a local linear rate. The result is of theoretical nature in the sense that in order to ensure that the limit point is an epsilon- optimal solution, one may have to restrict the steplength to the order of O(epsilon). The analysis does not depend on the non-degeneracy assumptions.

To appear in Annals of Operations Research.