Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Требуется найти точку
такую, что
. Предполагается, что функции
и
удовлетворяют условию Липшица на отрезке
.
Обозначим
, тогда для
выполняются следующие неравенства:
![{\displaystyle |g_{j}(x+\Delta x)-g_{j}(x)|\leqslant L_{j}\Delta x,\;a\leqslant x+\Delta x\leqslant b,}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/0e073e3620b81bdfe45189675a4418ca9bd7bb23)
где
— константы Липшица.
Пусть
. Ограничение, имеющее номер
, выполняется во всех точках области
, которая называется допустимой для этого ограничения. При этом допустимая область
исходной задачи определяется равенством:
![{\displaystyle Q=\bigcap _{j=0}^{m}Q_{j}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/6979deda0e68d2cb1ca2cd49592f0baaffb20131)
Испытание в точке
состоит в последовательном вычислении значений величин
, где значение индекса
определяется условиями:
![{\displaystyle x\in Q_{j},\;0\leqslant j<\nu ,\;x\notin Q_{\nu }.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/b9493396e12304ae1202bdfadc83374873a131b2)
Выявление первого нарушенного ограничения прерывает испытание в точке
. В случае, когда точка
допустима, то есть
испытание включает в себя вычисление всех функций задачи. При этом значение индекса принимается равным величине
.
Пара
, где индекс
лежит в границах
, называется результатом испытания в точке
.
Такой подход к проведению испытаний позволяет свести исходную задачу с функциональными ограничениями к безусловной задаче минимизации разрывной функции:
![{\displaystyle \psi (x^{*})=\min _{x\in [a;\;b]}\psi (x),}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/97b1387e506bf4ae02c57a4cab1eb0cd1b5ff1b2)
![{\displaystyle \psi (x)={\begin{cases}g_{\nu }(x)/L_{\nu }&\nu <M,\\(g_{M}(x)-g_{M}^{*})/L_{M}&\nu =M.\end{cases}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/e63a6857ad41b348ffaeb8ea93a17466434dcece)
Здесь
, а
.
В силу определения числа
, задача отыскания
всегда имеет решение, а если
, то
.
Дуги функции
липшицевы на множествах
с константой 1, а сама
может иметь разрывы первого рода на границах этих множеств.
Несмотря на то, что значения констант Липшица и величина
заранее неизвестны, они могут быть оценены в процессе решения задачи.
Пусть
. Индексы концевых точек считаются нулевыми, а значения
в них не определены. Первое испытание осуществляется в точке
. Выбор точки
любого последующего испытания определяется следующими правилами:
- Перенумеровать точки
предшествующих испытаний нижними индексами в порядке увеличения значений координаты:
и сопоставить им значения
.
- Для каждого целого числа
определить соответствующее ему множество
нижних индексов точек, в которых вычислялись значения функций
:
![{\displaystyle I_{\nu }=\{i\colon \nu (x_{i})=\nu ,\;1\leqslant i\leqslant k\},\;1\leqslant \nu \leqslant m+1.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/734b66d25b5d1aba53360aeb2ce9e1fce676c48b)
- Также определить максимальное значение индекса
![{\displaystyle M=\max\{\nu (x_{i}),\;1\leqslant i\leqslant k\}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/e16f57de9de2013a9e94ab6b041ae93613006275)
- Вычислить текущие оценки для неизвестных констант Липшица:
![{\displaystyle \mu _{\nu }=\max\{|g_{\nu }(x_{i})-g_{\nu }(x_{j})|/(x_{i}-x_{j})\colon i,\;j\in I_{\nu },\;i>j\}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/6a1265661b9549e76072ffbd70ddfd993616a9a4)
- Если множество
содержит менее двух элементов или если значение
оказывается равным нулю, то принять
.
- Для всех непустых множеств
вычислить оценки
![{\displaystyle z_{\nu }^{*}={\begin{cases}\min\{g_{\nu }(x_{i})\colon x_{i}\in I_{\nu }\}&\nu =M,\\-\varepsilon _{\nu }&\nu <M,\end{cases}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/ad67c3bbdd1b75cf572b4492ac00163b3fdd7402)
- где вектор с неотрицательными координатами
называется вектором резервов.
- Для каждого интервала
вычислить характеристику
![{\displaystyle R(i)={\begin{cases}\Delta _{i}+{\frac {(z_{i}-z_{i-1})^{2}}{(r_{\nu }\mu _{\nu })^{2}\Delta _{i}}}-2{\frac {z_{i}+z_{i-1}-2z_{\nu }^{*}}{r_{\nu }\mu _{\nu }}}&\nu =\nu (x_{i})=\nu (x_{i-1}),\\2\Delta _{i}-4{\frac {z_{i-1}-z_{\nu }^{*}}{r_{\nu }\mu _{\nu }}}&\nu =\nu (x_{i-1})>\nu (x_{i}),\\2\Delta _{i}-4{\frac {z_{i}-z_{\nu }^{*}}{r_{\nu }\mu _{\nu }}}&\nu =\nu (x_{i})>\nu (x_{i-1}),\end{cases}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/cafd480afba777b222d34904bedcf172f48efb62)
- где
.
- Величины
являются параметрами алгоритма. От них зависят произведения
, используемые при вычислении характеристик в качестве оценок неизвестных констант Липшица.
- Определить интервал
, которому соответствует максимальная характеристика
.
- Провести очередное испытание в середине интервала
, если индексы его концевых точек не совпадают:
![{\displaystyle x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1}).}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/12bdeb18d2334de1e716a1720f4d9010a08064ae)
- В противном случае провести испытание в точке
![{\displaystyle x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1})-{\frac {z_{t}-z_{t-1}}{2r_{\nu }\mu _{\nu }}},\;\nu =\nu (x_{t})=\nu (x_{t-1}),}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/c7111449ca5b09f34eb3e5c864dc75fb4cd1809a)
- увеличить
на 1.
- Если
(
— заданная точность метода), то прекратить выполнение алгоритма, иначе перейти на шаг 1.
Пусть исходная задача оптимизации имеет решение
и выполняются следующие условия:
- каждая область
представляет собой объединение конечного числа отрезков, имеющих положительную длину;
- каждая функция
удовлетворяет условию Липшица с соответствующей константой
;
- компоненты вектора резервов удовлетворяют неравенствам
, где
— длина отрезка
, лежащего в допустимой области
и содержащего точку
;
- начиная с некоторого значения
величины
, соответствующие непустым множествам
, удовлетворяют неравенствам
.
Тогда верно следующее:
- точка
является предельной точкой последовательности
, порождаемой методом при
в условии остановки;
- любая предельная точка
последовательности
является решением исходной задачи оптимизации;
- сходимость к предельной точке
является двухсторонней, если
.
Общая схема последовательного метода выглядит следующим образом:
- Упорядочить точки предшествующих испытаний в порядке возрастания их координат:
.
- Вычислить для каждого интервала
характеристику
.
- Определить интервал
, которому соответствует максимальная характеристика
.
- Провести следующее испытание в точке
, где
— правило размещения точки следующего испытания в интервале с номером
.
- Проверить выполнение критерия остановки
.
Параллельная модификация заключается в том, что на шаге 3 вместо одного интервала с наилучшей характеристикой выбирать
интервалов в порядке убывания характеристик и параллельно проводить в каждом из них испытания.
Схема параллельного алгоритма:
- Упорядочить точки предшествующих испытаний в порядке возрастания их координат:
.
- Вычислить для каждого интервала
характеристику
.
- Характеристики интервалов упорядочить по убыванию:
.
- Для всех интервалов с номерами
провести испытания в точках
.
- Проверить выполнение критерия остановки:
.
Такая схема распараллеливания целесообразна, если проведение испытания (то есть вычисление функций задачи) — трудоемкий процесс.
Метод достаточно просто обобщается на случай, когда функции
удовлетворяют условию Гёльдера с показателем
, где
, то есть
.
На шаге 3 значения
вычисляются по формуле:
![{\displaystyle \mu _{\nu }=\max\{|g_{\nu }(x_{i})-g_{\nu }(x_{j})|/(x_{i}-x_{j})^{1/n}\colon i,\;j\in I_{\nu },\;i>j\}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/7e6ce003baf840f1d2dbad2223bdad4f6a0970d9)
На шаге 5
.
На шаге 7 в случае совпадения индексов концевых точек
![{\displaystyle x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1})-\operatorname {sgn}(z_{t}-z_{t-1}){\frac {|z_{t}-z_{t-1}|^{n}}{2r_{\nu }\mu _{\nu }^{n}}},\;\nu =\nu (x_{t})=\nu (x_{t-1}).}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/81ac7c95e60f45ed9c4ae980a8648739e09c310d)
На шаге 8 критерий остановки принимает вид
.
- Параметры
отвечают за надежность метода. Чем больше их значения, тем больше итераций метода требуется для достижения заданной точности и тем вероятнее выполнение условия сходимости 4. Если устремить все
к бесконечности, то
, то есть метод превращается в перебор по равномерной сетке.
- Использование ненулевого вектора резервов позволяет ускорить сходимость метода, однако при этом необходимо оценить возможность выполнения условия сходимости 3.
- Одномерный метод может быть применен для решения многомерных задач без ограничений. Многомерная задача на множестве
представляется в виде
![{\displaystyle \min _{(x_{1},\;\ldots ,\;x_{n})\in S}f(x_{1},\;\ldots ,\;x_{n})=\min _{a_{1}\leqslant x_{1}\leqslant b_{1}}\min _{a_{2}\leqslant x_{2}\leqslant b_{2}}\ldots \min _{a_{n}\leqslant x_{n}\leqslant b_{n}}f(x_{1},\;\ldots ,\;x_{n}).}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/487d18543cc03d3a9bfc229e1031239d8db598f3)
Для решения задачи
, где
можно использовать одномерный алгоритм, но, чтобы вычислить значение функции
, необходимо решить задачу оптимизации размерности
.
Если
, то задача
решается одномерным методом (значение переменной
при этом зафиксировано), иначе к ней также применяется процедура снижения размерности. Такой способ решения многомерных задач довольно трудоемкий, поэтому на практике применим при
. Наличие нелинейных функциональных ограничений может привести к потере липшицевости во вспомогательных одномерных задачах.
- Баркалов К. А., СтронгинР. Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. — 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.
- [1] - реализация метода на языке C++.
- [2] - реализация на языке C++ модификации метода метода для решения многокритериальных многомерных задач.