Speaker
Азат Богданов
Description
Задача линейного программирования (ЛП)(1) является одной из самых распространенных задач, к которой можно свести очень большой класс проблем. Она имеет эффективный метод решения - Simplex-method, однако асимптотика его решения при некоторых условиях может вырождаться в экспоненциальную, что является неэффективно, однако в среднем она имеет линейную асимптотику, что приемлемо для этой задачи. Также есть решения, основанные на методе внутренней точки, они даже работают быстрее для разреженных задач с большой размерностью. В текущей работе предлагается алгоритм ускорения данного метода, основанный на требовании оптимальности(3) решения, что можно переписать следующим образом.
Primary author
Co-author
Dr
Роланд Хильдебранд
(ведущий научный сотрудник МФТИ)
