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

Материал из Wiki - Факультет компьютерных наук
Версия от 14:59, 15 октября 2018; Aapoludnitsin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Компания ИППИ РАН
Учебный семестр Осень 2018
Учебный курс 3-4-й курс
Максимальное количество студентов, выбравших проект: ?



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