Просмотр кода страницы Оценка константы Хоффмана для систем линейных неравенств численными параллельными методами линейной алгебры и глобальной оптимизации

{{Карточка_командного_проекта
|name=Оценка константы Хоффмана для систем линейных неравенств численными параллельными методами линейной алгебры и глобальной оптимизации
|company=Яндекс
|semester=Осень 2018
|course=3-4
|number_of_students=?
|categorize=yes
}}

В теории и вычислительных методах оптимизации важное значение имеет результат т. н. «теорема» (или «лемма») Алана Хоффмана, доказанная им в 1952 г. Установлено, что для любого множества решений конечной системы линейных неравенств, существует т. н. «константа Хоффмана», зависящая только от коэффициентов неравенств при переменных (а не от правых частей), дающая оценку расстояния до множества решений по легко вычисляемой характеристике нарушения указанных линейных неравенств. Несмотря на относительно несложный способ доказательства существования константы Хоффмана, вычисление ее значения (или - верхней оценки) является нетривиальной задачей. Известные схемы вычислений носят переборный характер. Одна схема — это построение всех крайних точек некоторого многогранного множества. Другая — основана на решении задачи глобальной максимизации выпуклой квадратичной функции на  множестве решений системы линейных или квадратичных неравенств. В работе нужно будет сравнить различные способы вычисления (оценки) константы Хоффмана для больших систем линейных неравенств. Можно применять пакеты языка Python SciPy, Pyomo; пакет анализа систем линейных неравенств (с возможностью работать в режиме параллельных вычислений), http://cgm.cs.mcgill.ca/~avis/C/lrslib/; решатель задач глобальной оптимизации SCIP, http://scip.zib.de/ и его параллельную реализацию ParaSCIP, http://ug.zib.de/.