Лекция 11 . Методы безусловной оптимизации


Содержание лекционного занятия:

· Градиентные методы

· Метод параллельных касательных

· Метод сопряженных градиентов

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

· О методах второго порядка

· О методах прямого поиска

· Методы одномерной минимизации

Это методы поиска минимума функции многих пере­менных при отсутствии ограничений.

Итерационные методы минимизации функции F(x) со­стоят в построении последовательности векторов, т.е. точек х0, х1,..., хkтаких что F(x0) > F(x1) > ... > F(xk) > ... Любой такой метод называется методом спуска. Естественно, должна быть обеспечена сходимость получаемой последо­вательности точек к точке минимума, т.е. рассматриваются методы, позволяющие получить точку минимума за конеч­ное число шагов или приблизиться к ней достаточно близко при соответствующем числе шагов. К сожалению, здесь нельзя употребить слова «сколь угодно близко при неогра­ниченном увеличении числа шагов». Дело в том, что тео­ретически все сходящиеся методы этим свойством облада­ют, но практически близость к минимуму в задачах боль­шой размерности ограничивается ошибками вычислений, которые обусловлены погрешностью представления чисел в компьютере. Поэтому необходимо вести вычисления с удвоенной точностью, выбирая соответствующие типы дан­ных при разработке конкретных компьютерных программ.

Для построения итерационной последовательности необхо­димо выбрать начальное приближение х0. В задачах с ограниче­ниями это должна быть допустимая точка, а в задачах без огра­ничений— теоретически любая точка. Однако целесообразно использовать всю имеющуюся информацию о поведении целе­вой функции F(x), чтобы выбрать х0 поближе к точке минимума.

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

1. Выбрать направление, по которому пойдем из х0 в точку с меньшим значением целевой функции (направление спуска);

2. Определить величину шага по направлению спуска. При любом методе спуска итерационная последователь­ность точек{хк} может быть записана в виде: хк+'=хк + λкpк,(к = 0, 1,...),

где вектор рк — это направление, а λк||рк|| — величина шага. Если ||рк|| =1, т.е. длина вектора спуска равна единице, то величина шага равна λк. Отметим, что иногда λк называ­ют шагом независимо от длины вектора рк. Здесь — длина вектора рк.

Методы спуска отличаются процедурами построения вектора рк и вычисления λк. При этом могут использоваться одна (последняя) или две последние (или более) из уже по­лученных точек.

Для задач безусловной минимизации любое направление является возможным (никакие ограничения не мешают), но далеко не все направления приемлемы. Нас могут интересо­вать только направления, обеспечивающие убывание целе­вой функции, хотя бы при достаточно малом шаге. Предпо­лагая непрерывность первых частных производных целевой функции и используя ее разложение в ряд Тэйлора в произ­вольной точке х, получим F(x + λр) ≈ F(x) + λ(g, p). Здесь g— градиент функции, вычисленный в точке х. Отсюда следует, что приращение функции F(x + λр) - F(x) < 0 при отрицательном скалярном произведении (g, p). Итак, направление спуска должно составлять острый угол с ан­тиградиентом. Этот вывод справедлив и для задач с огра­ничениями, но там еще дополнительно требуется, чтобы при достаточно малом шаге не нарушалось ни одно из огра­ничений.

Все такие направления называются подходящими (приемлемыми). Методы спуска, позволяющие получать последовательно подходящие направления, Зойтендейк (Zoutendijk G.) назвал методами возможных направлений.

Градиентные методы

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

(1)

т.е. направление спуска на каждой итерации - это анти­градиент, вычисленный в текущей точке хк.

Рис. 4. Линии уровня и антиградиент

На рис. 4 текущему вектору хк соответствует точка А. Примем за единицу значение целевой функции в этой точке и рассмотрим линию уровня со значением 1-ε, где ε доста­точно малая величина. При достаточно малом е эти линии уровня будем считать параллельными. Переход на линию уровня с меньшим значением при изменении только x1 дает точку С, а при изменении только х2 точку В. Обозначим расстояние АС через Δ1 ,а АВ через Δ2. Тогда для частных производных имеем приближенные равенства: дF/дх1 = - ε1 и дF/дх2 = -ε/ Δ2.

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

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

Траектория спуска в этом методе носит зигзагообразный характер и градиенты в любых двух последовательных точ­ках ортогональны (рис. 6).

Рис. 6. Зигзагообразная траектория наискорейшего спуска

Метод параллельных касательных

Алгоритм состоит в следующем:

1. Из точки х0 делаем два шага как в методе наискорейшего спуска (рис. 6) и получаем точку х2.

2. Из точки х2 идем не по антиградиенту, а по направлению х20(рис. 7).

3. Находим х3 как точку минимума функции в этом направ­лении и вычисляем антиградиент в ней.

4. Проверяем условия окончания счета и, если они не вы­полнены, повторяем пункт 1, используя х3 вместо х0.

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

Метод сопряженных градиентов

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

1. р0 = -g0, т.е. первый шаг делаем по антиградиенту,

2. pk+1 = -gk+1 + βkpk, где βк = (gk+', gk+') / (gk, gk).

Это означает, что

Другими словами, сделав из начальной точки один шаг по методу наискорейшего спуска, надо вычислить антиградиент в новой точке. Затем взять отноше­ние квадратов длин нового и старого градиентов (это и есть β0), умножить старый антиградиент на это число и результат сложить с новым антиградиентом. Это и будет направление спуска р1= -g1 – β0 g0, которое мы будем использовать вместо антиградиента -g1. В направлении р1 нужно дойти до точки минимума, в ней вычислить анти­градиент –g2 затем β1= (g2, g2) / (g1 ,g1) и р2 = -g2 + β1 p1 и т.д.

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

Рассмотрим еще один простой метод безусловной опти­мизации, идея которого состоит в том, чтобы свести опти­мизацию в многомерном пространстве к многократно по­вторяемой одномерной оптимизации. Метод состоит в сле­дующем:

1. В начальной точке х0 фиксируем все координаты, кроме xi.

2. Определяем такое значение x1, при котором целевая функция достигает минимума. Это одномерная задача, так как все переменные, кроме х1 фиксированы.

3. Фиксируем найденную координату x1 и все остальные, кроме х2.

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

5. Проверяем условия окончания счета и, если они не вы­полнены, возвращаемся к пункту 1, приняв полученную точку за х0. В качестве условия прекращения счета мож­но взять малое изменение функции после поочередного изменения всех координат или малые изменения всех координат.

О методах второго порядка

Методы второго порядка предусматривают использова­ние вторых частных производных целевой функции. По­скольку для квадратичной задачи целевая функция l/2(Qx, x) + (с, х), необходимое условие экстремума дает

Получаем критическую точку х* = -Q-1 с.

Если исходная точка х0и градиент в ней g 0 = Qx0 + с, то выражение для х можно записать так:

Другими словами, можно найти критическую точку за один шаг из любой точки. Но идти надо не по антиградиенту, а сначала умножить антиградиент на Q-1 (см. формулу 2.6). При положительно определенной квадратичной форме кри­тическая точка будет точкой минимума. Но для этого надо знать обратную матрицу Q-1 или (что равносильно) решить систему линейных уравнений Qx + с = 0. При большой раз­мерности задачи это требует большого объема вычислений (порядка n3 умножений).

О методах прямого поиска

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

Методы одномерной минимизации

Существует много методов поиска минимума функции одной переменной на заданном отрезке. Как правило, функция предполагается унимодальной, т.е. имеющей один минимум. Для гладких унимодальных функций точка минимума совпадает с точкой, в которой производная Функции равна нулю. Поэтому вместо точки минимума Функции f(x) можно искать корень уравнения f (х) = 0.

Вопросы для самоконтроля:

1.Методы спуска для задач безусловной оптимизации.

2.Метод Ньютона для задач безусловной оптимизации.

3.Квазиньютоновские методы.

Рекомендуемая литература:

1.Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

2.Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.