ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» . 2014. Том 10

Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами

Автор(ы)
И. Я. Заботин, Р. С. Яруллин

Аннотация

Для задачи условной минимизации предлагается метод, относящийся к классу методов отсечений, в котором используется аппроксимация надграфика целевой функции. В методах указанного класса на каждом шаге для построения итерационной точки либо область ограничений, либо надграфик целевой функции погружаются в аппроксимирующие их многогранные множества. Каждое погружающее множество строится путем отсечения от предыдущего одной или несколькими плоскостями некоторого подмножества, содержащего текущую итерационную точку. Методы отсечений труднореализуемы на практике, поскольку в них от итерации к итерации растет количество отсекающихплоск остей, которые формируют аппроксимирующие множества. Предлагаемый метод характерен тем, что позволяет периодически применять процедуры обновления аппроксимирующих множеств, заключающиеся в отбрасывании любых построенных в процессе минимизации отсекающих плоскостей. Эти процедуры основаны на введенном в работе критерии оценки качества аппроксимации надграфика целевой функции погружающими множествами. Кроме того, метод допускает его комбинирование с любыми другими известными или новыми релаксационными алгоритмами, предоставляет возможность использования параллельных вычислений при построении итерационныхт очек, а также позволяет в случае сильной выпуклости оценивать близость каждой итерационной точки к оптимальной. Обосновывается сходимость метода. Обсуждаются способы задания управляющих параметров метода.

Ключевые слова
аппроксимирующее множество, отсекающая гиперплоскость, оценки точности решения, последовательность приближений, сходимость, условная минимизация, надграфик

УДК
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.