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 function f: Rⁿ⇒R¹ on 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 •-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.