WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

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

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

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

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

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

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

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

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

Здесь , а .

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

Дуги функции липшицевы на множествах с константой 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.

Ссылки

  • - реализация метода на языке C++.
  • - реализация на языке С++ модификации метода метода для решения многокритериальных многомерных задач.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии