Ayudar a comprender la equivalencia de dos problemas de optimización

Question

El problema es la parte de un círculo. No entiendo por qué son equivalentes. En su notación, dos vectores ${\bf x} \ge {\bf y}$ significa que de cada componente de $\bf x$ es mayor o igual a la componente correspondiente del vector de $\bf y$.

Mi intento y más explicación (puede contener errores):

Por mi entendimiento, $\bf x$ aquí deben ser tratados como fijo. La primera es la optimización variación ${\bf a}_i$, y la segunda es la optimización variación ${\bf p}_i$.

Creo que los dos optimizaciones son equivalentes en el sentido de que $\max_{{\bf a}_i} {\bf a}_i^T{\bf x} =\min_{{\bf p}_i} {\bf p}^T_i{\bf d}_i$.

Es fácil ver ${\bf D}_i{\bf a}_i \le {\bf d}_i$ es equivalente a ${\bf p}_i^T{\bf D}_i{\bf a}_i \le {\bf p}_i^T{\bf d}_i, \forall {\bf p}_i \ge {\bf 0}$. Ahora bien, si existe ${\bf p}_i$ s.t. ${\bf p}_i^T{\bf D}_i = {\bf x}^T$, luego tenemos

$${{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{p}_i}^T}{{\bf{D}}_i} = {\bf{x}}_i^T$$

Por lo tanto el valor máximo de ${{\bf{x}}^T}{{\bf{a}}_i}$ es en la mayoría de las $\inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{p}}_i^T}{{\bf{d}}_i} = {\bf{x}}_i^T\} $. Aquí viene la pregunta: Primero,

La equivalencia en el círculo de la parte de la captura de pantalla que significa

$$\max \{ {{\bf{x}}^T}{{\bf{a}}_i}:{\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}}\} = \inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T\} $$

pero sólo puedo llegar a "$\le$" más bien tahn $=$, de la discusión anterior. $$\max \{ {{\bf{x}}^T}{{\bf{a}}_i}:{\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}}\} \leqslant \inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T\} $$

Yo no soy capaz de ver la totalidad de equivalencia.

En segundo lugar,

¿Qué sucede si no existe ${\bf p}_i$ s.t. ${\bf p}_i^T{\bf D}_i = {\bf x}^T$?

---

Papel: https://faculty.fuqua.duke.edu/~dbbrown/bio/papers/bertsimas_brown_caramanis_11.pdf

Answer 1

Estoy muy seguro de que este ejemplo 4.2.1 es exactamente lo que pides.

Esto es del libro "convexa de la teoría de la optimización", escrito por el autor de la ponencia que en el vínculo de la pregunta.

Answer 2

Me voy a dar una comprensión básica de la dualidad - más información se puede encontrar en un problema de programación lineal de texto, generalmente de un curso tomado en un nivel introductorio por sophomore, junior y matemáticas/ingeniería industrial/gestión de la ciencia a los estudiantes, o incluso como un primer curso de postgrado.

Considere el problema de programación lineal

\begin{align*} \max \ & c^T x \\ \text{subject to } & Ax \leq b \\ & x \geq 0 \end{align*}

donde $A$ $m \times n$ matriz y $c$ es un vector en $\mathbb{R}^n$ definición de costos. Para escribir el doble, consideramos que la variable dual de $u \in \mathbb{R}^m$. El doble es la siguiente:

\begin{align*} \min \ & b^T u \\ \text{subject to } & A^T u \geq c \\ & u \geq 0 \end{align*}

Lo que ha cambiado? Este problema de maximización se convirtió en un problema de minimización, el coeficiente de la matriz de $A$ ha sido sustituido por el de su transpuesta, y los vectores $b$ $c$ intercambiado posiciones. Aviso que este es el "estándar" de la forma - de las desigualdades en el tipo de $ w \leq z$ corresponden a un problema de maximización y $w \geq z $ un problema de minimización. Asegúrese de que las restricciones partido de este formulario antes de escribir el doble de lo contrario, utilice el hecho de que $ w \leq z \implies -w \geq -z$.

Para manejar las restricciones de igualdad, también uso ese $w = z \implies w \leq z \ \wedge \ w \geq z$.