Реферат. «Методы оптимизации без ограничений, использующие производные»
1 Санкт-Петербургский государственный политехнический университет Факультет технической кибернетики Кафедра распределённых вычислений и компьютерных сетей Реферат Тема: «Методы оптимизации без ограничений, использующие производные» Выполнил: студент 4-го курса группы 4087 А. Д. Комягин Проверил: проф. Ю. Б. Сениченков Санкт-Петербург 2010 г.
2 1 Введение В данной работе рассматриваются методы отыскания экстремума функции f(x) по всему пространству R n с использованием производных, т.е. при условии, что при поиске экстремальных точек каждая из переменных x 1, x 2. x n данной функции может принимать любое значение между и. Для определённости предположим, что требуется найти минимум функции f(x) в пространстве R n. Допустим также, что f(x) обладает единственным минимумом и что все частные производные, по крайней мере первого порядка, существуют при любом значении x в R n. Таким образом, цель работы заключается в описании процедур систематического получения последовательности векторов, т.е. точек x 0, x 1. x k в R n таких, что f(x 0 ) > f(x 1 ) >. > f(x k ) >. (1) и оценке их эффективности при локализации точек минимума. Методы, соответствующие условию (1), называются методами спуска или релаксационными. При получении таких последовательностей точек в качестве начальной точки x 0 может быть взята любая точка в R n. При этом нужно использовать любую имеющуюся информацию о поведении функции f( ), с тем чтобы выбрать x 0 не слишком далеко от точки минимума. После выбора начальной начальной точки, прежде чем получать следующую точку, нужно принять два решения: 1. необходимо выбрать направление, вдоль которого предполагается расположить следующую точку, 2. необходимо определить величину шага в выбранном направлении. При любом методе спуска последовательность подчиняется условию x k+1 = x k + t k d k, k = 0, 1. где d k есть направление, а t k d k величина шага. Если d k нормализовано, d k = 1, то величина шага будет равна t k. Изменяя процедуру выбора d k и t k, можно варьировать методы спуска. Направление d в точке x называется приемлемым, если f(x), d < 0. (2) 2
3 Механизм образования последовательности точек и его эффективность в локализации точки минимума сильно зависят от минимизируемой функции, а также от информации, которая может быть использована для определения следующей точки следующего прогноза точки минимума. Согласно [1], эти методы можно разбить на три группы: 1. методы, использующие только значения функций, называемые прямыми методами; 2. методы, использующие, кроме того, первые производные; 3. методы, которые дополнительно к этому требуют знания вторых производных. Производные могут вычисляться аналитически или численно. В данной работе рассматриваются последние две группы методов. Они вырабатывают следующую точку согласно условию: x k+1 = x k t k A k f(x k ). Матрица A k может являться постоянной матрицей или зависеть от ранее полученных точек и вектор-градиента. Методы оптимизации без ограничений рассматриваются на примере квадратичных функций f(x) = a + 2b T x + x T Qx по двум причинам. Первая заключается в том, что если метода не пригоден для квадратичных функций, то маловероятна его пригодность для функций с более сложной структурой. Другая причина заключается в том, что любую неквадратичную функцию можно аппроксимировать квадратичной функцией, если ограничиться в разложении в ряд Тэйлора членами не выше второго порядка. При этом минимум может быть получен минимизацией последовательности квадратичных функций, аппроксимирующих исходную функцию относительно точек, последовательно приближающихся к точке истинного минимума. 2 Градиентные методы 2.1 Алгоритм Обозначим вектор-градиент в точке x k через r k, r k = f(x k ). 3
4 Из разложения функции f(x) в ряд Тэйлора видно, что r k является приемлемым разложением. Кроме того, это же разложение показывает, что если выбрать x x k имеющим то же направление, чтоб и r k, то f(x) в окрестности x k будет иметь наискорейшее убывание. Градиентным методом называется метод, согласно которому точка x k+1 выбирается по отношению к x k в направлении r k : x k+1 = x k tr k, где t некоторая положительная скалярная величина. Таким образом, градиентный метод сводится к одномерной задаче поиска. В различных вариантах градиентного метода применяют различные способы выбора скаляра t. Этот выбор может также зависеть от того, насколько близко точка x k подошла к точке минимума. В том случае, когда t определяется путём решения одномерной задачи минимизации min t>0 f(x k tr k ), соответствующий вариант градиентного метода называется оптимальным градиентным методом. Рассмотрим следующую задачу минимизации: минимизировать где f(x) = 1 2 xt Qx, (3) Q T = Q > 0. Матрица Q положительно определённая, и, следовательно, функция положительна при всех x и f(0) = 0. Минимум этой функции: x = 0. Так как r = f(x), то можно показать, что в соответствии с градиентным методом следующая точка будет являться точкой минимума только в том случае, если (r T Q 1 r)(r T Qr) = (r T r) 2. Однако, если производить поиск по направлению Q 1 r, то минимум может быть достигнут за один шаг при t = 1. Следовательно, в данном случае оптимальный градиентный метод оказывается хуже, чем метод, согласно которому поиск производится в направлении Q 1 r. При оптимальном градиентном методе приближение к точке минимума происходит зигзагообразно и, в общем случае, не приводит к точке минимума (рис.1). Пусть вектор p k = x k+1 x k. Легко показать, что при оптимальном градиентном методе вектор p 0 будет параллелен p 2, а p 1 p 3. 4
5 Рис. 1: а) Оптимальный градиентный метод. Зигзагообразная траектория приближения к точке минимума. б) Вычисление x 1 и p 1 при оптимальном градиентном методе 2.2 Ускорение (метод параллельных касательных) Ранее было отмечено, что при двухмерной квадратичной функции f(x) точка минимума x может быть найдена точно. Для этого, найдя оптимальным градиентным методом x 1 и x 2 по известной x 0, надо прекратить применение оптимального градиентного метода и найти минимум значения функции путём поиска вдоль луча, определяемого точками x 0 и x 2 (см. рис.1). Основываясь на этом, можно ускорить обычный градиентный метод. Для этого будем обозначать точки x 0, x 1, x 2. как x 2j 4, x 2j 2, x 2j 1, j = 2, 3. и спользовать следующий алгоритм: 1. При заданном x 0 выберем следующую точку оптимально в направлении r 0 (назовём эту точку x 2, т.е. x 2k при k = 1). 2. При заданных x 2k 2 и x 2k выберем x 2k+1 оптимально в направлении r 2k. Тогда в качестве x 2k+2 выбирается оптимальная точка на направлении x 2k+1 x 2k 2 (шаг ускорения). 3. Повторить шаг 2, увеличив k на единицу. 4. Повторить процедуру заново через 2n 1 шагов, где n = dim x. Рис.2 иллюстрирует описанную процедуру. 5
6 2.3 Сходимость Рис. 2: Метод параллельных касательных При заданной целевой функции f(x) = x T Qx/2 градиентный метод не всегда даёт сходящуюся последовательность точек или даже последовательность с монотонно убывающими значениями функции, если только Q не является положительно определённой или, иными словами, если только поверхности постоянного значения функции не образуют семейства поверхностей, замкнутых вокруг начала. Формальное доказательство этого утверждения приведено в [1]. 2.4 Скорость сходимости Если f(x) = x T Qx/2, где Q T = Q > 0, то можно показать, что если x следующая за x точка, получаемая оптимальным градиентным методом, то 0 f(x ) f(x) (λ 1/λ n 1) 2 (λ 1 /λ n + 1), (4) 2 где λ 1 и λ n соответственно наибольшие и наименьшее собственные значения матрицы Q. Тогда при достаточно больших k зависимость f(x k ) от k определяется геометрической прогрессией f(x k ) Ca k, где C = f(x 0 ), а a некая постоянная величина в пределах от 0 до (λ 1 /λ n 1) 2 /(λ 1 /λ n + 1) 2. Введём понятие порядка сходимости как следующую величину: lim k ln f(x k ) ln f(x k+1 ). 6
7 Так, например, оптимальный градиентный метод имеет порядок сходимости, равный 1. Такой порядок сходимости означает, что значения целевой функции убывают в основном по закону геометрической прогрессии. 3 Метод сопряжённых направлений Два вектора x и y в пространстве R n называют Q-сопряжёнными, если x T Qy = 0. Если вектор x сопряжён с любым вектором подпространства M пространства R n, то x называют сопряжённым с подпространством M. Рассмотрим квадратичную целевую функцию f(x) = a, x + x T Qx/2, где Q T = Q > 0. Метод сопряжённых направлений вырабатывает последовательность таких точек x 0, x 1. что p k, Qp j = 0 для всех k, j, k j. Значение такой последовательности точек при минимизации квадратичной целевой функции основывается на том факте, что если целевая функция f( ) на подпространстве M пространства R n достигает минимума в точке x и та же функция в подпространстве N таком, что M N, достигает минимума в точке y, то вектор y x сопряжён с подпространством M. При заданном множестве из n Q-сопряжённых векторов минимум квадратичной функции f(x) (где Q её матрица Гессе) может быть найден не более чем за n шагов от любой точки, если выполнить ряд одномерных поисков вдоль каждого из сопряжённых векторов. Обычно множество сопряжённых векторов заранее не бывает известным. Образование сопряжённых векторов и одномерная минимизация, как правило, осуществляются совместно. Примером этого является рассматриваемый в следующем разделе метод сопряжённых градиентов, где сопряжённые векторы образуются из вектор-градиентов. 4 Метод сопряжённых градиентов Метод сопряжённых градиентов является частным случаем метода сопряжённых направлений. Первоначально он был разработан Хестенсом и Штифелем (1952) применительно к решению системы совместных уравнений с положительно определённой матрицей коэффициентов. 7
8 Пусть функция f(x) квадратичная с положительно определённой матрицей Гёссе Q. При неквадратичной целевой функции матрица Q должна быть заменена на матрицу Гёссе. Так как матрица Гёссе изменяется при получении каждой новой точки, то для того, чтобы метод был приемлемым, необходимо, чтобы матрицы Гёссе неквадратичных функций менялись не очень быстро. В алгоритме, основывающемся на работе Флетчера и Ривса, вместо использования r k в качестве направления спуска, метод сопряжённых градиентов преобразует вектор-градиент, взятый с обратным знаком, в направление d k, Q-сопряжённое с ранее найденными направлениями d. Эти векторы d вырабатываются следующим образом: d k = r k + β k 1 d k 1, 1 k, d 0 = r 0, где β k 1 выбирается так, чтобы сделать d k Q-сопряжённым с d k 1. Другими словами, β k 1 = r k, Qd k 1 / d k 1, Qd k 1. Сдледующая точка x k+1 отыскивается из x k с помощью одномерного поиска в направлении d k. Для обеспечения минимизации функции в этом направлении, t k = r k, d k / d k, Qd k. Процедуру метода сопряжённых градиентов можно сформулировать следующим образом: 1. Выбрать начальную точку x Определить направление d 0 = r x 1 = x 0 + t 0 d 0, где t 0 = r 0, d 0 / d 0, Qd Определить p 0 = x 1 x 0 = t 0 d 0 и вычислить r 1 5. Найти новое направление поиска d 1 = r 1 +β 0 d 0, где β 0 = r 1, Qd 0 / d 0, Qd 0 = r 1, r 1 / r 0, r 0. При этом будет исключено умножение d 0 на Q. 6. В общем случае, достигнув x i, вычислить r i и определить d i = r i + β i 1 d i 1, где, учитывая ортогональность и ортогональность r k с d k 1, β i 1 = r i, r i / r i 1, r i 1 8
9 7. Найти x i+1 из соотношения где t i = r i, d i / d i, Qd i. x i+1 = x i + t i d i, Необходимо заметить, что вычисление коэффициентов не требует знания матрицы Гёссе в явном виде. Если матрица Гёссе неизвестна, то одномерный поиск (шаг 7) надо осуществлять численно. 5 Метод Ньютона-Рафсона 5.1 Описание Перейдём к рассмотрению методов группы 3. Здесь, в отличие от ранее рассмотренных методов группы 2, при получении последовательности точек используются вторые частные производные. Опишем метод, являющийся прямым обобщением метода Ньютона отыскания корня уравнения φ(t) = 0, где φ(t) функция скалярной переменной. В этом методе последовательность вырабатывается формулой x k+1 = x k H 1 (x k ) f(x k ) (5) при условии, что существует обратная матрица H 1 (x k ). Таким образом, это градиентный метод с вектор-градиентом, модифицированным вторыми частными производными функции. Если f( ) квадратичная и равна f(x) = a T x + x T Qx/2, где Q положительно определенная матрица, то, исходя из произвольной точки x 0, с помощью (5) можно получить следующую точку: x 1 = x 0 Q 1 (a + Qx 0 ) = Q 1 a. Эта точка является точкой минимума функции f(x), т.е. точка минимума может быть найдена за один шаг. Если для выработки последовательности используется (5), то метод называется методом Ньютона- Рафсона. Однако этот метод требует затраты значительного времени на вычисление вторых производных функции f и обращение (nxn)-матрицы Гёссе. 5.2 Модификация Метод Ньютона-Рафсона сходится не всегда: последовательность точек, вырабатываемая (5), расходится, если матрица Гёссе не является положительно определённой. 9
10 Для этого метода Гринстад предложил способ модификации неположительно определённой матрицы Гёссе. Он вычисляет собственные значениями собственные векторы матрицы Гёссе H(x k ) и выражает эту матрицу в виде H k (x k ) = P k Λ k Pk T, где P k ортогональная матрица, столбцами которой являются собственные векторы, а Λ k диагональная матрица, составленная из собственных значений. Одной из причин того, что метод Ньютона-Рафсона не сходится, могут быть отрицательные собственные значения матрицы H k. Учитывая это, Гринстад берёт вместо матрицы Λ k матрицу ˆΛ k, составленную из абсолютных величин собственных значений, строит матрицу Ĥk(x k ) = P k ˆΛk Pk T и качестве следующего направлениями для поиска использует Ĥ 1 k rk = P k (ˆΛ k ) 1 P T k r k. Очевидным недостатком этого метода является необходимость решения задачи о собственных значениях. 5.3 Скорость сходимости Несмотря на указанную возможность расходимости метода Ньютона- Рафсона, в достаточно малой окрестности минимума он имеет порядок сходимости 2. Это, грубо говоря, означает, что число значащих цифр удваивается после каждой итерации. Если f является квадратичной функцией, то, как указывалось ранее, x можно получить за один шаг. В противном случае, надо каждый раз производить обращение матрицы Гёссе, что связано (особенно при больших n) с громоздкими вычислениями. Если же производить повторные обращения матрицы Гёссе не на каждом шаге, а через определённо число шагов, то это приведёт к уменьшению скорости сходимости. Поскольку при большом отклонении начального приближения x 0 от истинного значения минимума x метод Ньютона-Рафсона может не сходится, можно в начале вычислений применять какой-либо вариант градиентного метода. Когда скорость сходимости градиентного метода существенно уменьшится, можно осуществить переход к методу Ньютона- Рафсона. 10
11 6 Метод Дэвидона (метод переменной метрики) 6.1 Основные положения Рассмотрим метод, предложенный Дэвидоном и позволяющий обойти трудности, связанные с матрицей Гёссе в методе Ньютона-Рафсона. Согласно [1], в тех случаях, когда есть возможность вычисления градиентов, этот метод оказывается наиболее эффективным. Будем считать, что целевая функция является квадратичной: f(x) = a T x + x T Qx/2, Q > 0. (6) Её точка минимума x равна: x = Q 1 a. Зная вектор-градиент r в любой точке x и обратную матрицу Q 1, можно вычислить точку минимума x за один шаг: x = Q 1 (r Qx) = x Q 1 r. (7) Оптимальным направлением спуска является не r, а Q 1 r. Также Q 1 r является градиентом функции f, когда метрика задана выражением x, Qx 1/2. При неквадратичной функции f метод близок к градиентному с метрикой [x T H(x)x] 1/2. При этом матрица, обратная матрице Гёссе, строится постепенно, что и определяет название метода метод переменной метрики. Когда Q известно, это построение проводится так же, как и в методе Ньютона-Рафсона в случае квадратичной функции. Когда Q неизвестно, в методе Дэвидона производится последовательная оценка Q 1 построением последовательности матриц, являющихся обратными для матрицы Q на всё больших и больших подпространства R n. Общий алгоритм метода Дэвидона выглядит следующим образом: x k+1 = x k t k H k r k, (8) H k+1 = H k H ky k H k y k y k, H k y k + pk p k, k = 0, 1. (9) y k, p k где H 0 произвольная положительно определённая матрица, а p k = x k+1 x k и y k = r k+1 r k. t k должно минимизировать функцию f(x) на луче H k r k. Для квадратичной формы (6) t k будет определяться следующим выражением: t k = rk, H k r k, k = 0, 1. (10) H k r k, QH k r k 11
12 В [1] доказывается корректность этого метода на основе доказательства следующих утверждений: 1. является последовательностью положительно определённых матриц; 2. векторы p 0, p 1. образуют множество Q-сопряжённых векторов; 3. на многообразии, натянутом на p 0, p 1. p k 1, матрица H k будет равна Q 1 ; 4. при последовательном построении матрицы Q 1 влияние произвольного начального приближения H 0 уничтожается. 6.2 Влияние масштабирования Несмотря на то, что метод переменной метрики является достаточно эффективным при наличии производных целевой функции, могут возникать трудности, являющиеся следствием того, что матрицы H становятся особенными. Если целевая функция f(x) масштабируется умножением на постоянную величину α, т.е. если минимизируется не f(x), а αf(x), то векторградиенты и векторы y также оказываются умноженными на α. Если x масштабируется умножением на β, то векторы p также умножаются на β, а градиент и векторы y умножаются на 1/β. Анализ проблемы в [2] показывает, что для предотвращения вырождения матриц надо масштабировать функцию f и x так, чтобы в начальной точке соблюдалось приближённой равенство p 0 / y 0 1. В случае необходимости это же следует выполнять и в дальнейшем. 7 Метод экспоненциальной релаксации Рассмотрим более общую схему градиентных методов: x k+1 = x k A k (H k, t k ) f(x k ), (11) где A k матричная функция H k. Будем считать, что в некоторой ξ k - окрестности точки x k исходная, в общем случае 12
13 нелинейная, функция f достаточно точно аппроксимируется квадратичной функцией f(x) = 1/2 H k x, x b k, x + c k, где H k симметричная, не обязательно положительно определённая матрица. Без существенного ограничения общности можно считать, что b k = 0, c k = 0. Тогда метод (11) принимает вид: x k+1 = x k A k H k x k. Матричная функция A k должна выбираться так, чтобы выполнялись условия релаксационности процесса f(x k+1 ) < f(x k ) и чтобы при этом норма x k+1 x k ограничивалась сверху только параметром ξ k, характеризующим область справедливости локальной квадратичной аппроксимации. Функцией релаксации метода (11) называется скалярная функция R t (λ) = 1 A(λ, t)λ; λ, t R. В дальнейшем, для сокращения записи, индекс t в некоторых случаях будет опускаться. В [3] доказывается, что имеет смысл рассматривать в основном зависимости R t (λ) 1(t 0). При этом с помощью параметра t можно регулировать норму вектора продвижения в пространстве управляемых параметров с целью предотвращения выхода из области справедливости локальной квадратичной модели. Рассмотрим зависимость вида R(λ) = exp( λt)(t > 0). (12) Эта функция обобщает ранее рассмотренные методы и является в определённом смысле оптимальной. Например, разлагая экспоненту в ряд Тэйлора и ограничиваясь двумя первыми членами разложения, можно получить функцию релаксации для градиентного спуска: exp( λt) 1 λt. Конечная схема метода с экспоненциальной релаксацией, согласно [3], имеет вид: x k+1 = x k A k (H k, t k ) f(x k ); (13) A(H, t) = t Величина шага t k определяется равенством: 0 exp( Hτ)dτ. (14) t k = arg min t 0 f[x k A k (H k, t k ) f(x k )]. (15) 13
14 Можно доказать, что приведённый выше алгоритм сходится почти при тех же ограничениях на минимизируемый функционал, что и метод оптимального градиентного спуска, имея в определённых условиях существенно более высокую скорость сходимости. Более того, в [3] установлена его квадратичная скорость сходимости, характерная для методов ньютоновского типа. 8 Программное обеспечение Метод сопряжённых градиентов реализован в следующих программах: 1. программа UMCGG пакета IMSLM (существует также версия с двойной точностью DUMCGG); 2. программа E04DGF пакета NAG вычисления осуществляются с двойной точностью; 3. программа CG пакета NAPACK (двойная точность); 4. программа A22 пакета NASHLIB. Метод Ньютона-Рафсона реализован в программах UMIDH и UMIAH пакета IMSLM. В последней вторые производные задаются пользователем явно. Существуют версии с двойной точностью DUMIDH и DUMIAH. Программы, использующие метод переменной метрики: 1. LBFGS_UM пакета OPT двойная точность; 2. UMING пакета IMSLM, версия с двойной точностью DUMNIG; 3. MNG пакета PORT, версия с двойной точностью DMNG; 4. программа A21 пакета NASHLIB. Подробное описание описанных программ доступно в [4]. 14
15 Список литературы [1] Масанао Аоки Введение в методы оптимизации Москва, «Наука», [2] И.Г. Черноруцкий Методы оптимизации в теории управления Санкт-Петербург, «Питер», [3] И.Г. Черноруцкий Методы оптимизации и принятия решений Санкт-Петербург, «Лань», [4] NIST Guide to Available Mathematical Software 15
16 Содержание 1 Введение 2 2 Градиентные методы Алгоритм Ускорение (метод параллельных касательных) Сходимость Скорость сходимости Метод сопряжённых направлений 7 4 Метод сопряжённых градиентов 7 5 Метод Ньютона-Рафсона Описание Модификация Скорость сходимости Метод Дэвидона (метод переменной метрики) Основные положения Влияние масштабирования Метод экспоненциальной релаксации 12 8 Программное обеспечение 14 16