Menos desviaciones absolutas resolviendo utilizando el algoritmo de Barrodale-Roberts: ¿Terminación prematura?

Disculpe la pregunta larga, solo necesita alguna explicación para llegar al problema real. Aquellos familiarizados con los algoritmos mencionados probablemente podrían saltar directamente al primer tablau simplex.

---

Para resolver menos problemas desviación absoluta (también conocido como $L_1$ -Optimización), el Barrodale-Roberts-algoritmo es método un propósito especial simplex que las necesidades de menos almacenamiento y esfuerzos computacionales para encontrar un mínimo adecuado.

Mi implementación del algoritmo termina en un ejemplo simple antes de alcanzar un mínimo apropiado. Sin embargo, probablemente permítanme decir primero el problema de una manera más elaborada:

Dada la información $(x_i,y_i)$ , la optimización de $L_1$ intenta encontrar $c\in m$ que minimiza

$$\sum_{i=1}^n |y_i-f(x_i)| \quad\text{with}\quad f(x):=A_x\cdot \phi$$ donde$A_x$ es unamatriz$n\times m$ que depende de alguna manera de$x$ . Este problema puede expresarse como un programa lineal y, por lo tanto, entre otros, puede resolverse utilizando métodos simples.

Barrodale y Roberts sugirieron una modificación (aparentemente ampliamente utilizado) del método simplex que simplifica radicalmente el método simplex utilizando la estructura especial de -Problemas. En particular, esto es que una solución óptima interpola al menos r a n k ( A ) de los puntos de datos dados. Aquellos con acceso a Jstor pueden encontrar el artículo correspondiente aquí .$L_1$$\mathop{rank}(A)$

Lei y Anderson en 2002 propusieron una pequeña modificación que se supone que aumenta la estabilidad numérica y, por lo tanto, supera los problemas conocidos con el algoritmo simplex.

Básicamente, este algoritmo asume que usted comienza con un conjunto dado de puntos que tienen que ser interpolados, usa los procedimientos dados para construir un cuadro simplex y luego usa las reglas de Barrodale y Roberts para decidir sobre qué variables cambiar y, por lo tanto, modificar el conjunto de puntos de datos que se aproxima.

Barrodale y Roberts dan un pequeño ejemplo que intenté reproducir. Intenta aproximar los puntos por una función a 1 + a 2 x . Terminan su algoritmo con el siguiente cuadro simple condensado:$\{(1,1), (2,1), (3,2), (4,3), (5,2)\}$$a_1+a_2x$

$$\begin{array}{l|l|ll} \hline \text{Basis}&R& u_1 & u_3\\ \hline b_1 & 1/2 & 3/2 & -1/2 \\ v_2 & 1/2 & 1/2 & 1/2 \\ b_2 & 1/2 & -1/2 & 1/2 \\ u_4 & 1/2 & 1/2 & -3/2 \\ v_5 & 1 & -1 & 2 \\ \hline \text{Marginal cost} &2 & -1 & 0\\ \hline \end{array}$$

Lo más importante es que el primer y el tercer punto están interpolados y el error general es igual a . Concluyen que$2$

Dado que todos los vectores no básicos tienen un costo marginal no positivo [...]

la iteración ha finalizado y se alcanza el óptimo.

Si uso el algoritmo de Lei y Anderson, puedo reproducir ese cuadro simplex para el conjunto de interpolación {1,3}, como se espera. Sin embargo, si comienzo el algoritmo con el conjunto (que claramente no es óptimo), obtengo el siguiente cuadro simplex:$\{2, 5\}$

$$\begin{array}{l|l|ll} \hline \text{Basis}&R& u_2 & u_5\\ \hline u_1 & 1/3 & -4/3 & 1/3 \\ b_1 & 1/3 & 5/3 & -2/3 \\ u_3 & 2/3 & -2/3 & -1/3 \\ u_4 & 4/3 & -1/3 & -2/3 \\ b_2 & 1/3 & -1/3 & 1/3 \\ \hline \text{Marginal cost} &7/3 & -10/3 & -5/3\\ \hline \end{array}$$

$u_2$$u_1$

Información adicional: si comienzo con el cuadro inicial proporcionado por Barrodale y Roberts, también puedo reproducir el cuadro anterior mediante pasos simples simples, por lo tanto, estoy bastante seguro de que los valores numéricos reales son correctos y mi interpretación de la regla de selección de pivote es defectuoso.

Tiene alguna idea sobre esto?

Me doy cuenta de que la pregunta en sí misma es bastante complicada y probablemente requiere el conocimiento de al menos el algoritmo de Barrodale y Roberts para ser respondida suficientemente. El algoritmo en su conjunto es demasiado largo para repetirlo aquí con todo detalle. Sin embargo, si tiene preguntas adicionales sobre los pasos que tomé o sobre partes faltantes de información, no dude en preguntar y con gusto agrandaré la pregunta.

Resuelto. En realidad, Barrodale y Roberts lo resolvieron y simplemente no leí con cuidado.

$u_i$$i$$u_i=0$$v_i$

$b_j$$c_j$$u_i$$v_i$

Por lo tanto, mi cuadro simplex anterior debe pensarse de la siguiente manera:

$$\begin{array}{l|l|ll| ll} \hline \text{Basis}&R& u_2 & u_5 & v_2 & v_5\\ \hline u_1 & 1/3 & -4/3 & 1/3 & 4/3 & -1/3 \\ b_1 & 1/3 & 5/3 & -2/3 & -5/3 & 2/3 \\ u_3 & 2/3 & -2/3 & -1/3 & 2/3 & 1/3 \\ u_4 & 4/3 & -1/3 & -2/3 & 1/3 & 2/3 \\ b_2 & 1/3 & -1/3 & 1/3 & -1/3 & -1/3 \\ \hline \text{Marginal cost} &7/3 & -10/3 & -5/3 & 4/3 & -1/3\\ \hline \end{array}$$

$v_2$

Gracias por leer y darme un lugar para escribir mi problema, lo que generalmente ayuda a reducir significativamente la solución. Con suerte, esta respuesta a veces podría ser útil para cualquier otra persona que intente implementar Barrodale & Roberts.