Метод Стронгина (Bymk; Vmjkuinug)

Перейти к навигации Перейти к поиску

Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.

Постановка задачи оптимизации

[править | править код]

Требуется найти точку такую, что . Предполагается, что функции и удовлетворяют условию Липшица на отрезке .

Обозначим , тогда для выполняются следующие неравенства:

где  — константы Липшица.

Описание схемы учета ограничений

[править | править код]

Пусть . Ограничение, имеющее номер , выполняется во всех точках области , которая называется допустимой для этого ограничения. При этом допустимая область исходной задачи определяется равенством:

Испытание в точке состоит в последовательном вычислении значений величин , где значение индекса определяется условиями:

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

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

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

Здесь , а .

В силу определения числа , задача отыскания всегда имеет решение, а если , то .

Дуги функции липшицевы на множествах с константой 1, а сама может иметь разрывы первого рода на границах этих множеств.

Несмотря на то, что значения констант Липшица и величина заранее неизвестны, они могут быть оценены в процессе решения задачи.

Описание метода

[править | править код]

Пусть . Индексы концевых точек считаются нулевыми, а значения в них не определены. Первое испытание осуществляется в точке . Выбор точки любого последующего испытания определяется следующими правилами:

  1. Перенумеровать точки предшествующих испытаний нижними индексами в порядке увеличения значений координаты: и сопоставить им значения .
  2. Для каждого целого числа определить соответствующее ему множество нижних индексов точек, в которых вычислялись значения функций :
    Также определить максимальное значение индекса
  3. Вычислить текущие оценки для неизвестных констант Липшица:
    Если множество содержит менее двух элементов или если значение оказывается равным нулю, то принять .
  4. Для всех непустых множеств вычислить оценки
    где вектор с неотрицательными координатами называется вектором резервов.
  5. Для каждого интервала вычислить характеристику
    где .
    Величины являются параметрами алгоритма. От них зависят произведения , используемые при вычислении характеристик в качестве оценок неизвестных констант Липшица.
  6. Определить интервал , которому соответствует максимальная характеристика .
  7. Провести очередное испытание в середине интервала , если индексы его концевых точек не совпадают:
    В противном случае провести испытание в точке
    увеличить на 1.
  8. Если ( — заданная точность метода), то прекратить выполнение алгоритма, иначе перейти на шаг 1.

Достаточные условия сходимости

[править | править код]

Пусть исходная задача оптимизации имеет решение и выполняются следующие условия:

  1. каждая область представляет собой объединение конечного числа отрезков, имеющих положительную длину;
  2. каждая функция удовлетворяет условию Липшица с соответствующей константой ;
  3. компоненты вектора резервов удовлетворяют неравенствам , где  — длина отрезка , лежащего в допустимой области и содержащего точку ;
  4. начиная с некоторого значения величины , соответствующие непустым множествам , удовлетворяют неравенствам .

Тогда верно следующее:

  1. точка является предельной точкой последовательности , порождаемой методом при в условии остановки;
  2. любая предельная точка последовательности является решением исходной задачи оптимизации;
  3. сходимость к предельной точке является двухсторонней, если .

Модификации метода

[править | править код]

Параллельная модификация

[править | править код]

Общая схема последовательного метода выглядит следующим образом:

  1. Упорядочить точки предшествующих испытаний в порядке возрастания их координат: .
  2. Вычислить для каждого интервала характеристику .
  3. Определить интервал , которому соответствует максимальная характеристика .
  4. Провести следующее испытание в точке , где  — правило размещения точки следующего испытания в интервале с номером .
  5. Проверить выполнение критерия остановки .

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

Схема параллельного алгоритма:

  1. Упорядочить точки предшествующих испытаний в порядке возрастания их координат: .
  2. Вычислить для каждого интервала характеристику .
  3. Характеристики интервалов упорядочить по убыванию: .
  4. Для всех интервалов с номерами провести испытания в точках .
  5. Проверить выполнение критерия остановки: .

Такая схема распараллеливания целесообразна, если проведение испытания (то есть вычисление функций задачи) — трудоемкий процесс.

Модификация для решения задач c гёльдеровыми функциями

[править | править код]

Метод достаточно просто обобщается на случай, когда функции удовлетворяют условию Гёльдера с показателем , где , то есть

.

На шаге 3 значения вычисляются по формуле:

На шаге 5 .

На шаге 7 в случае совпадения индексов концевых точек

На шаге 8 критерий остановки принимает вид .

  • Параметры отвечают за надежность метода. Чем больше их значения, тем больше итераций метода требуется для достижения заданной точности и тем вероятнее выполнение условия сходимости 4. Если устремить все к бесконечности, то , то есть метод превращается в перебор по равномерной сетке.
  • Использование ненулевого вектора резервов позволяет ускорить сходимость метода, однако при этом необходимо оценить возможность выполнения условия сходимости 3.
  • Одномерный метод может быть применен для решения многомерных задач без ограничений. Многомерная задача на множестве представляется в виде

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

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

Литература

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