PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 18 February 2004

Solving problems on minmax optimization

Miguel A. Sainz, Pau Herrero and Josep Vehi
Institut d'Informatica i Aplicacions
University of Girona
Spain

In control systems or in the decision making situations described by antagonists games, uncertain controls or perturbations are often represented by parameters which conflict among them because the represented actions can be mutually compensate. When all the inputs and outputs are determined, the solution of the problem is equivalent to a find general solution and some kind of solution-sets arise.

To characterize the solution-sets is very related to some problems of minimax in operations research because they are linked by means of semantic statements based in first order logic formulae, with existential and universal quantifiers placed in any order For this reason, both problems are suscetible to be treated with techniques of Modal Interval Analysis. In the paper, minmax problems will be discussed using tools based on modal intervals, via certain interval extensions of the real continuous functions and their semantic meanings.

Classical Interval Analysis considers two interval extensions for a continuous function f to an interval multi-dimensional X: the united extension $Rf(X)$, which is the range of $f$ in $X$, and the natural extension $fR(X)$, which is done by substituting real numbers with intervals and real operations with their interval extensions. Both are related by means of the important property named the monotonic inclusion: $Rf(X)$ is a subset of $fR(X)$.

In Modal Interval Analysis, starting from the most simple interval extension function, which gives, for any point a of the domain where it is defined, an upper and a lower bounds to the analytically defined value $f(a)$, more general interval extensions are built: the ``modal interval extensions'' $f*$ and $f**$, defined in terms of the interval lattice operators 'meet' and 'join'. Two key results, named the semantic theorems, provide logical interpreattion to these semantic extensions, make equivalent the verification of a logical formula to an interval inclusion, provide rules to decide how to performe the necessary roundings and bound the solutions of those minmax problems where all min operators are before or after all max operators by means $f*(X)$ and $f**(X)$.

The main relation between both semantic extensions is the inclusion of $f*(X)$ in $f**(X)$. When $f*(X) = f**(X)$, $f$ is said `` JM-commutable'' . Important examples of JM-commutable functions are the one-variable continuous functions and every two-variable continuous function $f(x,y)$ which is partially monotonic in a domain $(X,Y)$, like the arithmetic operators $x+y$, $x-y$, $x*y$, $x/y$ and others like $x^y$, $\max(x,y)$ and $\min(x,y)$, whose modal semantic extensions can be computed by means of arithmetic operations with the interval bounds.

For any general function, to evaluate $f*(X)$ or $f**(X)$ is out of direct computations' reach, but. when the continuous function $f$ is a rational function, there exist a modal rational extensions which are obtained by using the computing program defined by the syntax tree of the expression of the function in which the real arguments are transformed into interval arguments and the real operators are transformed into their $*-$ or $**$-semantic extensions. If all the operators of the syntax tree are JM-commutable, there exists only one rational extension: fR(X) called 'modal rational extension'.

In the general theory of modal intervals, very important inclusion relations among the modal rational extension $fR$ and the semantic extensions are proved and they lead to compute the semantic extensions and, consequently, to solve minmax problems.

The definitions of $f*$ and $f**$ can be generalized considering any order in the lattice operators meet and join and a new class of semantic extensions, named fs functions, can be stablished.

Semantic extensions $f*(X)$, $f**(X)$ and $fs(X)$ are, in general, different since min and max operators are not commutable, but always $fs(X)$ is include in $f**(X)$ and includes $f*(X)$. If $f$ is a JM-commutable function on $X$, i.e., $f*(X) = f**(X)$, all the s-semantic extensions are equal $f*(X) = fs(X) = f**(X)$. Moreover if the rational extension $fR(X)$ is an optimal computation, i.e., $f*(X) = fR(X) = f**(X)$, then $fR(X)$ is also an optimal computation for any $fs(X)$ and any minmax problem, where operators min and max are in any order, can be solved. In this case, all the results obtained in the Modal Interval Analysis about optimality are applicable to find the interval result of any $fs(X)$, solving at the same time a minmax problem. If $fR(X)$ is not an optimal computation an branch-and-bound has been developed to find outer and inner estimates of $f*(X)$ and, consequently, $f**(X)$ or also any $fs(X)$ as closed as possible.

If $f$ is not a JM-commutable function on $X$, then $f*(X)$ is strictly included in $f**(X)$ and between both are all the rest of $fs(X)$, so $f*(X)$ and $f**(X)$ are only bounds for the general minmax problem.

Several examples illustrate this methodology.

Home page