Метод отделяющих плоскостей с дополнительными отсечениями и его применение в задачах анализа данных с неопределенностями

(По материалам кандидатской диссертации; Научный руководитель – д.ф.-м.н. Нурминский Е.А.)

Семинар: Информационно-вычислительные технологии
Начало заседания: 16:00

Дата выступления: 3 Ноябрь 2015

Организация: Дальневосточный федеральный университет (Владивосток)

Авторы: Воронцова Евгения Алексеевна

Для решения задач недифференцируемой выпуклой оптимизации в работе предлагается новый численный метод из семейства методов отделяющих плоскостей (МОП) [1]. В отличие от ранее предложенных алгоритмов на основе идеи МОП, в новом методе вводятся дополнительные отсечения верхней части надграфика сопряженной функции, что улучшает сходимость метода. Получено теоретическое обоснование сходимости метода; проведены вычислительные эксперименты, демонстрирующие преимущество разработанного метода перед уже существующими аналогами. К особенностям метода относится необходимость решать на каждой итерации вспомогательную задачу одномерной минимизации оригинальной оценочной негладкой функции. Для решения этой задачи в работе предложен быстросходящийся алгоритм одномерного поиска, для него доказана как минимум более быстрая, чем линейная, скорость сходимости. Все предложенные в работе вычислительные алгоритмы реализованы в виде комплекса программ на языке программирования octave, свободно распространяемом матрично-векторном вычислителе с синтаксисом, практически идентичным MATLAB. Один из алгоритмов зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.
         Кроме новых алгоритмов недифференцируемой оптимизации, в работе рассматривается интервальная модель межотраслевого экономического баланса. Для этой модели, следуя работе [2], исследуется линейная задача о допусках (ЛЗД). Используя перспективный метод распознающего функционала С.П. Шарого [3], проблему определения разрешимости ЛЗД можно свести к задаче негладкой выпуклой оптимизации, для решения которой применяются разработанные в диссертации алгоритмы. Вычислительные эксперименты продемонстрировали высокую эффективность предложенного в работе МОП с отсечениями для решения задачи определения разрешимости ЛЗД.
         Реализованный комплекс программ применен для практического решения задач прогнозирования потребности в выпусках продукции при моделировании межотраслевого баланса Приморского края, в ходе чего он зарекомендовал себя как надежный и эффективный инструмент моделирования. Проведены также сравнительные вычислительные эксперименты по решению этой задачи с помощью известных онлайн-солверов, доступных на NEOS Server: State-of-the-Art Solvers for Numerical Optimization, в том числе IBM ILOG CPLEX. Все эксперименты показали преимущество предложенных в работе методов.

[1] Nurminski E.A. Separating plane algorithms for convex optimization // Math. Program. 1997. Vol. 76. P. 373-391
[2] Rohn J. Input-output model with interval data // Econometrica. 1980. V. 48. P. 767-769
[3] Shary S.P. Solving the linear interval tolerance problem // Mathematics and Computers in Simulation. 1995. Vol. 39. P. 53-85