7
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Oct 17 at 2:55
  • $\begingroup$ 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. $\endgroup$
    – Solver Max
    Oct 17 at 3:21
  • $\begingroup$ Can you elaborate more on what constraints you consider in general? They are essential for answering this question. $\endgroup$ Oct 17 at 11:32
  • $\begingroup$ This is DeMorgan's Theorem plus some additional weighting. $\endgroup$
    – Ben Voigt
    Oct 19 at 17:56
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Solver Max
    Oct 18 at 8:09
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Solver Max
    Oct 17 at 18:49
  • $\begingroup$ 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. $\endgroup$ Oct 17 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.