18527

Оптимизация. Классификация методов оптимизации

Лекция

Информатика, кибернетика и программирование

Лекция 7 Оптимизация Сформулируем задачу оптимизации как задачу поиска экстремума целевой функции ФР. Классификация методов оптимизации 1. По числу параметров: одномерная оптимизация; многомерная оптимизация. 2. По использованию производных:

Русский

2013-07-08

329 KB

142 чел.

Лекция 7

Оптимизация

Сформулируем задачу оптимизации как задачу поиска экстремума целевой функции Ф(Р).

Классификация методов оптимизации

1. По числу параметров:

   - одномерная оптимизация;

   - многомерная оптимизация.

2. По использованию производных:

   - методы нулевого порядка (прямые методы);

   - методы первого порядка (градиентные методы);

- методы второго порядка.

  •  . . .

Целевую функцию Ф(Р) будем считать унимодальной.

Определение унимодальности функции

Предположим, что f - действительная функция, определенная на [0,1]. Предположим, далее, что имеется единственное значение х, такое, что f() — максимум f(x) на [0,1], и что f(x) строго возрастает для x и строго убывает для  ≤ x. Такая функция называется унимодальной: для ее графика имеются три возможные формы:

Рис. 1.Графики унимодальной функции

Заметим, что унимодальная функция не обязана быть гладкой или даже непрерывной.

Задачу оптимизации сформулируем следующим образом:

найти множество абсцисс x1, x2... хk, в которых вычисляется функция, такое, что оптимальное значение f лежит при некотором i в интервале хi-1 х ≤ хi+1 (этот интервал называется интервалом неопределенности).

Алгоритм выбора абсцисс xi (i=1,…,k) называется планом поиска. Если известно только то, что f унимодальная, то какова оптимальная стратегия для нахождения х? При заданном количестве вычислений функции оптимальным планом поиска будет тот, который приводит к наименьшему интервалу неопределенности.

Большинство методов многомерной оптимизации сводится к задаче одномерной оптимизации.

Рассмотрим три известных метода одномерной оптимизации:

1. Метод дихотомии (деления отрезка пополам)

Пусть имеется целевая функция, изображенная на рис.2. Необходимо определить экстремум функции на участке (a, b)

Делим ось абсцисс на четыре равные части и вычисляем значение целевой функции в пяти точках, далее выбираем минимум из пяти найденных значений. Очевидно, что экстремум функции лежит в границах участка (a', b') прилегающего к точке найденного минимума. Интервал поиска сужается в два раза.

Если минимум находится в точке а или b, то интервал сужается в четыре раза.

Полученный интервал вновь разбиваем на четыре равные части. Поскольку  значения целевой функции в трех точках были вычислены на предыдущем этапе, следующий этап требует вычисления целевой функции в двух точках.

Ф(Р)       

                

                                              р

 a      a'       b'     b

 0     1       2 3     4

  Рис. 2. Иллюстрация метода дихотомии

2.  Метод Фибоначчи

Определим координату точки х относительно интервала [а, b] как число, равное (х-а) / (b-а). Таким образом, а имеет по отношению к интервалу [a,b] координату 0, b - координату 1, а средняя точка — координату 1/2.

Пусть F0 = F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8,…, Fk = Fk-1+Fk-2. Числа Fi – числа Фибоначчи. Оптимальная стратегия последовательного поиска максимума называется поиском Фибоначчи, поскольку она тесно связана с этими числами. При оптимальной стратегии выбирают xk-1 = Fk-2/Fk и xk = Fk-1/Fk. Какой бы из интервалов [0, xk] или [xk-1,1] не стал суженным интервалом неопределенности, унаследованная точка будет иметь по отношению к новому интервалу одну из двух следующих координат: Fk-3/Fk-1 или Fk-2/Fk-1. Тогда в качестве xk-2 выбирается точка, имеющая по отношению к новому интервалу другую из этих координат. Используя

f(xk-2) и значение функции, унаследованное от прежнего интервала, можно еще сократить интервал неопределенности и передать в наследство  одно  значение  функции.

На последнем шаге мы придем к некоторому интервалу неопределенности [а,b], причем средняя точка будет унаследованной от  предыдущего  шага.   

Тогда  в  качестве  х1 выбирается точка с относительной координатой ½+ε, и окончательным интервалом неопределенности будет либо [0, ½], либо [½, 1] относительно [а, b].

На первом шаге длина интервала неопределенности уменьшилась с 1 до Fk-1/Fk. На последующих шагах уменьшение длин интервалов   выражается   числами

Fk-2/Fk-1, Fk-3/Fk-2,…, F2/F3, F1/F2(1+2ε).

Таким образом, длина окончательного интервала неопределенности равна (1+2ε)/Fk. Пренебрегая ε, заметим, что асимптотически 1/Fk равно rк при k→∞, где

                         r = (√5 – 1)/2 ≈ 0.6180                                               (1)

Заметим, что асимптотически, для больших k каждый шаг поиска Фибоначчи сужает интервал неопределенности с коэффициентом 0.6180. Этот результат нужно сравнить с 0.5, коэффициентом сужения интервала неопределенности в методе бисекции для нахождения   нуля   функции.

3. Метод золотого сечения

Для больших значений k координаты точек xk-1 и xk близки соответственно к 1-r ≈ 0.3820 и r ≈ 0.6180, и старт с этих значений близок к оптимальной стратегии. Чтобы понять, как продолжать дальше, предположим (для определенности), что f(0.3820)>f(0.6180). Тогда, как мы знаем,  находится в интервале [0, 0.6180]. Следовательно, нужно вычислять f в точках 0.3820*0.6180 и 0.6180*0.6180. Но, поскольку 0.6180*0.6180 ≈ 0.3820 ≈ xk-1, то в этой точке f уже известна. Таким образом, на каждом шаге, начиная со второго, требуется лишь одно вычисление функции, и каждый шаг уменьшает длину интервала неопределенности с коэффициентом 0.6180. В противоположность поиску Фибоначчи, здесь не нужно фиксировать число k до начала поиска.

Известно, что "золотое сечение" отрезка (a, b) это такое сечение, когда отношение r длины всего отрезка (a, b) к большей части (a, c) равно отношению большей части (a, c) к меньшей (c, b).

a_______________c_________b

Нетрудно показать, что r выражается формулой (1). Поэтому, при больших k метод Фибоначчи превращается в метод золотого сечения. 

4. Метод удвоения шага

Идея метода заключается в поиске направления убывания функции и движения в этом направлении с возрастающим шагом при удачном поиске.

Алгоритм:

  1.  выбираем начальную координату Р0  целевой функции Ф(Р), минимальную величину  шага h0 и направление поиска;
  2.  вычисляем значение функции в  точке Р0;
  3.  делаем  шаг и вычисляем значение целевой функции в следующей точке.

Если значение функции меньше, чем на предыдущем шаге, то делаем следующий шаг в этом же направлении, увеличив его вдвое.

Если значение функции больше чем на предыдущем шаге, то меняем направление поиска и начинаем двигаться в этом направлении с начальным значением шага h0.

Примечание: предложенный алгоритм может быть модифицирован.

Интерполяция целевой функции

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

Рассмотрим пример интерполяции. Пусть за n шагов интервал поиска оптимума сужается.

  Рис. 3 Интерполяция

Составим уравнения для точек  и :

                                                (2)

                                               (3)

В этих уравнениях неизвестны коэффициенты a, b и c. Поэтому необходимо еще одно уравнение. Возьмем случайную точку  внутри интервала :

                                               (4)

Решая систему уравнений (2), (3) и (4) найдем коэффициенты a, b, c.

Решив уравнение   найдем точку экстремума функции Ф(рx)

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

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

Методы второго порядка используют вторые производные и их применение весьма ограничено из-за трудностей вычисления вторых производных.

Методы нулевого порядка

Простейшим методом нулевого порядка является метод покоординатного спуска, где в качестве векторов Sj последовательно выбирают единичные координатные векторы. Основная идея метода состоит в том, что на каждом шаге фиксируются все переменные кроме одной, которая выбирается так, чтобы минимизировать. Геометрическая интерпретация данного метода показана на рис 4, где изображены линии уровня минимизированной функции и траектория движения рабочей точки от начальной точки поиска P0 =(p1,0 , p2,0) к оптимальной.

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

Одним из недостатков рассмотренного метода является  зигзагообразный характер движения к точке минимума, что значительно замедляет его сходимость. Рассмотрим класс методов нулевого порядка, которые обладают более высокой скоростью сходимости, а при минимизации квадратичной функции позволяют найти минимум не более чем за  m итерации.

Эти методы основаны на использовании сопряженных направлений. Для данной симметричной матрицы А порядка m направления  S1,S2 ….Sr  (r<m)  называются сопряженными, если Si линейно независимы  и

Si T А   Sj = 0 для всех ij

Основным свойством сопряженных направлений, позволяющим эффективно использовать их для решения задачи минимизации, является следующее. Пусть задана квадратичная функция вида

Ф(Р)=Вт Р+0,5РтАР,

где А- положительно определенная симметричная матрица, и m сопряженных направлений S1,S2 ….Sm (как положительному, так и отрицательному) найдем минимум Ф(Р).

Различные методы минимизации, использующие сопряженные направлении, отличаются в основном способом определения этих направлений. Опишем один из таких способов для произвольных квадратичных функций. Этот способ позволяет по данным r<m сопряженным направлениям построить новое сопряженное направление.

Пусть S1,S2 ….Sr , r<m,- сопряженные направления. Предположим, что P′ = (p1, p2, …,pm),

P′′ = (p′′1, p′′2, …,p′′m),получены путем минимизации Ф(Р) по каждому из направлений S1,S2 ….Sr из различных начальных точек и  Ф(Р′) > Ф(Р′′). Тогда направления S1,S2 ….Sr,Sr+1 , где Sr+1 = P′′-P′, являются сопряженными.

Точки P′′,P′ могут быть получены следующим образом.

Пусть P1 =(p1,1 , p2,1… pm,1 ) – произвольная начальная точка. Допустим, что по этой точке минимизируя Ф(Р) по каждому из направлений S1,S2 ….Sr, мы определяем точку P′. Если эта точка не является оптимальной, то всегда можно найти такую точку P2 =(p1,2 , p2,2… pm,2), что Ф(Р′)>Ф(P2).Выполнив для точки P2 тоже, что и для P1, мы получим точку Р′′, причем, так как  Ф(P2)>Ф(Р′′), то Ф(Р′)>Ф(P′′).

Процедура построения  для двумерного случая иллюстрируется на рис 5

Рис.5 Метод сопряженных направлений (двумерный случай)

Здесь Р1 и S1 – заданные  исходная точка и первое направление. Точка Р′ получается путем минимизации функции вдоль прямой, проходящей через точку Р1 в направлении S1 .Минимум функции может быть найден из произвольной точки Р3 за две минимизации функции вдоль полученных сопряженных направлений S1 и S2  .

Рассмотренный метод построения дополнительного сопряженного направления лежит в основе следующего алгоритма сопряженных направлений.

Шаг 0.Выбрать начальную точку Р00  и произвольное направление S1 ≠0 (это направление может совпадать, например, с одним из координатных направлений).Положить k=1.

Шаг 1. Определить точку Р к0 путем минимизации вдоль прямой, проходящей через точку Р к0 - в направлении Sk.

Шаг 2. Определить точку Р к1  такую, что Ф(Р к1 ) < Ф(Р к0 ) , используя одну итерацию метода покоординатного спуска. Если такую точку найти не удается, то остановиться, иначе перейти к следующему шагу.

Шаг 3. Положить i=1. Определить точку Р кi+1 путем минимизации функции вдоль прямой, проходящей через точку Р кi в направлении Si.

Шаг 4.Положить i=i+1.  Если  i<=k, то перейти к шагу 3, иначе – к шагу 5.

Шаг 5.Положить S k+1 =  Р кk+1 - Р к0  и к=к+1. Перейти к шагу 1.

Данный алгоритм останавливается тогда, когда ни по одной из координат не удается получить уменьшения функции Ф(Р). Это, очевидно, произойдет в некоторой точке Р к0 , в которой градиент минимизируемой функции равен нулю: т.е. выполняется необходимое условие оптимума.

Для квадратичной функции остановка алгоритма произойдет не позже, чем через m итераций, когда будут определены  m сопряженных направлений.

В случае минимизации функции общего вида с помощью данного алгоритма вычисления сопряженных направлений невозможно. Однако,  можно представить себе, что вычисляемые направления  являются сопряженными для некоторой квадратичной функции, которая аппроксимирует Ф(Р). При приближении к экстремуму такая аппроксимация становится, как правило, все более точной, что устраняет зигзагообразное движение, характерное для метода покоординатного спуска. Следует отметить, что при минимизации функции общего вида данный алгоритм обычно повторяют сначала через каждые m итераций.

Методы первого порядка

Одним из наиболее известных методов первого порядка является метод наискорейшего спуска Коши. В данном методе в качестве вектора Sj  , определяющего направление поиска, выбирается антиградиент минимизируемой функции, т.е. вычисления производится по формуле

Метод основан на том факте, что направление, определяемое антиградиентом функции, является направлением наиболее быстрого убывания функции в окрестности Рj .

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

Рис. 6 Метод наискорейшего спуска Коши.

Наиболее перспективными методами первого порядка являются методы, основанные на использовании сопряженных направлений. Как уже отмечалось, минимизация  квадратичной функции по сопряженным направлениям позволяет получить  её минимум не более, чем за  m шагов. Отличительной особенностью этих методов является использование информации о предыдущих направлениях поиска при определении очередного направления. Рассмотрим два наиболее распространенных метода, отличающихся способом определения сопряженных направлений.

Метод Флетчера-Ривса.

Шаг 0. Выбрать исходную точку Р0 и вычислить . Положить k=0.

Шаг 1.Определить точку Рk+1 путем минимизации функции Ф(Р) в направлении Sk .

Шаг 2. Вычислить . Если , то остановиться, иначе перейти к шагу 3.

Шаг 3.Вычислить новое направление по формуле    

              

                               (5)

где    - норма вектора . Положить k=k+1 и перейти к шагу 1.

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

Для функции общего вида алгоритм рекомендуется восстанавливать через каждые km+1 итерацию, т.е. выбирать , не по формуле (5).

Рассмотрение методов первого порядка закончим описанием наиболее эффективного, по мнению ряда исследователей, алгоритма минимизации, предложенного Флетчером и Пауэллом. Алгоритм (иногда его называют алгоритмом с переменной метрикой) широко используется и обладает хорошей вычислительной устойчивостью. Недостатком алгоритма является необходимость хранения в памяти ЭВМ матрицы размером mxm, что может привести к трудностям его использования на ЭВМ с малым объемом оперативной памяти для решения задач большой размерности.

Метод Флетчера-Пауэлла.

Шаг 0. Выбрать исходную точку Р0 и вычислить . Положить H0 =I (I –единичная матрица размером mxm) и k=0.

Шаг 1.Определить точку Рk+1 путем минимизации функции Ф(Р) в направлении Sk .

Шаг 2. Вычислить . Если , то остановиться, иначе перейти к шагу 3.

Шаг 3. Положить

где

Вычислить новое направление по формуле    

Положить k=k+1 и перейти к шагу 1.

При минимизации положительно определенной квадратичной формы направления  S1,S2 ….Sm-1 оказываются  сопряженными относительно матрицы А, что обеспечивает сходимость метода в данном случае за m итераций. Кроме того, в данном алгоритме происходит обращение матрицы вторых частных производных в точке минимума, т.е. Hm=A-1 .

Использование метода Флетчера–Пауэлла для минимизации квадратичной функции приводит к построению  точно такой же последовательности  векторов Pj   и Sj , как и в методе Флетчера–Ривса. Однако, в более общем случае, метод переменной метрики быстрее. Это можно объяснить тем, что в отличии от метода  Флетчера – Ривса, в методе Флетчера – Пауэлла при определении очередного направления учитывается не одно, а все предыдущие направления.

Методы второго порядка

Рассмотренный метод наискорейшего спуска основан на линейной аппроксимации ФL(P) минимизируемой  функцией Ф(Р) в точке Рj :

                         (6)

Данная аппроксимация является довольно точной в окрестности точки Рj , поэтому движение в направлении антиградиента локально является наиболее выгодным для минимизации Ф(Р).

Методы второго порядка так же основаны на разложении минимизируемой функции в ряд Тейлора, однако они используют на один член разложения больше. Типичным представителем методов второго порядка является метод Ньютона. Идея данного метода основана на возможности аналитического вычисления точки минимума квадратичной функции. При этом необходимые формулы вычисляют следующим образом.

Разлагая Ф(Р) в точке  Рj в ряд Тейлора, получаем квадратичное приближение к Ф(Р)

вида

                   (7)

где H(Pj)- матрица Гессе вторых частных производных Ф(Р) в точке Рj  .

Учитывая, что в точке минимума Р*  функция ФQ(Р) выполняется неравенство , можно найти следующую формулу после дифференцирования (7):

(8)

Соотношение (8) определяет положение точки минимума функции (7), которая является квадратичной аппроксимацией Ф(Р). Таким образом, если минимизируемая функция является положительно определенной квадратичной формой, то формула (8) позволяет найти её минимум за одну итерацию.

Для функции общего вида на основании (8) можно записать следующую итерационную формулу Ньютона:

                                     (10)

т.е. в данном методе в качестве Sj , определяющего направление поиска, выбирается  вектор . Формула (8) позволяет получать последовательность минимумов аппроксимирующих функций. Если минимизируемая функция выпуклая, то (10) гарантирует её монотонное убывание от итерации к итерации.

Метод Ньютона обладает квадратичной скоростью сходимости, т.е.

                                       (11)

 

где Р* - точка оптимума, а коэффициент γ  зависит от вида минимизируемой функции. Однако, для невыпуклых функций он сходится не из любых начальных точек. Для  успешного использования метода в таких условиях требуется задание «хорошего»  начального приближения. Вторым существенным недостатком этого метода является то, что он, хотя и сходится за меньшее число итераций, чем рассмотренные выше методы первого порядка, однако требует значительно больших вычислительных затрат  на каждой итерации, связанных с вычислением матрицы вторых частных производных. Поэтому метод может быть рекомендован лишь для решения тех задач, в которых вычисления матрицы Гессе производится сравнительно легко.