A PRACTICAL ALGORITHM FOR MINIMIZING A RANK-TWO SADDLE FUNCTION ON A POLYTOPE

This paper addresses a practical method for minimizing a class of saddle functions f: R "-+ R1 on a polytope. Function f is.continuous and possesses a rank-two property, i.e., the value of f is defined only by two linearly independent vectors. It is shown that a parametric right-hand-side simplex algorithm decomposes the problem into a finite sequence of one-dimensional subproblems. A globally c-optimal solution of each subproblem is obtained by using a successive underestimation method. Computational results indicate that the algorithm can solve fairly large scale problems efficiently