91146

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

Лекция

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

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

Русский

2015-07-13

1.23 MB

9 чел.

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


 

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

875. Шпаргалка по мировой экономике 576.5 KB
  Совокупность национальных хозяйств и экономических взаимосвязей между ними. Характеристика факторов, влияющих на развитие мирового хозяйства. Международная специализация и кооперирование производства. Показатели, характеризующие производство основных видов продукции на душу населения, уровень и качество жизни.
876. Свободные и вынужденные колебания в контуре 182.5 KB
  Ознакомление с приборами и лабораторным стендом. Свободные колебания в одиночном контуре. Вынужденные колебания в последовательном контуре. Получение синусоидальных колебаний звуковых и ультразвуковых частот в диапазоне 20 Гц - 200 кГц с напряжением от долей вольта до 30 вольт.
877. Сущность и методология маркетинговых исследований 506.5 KB
  Уменьшение неопределенности и риска при принятии коммерческих решений. Теоретические основы проведения маркетинговых исследований. Проведение маркетингового исследования эффективности рекламы. Анализ рынка шоколадных батончиков.
878. Воспитание и педагогическая мысль в эпоху Античности 416.5 KB
  Факторы, влияющие на социализацию и составляющие контекст воспитания и образование. Развитие воспитания и образования в древней Греции. Религия как фактор влияния на человека в древнегреческом обществе. Влияние общества и отношение к обществу. Семья как фактор воспитания. Отношение к семье.
879. Принятие решений в финансовом менеджменте с использованием финансовых функций MS Excel 198.5 KB
  Определите, сколько денег окажется на счете в конце пятого года для каждого варианта. Будущее значение вклада на конец пятого года. Если срок вклада увеличить до 10 лет, как изменится ставка процента.
880. Работа со списками (базами данных) в Excel 181 KB
  Правила формирования списка. Использование формы данных. Поиск и фильтрация данных. Использование Автофильтра. Вывод на экран записей, данные в которых в этом поле совпадают с выбранным значением. Использование Расширенного фильтра.
881. Философия Просвещения 178.5 KB
  Социально-политические и идейные предпосылки идеологии Просвещения. Томас Гоббс как идейный предшественник английского Просвещения. Учение Гоббса об обществе и государстве. Социально-философские идеи Дж. Локка. Французский материализм 18 века. Социальная философия французского Просвещения.
882. Вычисление определенного интеграла методом Симпсона 169 KB
  Реализовано вычисление определенного интеграла заданной функции методом Симпсона с заданной точностью. Предусмотрено сохранение и загрузка рабочих параметров программы. Алгоритм вычисления по формуле Симпсона.
883. Основы теории изобразительной грамоты 172.5 KB
  Академический рисунок как методическая система обучения изобразительному искусству. Вспомогательные линии построения формы. Методическая последовательность работы над рисунком натюрморта. Закономерности построения формы тоном.