A NEW MINMAX ALGORITHM
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-13
Software Patent Institute
Vardi, Avi: AUTHOR [+2]
Avi a r d i
A NEW MINMAX ALGORITHM
Avi ~ a r d i *
RAFAEL, Armament Development Authority Haif a, Israel
The paper deals with the minimax problem inin max f i(x). We work x E IF? i=l,***,m
with its equivalent representation min t s.t. fi(x) - t -
< 0 for all i.
For this problem we design a new active set strategy in which there are three types of functions: active, semi-active, and non-active. This technique w i l l help in preventing zigzagging which often occurs when an active set strategy is used. Some of the inequality constraints are handled with slack variables.
Also a trust regLon strategy is used in which at each iteration there is a sphere around the current point in which the local approximation of the function is trusted. The algorithm suggested in the paper was implemented into a successful computer program. Numerical results are provided.
* This research was supported by the ~ational Aeronautics and Space Administration under NASA Contract No. NAS1-1.5810 while the author was in residence at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, VA 23665.
This paper deals with the minimax problem min max fi(x) x E @ i=l,.**,m
where f ,
are real valued functions defined on 3. We begin by
transforming the problem into an equivalent inequality constrained minimization problem min t set. fi (x) - t 4; 0 for all i, i=l,
this problem we suggest a new active set strategy in which there are three types of functions: nonactive, semi-active and active and these sets play a different role in our algorithm. The active ones are treated as equality constraints; the semi-active ones are assigned slack variables so that they can be treated as equalities too. The introduction of semi-active functions may help prevent the possibility of zigzagging that sometimes occurs i n algorithms that use active set strategy.
A t the end we solve an equality consl:rained minimization problem for which we design a trust region algorithm that takes into advantage the special structure of the problem. In this algorithm we have at every iteration a sphere of radius r, in which the local model that is used to approximate the functions is trusted.
Section 2 contains the basic model with all the necessary notation as well as the introduction of the new active set strategy. In Section 3 we give a description of the trust region strategy in unconstrained minimization and in constrained minimization. We suggest the use of the trust region for the minimax problem in Section 4. In Section 5 we discuss our numerical implementation of the algorithm and in Section 6 we give the numerical results of six problems taken from the literatu...