Minimizar la suma de ratios lineales

Question

¿Hay alguna manera de transformar el siguiente problema de optimización en un problema convexo equivalente?

$ \mathrm{min}_x \, \Large \left\{ \sum\limits_{i=1}^n \frac{\langle x,a_i \rangle}{\langle x,b_i\rangle} \right\} $

con $x \in \mathcal{X}$ y $ \mathcal{X} \subset \mathbb{R}^n$ es un subconjunto convexo de $\mathbb{R}^n$ y $\langle\cdot,\cdot\rangle$ denota el producto escalar estándar en $\mathbb{R}^n$ . Además, $a_i, b_i \in \mathbb{R}^n$ y $b_i > 0 \,\,\, \forall \, i$ (es decir, todos los componentes de los vectores $b_i$ son positivos. Si fuera necesario, el problema podría reformularse de manera que también los vectores $a_i$ sólo tienen componentes positivos).

El conjunto convexo $\mathcal{X}$ se define mediante las desigualdades

$c_1 \leq x \leq c_2, \,\,\,\,\,\, c_1,c_2 >0$

$\sum_{i=1}^n \langle x, A_i\, x \rangle \,\, \leq c_3$

con vectores positivos $c_1$ y $c_2$ y una constante positiva $c_3$ y matrices simétricas, semidefinidas positivas $A_i$ . Además, existen otras restricciones lineales de igualdad de la forma

$f(x) =c_4$ con una función lineal $f$ .

Quiero transformar este problema en un problema de optimización convexo equivalente.

He construido varias posibilidades para transformar este problema en uno convexo para $n=1$ . En este caso también puedo demostrar varias propiedades agradables. Sin embargo, para $n>1$ No he podido transformar este problema en uno convexo. ¿Alguien sabe si esto es posible y, en caso afirmativo, cómo se puede hacer?

¡Muchas gracias!

Answer 1

Los problemas generales del tipo que das son difíciles NP. Sin embargo, las clases estructuradas pueden resolverse. Aquí hay un argumento que muestra la dureza en general:

Consideremos el programa entero (difícil) de encontrar un vector $x \in \mathbb{R}^n$ para satisfacer las siguientes restricciones:
\begin{align} &Ax \leq b \\ &\sum_{i=1}^n x_i = k\\ &x_i \in \{0, 1\} \quad, \forall i \in \{1, ..., n\} \end{align}

Supongamos que el programa entero es factible (por lo que existe una solución entera que satisface las restricciones). Definamos a nuevo (no enteros) del tipo general que planteas, y luego mostrar que podría utilizarse para resolver el problema anterior (difícil). El nuevo problema es:

\begin{align} \mbox{Minimize:} \quad & \sum_{i=1}^n \frac{x_i}{1+x_i} \\ \mbox{Subject to:} \quad & A x\leq b\\ &\sum_{i=1}^n x_i = k \\ &x_i \in [0,1] \quad , \forall i \in \{1, ..., n\} \end{align}

Afirmación: Si el programa entero es factible, entonces el nuevo problema también es factible y su solución satisface las restricciones del programa entero.

Prueba de ello: Sea $y^*$ sea una solución al problema entero. Entonces $y_i^* \in \{0,1\}$ y $\sum_{i=1}^n y_i^*=k$ . Obsérvese que la función $x/(1+x)$ satisface $$ (Fact 1): \quad \frac{x}{1+x} \geq \frac{x}{2} \quad , \forall x \in [0,1], \mbox{with equality iff $ x en {0,1\} $} $$ Por lo tanto, $$ \sum_{i=1}^n \frac{y_i^*}{1+y_i^*} = \sum_{i=1}^n \frac{y_i^*}{2} = k/2 $$ Observe que $y^*$ satisface las restricciones del nuevo problema y alcanza un valor objetivo de $k/2$ . Por lo tanto, el nuevo problema es factible, y su óptimo valor objetivo es menor o igual a $k/2$ .

Ahora dejemos que $x^*$ sea una solución óptima para el nuevo problema. Basta con demostrar $x^*$ es un vector binario. Como el valor objetivo óptimo no es más que $k/2$ tenemos: $$ \sum_{i=1}^n \frac{x_i^*}{1+x_i^*} \leq k/2 $$ Por otro lado: $$ k/2 \geq \sum_{i=1}^n \frac{x_i^*}{1+x_i^*} \overset{(a)}{\geq} \sum_{i=1}^n \frac{x_i^*}{2} \overset{(b)}{=} k/2 $$ donde (a) se cumple por el Hecho 1 y (b) se cumple porque $x^*$ satisface la restricción $\sum_{i=1}^n x_i^*=k$ . De ello se desprende que $$ \sum_{i=1}^n\frac{x_i^*}{1+x_i^*} = \sum_{i=1}^n \frac{x_i^*}{2}$$ Pero para cada $i \in \{1, ..., n\}$ sabemos por el hecho 1 que $$\frac{x_i^*}{2} \geq \frac{x_i^*}{1+x_i^*}$$
Así que la igualdad debe mantenerse en cada término $i$ Es decir, $\frac{x_i^*}{2} = \frac{x_i^*}{1+x_i^*}$ , lo que implica $x_i^* \in \{0,1\}$ por el hecho 1. $\Box$

---

Las "clases estructuradas" de problemas que he mencionado anteriormente son generalizaciones de los problemas fraccionarios lineales en los que los términos del denominador pueden agruparse sobre variables separadas, como \begin{align} \mbox{Minimize:} \quad & \sum_{i=1}^G \frac{g_i(x)}{T_i(x)} \\ \mbox{Subject to:} \quad & \sum_{i=1}^G \frac{h_{i,k}(x)}{T_i(x)} \leq c_k, \quad \forall k \in \{1, ..., K\} \\ \end{align} donde $G$ es el número de grupos, y donde para cada grupo $i \in \{1, ..,G\}$ las funciones $g_i(x)$ y $T_i(x)$ , $h_{i,k}(x)$ son funciones de un conjunto disjunto de componentes del $x$ vectorial. Por ejemplo, el grupo 1 sólo utiliza los componentes $x_1, x_2$ . El Grupo 2 utiliza componentes $x_3, x_4$ y así sucesivamente. He hecho algunos trabajos en escenarios estocásticos más complicados que utilizan esta estructura, por ejemplo el Teorema 1 aquí (que lamentablemente está escrito para un sistema más complicado, se podría escribir una versión simplificada para este problema):

http://ee.usc.edu/stochastic-nets/docs/asynch-markov-v8.pdf