Симплекс-метод vs метод Дикина

[alex_user]

Добрый день!

При реализации симплекс метода, узнал, что есть пример Кли Минти, на котором он работает долго (обходит весь куб Кли Минти), а также, что есть метод Дикина, который работает за полиномиальное время. Но о методе было упомянуто на лекции и вскользь, а гугл ничего не дает кроме статьи и книжки самого Дикина. И то и другое - в закрытом доступе.

Из того, что успел услышать:

в методе есть какой-то вспомогательный шаг - решается вспомогательная задача:

$\min(c,x), x \in R^n$
$Ax=b, b \in R^m, m<n$
$(x-x^k)^{T} \cdot D_k \cdot (x-x^k) = 1, D_k=\operatorname{diag} {1/(x_1^k)^2, 1/(x_2^k)^2,...} $
$x^{k+1} = \operatorname{argmin} {(c,x)}$

Слышал, что якобы эта задача решается в явном виде. Это и есть метод Дикина?
Если да, то в чем тут суть и как можно решить эту задачу в явном виде?

P.S. Если есть какие-то ссылки, статьи или книги в свободном доступе на эту тему, скиньте пожалуйста

[мат-ламер]

Можно погуглить по словам "метод внутренней точки". Метод Дикина только первый в этом направлении.

[alex_user]

гуглил - но именно этого метода с такой матрицей (да вообще с эллипсом) - не могу найти