Solução de desvios mínimos absolutos usando o algoritmo Barrodale-Roberts: terminação prematura?

Por favor, desculpe a pergunta demorada, ela só precisa de explicações para chegar ao problema real. Aqueles familiarizados com os algoritmos mencionados provavelmente poderiam pular diretamente para o primeiro tablau simplex.

---

Para resolver problemas de desvio mínimo absoluto (também conhecido como otimização ), o algoritmo Barrodale-Roberts é um método simplex de propósito especial que requer muito menos armazenamento e esforços computacionais para encontrar um mínimo adequado.$L_1$

Minha implementação do algoritmo termina em um exemplo simples antes que um mínimo adequado seja alcançado. No entanto, provavelmente deixe-me declarar o problema de uma maneira mais elaborada primeiro:

Dado dados , L 1 -optimization tentativas para encontrar c ∈ m que minimiza n Σ i = 1 | y i - f ( x i ) $(x_i,y_i)$$L_1$$c\in m$ onde A x é um n ×

$$\sum_{i=1}^n |y_i-f(x_i)| \quad\text{with}\quad f(x):=A_x\cdot \phi$$ $A_x$$n\times m$ matriz que depende de alguma forma em $x$ . Esse problema pode ser declarado como um programa linear e, portanto, entre outros, ser resolvido usando métodos do tipo simplex.

Barrodale e Roberts sugeriram uma modificação (aparentemente amplamente usada) do método simplex que simplifica radicalmente o método simplex usando a estrutura especial de $L_1$$\mathop{rank}(A)$

Lei e Anderson, em 2002, propuseram uma pequena modificação que deveria aumentar a estabilidade numérica e, portanto, superar problemas conhecidos com o algoritmo simplex.

Basicamente, esse algoritmo pressupõe que você comece com um determinado conjunto de pontos que precisam ser interpolados, use os procedimentos fornecidos para criar um quadro simplex e use as regras de Barrodale e Roberts para decidir em quais variáveis ​​básicas serão alteradas e, portanto, modificar o conjunto de pontos de dados aproximados.

$\{(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}$$

Mais importante ainda, o primeiro e o terceiro ponto são interpolados e o erro geral é igual a $2$. Eles concluem que

Como todos os vetores não básicos têm custo marginal não positivo [...]

a iteração está concluída e o melhor é alcançado.

Se eu usar o algoritmo de Lei e Anderson, posso reproduzir esse quadro simplex para o conjunto de interpolação {1,3}, conforme o esperado. No entanto, se eu iniciar o algoritmo com o conjunto$\{2, 5\}$ (which clearly is not optimal), I get the following simplex tableau:

$$\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}$$

This result is puzzling me, though. If I understand the quote above correctly, having no positive marginal cost indicates that the optimum is reached. The function value of about 2.33 certainly is not optimal, though. Exchanging $u_2$ with $u_1$ would yield a result that is on par with the solution of Barrodale and Roberts and therefore optimal.

Additional info: If I start with the initial tableau given by Barrodale and Roberts, I am also able to reproduce the tableau above by ordinary simplex steps, thus I am fairly confident that the actual numerical values are correct and my interpretation of the pivot selection rule is faulty.

Any thoughts on this?

I realize that the question itself is quite complicated and probably requires knowledge of at least the Barrodale and Roberts algorithm to be answered sufficiently. The algorithm as a whole is to long to repeat it here in full detail. However, if you have additional questions on steps I took or on missing bits of information, feel free to ask and I will gladly augment the question.

Solved it. Actually, Barrodale and Roberts solved it and I just did not read carefully.

In my question I left it to the reader to understand that the variables Barrodale and Roberts labeled $u_i$ stand for the positive residuals the $i$-th datapoint in relation to the current fit. If the residual is negative, $u_i=0$ and $v_i$ takes the corresponding value. As only one of them may be within the basis and the coefficients in the simplex tableau are just the negatives of each other, it is not necessary to explicitly state them in the simplex tableau. Barrodale and Roberts mention in their article:

[...] and that the sum of the marginal (or reduced) costs of $b_j$ and $c_j$ is zero and of $u_i$ and $v_i$ is -2.

Thus, my simplex tableau above has to be thought to look as follows:

$$\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}$$

where we clearly see that $v_2$ can be brought into the basis to archive a better result. Doing this the algorithm terminates while interpolating the first and fifth datapoint with an overall error of 2 - which is the best solution.

Thanks for reading and giving me some place to write my problem down, which usually helps to narrow the solution down significantly. Hopefully, this answer might sometimes be helpful for anybody else trying to implement Barrodale & Roberts.