Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление
 Скачать 3.86 Mb.
|
|
15.2.Введение в многомерную минимизацию. Ограничимся методами безусловной оптимизации. 15.2. 1. Постановка задачи. Пусть f(x)=f(x 1 , x 2 , …, x n ) действительная функция многих переменных, определенная на множестве x R n Точка x* называется точкой глобального минимума, если f(x*) n . Если неравенство справедливо только в окрестности точки x*, говорят о локальном минимуме. В дальнейшем излагаются методы поиска локальных минимумов. 15.2.2. Поверхности уровня. Градиент и матрица Гессе. Необходимые и достаточные условия локального минимума. Множество точек, для которых целевая функция принимает постоянные значения f(x)=с, называется поверхностью уровня. В трехмерном случае для параболоида z=x 2 +y 2 поверхности становятся линиями уровня – в данном случае окружностями. Для дифференцируемой 181 функции существует вектор из первых производных, называемый градиентом 1 2 ( ) '( ) ( ), ( ),..., ( ) T n f f f g x f x x x x x x x . Если в точке x градиент не равен нулю, он перпендикулярен к поверхности уровня, проходящей через эту точку, и указывает направление наискорейшего возрастания функции. Вектор –g(x) называется антиградиентом и указывает направление наискорейшего убывания функции. Необходимым условием существования минимума в точке x является равенство g(x)=0. В этом случае точка x называется стационарной. Однако не всякая стационарная точка оказывается точкой минимума. Достаточным условием существования точки минимума является положительная определенность матрицы G(x)=f''(x)= 2 2 2 1 1 2 2 2 1 ( ) ( ) ( ) ( ) n n n f f x x x x x f f x x x x x . Эта матрица Якоби для g(x) называется матрицей Гесса. Матрица Гесса 182 симметрическая матрица, что не является обязательным для матрицы Якоби произвольной вектор функции. Функция называется строго выпуклой, если для любых x ≠y, 0<λ<1 выполняется неравенство f(λx+(1-λ)y)<λf(x)+(1-λ)f(y). графическая интерпретация для одномерного случая представлена на рисунке. x 1 x 2 f(x) x x 1 ,f(x 1 ) x 2 ,f(x 2 ) Для произвольных x 1 и x 2 график строго выпуклой функции лежит ниже хорды, соединяющей точки (x 1 ,f(x 1 )) и (x 2 ,f(x 2 )). Положительная определенность матрицы Гессе является достаточным условием строгой выпуклости. Действительно В дальнейшем предполагается, что предварительно произведена локализация локального минимума, т. е. определена область, внутри которой целевая функция является строго выпуклой и, значит, матрица Гессе обладает свойством положительной определенности. 15.2. 3. Задача минимизации квадратичной функции. Задача минимизации квадратичной функции в методах минимизации играет роль тестовой задачи . Пусть задана квадратичная функция 183 F(x 1 , x 2 , …, x n ) = 1 1 1 1 2 n n n ij i j i i i j i a x x b x , элементы a ij которой являются компонентами симметрической и положительно определенной матрицы А (при положительной определенности гарантировано существование минимума). В матричной форме имеем F(x)=(1/2)(Ax,x)-(b,x). (1) Вычислим градиент и матрицу Гессе для F(x). Дифференцирование по x k дает 1 1 1 1 2 2 n n kj j ik i k j i k dF a x a x b x . Пользуясь симметрией матрицы А, получаем 1 n kj j k j k dF a x b x . Таким образом F'(x)=Ax-b. Элементы матрицы Гессе можно получить следующим образом: 2 kl l k k l dF dF F a x x x x . Это означает, что для квадратичной функции матрица Гессе не зависит от x. Задача минимизации квадратичной функции интересна потому, что в малой окрестности точки минимума x* гладкая целевая функция хорошо апроксимируется суммой первых трех слагаемых её разложения в ряд Тэйлора * * * * * * * 1 ( ) ( ) ( ) ( ( ), ) ( ( )( ), ) 2 f x F x f x g x x x G x x x x x с центром в точке x * ≈x*. Функция F * c точностью до постоянного слагаемого может быть записана в виде (1) с матрицей А=G(x * ) ≈G(x*). Поэтому можно ожидать, что вблизи точки минимума качественный характер поведения итерационной последовательности x n окажется почти таким же, как и для квадратичной функции F. Дополнительно отметим, что если А симметрическая положительно определенная матрица, задача минимизации функции (1) эквивалентна задаче решения системы линейных алгебраических уравнений Ax=b. Действительно, в точке минимума должно быть F'(x*)=Ax*-b=0. 184 15.2. 4. Обусловленность задачи минимизации. Предположим, что в некоторой окрестности точки минимума вычисляемые приближенные значения f*(x) удовлетворяют неравенству |f(x)-f*(x)| Δ(f*). Обобщая результаты, полученные для одномерного случая, можно показать, что погрешность расчета точки минимума Δ(x )=||x-x*|| ≈ 1 2 ( *) || ( *) || f G x = min ( *) 2 f , где λ min >0 – минимальное собственное значение матрицы Гессе. 15.2. 5. Понятие о методах спуска. Процесс нахождения минимума часто называют процедурой спуска. Алгоритм. Опишем структуру типичной (n+1)-ой итерации метода спуска. 1. Находят вектор p n ≠0, называемый направлением спуска, такой чтобы при достаточно малых α>0, выполнялось неравенство f(x n +αp n ) Обозначив φ n (α)=f(x n +αp n ), неравенство перепишется φ n (α)<φ n (0). 2. Вычисляем α n >0, для которого неравенство (2) выполнено. 3. За очередное приближение к точке минимума принимаем x n+1 =x n +α n p n 4. Проверяют выполнение критерия окончания итераций. В случае его выполнения итерации прекращают, полагая x* ≈x n+1 . В противном случае итерации продолжаются. Направление спуска. При движении в направлении p n значение целевой функции должно уменьшаться. Для этого необходимо, чтобы угол γ между векторами p n и градиентом g(x n ) должен быть тупым, то есть n n n n n ((g(x ) f '(x ), p ) cos( ) 0 || g(x ) || ||p || n .Тогда ((g(x n ) =f'(x n ), p n )<0. (3) 185 В этом случае говорят, что p n задает направление спуска. Способ выбора направления спуска задает конкретный численный метод, а варианты метода определяются алгоритмом вычисления шага спуска α n Выбор шага спуска. В качестве α n можно выбирать значение α, которое обеспечивает достижение наименьшего значения функции f при движении вдоль луча x=x n +α p n , α ≥0. В этом случае для вычисления α n требуется решение одномерной минимизации функции φ n (α)=f(x n +αp n ). Этот путь надежен, но связан с большими вычислительными затратами. Активно используются менее затратные методы. Один из них метод дробления шага состоит в следующем. Фиксируют начальное значение шага α и выбирают параметр γ, 0<γ<1. Часто задают γ=1/2. За шаг спуска принимают α n= α n i где i n первый из номеров, для которых выполнено условие f(x n +α n p n )-f(x n ) γα β i (g(x n ) =f'(x n ), p n ). i n = 0,1,…; 0<β<1- некоторый дополнительный параметр. Критерии окончания итераций. Часто используются следующие критерии ||x n+1 -x n ||<ε 1 |f(x n+1 )-f(x n )|<ε 2 |f'(x n )|<ε 3 15.2.6. Покоординатный спуск. В качестве очередного направления спуска выбирают направление очередной координатной оси. Широко распространен метод циклического покоординатного спуска. Пусть приближение x (k) уже найдено. Цикл с номером k+1 состоит из n шагов. На первом шаге производят спуск по координате x 1 . Значения остальных координат x 2 = x 2 (k) , … , x n = x n (k) фиксируют, а x 1 (k+1) выбирают из условия 186 f (x 1 (k+1) ,x 2 (k) , …,x n (k) )= 1 min x f (x 1 ,x 2 (k) , …,x n (k) ). Иными словами решается задача минимизации функции одной переменной f 1 (x 1 ) = f (x 1 ,x 2 (k) , …,x n (k) ). На втором шаге фиксируют значения координат x 1 (k+1) ,x 3 (k) , …,x n (k) и рассчитывают x 2 (k+1) как результат решения задачи одномерной минимизации. Аналогично осуществляют остальные шаги. В результате получают очередное приближение x (k+1) Далее цикл метода снова повторяют. Метод циклического покоординатного спуска теоретически эффективен в случае единственного минимума функции. На практике он оказывается медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основе уже полученных данных значений функции. Назовем некоторые из этих методов нулевого порядка (не использующих производные целевой функции). 1.Метод Хука – Дживса (поиск по образцу). 2. Меод Нелдера – Милда или метод деформируемого многогранника. Методы нулевого порядка в большинстве случаев оказываются очень неэффективными, но по необходимости их используют, если производные целевой функций не существуют. 15.2. 7. Градиентный метод. Ранее уже отмечалось, что в окрестности точки x n направление наискорейшего убывания функции f задается антиградиентом -g n . В градиентном методе за направление спуска выбирается направление антиградиента. Таким образом, x n+1 =x n -α n g n Способ выбора шага α n задает определенный вариант градиентного метода. 187 15.2.7.1.Метод наискорейшего спуска. Направление спуска p n = -g n Рассмотрим функцию φ n (α)=f(x n -αg n ) одной скалярной переменной α>0 и выберем в качестве α n то значение α>0, для которого выполняется равенство φ n (α n )=min φ n (α). Это первый вариант метода, предложенный в 1845 году О. Коши. Второй вариант метода предполагает для вычисления α n использовать методику дробления шага. Теорема сходимости для второго варианта имеет следующую формулировку. Теорема. Пусть выполнены следующие условия: 1) f(x) ограничена снизу; 2) градиент g(x) удовлетворяет условию Липшица || ( ) ( ) || || || x,y R ; n g x g y L x y L=||G(ξ)||, ξ [x,y]. 3) параметр α n выбирается из условия 1 1 ( ) ( ) ( , ), 0< <1, где x n n n n n n n f x f x g p x g Тогда ||g n || →0, если n→∞ . С ростом n целевая функция монотонно уменьшается. В процессе доказательства теоремы формулируются требования к выбору коэффициента 1 L Алгоритм метода в соответствии с теоремой сходимости имеет вид. 1. Выбираем произвольную точку x 0 – начальное приближение. Полагаем x n =x 0 2. Выбираем произвольное значение α. 3. Определяем новую точку x n+1 =x n -αg n 4. Вычисляем f(x n+1 )=f(x n -αg n ) и f(x n ). 5. Если f(x n+1 )-f(x n ) γα(g(x n ), p n ), 0<γ<1, то значение α берем в качестве искомого α n и переходим к шагу 6, иначе α=α/2 и переходим к шагу 4. 188 6. Вычисляем новое приближение x n+1 =x n -αg n 7. Проверяем выполнение условия стационарности ||g n+1 ||= (g n+1 ,g n+1 ) ε – заданная погрешность. Если условие выполнено переходим к шагу 8, иначе к шагу 2, положив x n =x n+1 8. Останов. Метод наискорейшего спуска сходится с линейной скоростью при удачном выборе γ, α. Начальное приближение должно находиться в области существования минимума. Следует сказать, что метод наискорейшего спуска не рекомендуется в качестве "серьезной" оптимизационной процедуры. На первый взгляд он привлекателен, но для практического применения работает слишком медленно. Дело в том, что свойство наискорейшего спуска является лишь локальным свойством, и поэтому необходимо частое изменение направления, что приводит в итоге к не эффективной вычислительной процедуре. Метод оказывается непригодным для использования второй производной целевой функции. Указанные недостатки метода становятся особенно существенными при работе с "овражными" функциями. Для таких функций поверхности уровней имеют форму вытянутых оврагов. В простейшем варианте это можно продемонстрировать на примере квадратичных функций. . Отметим, что поверхностями уровня квадратичной функции F(x)=(1/2)(Ax,x)-(b,x) являются n-мерные эллипсоиды с центром в точке x*. Отношение их осей равно cond 2 (A)=λ max /λ min . Чем больше число обусловленности, тем больше вытянутость эллипсоидов. При этом поверхности уровней становятся похожими по форме на овраги. Здесь возникает проблема овражности. Если есть длинная и узкая впадина на поверхности, определяемой функцией F(x), то компоненты градиента вдоль основания впадины — малы, а в направлении к стенкам — велики. Попав на склон оврага и стараясь идти в направлении антиградиента, мы движемся по склону, то время как идти желательно по основанию оврага. 189 Если не принять специальных мер, объем вычислительной работы в этих случаях резко возрастает. Графическая интерпретация ситуации приведена на нижнем рисунке. x 0 15.2.7.2. Метод сопряженных градиентов. Напомним процедуру метода наискорейшего спуска: 1. В начальной точке x (0) вычисляется градиент и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция (решается задача одномерной минимизации с целью определения величины шага α 0 ). 190 2. В точке, где функция перестает уменьшаться, опять вычисляется антиградиент и шаг α n , и спуск продолжается в новом направлении -g (n) 3. Процесс продолжается до достижения точки минимума. Однако, существует более разумный способ выбора p (n) нового направления движения вместо -g (n) , и он называется метод сопряженных направлений. Метод сопряженных градиентов относится к группе методов сопряженных направлений. Определение сопряженности формулируется следующим образом: два вектора x и y называются А – сопряженными или А – ортогональными, если выполнено условие (x,Ay)=x T Ay=0. Остается выяснить, каким образом вычислять сопряженные направления. Если матрица А известна (как, например, в задаче минимизации квадратичной функции), можно использовать методы линейной алгебры, в частности, процесс ортогонализации Грамма – Шмидта. Для случая целевой функции общего вида также разработаны приемы вычисления сопряженных направлений. Рассмотрим каждый из этих случаев отдельно. Минимизация квадратичной функции. В этом методе направления p (n) строятся по правилу p (0) = -g (0) , p (n) = -g (n) + β n-1 p (n-1) , n 1 где ( 1) ( ) 1 ( 1) ( 1) ( , ) ( , ) n n n n n Ap g Ap p Так как p (0) = -g (0) , то первый шаг этого метода совпадает с шагом наискорейшего спуска. Можно показать, что при указанном выборе β n-1 , направления p (n) (n=0,1,…) действительно являются сопряженными относительно матрицы А. Более того, градиенты g (n) (n = 0,1,..) оказываются взаимно ортогональными. Итерационный процесс осуществляется по закону 191 x (n+1) = x (n) + α n p (n) В случае квадратичной целевой функции её минимум в направлении p (n) достигается при величине шага ( ) ( ) ( ) ( ) ( , ) ( , ) n n n n n p g Ap p При отсутствии вычислительных ошибок требуется не более n итераций. Ранее указывалось, что минимизация квадратичной функции 1 ( ) ( , ) ( , ) 2 F x Ax x b x эквивалентна решению системы линейных алгебраических уравнений Ax = b. Метод сопряженных градиентов в общем случае . В общем случае для расчета β n-1 можно использовать одну из следующих формул 1. ( ) ( ) ( 1) 1 ( 1) ( 1) ( , ) ( , ) n n n n n n g g g g g Формула Полака – Райбера. 2. ( ) ( ) 1 ( 1) ( 1) ( , ) ( , ) n n n n n g g g g Формула Флетчера – Ривса. 3. ( 1) ( 1) 1 1 ( 2) ( 1) 1 ( ' , ) ( ' , ) n n n n n n n g p g g p p Эти формулы не содержат явным образом матрицу А. Минимизация идет в следующей последовательности p (0) = -g (0) , p (n) = -g (n) + β n-1 p (n-1) , n 1 ( ) ( ) ( ) min ( ), ( ) ( ), 0. n n n n n n f x p ( 1) ( ) , 0. n n n n x x p n При расчете β n-1 по третьей формуле приходится вычислять матрицу Гессе g' (n) . Однако в этом случае возможно использование квазиньютоновских методов для аппроксимации этой матрицы. Реализация такой процедуры использована в популярном BFGS – алгоритме (Broyden, Fletcher, Goldfarb, Shanno). |