7

I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$

The objective function represents the combined probability of success for a series of independent stochastic trials.

I assert that this is equivalent to the linear objective function $$\min \sum_{i=1}^{n}a_{i}x_{i}$$ where

  • $a_{i}$ are constant weights (failure rate) in the range $(0,1]$ (the assertion breaks down if any $a_{i}=0$);

  • $x_{i}$ are binary variables.

The assertion is true for the small set of cases that I've tested. That is, the optimal set of $x_{i}$ variables is the same for both forms of the objective function.

But is the assertion true in general? Why / why not?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Solver Max
  • 315
  • 2
  • 6
  • 1
    If you have no constraints, it is trivially true: the unique optimal solution for both is $x_i=0$ for all $i$. Otherwise, whether it is true depends on your constraints. – RobPratt Oct 17 '21 at 02:55
  • A minimal set of constraints is that $\sum_{i}x_{i}= [-1,0, or +1]$ for various selections of $i$. These constraints are a type of node flow balance in a network. – Solver Max Oct 17 '21 at 03:21
  • Can you elaborate more on what constraints you consider in general? They are essential for answering this question. – worldsmithhelper Oct 17 '21 at 11:32
  • This is DeMorgan's Theorem plus some additional weighting. – Ben Voigt Oct 19 '21 at 17:56

2 Answers2

6

No it's not true in general.

Consider $n=4$ with $a=(0.3,0.7,0.5,0.5)$ under the constraint $(x_1 \wedge x_2) \text{xor}(x_3\wedge x_4)$ which can be expressed in terms of MILP by introducing helper binary variables. For the linear term, $(1,1,0,0)$ and $(0,0,1,1)$ are equally good optima while for the product term they obviously differ in quality, meaning solving the MILP can produce a sub-optimal result.

worldsmithhelper
  • 4,007
  • 6
  • 21
  • Thanks. I'm not surprised that the equivalence is not true in general. But I am surprised that it appears to be true in my network flow model. – Solver Max Oct 17 '21 at 18:49
  • One thing you might want to look into is disciplined convex programming. If you can reformulate using cones ( exponential cone and turning the product in a sum of logarithms) you might that the non integer part of your problems is convex. Network flow is also a problem problem in P which might together might explain the niceties you see. – worldsmithhelper Oct 17 '21 at 18:58
6

It is not true in general, but you can make it work with

$$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$

Since $\log$ is monotonic, your objective is equivalent to $$\max\log\left(\prod_{i=1}^{n}(1-a_{i}x_{i})\right)$$ which becomes $$\max\sum_{i=1}^{n}\log(1-a_{i}x_{i})$$ and finally, since $x_i$ is binary and $\log(1) = 0$ $$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$

I guess that your $a_i$ are quite small, in which case $\log(1 + a_i) \approx a_i$, and the objective you tried is a good approximation.

Ggouvine
  • 1,877
  • 7
  • 13
  • Thanks, that's very helpful. I had considered a log transformation, but I didn't recognize that the objective function can be rearranged to be linear in the special case where the variables are binary. – Solver Max Oct 18 '21 at 08:09