Solving max-separable optimization problems
Karel Zimmermann
Faculty of Mathematics and Physics
Charles University Prague
(Abstract)
Let function f: Rn → R have the form
f(x1, …, xn ) = maxj ÎJ fj (xj ),
where J = {1, …, n} and fj (xj ) are continuous
functions of one variable for all jÎJ.
Function f will be called max-separable. We will study properties of the
following special system of inequalities with max-spearable functions:
max j ÎJ(aij Ù rij
(xj)) ³ bi , iÎI1
max j ÎJ(aij Ù rij
(xj)) £ bi , iÎI2
where I1 , I2 are finite index sets and for all i, j aij
Î R, rij (xj) are
continuous and strictly increasing functions. Motivation for the investigation
of such systems as well as relations to the (max,plus)- and (max,min)-linear
systems will be shortly discussed.
Let M(b) denote the
set of all solutions of the max-separable inequality system above. Using the
properties of the set M(b) we will propose an explicit formula for the optimal
solution of the optimization problem
f(x ) = maxj ÎJ fj (xj
) → min
subject to x Î M(b).
If for some b* the
set M(b*) is empty the problem is called
improperly (or incorrectly) posed.
We propose a
parametric method for solving the problem
||b – b* || = maxiÎI |bi – bi*
| → min subject to M(b) ≠ Æ,
i.e. we find the
nearest right hand side to b* , for which the max-separable system is solvable.
Some modifications and generalizations of the problems as well as further
possible subjects of research in the area will be briefly discussed.