Encontrar la envolvente convexa de la función no convexa para demostrar que es globalmente óptima utilizando branch-and-bound

Question

En base a esto referencia Los métodos de branch-and-bound pueden obtener soluciones globalmente óptimas a problemas de programación no lineal en los que hay que minimizar una función no convexa. Tengo una función no convexa como la siguiente:

$$\min_{\mathbf{x}} F(\mathbf{x}) = \min_{\mathbf{x}} \sum_{i=1}^I \bigg( x_i + (1 - x_i) \Big[\big(\prod_{j=1}^J1-x_j\big)c\Big]\bigg),$$

donde $c$ es constante y $\mathbf{x}$ es un vector de variables binarias. Quiero demostrar que esta función puede alcanzar la solución óptima global utilizando branch-and-bound. Para ello, necesito encontrar la envolvente convexa de la función $F^c(\mathbf{x})$ . Si puedo encontrar eso

$F^c(\mathbf{x^*}) = F(\mathbf{x^*})$ ,

donde $\mathbf{x}^*$ es la solución óptima, por lo que la función puede alcanzar la solución globalmente óptima. Sin embargo, no entiendo cómo obtener la envolvente convexa de mi función. ¿Hay alguna manera de demostrar que la envolvente convexa de mi función tiene el mismo resultado que mi función no convexa anterior cuando se aplica el algoritmo de branch-and-bound?

Answer 1

Como seguimiento a los comentarios donde sostengo que una forma sencilla de resolver el problema es escribirlo como un MILP en su lugar.

Introducir una nueva variable de decisión binaria $q$ representando a $\prod_{j=1}^J(1-x_j)$ . Esto puede lograrse con las restricciones $q\leq 1-x_j, q\geq \sum_{j=1}^J(1-x_j)-J+1$ .

Introducir otro conjunto de variables binarias $s_i$ representando a $(1-x_i)q$ . Esto se puede modelar con las restricciones $s_i \leq q, s_i \leq 1-x_i, s_i \geq q + (1-x_i)-1$ .

Su objetivo es ahora $\sum_{i=1}^I x_i + cs_i$ que debe ser minimizado sujeto a las restricciones lineales anteriores.