The Steepest Descent Method for Linear Minimax Problems

Abstract

The multi-dimensional linear minimax problems is of the form: Minimize Max {L 1 (x), L 2 (x), . . . , L k (x)} where x ∈ R n and L i (x), i = 1, 2, . . . , k are linear. The functions become the piecewise-linear functions which are not differentiable at some points. So, the gradients of the functions can not be used as the steepest descent direction. The method developed here consists of a series of two algorithms: The first one is the direction search that computes the steepest descent direction among the subgradients. The second is the line search algorithm which is developed so that the exact solution can be obtained. The method can be used directly to solve the problems in the stated form. Also, many linear programming problems can be transformed to be the linear minimax problems so that the method can be applied. Compared to the simplex algorithm, the method presented is considered the one that takes the lesser number of iterations to reach the optimal point.