1
$\begingroup$

I encountered the following real-life optimization problem:

Minimize $\max(e,f)$

Given the equations:

$$a = c + d$$ $$b = Ac + d$$ $$E + f = b$$ $$e + a = F$$

Given the complex inequalities: $$e+d \geq Bc + C$$ $$c \leq D$$

And given the simple non-negativeness inequalities:

$$a \geq 0 \ \ \textrm{(this follows from others trivially)}$$ $$b \geq 0 \ \ \textrm{(this follows from others, as A is nonnegative)}$$ $$c \geq 0$$ $$d \geq 0$$ $$e \geq 0$$ $$f \geq 0$$

Where $a$, $b$, $c$, $d$, $e$ and $f$ are free variables and $0<A<1$, $B \geq 0$, $C \geq 0$, $D \geq 0$, $E$ and $F \geq 0$ are constants.

I'm starting to understand how to create a computer program to optimize this kind of problem: the optimum should be at some inequality boundary. So I test various points where the optimum could be and calculate $\max(e,f)$ at those points after verifying the inequalities in a manner that accepts floating-point inaccuracies.

The problem is very similar to linear programming, but with the difference is that there are two variables that are co-optimized, and both of them need to be optimized at the same time given the nonlinear "max" operator.

I'm thinking that this problem, in its basic form is not linear programming, however. The reasoning is that the "max" operator is non-linear.

Is there some kind of mathematical term for this kind of optimization problem? Is the optimization problem well-known, i.e. could I find some theory related to it somewhere? Any kind of proof that my solution approach is the correct one, or any kind of analysis that could help minimizing the code line count and maximizing the solution performance could help.

Could the problem somehow be reduced to linear programming?

$\endgroup$

1 Answer 1

3
$\begingroup$

To minimize a maximum, you can linearize as follows. Introduce variable $z$, linear constraints $z \ge e$ and $z \ge f$, and now the objective is to minimize $z$.

Maximizing a minimum is similar: just reverse the inequalities and change the sense of the objective.

$\endgroup$
1
  • $\begingroup$ Thanks! I just realized this at the same time and was going to post an answer but you did it first! $\endgroup$
    – juhist
    Apr 8, 2020 at 19:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .