Browse Prior Art Database

A NEW MINMAX ALGORITHM Disclosure Number: IPCOM000149122D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-13
Document File: 40 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Vardi, Avi: AUTHOR [+2]


Avi a r d i

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 40


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 page contains 1 picture or other non-text object]

Page 2 of 40

[This page contains 1 picture or other non-text object]

Page 3 of 40


This paper deals with the minimax problem min max fi(x) x E @ i=l,.**,m

where f ,
1 l
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,

+s+,m. For

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...