Convergence of a cyclic ellipsoid algorithm for systems of linear equalities

A variable metric optimization method for non differentiable functions due to Shor, Yudin and Nemirovskii, and Khacian, is applied to a full rank system of linear equalities, under a cyclic implementation. At each step of the iteration, the variable metric matrix is used to construct an ellipsoid around the current iterate; this ellipsoid contains the solution. The variable metric matrix is updated in such a way that this inclusion property always hold, and that the volume of the ellipsoid shrinks as a geometric progression, whose rate depends only on the dimension of the space.For the problem of linear equalities, with cyclic implementation, it is shown that every axis of the ellipsoid shrinks more or less as a geometric progression (with the same rate for every axis) and thus that the distance between the iterates and the solution converges to zero as a geometric series whose rate depends only on the dimension of the space. The variable metric matrix is shown to build up information about the inverse of the matrix defining the system of equalities.A somewhat different implementation of the method is shown to converge in a number of steps equal at most to the dimension of the space.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada, under Grant A4152 and the S.S.H.R.C. of Canada.