91146

Классический метод безусловной оптимизации функции многих переменных

Лекция

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

Для функции многих переменных условия оптимальности формулируются следующим образом. Определить точки локальных экстремумов функции . Итерационные методы поиска точек экстремума функций одной переменной Принято разделять итерационные методы поиска точек экстремума на: Пассивные; Активные Пассивные методы поиска Метод оптимизации называется пассивным когда все точки вычислений характеристик задачи в данном случае значения целевой функции выбираются одновременно до начала вычислений.

Русский

2015-07-13

1.23 MB

5 чел.

PAGE  21

Лекция 4

Классический метод безусловной оптимизации функции многих переменных

Для функции f(x) многих переменных точка х представляет собой вектор, f'(x) - вектор первых производных (градиент) функции f(x), f " (x) - симметричную матрицу вторых частных производных (матрицу Гессе - гессиан) функции f(x).

Для функции многих переменных условия оптимальности формулируются следующим образом.

Необходимое условие локальной оптимальности. Пусть f(x) дифференцируема в точке . Если - точка локального экстремума, то

. (1.3)

Как и ранее, точки, являющиеся решениями системы уравнений (1.3), называются стационарными. Характер стационарной точки  связан со знакоопределенностью матрицы Гессе .

Достаточное условие локальной оптимальности. Пусть F(x) дважды дифференцируема в точке , причем F'(x*)=0. т.е. x* - стационарная точка. Тогда, если матрица F"(x*) является положительно (отрицательно) определенной, то x* - точка локального минимума (максимума); если матрица F"(x*) является неопределенной, то x* - седловая точка.

Если матрица F"(x*) является неотрицательно (неположительно) определенной, то для определения характера стационарной точки x* требуется исследование производных более высокого порядка.

Для проверки -знакоопределенности матрицы, как правило, используется критерии Сильвестра. Согласно этому критерию, симметричная матрица А является положительно определенной в том и только том случае, если все ее угловые миноры положительны. При этом угловым минором матрицы А называется определитель матрицы, построенной из элементов матрицы А. стоящих на пересечении строк и столбцов с одинаковыми (причем первыми) номерами. Чтобы проверить симметричную матрицу А на отрицательную определенность, надо проверить матрицу (-А) на положительную определенность.

Пример. Определить точки локальных экстремумов функции

.

Решение.

Находим первые частные производные F(x):

.

Решаем систему уравнений

Разрешаем уравнение (2) относительно

Подставляя полученное выражение в уравнение (1). Находим .

Соответственно

.

Таким образом, получили две стационарные точки (N = 2):

.

Находим вторые частные производные F(x):

Составляем матрицу Гессе

.

Дальнейшее рассмотрение будем вести для одной стационарной точки – Х2

Находим :

Вычисляем угловые миноры :

M1=|10|>0,

Поскольку матрица является положительно определенной, то  является точкой локального минимума.

Ответ: функция  имеет в точке x=(5/3,8/3) локальный минимум.

Итерационные методы поиска точек экстремума 

функций одной переменной

Принято разделять итерационные методы поиска точек экстремума на:

  •  Пассивные;
  •  Активные

Пассивные методы поиска ()

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

Метод перебора

Разобьем отрезок [a,b] на котором ищется экстремум на n равных частей точками деления xi=a+i(b-a)/n. Вычислив значение функции в точках xi, путем сравнения  найдем точку xm для которой значение функции минимальное (максимальное).

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

n>=(b-a)/

Активные методы поиска экстремума

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

Методы дихотомии (половинного деления)

Суть метода заключается в том, что заданный отрезок [а; b] делится пополам:

.

Затем в каждой из половин отрезка [а; с] и [с; b] выбираются по одной точке x1 и х2, в них вычисляются значения функций, производится сравнение полученных значений, и в результате сравнения устанавливается отрезок, в котором минимума быть не может. Откинув его, продолжаем ту же процедуру с полученным отрезком до тех пор, пока вновь полученный отрезок не станет меньше по длине некоторой наперед заданной величины:

.

Скорость достижения  очевидно зависит от величины откидываемого отрезка. Поэтому x1 и х2 выбираются симметрично на расстоянии :

 (4)

где δ> 0 - малое число.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство .

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить середину отрезка и значения x1 и х2 по формулам (4). Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если , то перейти к отрезку [а; x2], положив b = x2, иначе - к отрезку [x1; b], положив а = x1.

Шаг 3. Найти достигнутую точность . Если  то перейти к следующей итерации, вернувшись к шагу 1. Если , то завершить поиск х*, перейдя к шагу 4.

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

.

Пример. Определить методом дихотомии минимум функции , заданной на отрезке =[1,3], при N=4 и =0,1

Поиск экстремума методом золотого сечения

В методе Деление отрезка пополам (для отыскания минимум: функции) представляется естественным, но явно не единственным путем решения задачи. Интуитивно ясно, что если последовательно делить отрезок на две части другим способом, то можно достичь того же результата. Возникает вопрос: какой способ деления отрезка наиболее эффективен для поиска минимума унимодальной функции? В связи с этим вопросом возникает метод та называемого золотого сечения.

Золотое сечение — это такое пропорциональное деление отрезка на части, при котором весь отрезок относится к большей части, как сама большая часть относится к меньшей; другими словами, меньший отрезок относится к большему, как больший к всему.

АС2=АВ*СВ

АВ есть 1, больший член АС есть , тогда СВ=1-

2=1*1-

Откуда

 

1-=0,382

Обозначим Ф1=0,382  Ф2=0,618

В случае метода золотого сечения используются два условия окончания вычислений:

а) выполнение заданного количества вычислений N,

б) достижение заданной величины   уменьшения отрезка локализации.

Итак, алгоритм поиска минимума унимодальной функции методом золотого сечения заключается в следующем.

  1.  Задается N (либо ), получается j=1
  2.  На j–й итерации вычисляются

x1(j) = a(j-1) + Ф1(b(j-1) - a(j-1)),

x2(j) = a(j-1) + Ф2(b(j-1) - a(j-1)),

f1(j) = f(x1(j)),  f2(j) = f(x2(j)).  

Если  то

Если  то

Проверяется условие окончания вычислений

Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума х* и величины минимума f* и вычисления завершаются.

Если условие не выполняется, то полагается j=j+1 и осуществляется переход к п.2.

Пример. Определить методом золотого сечения минимум функции

f(x) = х4 - 6х2 +10 , заданной на отрезке =[1,3], при N=4.

Решение.

В данном случае будут выполнены N -1 = 3 итерации. Результаты вычислений заносим в табл. 4.5.

Таблица 4.5

Номер итерации

0

1

2

3

-

1,764* 1,472* 1,764

-

2,236* 1,764 1,944*

-

1,012 1,694 1,012

<

>

<

-

4,999 1,012 1,607

1

1

1,472 1,472

3

2,236 2,236 1,944


Поскольку j = N -1 = 3 , то вычисления завершаются.

Точка минимума локализована на отрезке = [1,472; 1,944], =1,764,   

= 1,012. Ответ: = [1,472; 1,944], х*  1,764,    f*  1,012.

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

Поиск экстремума методом Фибоначчи 

Пусть нужно определить минимум с наименьшим возможным интервалом неопределенности (точность), но при этом можно выполнить только n вычислений функции. Как следует выбрать точки, в которых вычисляется функция?

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

Предположим, что имеется интервал неопределенности (x1,x3) и известно значение функции f(x2) внутри этого интервала. Если можно вычислить значение функции всего один раз в точке x4, то где следует поместить точку x4, чтобы получить наименьший возможный интервал неопределенности?

Пусть x2-x1=L, x3-x2=R, L>R. Эти значения фиксированы, если известны x1,x2,x3.

Если x4 находится в интервале (x1,x2), то:

1) если f(x4)<f(x2), то новым интервалом неопределенности будет  (x1,x2)длиной x2-x1=L;

2) если  f(x4)>f(x2), то новым интервалом неопределенности будет  (x4,x3)длиной x3-x4.

Поскольку неизвестно, какая из этих ситуаций будет иметь место, выберем x4 таким образом, чтобы минимизировать наибольшую из длин x3-x4 и x2-x1. Достигается это тем, что x4 помещается в (x1,x3) симметрично относительно x4. В этом случае x3-x4 = x2-x1. В любом другом случае размещения x4 может быть так, что полученный интервал будет больше L.

Если окажется, что можно выполнить еще одно вычисление, то следует применить описанную процедуру к интервалу (x1,x2) или (x4,x3). Последовательное применение такой процедуры и образует итерационный процесс приближения к точке минимума, называемый поиском Фибоначчи.

Числа Фибоначчи определяются следующим образом:

F0=1, F1=1,Fk=Fk-1+Fk-2, k=2,3,...

то есть  (1,1,2,3,5,8,13,21,...)

Если начальный интервал (a,b) имеет длину L=(b-a),  ε - точность вычисления значения функции, то конечный интервал неопределенности будет равен

       

то есть уменьшится в Fn раз (пренебрегая ε) и это наилучший гарантированный результат.

Отметим, что в начале поиска, когда известны только a и b, необходимо правильно установить первую внутреннюю точку. Она размещается на расстоянии L2 от любого конца интервала

то есть тоже определяется с помощью чисел Фибоначчи.

 

Итак, алгоритм поиска минимума унимодальной функции методом Фибоначчи заключается в следующем.

1. Задается N, определяются числа Фибоначчи Fk, , выбирается  из условия

Полагается j= 1.

  1.  На j-й итерации вычисляются

Если  то

Если  то

  1.  Проверяется условие окончания вычислений

j = N -1.

Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума х* и величины минимума f* = f(x*) и вычисления завершаются.

Если условие не выполняется, то полагается j = j+1 и осуществляется переход к п.2.

Примечание. На j-й, j>1, итерации вычисляется только та точка , i= 1,2, которая не была определена на предыдущей итерации.

Отметим, что оценкой точки минимума х* является та из точек , i = 1,2, которая осталась внутри итогового отрезка локализации .

Пример. Определить методом Фибоначчи минимум функции f(х) = х4 - 6х2 +10, заданной на отрезке  =[1,3], при N=4.

Решение.

В данном случае будут выполнены N -1 = 3 итерации.

Определяем числа Фибоначчи Fk, k=:

F0 = F1, F2 = 2, F3 = 3, F4 = 5, F5 = 8.

Выбираем=0,1

Первая итерация

Вторая итерация

Третья итерация

Результаты вычислений заносим в табл. 4.4.

Таблица 4.4

Номер итерации

0

1

3

1

1,78*

2,22*

1,028

<

4,719

1

2,22

2

1,44*

1,78

1,858

>

1,028

1,44

2,22

3

1,78

1,88*

1,028

<

1,286

1,44

1,88

Примечание. Знаком * помечаем точки , , i=1,2, вычисляемые на j-й итерации.

Поскольку j=N-1=3, то вычисления завершаются.

Точка минимума локализована на отрезке  =[1,44; 1,88],

= 1,78, = 1,028 .

Ответ:  =[1,44; 1,88],  1,78, 1,028 .

График функции

Значение Х

Значение функции

1

5

1,2

3,4336

1,4

2,0816

1,6

1,1936

1,8

1,0576

2

2

2,2

4,3856

2,4

8,6176

2,6

15,1376

2,8

24,4256

3

37

Заключение

Асимптотически метод золотого сечения переходит в метод Фибоначчи. Окончательный интервал в методе «золотого» сечения всегда на 17% больше чем в методе Фибоначчи. Если количество измерений не задано, то чаще используется метод «золотого» сечения, если задано - то метод Фибоначчи.

Интерполяционные методы отыскания экстремума функции первого порядка

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

Метод хорд (секущих)

Метод хорд относится к последовательным методам первого порядка. В основе данного метода лежит следующее обоснование. Необходимым и достаточным условием глобального минимума выпуклой непрерывно дифференцируемой функции является равенство f '(х) = 0. Если на концах промежутка [a,b] производная f '(х) имеет разные знаки, т.е. f '(a) f '(b) < 0, то на промежутке найдется точка, в которой f '(х) обращается в нуль, и поиск точки минимума f (х) на промежутке [a,b] эквивалентен решению уравнения

f '(х)=0, x [a,b]

Для приближенного решения данного уравнения можно использовать метод хорд. Этот метод основан на сокращении отрезков путем определения точки у пересечения с осью ОХ хорды графика функции f '(х). Координата точки у определяется по формуле 

Отрезок дальнейшего поиска [a; y] или [y; b]  выбирается в зависимости от знака f '(y). Если f '(y) > 0, то выбирается [a; y], если f '(y) < 0 - [y; b] .

Таким образом, метод используется при наличии информации об отрезке [a;b] таком, что f'(a) < 0, a f'(b) > 0.

Алгоритм

Шаг 1. Задать начальный промежуток неопределенности L0 = [a0,b0] и > 0  - требуемую точность. Положить k = 0.

Шаг 2. Вычислить .

Шаг 3. Вычислить f'(yk).

Шаг 4. Если  , то положить х* = ук, f (х*) = f(yk) и поиск завершить, иначе перейти к шагу 5.

Шаг 5. Если f'(yk)> 0, то положить b = уk, f'(b)= f'(yk), иначе положить       а = уk,  f'(a) = f'(yk). Положить k = k +1 и перейти к шагу 2.

В данном методе мы предполагали, что f'(a) f'(b) <0. При нарушении этого условия точку х* можно указать сразу. Так, если f'(a) > 0 и f'(b) > 0, то f(x) возрастает на [a,b] следовательно, х*=а, если f’(a)< 0 и f’(b)< 0, то f(x) убывает на [a,b] следовательно, х*=b. В случае, если производная равна 0 на одном из концов отрезка [a,b], то этот конец и является решением задачи.

Пример 4. Найти минимум функции f(x) = х4 +e-x  методом хорд.

Решение. В качестве начального промежутка неопределенности возьмем промежуток L0 = [a0,b0] = [0;1], положим  = 0,05.

 

На 6-й итерации получаем промежуток с концами a5=0.504, b5=1. На данном промежутке метод генерирует точку у5 =0.516, в которой f'(y5)= -0.046. Алгоритм завершает работу, поскольку достигнута требуемая точность | f'(y5)| <  = 0,05.

Существует и модификация метода хорд не связанная с вычислением производной. В зависимости от того, лежат ли точки xi-1 и xi по разные стороны от корня x* или же по одну и ту же сторону, получаем такие чертежи:

Рис.9.14.Построение последовательного приближения по методу хорд: два случая

И корень будем искать как функцию с угловым коэффициентом, равным разностному отношению

построенному для отрезка между точками xi-1 и xi

Решая уравнение l(x)=0, находим

 Пример 9.8   Решим уравнение x3+2x2+3x+5=0 методом хорд. Зададимся точностью =0.00001и возьмём в качестве начальных приближений x0 и x1 концы отрезка, на котором отделён корень: x0 =-2, x1=-1. Итерационная формула метода хорд при f(x)=x3+2x2+3x+5 имеет вид

По этой формуле последовательно получаем:

x2 = -1.75; x3 = -1.905660; x4 = -1.840182; x5 = -1.843603; x6 = -1.843735;

x7 = -1.843734; x8 = -1.843734

Седьмое приближение уже дало нам значение корня с нужной точностью; восьмая итерация понадобилась для того, чтобы убедиться: с заданной точностью значение перестало изменяться. Получаем, что  =-1.843734

Интерполяционные методы отыскания экстремума функции второго порядка

Метод Ньютона

Метод Ньютона является последовательным методом второго порядка. Предполагается, что функция f(x) дважды дифференцируема, причем f”(x) > 0 (это гарантирует выпуклость функции f(x)). В этом случае корень уравнения f’(x) = 0 можно приближенно искать методом касательных. В отличие от предыдущих методов, метод Ньютона не относится к методу сокращения промежутков. Для начала работы метода вместо задания начального промежутка неопределенности требуется задание начальной точки х0. в которой вычисляется f’(x0) и f”(x0). В процессе работы метода генерируется последовательность хk, k = 1,2... В очередной точке хk строится линейная аппроксимация функции f’(x) (касательная к графику f’(x)). Точка, в которой линейная аппроксимирующая функция обращается в нуль, используется в качестве следующего приближения xk+1.

Уравнение касательной к графику f’(x) в точке xk имеет вид

у = f’(xk) + f”(xk)(x- xk), поэтому точка xk+1, найденная из условия у = 0, определяется формулой

Процедура нахождения точек xk продолжается до тех пор. пока не будет достигнута требуемая точность, т.е. | f’(xk)|.

Алгоритм

Шаг 1. Задать начальную точку x0, > 0 - требуемую точность.

Положить k = 0.

Шаг 2. Вычислить f’(xk).

Шаг 3. Если  | f’(xk)|, то положить х* = хk, f(x*) = f(xk) и поиск завершить, иначе перейти к шагу 4.

Шаг 4. Вычислить

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

Исследования метода Ньютона показывают, что при достаточно близком к точке минимума х* выборе начального приближения х0, гарантируется скорость сходимости последовательности хk, k = 0,1,... к х* вида |хk х*|, , С>0, q и С зависят от функции f(x) и выбора точки x0. Если начальное приближение x0 выбрано не достаточно близко к точке х*, то последовательность хk, k = 0,1,... метода Ньютона может расходиться. В подобных случаях необходимо найти лучшее начальное приближение х0, например, с помощью нескольких итераций метода золотого сечения.

Пример 5. Найти минимум функции f(х) = xarctgx - ln(1 + x2 ) методом Ньютона.

Решение. Данная функция дважды дифференцируема и . В качестве начального приближения возьмем точку х0 = 1, положим =10-7.

1. Вычислим f’(x0)= 0,785.

2. Поскольку | f’(x0)| >= 10-7 , то перейдем к шагу 4.

3. Вычислим х1 = = -0,57.

4. Положим k = 1. Перейти к шагу 2.

5. Вычислим f ’(x1)= -0,519 .

6. Поскольку | f ’(x1)| > =10-7 , то перейдем к шагу 4.

7. Вычислим .

8. Положим k = 2. Перейти к шагу 2.

9. Поскольку | f ’(x2)| > =10-7, то перейдем к шагу 4.

10. Вычислим .

11. Положим k = 3. Перейти к шагу 2.

12. Вычислим  f ’(x3)= -1,061*10-3 .

13. Поскольку | f ’(x3)| > =10-7 , то перейдем к шагу 4.

14. Вычислим .

15. Положим k= 4. Перейти к шагу 2.

16. Вычислим f ’(x4) = 9*10-8 .

17. Поскольку | f ’(x3)| < =10-7, процесс поиска заканчивается. В качестве решения задачи принимается точка х* = x4 = 9* 10-8  0.

Быстрая сходимость метода Ньютона для рассмотренного примера объясняется хорошим выбором начального приближения х0. Если, например, для данной функции в качестве начального приближения выбрать х0 = 3, то методом будет генерироваться последовательность точек

x1 =-9,5; х2=124; х3 =-23905; х4 = 8,97*108; х5 =-1,27*101S;..., которая расходится.


 

А также другие работы, которые могут Вас заинтересовать

33154. КОЛЛЕКТИВНЫЕ ТВОРЧЕСКИЕ ДЕЛА 17 KB
  Тогда ты и сам сможешь придумать дела. малым группам; многое зависит от того кто станет ведущим этого дела; экономь время Времени на подготовку не должно быть много или мало: только в “самый разâ€. Творческая подготовка конкурсов и дел участие в общелагерных делах.
33155. Мозговой штурм. Деловая игра для педагогов 34 KB
  Один из вариантов методики мозгового штурма хорошо знаком нам по любимой не одним поколением телезрителей передаче Что Где Когда. Я думаю что для начинающего психолога мучительно размышляющего над вопросом как ему начать работу с педагогами методика мозгового штурма может стать первым шагом в этом направлении.Хочу предложить один из самых простых вариантов методики мозгового штурма который может быть реализован на педагогическом совете в процессе психологического тренинга учителей или как отдельное специальное мероприятие.
33156. НАЗВАНИЯ ОТРЯДОВ И ДЕВИЗЫ 39.5 KB
  ОбаНа Мы не панки не шпана мы ребята ОбаНа. Обана Обана это чудо Обана это класс мы живем совсем не худо вы соскучитесь без нас.
33157. Никогда не заблудишься ! (дополнение к Ориентированию) 20 KB
  Крона деревьев лучше развита на юге. Кора березы на юге эластичнее и светлее. Пологий склон муравейника на юге.
33158. Проведение смены для очень маленьких детей ( самый маленький и предпоследний отряд в лагере - 6-8 лет ) 72 KB
  Команды каждый раз меняем. Под словом эстафета понимается прохождение команды детей по маршруту по карте на которой отмечены места где находятся этапы. Команды одновременно выбегают с начальной точки и проходят все этапы по порядку но начальные этапы сдвинуты и команды встречаются только вовремя перебежек с этапа на этап. Под КВН понимается такое мероприятие в котором участвует несколько команд им выдаются задания и или команда целиком выполняет его или часть команды или по одному участнику.
33159. Клуб «Пластилиновые краски» 119.5 KB
  Ход занятия: Ребята вспоминают приемы рисования пластилином. Ход занятия: Знакомство 10 мин. 10 мин. 30 мин.
33160. Примерный план проведения сбора «Планирование деятельности отряда и дел лагеря» 22 KB
  Задачи: диагностика участников сбора для понимания мотивов участия в деятельности отряда и лагеря организация обмена информацией; обучение формам общения для их дальнейшего применения. Ход сбора: 1. Задача первою этапа сбора вывести ребят на размышления о том Что такое человек Чем он отличается от других существ Что такое гармонично развитый человек .
33161. ADO.NET 96 KB
  Создать таблицу, связанную с таблицей элемента контейнера отношением «один ко многим» (Например, если таблицей для хранения элементов контейнера является таблица Книга, то связанная с ней отношением «один ко многим» может быть таблица АвторКниги, т.к. один автор может написать много книг).
33162. Формы тематических отрядных дел 24 KB
  В ходе обыгрывания и последующего обсуждения различных ситуаций из жизни школьников подростки учатся говорить нет преодолевать конформизм приобретают интерес к поиску умного выхода из затруднительных ситуаций обучаются алгоритму отказа отказсоглашение отказобещание отказальтернатива отказотрицание отказконфликт.