91146

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

Лекция

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

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

Русский

2015-07-13

1.23 MB

11 чел.

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;..., которая расходится.


 

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

1791. Виховна година: Збережемо природу рідного краю 21.89 KB
  Вчити учнів усвідомлювати себе частиною світу природи; формувати інтерес до навколишнього середовища; розвивати увагу, спостережливість, бажання допомогти довкіллю; виховувати в школярів дбайливе і гуманне ставлення до природи, бажання милуватися її красою.
1792. Виховна година. Будь обережним на дорозі 55 KB
  Поглибити знання учнів про правила дорожнього руху, повторити основні правила пішоходів, велосипедистів, мотоциклістів, пасажирів, водіїв, сприяти розвитку мислення, мовлення, пам'яті, навичок поведінки на дорозі, виховувати повагу до оточуючих, увагу, правила ввічливості
1793. Виховна година: Правильне харчування та здоровий сон – запорука гарного сомопочуття 20.46 KB
  Продовжити знайомство з резервами самопочуння людини, значенням раціонального харчування в системі здорового способу життя, навчити розділяти індивідуальну програму харчової поведінки, продовжити знайомство з компонентами етноздоров'я населення України
1794. Виховна година: Розуміння себе 42 KB
  Довести учням ідею неповторності й унікальності кожної особистості, розвивати здібності аналізувати себе та свої вчинки, виховувати любов до себе та оточуючих, почуття справедливості та гуманності, естетичні смаки та уподобання.
1795. Виховна година: Місія 25.79 KB
  Навчити учнів правильно використовувати свої знання з різних предметів. Виховати в учнів почуття відповідальності не тільки за себе, але і за своїх знайомих і рідних,вміння правильно розприділяти свій час. Розвинути логічне мислення, правильно робити передбачення з даної теми.
1796. Толерантність. Позитивне значення толерантності у формуванні цілісної особистості молодої людини 70.5 KB
  Психологічна установка. Поняття про толерантність. Діагностика толерантної особистості. Мудрість з дерева пізнання (Обговорення висловів видатних людей про толерантність). Виконання творчого завдання в групах.
1797. Друг — це означає другий Я 74 KB
  Учити дітей сприймати різні життєві ситуації, аналізувати їх і знаходити шляхи виходу з них, виховувати у дітей правильне ставлення до таких понять як друг, дружба, розвивати в учнів загальнолюдські чесноти.
1798. Урок-виховний захід. Я і мій класний колектив 23.54 KB
  Навчати учнів культури спілкування, пошуку конструктивних способів вирішення проблемних ситуацій у класі, сприяти поліпшенню психологічного клімату в класі, налагодженню доброзичливих стосунків, виховувати в учнів повагу одне до одного, відповідальність за власні слова і вчинки.
1799. Критерії успішної виховної діяльності вчителя 16.85 KB
  Утримування рівня організованості учнівського колективу як у навчанні так і в позаурочній роботі. Підвищення рівня розвитку учнівського колективу (його згуртованість, активність, ініціативність учнів, виховний вплив колективу на його членів).