Вариационные методы поиска экстремума выпуклой функции

Лекция ТТПЭР № 6 Вариационные методы поиска экстремума выпуклой функции Поиск местоположения экстремума Рассмотрим постановку общей задачи оптимизации, критерий оптимальности которой формируется на унимодальной (выпуклой) функции цели f(x), и решение задачи связано с оценкой местоположения её экстремальной, оптимальной точки, например, arg min. Для определённости будем рассматривать функцию цели f(x), как квадратичную. Тогда её производная g(x) = f ’(x) – линейная функция, а задача оптимизации целевой функции f(x) превращается в задачу оценки корня g(x) = 0 её производной. Положим далее, что у функции f (x) требуется определить местоположение её оптимума, который является экстремумом функции. Если у оптимизируемой функции f(x) существует непрерывная производная f (x) , то корень уравнения f ' ( x)  0 будет определять местоположение экстремума функции f (x) . Тогда корни уравнения f ( x)  0 можно вычислять, используя многошаговый метод вложенных оценок, используя схему метода касательных (метод Ньютона). y y* x* x Рис. 6.1 Рассмотрим эту процедуру, называя её поиском, на примере отыскания на плоскости местоположения минимума параболы. b y  y *  ( x  x*)2 ; y  b( x  x*); b  0; 2 x  xi ; y( xi )  yi ; yi  b( xi  x*); Монотонность, а у квадратичной оптимизируемой функции – линейность производной позволяет с помощью её знака определять направление движения поиска. xi 1  xi  1 yi; xi 1  xi  ayi; b a  0; ai  0; (6.1) 1 Рисунок 6.2 Если b < 1, т.е. склоны функции пологие, то а должно быть большим. Если b > 1, т.е. склоны функции крутые, тогда а должно быть маленьким. Рассмотрим теперь 2-х мерный случай x  ( x1 , x2 ) . В этом случае унимодальная оптимизируемая функция может иметь вид параболоида вращения или эллиптического параболоида. Различие между этими пространственными фигурами легко усмотреть в сравнении их линий равного уровня, которые получаются в результате сечения пространственной фигуры плоскостями параллельными координатной плоскости. Рисунок 6.3 Линии равного уровня функции отклика а) в канонической форме Рисунок 6.4 Линии равного уровня b) с пологим склоном по x1 и крутым склоном по x2. В первом случае дифференциальная процедура поиска (5.6) может быть применена поочерёдно по каждой из двух переменных x1 и x2. Это метод Гаусса – покомпонентный поиск. Во втором случае такой подход может привести к расходимости поиска, поскольку крутизна склонов по каждой переменной разная. Здесь следует применять градиентный поиск. xi1  xi  a grad f ( xi ) Название этого метода связано с тем, что определять направление движения поиска в многомерном случае определяет вектор-градиент grad f ( xi ) , компонентами которого являются частные производные по каждой пространственной переменной x1 и x2. Процедуры поиска 2 Здесь направленность поиска связана с дифференциальной оценкой вектора направления (градиента) на экстремум. Поскольку в данном случае поиск экстремума ведётся на выпуклой функции, то градиент даёт гарантированную надёжную оценку направления на экстремум. Рассмотрим два основных подхода к дифференциальному поиску экстремума. Метод градиента Вектор-градиент определяет направление наибольшего возрастания функции качества. В случае поиска минимума ЦФ используется, так называемый, антиградиент: вектор-градиент, все компоненты которого имеют противоположный знак. Поэтому этот метод является оптимальным в том смысле, что он стимулирует движение системы в наилучшем направлении. Метод Ньютона-Рафсона В этом методе, как и в других методах безусловной оптимизации второго порядка, кроме вектора-градиента используется обратная матрица вторых частных производных минимизируемой функции. Методы и Алгоритмы Поисковой Оптимизации Алгоритмы поиска, как и любой алгоритм, является реализацией метода (способа) достижения цели, и представляет собой последовательность целенаправленных операций. Критерием, как и в подавляющем большинстве случаев поиска, является критерий наименьших квадратов. Метод поочередного, покоординатного поиска (Метод Гаусса) Структура данного метода в виде оболочки используется как в алгоритмах нулевого, так и первого порядков. Разница в их реализации только в выборе способа оценки направления движения к оптимуму. Данный метод предполагает поочередную оптимизацию последовательно по каждому регулируемому параметру объекта. Вначале поиск проводится только, например, по первой переменной, затем переходят к следующей переменной и так далее в цикле до полного перебора всех переменных, но до тех пор, пока функция цели не перестанет улучшаться (уменьшаться). Как правило, за один цикл не удается найти искомую оценку с необходимой точностью, соответствующую минимуму функции цели. Поэтому необходимо многократное повторение указанных циклов. Отличительной особенностью метода Гаусса является существенная зависимость от выбора системы координат, поскольку поиск ведётся по каждой переменной независимо от других, т.к. в нём они считаются равноправными. Для этого надо привести целевую функцию к каноническому виду: Процедура первого порядка, называемая методом Гаусса-Зейделя с оценкой градиента, сводится к схеме вида: каждая следующая оценка xi 1 получается переходом из xi в соответствии с решением каждого уравнения системы xi 1, j  xi , j  1 yx ( xi , j ) yx2 j j = 1,…,n (6.2) j независимо друг от друга. Следовательно, оператор рабочего шага (см. (6.1)) имеет вид диагональной матрицы 3 0  a1   A  , 0 a n   Если показатели крутизны склонов целевой функции по каждой переменной существенно различаются, то необходимо двигаться с рабочими шагами разной величины. Если целевая функция по каким-либо причинам не приведена к каноническому виду, например, переменные по условию взаимосвязаны, то поиск должен вестись по всем переменным одновременно. Следовательно, этот метод в подобной ситуации неприменим. Эффективность этого метода также снижается при наличии ограничений. Так что, в большинстве случаев экстремум не может быть достигнут. Градиент целевой функции Известно, что направление, определяющее движение к extr из каждой точки на поверхности унимодальной функции y  f ( x )  f  x1 ,..., xn  , коллинеарно1 вектор-градиенту этой функции:  f f  . . grad f ( x1 ,..., xn )  f ( x1 ,..., xn )   ,..., (6.3) xn   x1 При этом направление движения поиска совпадает с направлением антиградиента (вектора с компонентами противоположного знака к f и, соответственно, имеющего противоположное направление), если ЦФ имеет минимум: знак «минус» в (6.1)-(6.2). Т.о. вектор-градиент определяет направление наилучшего, оптимального изменения (убывания) функции цели. Неполная априорная информация о функции цели Предполагается, что аналитическое выражение ЦФ неизвестно, т.к. в противном случае задача может быть решена аналитически. Если функция не задана аналитически, а представима только экспериментальными значениями в моменты измерений, то градиент аналитически вычислить невозможно. В этом случае градиент может быть представлен через конечные разности в связи с табличным (дискретным) представлением функции: grad f ( x1 ,..., xn )  f ( x1 ,..., xn )   x1 f ,...,  xn f . (6.4)    xi f определяются в окрестности точек наблюдения. Разностные оценки частных производных по каждому фактору определяются при фиксированных значениях остальных переменных: yx   x y   x f  f ( x  x )  f ( x ) (6.5) в равноотстоящих узлах с квантованием по каждой переменной, при этом промежуток квантования можно положить равным единице: x j  1 j . В процедуре поиска удобно положить, что квантование происходит во времени на каждом шаге поиска от xi к xi 1 и приращение по всем переменным можно положить равным единице. 1 Коллинеарность векторов означает, что они расположены на параллельных прямых, но могут быть разнонаправлены. 4 f ( xi )   x f  f ( xi 1 )  f ( xi ) . Градиентный метод поиска Градиентная процедура поиска местоположения экстремума функции записывается в одномерном случае: (6.6) x  R1 , xi 1  xi  ayi/ , где a  const , т.е. x  a * y. В многомерном случае: xi 1  xi  ai Ri  xi  aif  xi  при этом Ri  Ai Ni ; Ai – положительно определённая определяющих величину «рабочего» шага поиска; матрица (6.7) коэффициентов, N i –вектор, например, градиент, определяющий направление движения к экстремуму целевой функции и зависящий от свойств этой функции. Есть виды поиска, в которых «рабочий» шаг определяется как положительная скалярная величина ai. при этом, если у каждого фактора коэффициент рабочего шага индивидуальный, то (6.8) x  Rn , xi 1  xi  A F ( xi ), Метод наискорейшего градиентного спуска Так же как и в случае покоординатного поиска Гаусса структура данного метода в виде оболочки используется как в алгоритмах нулевого, так и первого порядков. Здесь в качестве способа оценки направления движения к оптимуму используется градиент. Суть этого метода сводиться к следующему. После определения наилучшего направления, в предположении о линейности первой производной функции цели, система поиска начинает спуск, т.е. делает шаг в выбранном направлении (по градиенту) до тех пор, пока значения функции не перестанут улучшаться. Т.е., если значение функции цели уменьшается по сравнению с исходным, то делается очередной рабочий шаг в том же направлении, а не вычисляются значения производных, как это имело место в методе градиента. Если же после очередного шага поиска значение функции цели увеличилось по сравнению с предыдущим значением, то спуск прекращается, заново оценивается градиент, и т.д. Как легко заметить, этот метод оказывается более выгодным по сравнению с методом градиента, так как он позволяет выиграть время за счет сокращения объема анализа и снижается трудоёмкость вычислений за счёт уменьшения числа расчётов градиента. Действительно, подробный анализ объекта после каждого рабочего шага, который необходим при оптимизации по методу градиента, здесь проводится, не всегда и часто заменяется однократным замером приращения функции цели за рабочий шаг. Матрица Гёссе целевой функции Зависимость рабочего шага поиска от вторых частных производных по каждой переменной определяется матрицей B обратной к матрице Гёссе G. 5 В дифференциальных методах поиска второго порядка дополнительно используют информацию о вторых частных производных целевой функции в виде обращённой матрицы вторых производных  2 f 1 BG   xi x j  1   ,  1  n (6.9) которая определяет величину «рабочего» шага поиска. Неполная априорная информация об операторе объекта Если функция не задана аналитически, а представима только значениями в опытных точках, то градиент вычислить аналитически невозможно. В этом случае градиент может быть представлен через конечные разности в связи с табличным (дискретным) представлением функции в равноотстоящих узлах значений факторов с квантованием по каждому фактору x j  1 j :   grad f ( x1 ,..., xn )  f ( x1 ,..., xn )   x1 f ,...,  xn f . (6.10)  xi f определяются в окрестности точек наблюдения. Как и в одномерном случае, разностные оценки частных производных по каждому фактору определяются при фиксированных значениях остальных факторов: (6.11) y   y   x f  f ( x  x)  f ( x)  f ( xi 1 )  f ( xi ) здесь обычно полагают, что квантование во времени происходит равноотстоящими узлами и приращение по каждому фактору можно положить равным единице. При отыскании экстремума в условной задаче оптимизации (2.5)–(2.7), градиент преобразованной целевой функции представим так же через конечные разности: gradF ( x1 ,..., xn )  F ( x1 ,..., xn )   x1 F ,...,  xn F (6.12)   Градиентный метод (метод градиентного спуска) Градиентная процедура поиска местоположения экстремума функции записывается в виде линейной процедуры с учётом (2.1), (2.2). В одномерном случае: x  R1 , (6.13) xi 1  xi  ayi/ , где a  const , т.е. x  a * y. В многомерном случае: xi 1  xi  ai Ri  xi  f  xi  (6.14) при этом, если у каждого фактора коэффициент рабочего шага индивидуальный, то x  Rn , xi 1  xi  A F ( xi ), (6.15) 0  a1    где A   , 0 a n   Алгоритм поиска, как и любой алгоритм, является реализацией метода (способа) достижения цели, и представляет собой последовательность целенаправленных действий. Заметим, что при отыскании местоположения максимума функции в процедуре поиска перед градиентом стоит знак «плюс», а при нахождении минимума – знак «минус», т.к. в последнем случае поиск идёт в направлении «антиградиента». 6