Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 1 сентября 2017 года; проверки требуют 3 правки.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 1 сентября 2017 года; проверки требуют 3 правки.
Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Пусть . Ограничение, имеющее номер , выполняется во всех точках области , которая называется допустимой для этого ограничения. При этом допустимая область исходной задачи определяется равенством:
Испытание в точке состоит в последовательном вычислении значений величин , где значение индекса определяется условиями:
Выявление первого нарушенного ограничения прерывает испытание в точке . В случае, когда точка допустима, то есть испытание включает в себя вычисление всех функций задачи. При этом значение индекса принимается равным величине .
Пара , где индекс лежит в границах , называется результатом испытания в точке .
Такой подход к проведению испытаний позволяет свести исходную задачу с функциональными ограничениями к безусловной задаче минимизации разрывной функции:
Здесь , а .
В силу определения числа , задача отыскания всегда имеет решение, а если , то .
Дуги функции липшицевы на множествах с константой 1, а сама может иметь разрывы первого рода на границах этих множеств.
Несмотря на то, что значения констант Липшица и величина заранее неизвестны, они могут быть оценены в процессе решения задачи.
Пусть . Индексы концевых точек считаются нулевыми, а значения в них не определены. Первое испытание осуществляется в точке . Выбор точки любого последующего испытания определяется следующими правилами:
Перенумеровать точки предшествующих испытаний нижними индексами в порядке увеличения значений координаты: и сопоставить им значения .
Для каждого целого числа определить соответствующее ему множество нижних индексов точек, в которых вычислялись значения функций :
Также определить максимальное значение индекса
Вычислить текущие оценки для неизвестных констант Липшица:
Если множество содержит менее двух элементов или если значение оказывается равным нулю, то принять .
Для всех непустых множеств вычислить оценки
где вектор с неотрицательными координатами называется вектором резервов.
Для каждого интервала вычислить характеристику
где .
Величины являются параметрами алгоритма. От них зависят произведения , используемые при вычислении характеристик в качестве оценок неизвестных констант Липшица.
Определить интервал , которому соответствует максимальная характеристика .
Провести очередное испытание в середине интервала , если индексы его концевых точек не совпадают:
В противном случае провести испытание в точке
увеличить на 1.
Если ( — заданная точность метода), то прекратить выполнение алгоритма, иначе перейти на шаг 1.
Общая схема последовательного метода выглядит следующим образом:
Упорядочить точки предшествующих испытаний в порядке возрастания их координат: .
Вычислить для каждого интервала характеристику .
Определить интервал , которому соответствует максимальная характеристика .
Провести следующее испытание в точке , где — правило размещения точки следующего испытания в интервале с номером .
Проверить выполнение критерия остановки .
Параллельная модификация заключается в том, что на шаге 3 вместо одного интервала с наилучшей характеристикой выбирать интервалов в порядке убывания характеристик и параллельно проводить в каждом из них испытания.
Схема параллельного алгоритма:
Упорядочить точки предшествующих испытаний в порядке возрастания их координат: .
Вычислить для каждого интервала характеристику .
Характеристики интервалов упорядочить по убыванию: .
Для всех интервалов с номерами провести испытания в точках .
Проверить выполнение критерия остановки: .
Такая схема распараллеливания целесообразна, если проведение испытания (то есть вычисление функций задачи) — трудоемкий процесс.
Модификация для решения задач c гёльдеровыми функциями
Параметры отвечают за надежность метода. Чем больше их значения, тем больше итераций метода требуется для достижения заданной точности и тем вероятнее выполнение условия сходимости 4. Если устремить все к бесконечности, то , то есть метод превращается в перебор по равномерной сетке.
Использование ненулевого вектора резервов позволяет ускорить сходимость метода, однако при этом необходимо оценить возможность выполнения условия сходимости 3.
Одномерный метод может быть применен для решения многомерных задач без ограничений. Многомерная задача на множестве представляется в виде
Для решения задачи , где можно использовать одномерный алгоритм, но, чтобы вычислить значение функции , необходимо решить задачу оптимизации размерности .
Если , то задача решается одномерным методом (значение переменной при этом зафиксировано), иначе к ней также применяется процедура снижения размерности. Такой способ решения многомерных задач довольно трудоемкий, поэтому на практике применим при . Наличие нелинейных функциональных ограничений может привести к потере липшицевости во вспомогательных одномерных задачах.
Баркалов К. А., СтронгинР. Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. — 2002. — Т. 42. — № 9. — стр. 1338—1350.
Городецкий С. Ю., Гришагин В. А. Нелинейное программирование и многоэкстремальная оптимизация. — Нижний Новгород: Издательство Нижегородского Университета, 2007.
Стронгин Р. Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). — М.: Наука, 1978. — 240 с.
Sergeyev Ya. D., Grishagin V. A. Sequential and parallel algorithms for global optimization // Optimization Methods and Software, 3:1-3, 1994, pp. 111—124.
Маркин Д. Л., Стронгин Р. Г. Метод решения многоэкстремальных задач с невыпуклыми ограничениями, использующий априорную информацию об оценках оптимума // Ж. вычисл. матем. и матем. физ., 27:1 (1987), стр. 56—62.