УДК 519.85
П.І. СТЕЦЮК
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
stetsyukp@gmail.com
А. ФІШЕР
Технічний університет Дрездена, Інститут обчислювальної математики,
Дрезден, Німеччина, Andreas.Fischer@tu-dresden.de
О.М. ХОМ’ЯК
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
khomiak.olha@gmail.com
УНІФІКОВАНЕ ПРЕДСТАВЛЕННЯ КЛАСИЧНОГО
МЕТОДУ ЕЛІПСОЇДІВ
Анотація. Розглянуто параметричну версію методу еліпсоїдів з масштабуванням простору
за скалярним параметром λ > 0.
Для певних значень параметра λ вона зводиться
до відомих варіантів методу еліпсоїдів Шора, Хачіяна, Немировського та Юдіна.
Обґрунтовано властивості двох алгоритмічних реалізацій параметризованого методу еліпсоїдів.
Перший алгоритм базується на оновленні несиметричної матриці B, а другий оновлює
симетричну матрицю H = BBT.
Описано застосування алгоритмів для розв’язання задач опуклого програмування та для знаходження сідлової точки опукло-увігнутої функції.
Ключові слова: метод еліпсоїдів, розтягнення простору, опукле програмування, сідлова точка.
повний текст
СПИСОК ЛІТЕРАТУРИ
- Глушков В.М. Основы безбумажной информатики. Изд. 2-е. Москва: Наука, 1987. 552 с.
- Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач. Экономика и математические методы. 1976. Вып. 2. С. 357–369.
- Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика. 1977. № 1. С. 94–95.
- Шор Н.З., Билецкий В.И. Метод растяжения пространства для ускорения сходимости в задачах овражного типа. Труды семинара Науч. совета АН УССР по кибернетике «Теория оптимальных решений». Киев. 1969. № 2. С. 3–18.
- Шор Н.З. Использование операции растяжения пространства в задачах минимизации выпуклых функций. Кибернетика. 1970. № 1. С. 6–12.
- Stetsyuk P.I., Fischer A., Khomiak O.M. Ellipsoid methods with space scaling. Proc. of the 8th International Conference on Control and Optimization with Industrial Applications (COIA 2022) (24–26 Aug., 2022, Baku, Azerbaijan). 2022. Р. 402–404.
- Nemirovsky A.S, Yudin D.B. Problem complexity and method efficiency in optimization. New York: John Wiley, 1983.
- Khachiyan L.G. Polynomial algorithms in linear programming, USSR Comput. Math. Math. Phys. 1980. Vol. 20, N 1. Р 53–72.
- Fischer A., Khomyak O., Stetsyuk P. The ellipsoid method and computational aspects. Commun. Optim. Theory. 2023. Vol. 21. P. 1–14.
- Скоков В.А. Замечание к методам минимизации, использующим операцию растяжения пространства. Кибернетика. 1974. № 4. C. 115–117.
- Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук. думка, 1979. 200 с.
- Grtschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimization. Berlin: Springer-Verlag, 1988. 362 p.
- Шор Н.З. Новые направления в развитии методов негладкой оптимизации. Кибернетика. 1977. № 6. С. 87–91.
- Семенов В.В. Варіаційні нерівності: теорія та алгоритми. Київ: ВПЦ «Київський університет», 2021. 167 с.
- Shor N.Z. Nondifferentiable optimization and polynomial problems. Amsterdam: Kluwer, 1998.
- Стецюк П.И., Фесюк А.В., Хомяк О.Н. Обобщенный метод эллипсоидов. Кибернетика и системный анализ. 2018. Т. 54, № 4. С. 70–80.
- Stetsyuk P., Fischer A., Khomyak O. The generalized ellipsoid method and Its implementation. In: Jacimovic M., Khachay M., Malkova V., Posypkin M. (Еds.). Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science. Cham: Springer, 2020. Vol. 1145. P. 355–370.
