Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

2)методы первого порядка – методы, использующие, кроме того, первые производные;

3)методы второго порядка – методы, использующие, кроме первых производных, еще и вторые производные.

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

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

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

1.3.1.Методы нулевого порядка

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

Наиболее простым способом определения направления спуска

является выбор в качестве ˆ одного из координатных векторов

Sk

e1 , e2 , …, en .

вектор, у которого i-я компонента равна 1, а остальные – нулю. Иначе говоря, в методе покоординатного спуска на каждой итерации поиск точки с меньшим значением функции осуществляется изменением одной компоненты вектора x при неизменных остальных.

Существует несколько вариантов покоординатного спуска. Мы рассмотрим некоторые из них.

36

Покоординатный спуск с удвоением шага (первый вариант)

Опишем первый цикл метода, состоящий из п итераций.

удвоения шага продолжают до тех пор, пока убывание функции не прекратится;

3) если f (x0 + λ1S1 ) ≥ f (x0 ) , то выбирают λ1 = λ1 / 2 и переходят к п. 2.

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

Если в направлении e1 функция f (x) убывает, то фиксируют λ1 и переходят к следующей итерации. В противном случае выбирают направление S1 = −e1 и снова определяют величину шага λ1

способом удвоения. Если и в данном направлении функция не убывает, то фиксируют неудачный поиск в данном направлении; в качестве значения λ1 берут начальное значение шага λ0 и переходят к следующей итерации.

Если в направлении − e1 функция убывает, то фиксируют

найденную величину шага λ1 и переходят к следующей итерации. На следующей итерации выбирают направление S2 = e2 и

полагают начальное значение шага λ2 = λ1, а начальную точку x1= x0 + λ1S1 (если поиск неудачный, то x1 = x0 ) и повторяют

процесс, как на первой итерации.

Цикл заканчивается при k = n , т.е. после того, как пройдет поиск по всем п направлениям S1 = ±e1, S2 = ±e2 , …, S n = ±en .

Если поиск по всем n направлениям оказался неудачным, то процесс прекращается: x* = xn .

В противном случае начинается новый цикл: Sn+1 = e1 и т.д.

37

Покоординатный спуск с удвоением шага (второй вариант)

Каждый цикл этого метода характеризуется тем, что величина шага λ в течение всех n итераций цикла остается постоянной. Предполагается, что в результате завершения предыдущего цикла получена некоторая величина шага λ.

Рассмотрим i-ю итерацию цикла (1 ≤ i ≤ n ), которая состоит в следующем:

1) если

то x не меняют (полагают x = x ) и переходят к следующей итерации.

Таким образом, осуществляется n итераций цикла.

Если неравенства (1.6) и (1.9) имеют место для всех 1 ≤ i ≤ n , то уменьшают величину λ, полагая, как правило, λ = λ / 2 , и переходят к следующему циклу, то есть повторяют все процедуры предыдущего цикла, но уже с шагом, уменьшенным в два раза.

Если неравенства (1.6) или (1.9) имеют место не для всех i, то шаг λ не дробится.

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

38

Покоординатный спуск с одномерной минимизацией

Цикл данного метода опять содержит n итераций. Каждая итерация состоит в поиске минимума функции вдоль одной из координат при неизменных остальных. Поиск минимума осуществляется одним из методов одномерной минимизации. Изобразим алгоритм в виде блок-схемы, представленной на рис. 1.12.

Вход

Ввод исходных данных

εi , ε2 , n, x0 , f (x0 ), k = 0

i=1

да i ≤ n

нет

нет

f (xk +1 ) − f (xk ) ≤ ε

да

xk = xk +1

Выход

Рис. 1.12. Блок-схема алгоритма метода покоординатного спуска

39

Недостаток метода покоординатного спуска (всех его вариантов) заключается в том, что он может «застревать», т.е. он может остановиться вдали от точки минимума и не обеспечить дальнейшего улучшения. Такая ситуация может возникнуть, если поверхности уровня целевой функции обладают острыми углами или очень изогнуты. На рис. 1.13, приведенном ниже и отображающем расположение линий уровня f (x) =C , представлен

пример такой ситуации.

Рис. 1.13. Линии уровня в методе покоординатного спуска

Если процесс решения привел в точку x0 , то каким бы малым ни брать шаг в направлении x1 или x2 , нельзя получить

уменьшение значения функции. Метод «застревает» в точке x0 . Рассмотрим несколько примеров применения метода

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

Задача 1. Построить блок-схему метода покоординатного спуска с удвоением шага (второй вариант).

Решение. Блок-схема метода покоординатного спуска с удвоением шага при поиске минимуму по каждой координате приведена на рис. 1.14. При этом использованы следующие обозначения:

k – номер цикла;

i – номер (внутри цикла) итерации движения по i-му направлению ( i =1, n );

j – счетчик неудачных шагов, когда x не меняется; x – текущее значение аргумента (без индекса).

40