SOLUTION OF PROJECTION PROBLEMS OVER POLYTOPES

In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytopes. By using the special structure of the projection problems, an iterative algorithm with constant step-size is given. which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimum norm problems over transportation or general network polytopes only O(n) additions and O(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems.