РАЗРАБОТКА КОМПЬЮТЕРНОЙ ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ МНОГОМЕРНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ МЕТОДОМ ЦИКЛИЧЕСКОГО ПОКООРДИНАТНОГО ПОИСКА ГАУССА-ЗЕЙДЕЛЯ

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

Рассматривая локальный  и глобальный  экстремумы функции можно отметить их особенности. Функция  имеет локальный минимум в точке , если существует окрестность такая, что  больше  во всех точках этой окрестности. В случае глобального минимума в точке  для всех  справедливо неравенство .

Рассмотрим математические основы на примере метода циклического покоординатного поиска Гаусса-Зейделя [1].

Метод Гаусса-Зейделя является итерационным методом решения систем линейных алгебраических уравнений (СЛАУ) и относится к классу методов последовательных приближений. Он основан на идее использования уже вычисленных значений переменных для улучшения следующих приближений, что делает его более эффективным по сравнению с другими итерационными методами, такими как метод простой итерации.

Метод Гаусса-Зейделя или циклического покоординатного поиска заключается в том, что на итерациях по каждой переменой определяется минимум целевой функции вдоль направления координатных осей. Поиск по направлениям, совпадающим с координатными осями, можно проводить любым известным методом одномерной оптимизации, например, методом золотого сечения или обратного переменного шага. Таким образом, задача сводится к многократному использованию метода одномерной оптимизации. Очередность варьирования переменных обычно устанавливается произвольно и в процессе поиска не меняется. Точность поиска проверяется по сравнению значений переменных или функции на (k + 1) и (k) итерациях [2].

Алгоритм численной реализации следующий. Начальный этап. Выбрать начальную точку , и e > 0 - точность поиска. Пусть  - единичные координатные направления. Положить  и перейти к основному этапу.

Основной этап. Шаг 1. Любым методом одномерной оптимизации найти  - оптимальное решение задачи минимизации функции  и положить . Если , то заменить  на  и вернуться к шагу 1. Если , то перейти к шагу 2.

Шаг 2. Положить . Если , то остановиться; в противном случае положить , заменить  на , положить  и перейти к шагу 1.

Реализация алгоритма была выполнена в бесплатной облачной платформе для создания и выполнения кода Python. Пользователю доступен ввод стартовой точки и точности поиска с клавиатуры.

Для контрольного примера выберем функцию , для которой необходимо найти минимум с точностью  и начальной точкой .

После ввода начальной точки и точности оптимизации, а также – выполнения алгоритма расчёта, пользователь может ознакомиться с найденным решением в кратком и подробном форматах (Рисунок 1 - Рисунок 2).

Можно заметить, что на 3-ей итерации решение уже найдено, но алгоритм считает финальной итерацией 4-ую при одинаковом решении x1 и х2. Это можно отнести к особенностям условия выхода из цикла, которое сверяет разность новой и предыдущей точек с заданной точностью.

Рисунок 1. Краткий ответ, найденный в процессе решения при заданных входных параметрах

Рисунок 2. Таблица поитерационных расчётов

Для того чтобы понять эффективность работы метода оптимизации, было проведено исследование на тестовых задачах.

Первым этапом тестировалась работоспособность и эффективность алгоритма при фиксированных начальных условиях, но для полиномов целевой функции во 2, 4, 6 и 8 степенях. В процессе исследования выяснялось, что из-за особенностей целевой функции, количество итераций не будет зависеть от различных чётных степеней полинома целевой функции, что и подтвердилось на практике.

Вторым этапом было проведено исследование зависимости количества итераций от заданной начальной точки и точности поиска. Ход исследования приведен ниже (Таблица 1, Рисунок 3).

Таблица 1

Исследование зависимости количества итераций от заданной начальной точки

Рисунок 3. Зависимость количества итераций от заданной точности поиска

В результате исследования было выявлено, что метод Гаусса-Зейделя может быть чувствителен к выбору начальной точки, а также – не всегда находит глобальный минимум, если на пути метода встретится точка локального минимума. Что же касается исследования работоспособности от сложности полинома целевой функции, то из-за особенностей этой функции, глобальный минимум всегда находится в единственной точке, которую алгоритм определяет за 4 итерации независимо от степени функции.

Таким образом, была изучена теоретическая основа метода оптимизации циклического покоординатного поиска Гаусса-Зейделя, и был разработан алгоритм численной реализации. Над этим алгоритмом было проведено исследование, которое установило, что метод оптимизации имеет свои ограничения, особенно в контексте нахождения глобального минимума при наличии локальных минимумов. Тем не менее, разработанный алгоритм продемонстрировал свою работоспособность и эффективность в решении задач различной сложности. Полученные результаты могут быть полезны для дальнейших исследований в области численных методов оптимизации и их применения в различных областях науки и техники.

Список литературы:

1. Методы оптимизации: теория и алгоритмы: учебное пособие для вузов / А. А. Черняк, С. А. Богданович, Ж. А. Черняк, Ю. М. Метель-ский. – 2-е изд., испр. и доп. – Москва : Издательство Юрайт, 2019. – 357 с. – ISBN 978- 5-534-04103-3. – URL: https://urait.ru/bcode/453567 (дата обращения: 07.12.2023).
2. Летова, Т. А. Методы оптимизации. Практический курс : учебное по- собие / Т. А. Летова, А. В. Пантелеев. – Москва : Логос, 2011. – 424 с. – URL: http://biblioclub.ru/index.php?page=book&id=84995 03.02.2023).