по Общей теории систем и системный анализ (стр. 4 из 13)

4.10 Методы спуска (общая схема).

Все методы спуска решения задачи безусловной оптимизации (16) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности {xk}.

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

• точке xk выбирается направление спуска – sk;

• находят (к + 1) – е приближение по формуле:

(18)

где в качестве величины

выбирают любое число, удовлетворяющее неравенству

(19)

где число

– любое такое число, когда

В большинстве методов спуска величина lк выбирается равной единице. Таким образом, для определения bк приходится решать задачу одномерной минимизации.

4.11 Метод градиентного спуска.

Поскольку антиградиент –

указывает направление наискорейшего убывания функции f(x), то естественным является перемещение из точки хk по этому направлению. Метод спуска, в котором называется методом градиентного спуска. Если , то релаксационный процесс называется методом скорейшего спуска.

4.12 Метод сопряженных направлений.

В линейной алгебре этот метод известен как метод сопряженных градиентов решения систем линейных алгебраических уравнений АХ=b, а следовательно, как метод минимизации квадратичной функции

Схема метода:

(20)

Если

= 0, то эта схема превращается в схему метода скорейшего спуска. Соответствующий выбор величины tk гарантирует сходимость метода сопряженных направлений со скоростью того же порядка, что и в методах градиентного спуска и обеспечивает конечность числа итераций в квадратичном спуске (например ).

4.13 Покоординатный спуск.

На каждой итерации в качестве направления спуска – sk выбирается направление вдоль одной из координатных осей. Метод имеет скорость сходимости процесса минимизации порядка 0(1/m). Причем она существенно зависит от размерности пространства.

Схема метода:

где

координатный вектор

(21)

Если в точке xk имеется информация о поведении градиента функции f(x), например:

то в качестве направления спуска sk можно взять координатный вектор еj. В этом случае скорость сходимости метода в n раз меньше, чем при градиентном спуске.

На начальном этапе процесса минимизации можно использовать метод циклического покоординатного спуска, когда сначала спуск осуществляется по направлению е1, затем по е2 и т. д. вплоть до еп, после чего весь цикл повторяется снова. Более перспективным по сравнению с предыдущим является покоординатный спуск, в котором направления спуска выбираются случайным образом. При таком подходе к выбору направления существуют априорные оценки, гарантирующие для функции f(x) с вероятностью, стремящейся к единице при

, сходимость процесса со скоростью порядка 0(1/m).

Схема метода:

На каждом шаге процесса из n чисел {1, 2, ..., n} случайным образом выбирается номер j(k) и в качестве sk выбирается единичный координатный вектор еj(k), после чего осуществляется спуск:

(22)

4.14 Метод случайного спуска.

На n-мерной единичной сфере с центром в начале координат выбирается случайная точка sk, подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на k-м шаге процесса элементу хк определяется

:

(23)

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

4.15 Релаксационные методы математического программирования.

Вернемся к задаче 36 ((16) – (17)):

при условиях

В оптимизационных задачах с ограничениями выбор направления спуска сопряжен с необходимостью постоянной проверки того, что новое значение хk+1 должно также, как и предыдущее xk удовлетворять системе ограничений X.

4.16 Метод условного градиента.

В этом методе идея выбора направления спуска состоит в следующем: в точке хк линеаризуют функцию f(x), строя линейную функцию

и затем, минимизируя f(x) на множестве х, находят точку yk. После этого полагают и далее вдоль этого направления осуществляют спуск , так, чтобы

Таким образом, для отыскания направления – sk следует решить задачу минимизации линейной функции на множестве X. Если X в свою очередь задается линейными ограничениями, то она становится задачей линейного программирования.

4.17 Метод возможных направлений.

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

Направление – s в точке х Î X называется возможным, если существует такое число

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

При условиях:

(24)

(25)

(26)

Пусть

– решение этой задачи. Условие (24) гарантирует, что направление – – возможное. Условие (25) обеспечивает максимальность величины ( , то есть среди всех возможных направлений – s, направление – обеспечивает самое быстрое убывание функции f(x). Условие (26) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно и эта задача пока остается нерешенной.

4.18 Метод случайного поиска.

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

Схема метода:

На n-мерной единичной сфере с центром в начале координат выбирается случайная точка rk, подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска – sk из условий

,