Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации
 Скачать 3.42 Mb.
|
|
Замечание 1. Следует иметь в виду, что если функция ) ( X f многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума ) ( X f Замечание 2. Если ограниченность целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова. Лекция №5. Многомерная оптимизация (продолжение). Далее рассмотрим прямые методы решения задачи безусловной минимизации, использующие простейшие вычислительные алгоритмы, основанные на рекуррентной формуле k k k k S X X 1 , ( 1) где k S - направление поиска точки 1 k X из точки k X , а положительное число k - величина шага в этом направлении. Способ выбора k S и k будет определять одну из рассматриваемых далее модификаций метода покоординатного спуска. Метод циклического покоординатного спуска Метод циклического покоординатного спуска заключается в последовательной минимизации целевой функции ) ( X f сначала по направлению первого базисного вектора 1 e , затем второго - 2 e и т.д. После окончания минимизации по направлению последнего базисного вектора n e цикл повторяется. Таким образом, метод циклического покоординатного спуска заключается в изменении каждый раз одной переменной, тогда как другие остаются постоянными. Опишем этот метод : Пусть 0 X - некоторое начальное приближение, а 0 – некоторое положительное число, являющееся параметром алгоритма. Допустим, что уже известны точка n k E X и число 0 k при некотором 0 k . Обозначим ) 0 ,..., 0 , 1 , 0 ,..., 0 ( j e - единичный координатный вектор, у которого j-я координата равна 1, остальные равны нулю, j=1,…,n. Положим 1 , n k n k j e S k j k k ( 2) где n k - целая часть числа k/n. Условие (2.13) обеспечивает циклический перебор координатных векторов n e e ,..., 1 , т.е. 1 0 e S ,…, n n e S 1 , 1 e S n ,…, n n e S 1 2 , 1 2 e S n … Вычислим значение функции ) ( X f в точке k k k S X X и проверим неравенство ) ( ) ( k k k k X f S X f ( 3) Если оно выполняется, то полагаем k k k k S X X 1 , k k 1 ( 4) В случае если условие (3) не выполняется, вычисляем значение функции ) ( X f в точке k k k S X X и проверяем неравенство ) ( ) ( k k k k X f S X f ( 5) При выполнении условия (5) полагаем k k k k S X X 1 , 1 k = k ( 6) Будем считать (k+1) - ый этап удачным, если выполнилось хотя бы одно из условий (3) или (5). Если же ни одно из этих условий не выполнено, считаем (k+1) - ый этап неудачным и полагаем k k X X 1 , , 1 0 ; , 1 1 1 n k или x x или n j при x x n j при n k k k k n k k k k k ( 7) где ) 1 ; 0 ( – фиксированное число, являющееся параметром алгоритма. Условие (7) означает, что если за один цикл из n этапов при переборе направлений всех координатных векторов n e e ,..., 1 с шагом k реализовался хотя бы один удачный этап, то длина шага k не дробится и сохраняется на протяжении по крайней мере следующего цикла из n этапов. Если же среди последних n этапов ни одного удачного не оказалось, то шаг k дробится. Опишем алгоритм метода покоординатного спуска. Шаг 0. Задать параметр точности 0 , начальный шаг 0 0 , коэффициент уменьшения шага 1 ; 0 , точку начального приближения n E X 0 , вычислить значение функции ) ( 0 X f , положив k=0. Шаг 1. Вычислить 1 n k n k j , где n k - целая часть числа n k и положить j k e S , где j e - единичный вектор, у которого j - я компонента равна 1, а остальные нулю. Шаг 2. Вычислить значение функции ) ( X f в точке k k k S X X Шаг 3. Если ) ( ) ( k X f X f , то перейти к шагу 6, иначе вычислить ) ( X f в точке k k k S X X . Шаг 4. Если ) ( ) ( k X f X f , то перейти к шагу 6, иначе – к шагу 5. Шаг 5. Если n j , то положить k=k+1 и перейти к шагу 1, иначе положить k=k-n+1, k k и перейти к шагу 1. Шаг 6. Положить 1 ), ( ) ( , , 1 1 1 k k X f X f X X k k k k Шаг 7. Если n j , то перейти к шагу 8, иначе к шагу 1. Шаг 8. Проверить условие достижения заданной точности n k k X X или )) ( ( n k k X f X f и если оно выполняется, то перейти к шагу 9, иначе – к шагу 1. Шаг 9. Завершить вычисления, полагая ) ( , * * k k X f f X X Скорость сходимости данного метода невысока. Несмотря на это, метод циклического покоординатного спуска широко применяется на практике благодаря простоте реализации. Заметим, что такой метод работает плохо, если в выражение минимизируемой функции входят произведения j i x x , т.е. если имеет место взаимодействие между ,..., 1 , n i x i Методы безусловной оптимизации, использующие производные функции Будем рассматривать задачу безусловной оптимизации предполагая, что функция ) ( X f непрерывно дифференцируема на n E . Для ее решения воспользуемся простейшими итерационными процедурами вида k k k k S X X 1 , ( 8) где направление убывания k S будем определять тем или иным способом с использованием информации о частных производных функции ) ( X f в точке k X . Если k X не является стационарной точкой, т.е. 0 ) ( k X f , то в этой точке существует бесконечное множество направлений убывания. Какому из них отдать предпочтение? В курсе линейной алгебры доказывается, что при 0 ) ( k X f направление наибыстрейшего возрастания функции ) ( X f в точке k X совпадает с направлением градиента ) ( k X f , а направление наибыстрейшего убывания, следовательно, с направлением антиградиента )) ( ( k X f Это свойство градиента и кладется в основу так называемых градиентных методов минимизации функции. Таким образом, при решении задачи с помощью итерационной процедуры (8) в качестве направления убывания целесообразно выбирать направление антиградиента. Как и все итерационные методы, они предполагают выбор начального приближения – некоторой точки n E X 0 . Общих правил этого выбора нет. В тех случаях, когда известна какая-либо априорная информация об области расположения точки минимума, начальное приближение 0 X выбирают поближе к этой области. Пусть начальная точка 0 X уже выбрана. Тогда градиентный метод заключается в построении последовательности точек k X по правилу ,. 2 , 1 , 0 , 0 ), ( 1 k X f X X k k k k k ( 9) Число k из (3.43) называют длиной шага или просто шагом градиентного метода. Если 0 ) ( k X f , то шаг 0 k можно выбрать так, чтобы ) ( ) ( 1 k k X f X f Существуют различные способы выбора величины k в методе (9). В зависимости от способа выбора k можно получить различные варианты градиентного метода. Далее рассмотрим из них наиболее употребительные на практике. Метод градиентного спуска В соответствии с основной идеей градиентного метода минимизирующая последовательность k X строится по правилу (9), т.е. в качестве направления убывания функции ) ( X f выбирается направление антиградиента ( ) ( k k X f S ), которое, как показано выше, обеспечивает в малой окрестности точки k X наискорейшее убывание функции ) ( X f . В качестве длины шага k в этом варианте градиентного метода находится какое-либо число 0 k , обеспечивающее условие монотонного убывания функции k k X f X f 1 . ( 10) С этой целью задается какое-либо число k . При этом для каждого 0 k проверяют условие монотонного убывания (10), и в случае его нарушения величину k дробят до тех пор, пока не восстановится монотонность метода. Приведем алгоритм одного из вариантов метода градиентного спуска. Шаг 0. Задать параметр точности 0 , начальный шаг 0 , параметр алгоритма ) 1 ; 0 ( , выбрать n E X 0 , вычислить значение ) ( 0 X f , положить 0 k Шаг 1. Найти градиент ) ( k X f и проверить условие достижения заданной точности ) ( k X f . Если оно выполняется, то перейти к шагу 6, иначе - к шагу 2. Шаг 2. Найти новую точку X в направлении антиградиента ) ( k k X f X X и вычислить ) ( X f Шаг 3. Проверить неравенство k X f X f , Шаг 4. Если неравенство (3.45) выполняется, то положить X X k , ) ( ) ( X f X f k , 1 k k и перейти к шагу 1, иначе - перейти к шагу 5. Шаг 5. Положить , где 1 0 и перейти к шагу 2. Шаг 6. Завершить вычисления, положив ) ( , * * k k X f f X X Замечание. Вблизи стационарной точки функции ) ( X f величина ) ( X f становится малой. Это может привести к замедлению сходимости последовательности k X . Поэтому в (10) вместо вектора антиградиента )) ( ( k X f используют вектор единичной длины ) ( ) ( k k X f X f Пример 1. Проведем одну итерацию градиентного спуска для функции 13 8 6 4 ) ( 2 1 2 2 2 1 x x x x x f из начальной точки 0 1 0 X . Пусть 1 и параметр 5 , 0 . Вычислим 8 ) ( 0 X f Найдем градиент функции ) ( X f в точке 0 X : 8 4 8 8 6 2 ) ( 0 2 0 1 0 x x X f Определим новую точку ) ( 0 0 X f X X , вычислив ее координаты: 5 4 1 ) 4 ( 1 ) ( 1 0 0 1 1 x X f x x 8 8 ) 8 ( 0 ) ( 2 0 0 2 2 x X f x x Вычислим 200 )) ( ( ) ( 0 0 X f X f X f Так как ) ( ) ( 0 X f X f , то выполняем дробление шага, полагая: 5 , 0 5 , 0 1 Снова вычисляем координаты следующей точки: 3 4 1 1 x , 4 8 2 x и находим значение 39 ) ( X f Так как опять ) ( ) ( 0 X f X f , то еще уменьшаем величину шага, полагая 25 , 0 5 , 0 5 , 0 . Вычисляем новую точку с координатами 2 25 , 0 4 1 1 x ; 2 25 , 0 8 2 x и значение функции в этой точке 5 ) ( X f . Поскольку условие убывания ) ( ) ( 0 X f X f выполнено, то считаем, что найдена очередная точка минимизирующей последовательности ) 2 ; 2 ( 1 X . Первая итерация завершена. 1 Лекция №6. Метод наискорейшего спуска В методе наискорейшего спуска минимизирующая последовательность k X также строится по правилу 0 ), ( 1 k X f X X k k k k . Однако величина шага k находится в результате решения следующей вспомогательной задачи. На луче 0 ), ( : k k n X f X X E X , выходящем из точки k X и направленным по антиградиенту, введем функцию одной переменной )) ( ( ) ( k k k X f X f и определим k из условия ) ( min ) ( 0 k k k ( 1) Рис. 1. Поиск оптимальной величины шага в направлении антиградиента.. Таким образом, на каждой итерации метода наискорейшего спуска в направлении антиградиента ) ( k k X f S выполняется исчерпывающий спуск. Для решения вспомогательной задачи можно воспользоваться одним из методов одномерного поиска, например, методом поразрядного поиска. 2 Опишем алгоритм метода наискорейшего спуска. Шаг 0. Задать параметр точности 0 , выбрать n E X 0 , положить 0 k Шаг 1. Найти ) ( k X f и проверить условие достижения заданной точности ) ( k X f . Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2. Шаг 2. Определить шаг k , решив вспомогательную задачу 0 min k с использованием алгоритма поразрядного поиска. Найти очередную точку ), ( 1 k k k k X f X X положить 1 k k и перейти к шагу 1. Шаг 3. Завершить вычисления, положив ) ( , * * k k X f f X X |