Вариант метода штрафов с аппроксимацией надграфиков вспомогательных функций

И.Я. Заботин, К.Е. Казаева
Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF

DOI: 10.26907/2541-7746.2019.2.263-273

Для цитирования: Заботин И.Я., Казаева К.Е. Вариант метода штрафов с аппроксимацией надграфиков вспомогательных функций // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 2. – С. 263–273. – doi: 10.26907/2541-7746.2019.2.263-273.

For citation: Zabotin I.Ya., Kazaeva K.E. A version of the penalty method with approximation of the epigraphs of auxiliary functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 2, pp. 263–273. doi: 10.26907/2541-7746.2019.2.263-273. (In Russian)

Аннотация

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

Литература

1. Васильев Ф.П. Методы оптимизации: в 2 кн. – М.: МЦНМО., 2011. – Кн. 1 – 620 с.
2. Коннов И.В. Нелинейная оптимизация и вариационные неравенства. – Казань: Казан. ун-т, 2013. – 508 с.
3. Поляк Б.Т. Введение в оптимизацию. – М.: Наука., 1983. – 384 с.
4. Булатов В.П. Методы погружения в задачах оптимизации. – Новосибирск: Наука,
1977. – 161 с.
5. Булатов В.П., Хамисов О.В. Метод отсечений в En+1 для решения задач глобальной оптимизации на одном классе функций // Журн. вычисл. матем. и матем. физики. – 2007. – Т. 47, № 11. – С. 1830–1842.
6. Zabotin I.Ya., Yarullin R.S. A cutting-plane method based on epigraph approximation with discarding the cutting planes // Autom. Remote Control. – 2015. – V. 76, No 11. – P. 1966–1975. – doi: 10.1134/S0005117915110065.
7. Zabotin I., Shulgina O., Yarullin R. A minimization algorithm with approximation of an epigraph of the objective function and a constaint set // CEUR Workshop Proc. – 2016. – V. 1623: Discrete Optimization and Operations Research 2016. (DOOR 2016). – P. 321–324.
8. Нурминский Е.А. Метод отделяющих плоскостей с ограниченной памятью для решения задач выпуклой негладкой оптимизации // Вычисл. методы и программирование. – 2006. – Т. 7, № 1. – С. 133–137.
9. Zabotin I., Kazaeva K. Cutting-plane method with embedding of epigraphs of auxiliary functions // Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov). – IEEE, 2017. – P. 1–4. – doi: 10.1109/CNSA.2017.7974033.
10. Zabotin I.Ya., Yarullin R.S. A cutting-plane method without inclusions of approximating sets for conditional minimization // Lobachevskii J. Math. – 2015. – V. 36, No 2. – P. 132–138. – doi: 10.1134/S1995080215020195.
11. Zabotin I.Y., Shul'gina O.N., Yarullin, R.S. A minimization method with approximation of feasible set and epigraph of objective function // Russ. Math. – 2016. – V. 60, No 11. – P. 78–81. – doi: 10.3103/S1066369X16110098.
12. Заботин И.Я., Шульгина О.Н., Яруллин Р.С. Метод отсечений и построение на его основе смешанных алгоритмов минимизации // Учeн. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2014 . Т. 156, кн. 4 – С. 14–24.
13. Заботин И.Я. О некоторых алгоритмах погружений-отсечений для задачи математического программирования // Изв. Иркут. гос. ун-та. Сер. Матем. – 2011. – Т. 4, №. 2. – С. 91–101.

Поступила в редакцию
11.03.19

Заботин Игорь Ярославич, доктор физико-математических наук, профессор кафедры
анализа данных и исследования операций
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: IYaZabotin@mail.ru

Казаева Ксения Евгеньевна, аспирант кафедры анализа данных и исследования операций
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: k.e.kazaeva@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.