Un problema de optimización convexa sobre dos vectores

Question

Tengo un problema en vectores $\mathbf{x} = (x_1,\ldots,x_n)$$\mathbf{y}=(y_1,\ldots,y_n)$, donde cada $x_i,y_i\in\mathbb{R}_{\geq 0}$,

$$\begin{array}{ll} \text{maximize} & \displaystyle\sum_{i=1}^n \left(\frac{y_i}{x_i}\right)^ux_i\\ \text{subject to} & \displaystyle\sum_{i=1}^n x_i = 1\\ & \displaystyle\sum_{i=1}^n y_i = 1\\ & \mathbf{a} \leq \mathbf{x} \leq \mathbf{b}\\ & \mathbf{c} \leq \mathbf{y} \leq \mathbf{d}\end{array}$$

donde $u \in (0,1)$ y no negativo de vectores $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$, $\mathbf{d}$ se dan. Mis preguntas son:

• Existe un algoritmo eficiente para resolver esto?
• ¿Alguna vez has visto el mismo o similar problema de optimización, como el anterior?

Apéndice: Las siguientes condiciones son también conocidas: $$ \sum_{i=1}^n a_i<1,\ \sum_{i=1}^n c_i<1,\quad \mbox{y}\quad \sum_{i=1}^n b_i>1,\ \sum_{i=1}^n d_i>1 $$

Answer 1

El mínimo estricto de las desigualdades de $a<x<b$, $c<y<d$ es más probable que no exista, como la solución óptima sería más probablemente ocurren en la frontera y obtener igualdades para algunos $x_i,y_i$. Es crítico?

De lo contrario, la función objetivo

$$\sum_{i=1}^n x_i^{1-u} y_i^u$$

es cóncava para $u\in(0,1)$ positiva y $x,y$, las restricciones son simples, el número de variables no es demasiado, es un medio-problema de escala, así que yo esperaría que la mayoría de los algoritmos de realizar muy bien aquí, por ejemplo, el primal-dual método de punto interior o incluso Cuasi-Newton/método de Newton.

Otra posibilidad es hacer el doble de descomposición. Si introducimos los multiplicadores de Lagrange para las restricciones de igualdad, el Lagrangiano se convierte en \begin{align} L(x,y,\lambda,\mu)&=\sum_{i=1}^nx_i^{1-u}y_i^u+\lambda\left(\sum_{i=1}^nx_i-1\right)+\mu\left(\sum_{i=1}^ny_i-1\right)=\\ &=\sum_{i=1}^n(x_i^{1-u}y_i^u+\lambda x_i+\mu y_i)-\lambda-\mu, \end{align} por lo tanto, para calcular el doble problema para determinado $\lambda,\mu$ uno tiene que solucionar $n$ independiente escalarproblemas $$ g_i(\lambda\mu)=\max\ x_i^{1-u}y_i^u+\lambda x_i+\mu y_i\quad\text{objeto } a_i\le x_i\le b_i,\ c_i\le y_i\le d_i $$ y a continuación, obtener la solución de la unconstraint doble problema $$ \min_{\lambda\mu}\left(\sum_{i=1}^ng_i(\lambda\mu)-\lambda\mu\right). $$ Si las restricciones de la desigualdad son compatibles con la igualdad, es decir, $$ \sum a_i<1,\ \sum c_i<1,\ \sum b_i>1,\ \sum d_i>1 $$ entonces no hay ninguna dualidad de la brecha, y la principal solución puede ser construido a partir de la doble solución.