Методы проектирования и редукции градиента

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Комплексный метод Бокса

Более эффективную модификацию метода Нелдера-Мида предложил Бокс, который указал, что число точек в многограннике должно быть больше n+1. Таким образом, Бокс предложил вместо симплекса использовать комплекс, то есть не самую простую фигуру соответствующей размерности.

Рассмотрим задачу оптимизации:

              z = f(X) ® min,

              l_j £ x_j £ u_j, j = 1, …, n,

              g_i(X) £ b_i, i = 1, …, m.

Алгоритм Бокса.

1. Определить начальную точку X¹, удовлетворяющую всем ограничениям.

2. Определить остальные k-1 точки комплекса по правилу:                              

X = L + r×(U - L),

где L = (l₁, l₂, ..., l_n)^T, U = (u₁, u₂, ..., u_n)^T, r - псевдослучайная величина, равномерно распределенная в интервале (0, 1).

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

4. Найти точку X^h с наибольшим значением функции и центр X⁰ остальных (k-1) точек.

5. Получить новую точку X^r отражением X^h относительно X⁰:

              X^r = (1+a)×X⁰ - a×X^h, a > 0.

6. Проверить является ли X^r допустимой.

а) если X^r нарушает ограничения по l_j или u_j, то полагаем  или  соответственно;

б) если не выполняются ограничения g_i(X^r), то выбираем новую точку по правилу:  

              .

Провести повторную проверку на допустимость и повторять шаг 6, пока не будет получена допустимая точка.

7. Вычислить f(X^r) и сравнить с наибольшим значением функции f(X^k). Если f(X^r)>f(X^k), то положить

и перейти к шагу 6.

8. Если f(X^r)<f(X^k), то полагаем X^k=X^r и снова упорядочиваем точки комплекса.

9. Осуществляется проверка на сходимость. Если условия сходимости не выполнены, то переходим к шагу 4. Иначе - остановка.

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

Методы штрафных функций

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

Пусть решается задача условной оптимизации

              z = f(X) ® min,

              c_j(X) > 0, j = 1, 2, . . . , m.

Построим функцию штрафа P(X):

    ,

где r>0 - коэффициент штрафа.

Тогда можем записать новую целевую функцию в виде

    .

Если X принимает допустимые значения, т.е. c_j(X)>0, то j(X,r) принимает значения, которые больше f(X), но разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если X хотя и допустим, но очень близок к границе (хотя бы одна из функций c_j(X) близка к нулю), то значения функции P(X), а значит, и функции j(X,r) становятся очень большими. Таким образом, P(X) создает "гребень с крутыми краями" вдоль каждой границы области ограничений. Следовательно, если поиск начинается из допустимой точки и производится поиск минимума функции j(X,r) без ограничений, то минимум будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной для того, чтобы влияние P(X) было малым в точке минимума, можно сделать точку безусловного минимума функции j(X,r) сколь угодно близкой к точке условного минимума функции f(X). В общем случае, решая последовательность задач безусловной оптимизации с уменьшающимся r, можно получить приближенное решение задачи условной оптимизации. На этом основан так называемый SUMT-метод Фиакко и Маккормика (метод последовательной безусловной оптимизации).

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

              .

Эта барьерная функция вообще не определена за пределами допустимой области.

Штрафные функции могут иметь и другой вид. Например, для ограничений-равенств имеем:

 - квадратичная штрафная функция,

 - абсолютная штрафная функция,

 - штрафная функция, позволяющая учитывать "важность" ограничений.

Если же в постановке задачи присутствуют ограничения-равенства (h_j(X)) и ограничения-неравенства (g_i(X)) одновременно, то штрафная функция может быть записана, например, в виде:

P(X) = ,

P(X) = .

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

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

Это - целое семейство алгоритмов, которое еще называют методами допустимых направлений.

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

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

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров