Solving max-separable optimization problems

Karel Zimmermann

Faculty of Mathematics and Physics

Charles University Prague

(Abstract)

Let function f: Rⁿ → R have the form

f(x₁, …, x_n ) = max_{j ÎJ} f_j (x_j ),

where J = {1, …, n} and f_j (x_j ) 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}(a_ij Ù r_ij (x_j)) ³ b_i , iÎI₁

max _{j ÎJ}(a_ij Ù r_ij (x_j)) £ b_i , iÎI₂

where I₁ , I₂ are finite index sets and for all i, j a_ij Î R, r_ij (x_j) 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 ) = max_{j ÎJ} f_j (x_j ) → 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^* || = max_iÎI |b_i – b_i^* | → 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.