An Efficient Method to Solve the Minimax Problem Directly

Abstract

Over the past few years the circuit and system designers have shown great interest in minimax algorithms. The purpose of this paper is to present a new algorithm to solve the nonlinear minimax problem. The minimax optimization problem can be stated as: \[\mathop {{\text{minimize}}}\limits_x M_f (x)\] where \[M_f (x) = \mathop {\max }\limits_{1 \leqq i \leqq m} f_i (x)\] and $x = [x_1 ,x_2 , \cdots ,x_n ]^T $. The above objective function has discontinuous first partial derivatives at points where two or more of the functions $f_i$ are equal to $M_f$ even if $f_i (x),1 \leqq i \leqq m$ have continuous first partial derivatives. Thus we cannot use directly the well known gradient methods to minimize $M_f (x)$. Unlike the work by Bandler and Charalambous where they tackle the minimax problem as a limiting case of the least pth problem (so as to overcome the difficulty of discontinuous first partial derivatives) our approach is direct. We use two distinct search directions in the algorithm. The first, the horizontal direction, attempts to reduce $M_f (x)$ whilst, at the same time, keeping those functions whose values are close to $M_f (x)$, approximately equal. The second, the vertical direction, amounts to attempting to decrease the error to within which those functions are equal to $M_f (x)$ by means of linearization. A linear search follows after the horizontal direction has been calculated. The linear search incorporates several simple features of the algorithm and numerical results to date suggest the resulting algorithm is very efficient.