2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Симплекс-метод vs метод Дикина
Сообщение18.11.2012, 13:51 
Добрый день!

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

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

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

$\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. Если есть какие-то ссылки, статьи или книги в свободном доступе на эту тему, скиньте пожалуйста

 
 
 
 Re: Симплекс-метод vs метод Дикина
Сообщение18.11.2012, 15:42 
Аватара пользователя
Можно погуглить по словам "метод внутренней точки". Метод Дикина только первый в этом направлении.

 
 
 
 Re: Симплекс-метод vs метод Дикина
Сообщение18.11.2012, 15:49 
гуглил - но именно этого метода с такой матрицей (да вообще с эллипсом) - не могу найти

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group