Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами
| Авторы: | И. Я. Заботин, Р. С. Яруллин |
| Аннотация: | Для задачи условной минимизации предлагается метод, относящийся к классу методов отсечений, в котором используется аппроксимация надграфика целевой функции. В методах указанного класса на каждом шаге для построения итерационной точки либо область ограничений, либо надграфик целевой функции погружаются в аппроксимирующие их многогранные множества. Каждое погружающее множество строится путем отсечения от предыдущего одной или несколькими плоскостями некоторого подмножества, содержащего текущую итерационную точку. Методы отсечений труднореализуемы на практике, поскольку в них от итерации к итерации растет количество отсекающихплоск остей, которые формируют аппроксимирующие множества. Предлагаемый метод характерен тем, что позволяет периодически применять процедуры обновления аппроксимирующих множеств, заключающиеся в отбрасывании любых построенных в процессе минимизации отсекающих плоскостей. Эти процедуры основаны на введенном в работе критерии оценки качества аппроксимации надграфика целевой функции погружающими множествами. Кроме того, метод допускает его комбинирование с любыми другими известными или новыми релаксационными алгоритмами, предоставляет возможность использования параллельных вычислений при построении итерационныхт очек, а также позволяет в случае сильной выпуклости оценивать близость каждой итерационной точки к оптимальной. Обосновывается сходимость метода. Обсуждаются способы задания управляющих параметров метода. |
| Ключевые слова: | аппроксимирующее множество, отсекающая гиперплоскость, оценки точности решения, последовательность приближений, сходимость, условная минимизация, надграфик |
| УДК: | 519.853 |
| Литература: |
1. Булатов В. П. Методы погружения в задачах оптимизации / В. П. Булатов. – Новосибирск : Наука, 1977. – 161 с. 2. Булатов В. П. Методы отсечения в En+1 для решения задач глобальной оптимизации на одном классе функции / В. П. Булатов, О. В. Хамисов// Журн. вычисл. математики и мат. физики. – 2007. – Т. 47, № 11. – C. 1830-1842. 3. Васильев Ф. П. Методы оптимизации : в 2 кн. / Ф. П. Васильев. – М. : МЦНМО, 2011. – Кн. 1. – 620 с. 4. Заботин И. Я. О некоторых алгоритмах погружений-отсечений для задачи математического программирования / И. Я. Заботин // Изв. Иркут. гос. ун-та. Сер. Математика. – 2011. – Т. 4, № 2. – С. 91–101. 5. Заботин И. Я. Метод отсечений с обновлением погружающих множеств и оценки точности решения / И. Я. Заботин, Р. С. Яруллин // Учен. зап. Казан. гос. ун-та. Сер. Физ.-мат. науки. – 2013. – Т. 155, кн. 2. – С. 54–64. 6. Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании / А. А. Колоколов // Сиб. журн. исслед. операций. – 1994. – Т. 1, № 2. – С. 18–39. 7. Коннов И. В. Нелинейная оптимизация и вариационные неравенства / И. В. Коннов. – Казань : Казан. ун-т, 2013. – 508 с. 8. Левитин Е. С. Методы минимизации при наличии ограничений / Е. С. Левитин, Б. Т. Поляк // Журн. вычисл. математики и мат. физики. – 1966. – Т. 6, № 5. – C. 787-823. 9. Нестеров Ю. Е. Введение в выпуклую оптимизацию / Ю. Е. Нестеров. – М. : МЦНМО, 2010. – 274 c. 10. Нурминский Е. А. Метод отделяющих плоскостей с ограниченной памятью для решения задач выпуклой негладкой оптимизации / Е. А. Нурминский // Вычисл. методы и программирование. – 2006. – Т. 7. – С. 133–137. 11. Kelley J. E. The cutting-plane method for solving convex programs / J. E. Kelley // SIAMJ. – 1960. – Vol. 8, N 4. – P. 703–712. 12. Lemarechal C. New variants of bundle methods / C. Lemarechal, A. Nemirovskii, Yu. Nesterov // Mathematical Programming. – 1995. – Vol. 69. – P. 111–148. 13. Zabotin I. Ya. One approach to constructing cutting algorithms with dropping of cutting planes / I. Ya. Zabotin, R. S. Yarullin // Russian Math. (Iz. VUZ), Allerton Press Inc. – 2013. – Vol. 57, N 3. – P. 60–64. |