Методы оптимизации: Численные методы минимизации

Министерство образования и науки РФ
Федеральное государственное автономное образовательное учреждение высшего
образования
Национальный исследовательский
Томский политехнический университет
УТВЕРЖДАЮ
Зам. директора ИК
по учебной работе
_____________С.А. Гайворонский
«___»_________________2015 г.
МЕТОДЫ ОПТИМИЗАЦИИ
Методические указания к выполнению лабораторной работы № 2
«Численные методы одномерной минимизации с использованием производной»
по дисциплине
«Методы оптимизации»
для студентов направления 01.03.02
«Прикладная математика и информатика»
Томск 2015 г.
УДК 519.8 ББК 22.14
Методы оптимизации. Методические указания к выполнению лабораторной
работы № 2. «Численные методы одномерной минимизации с использованием
производной»
по
дисциплине
«Методы
оптимизации»
для
студентов
направления 01.03.02 «Прикладная математика и информатика». – Томск: Изд.
НИ ТПУ, 2015. – 11 с.
Составитель – доц. канд. техн. наук Ю. В. Бабушкин
Резензент – доц. канд. техн. наук В. Г. Гальченко
Методические
методическим
указания
рассмотрены
семинаром
и
рекомендованы
кафедры
прикладной
«___»_________2015 г.
Зав. кафедрой
Доцент, к.т.н. _________________Гергет О.М.
к
изучению
математики
Лабораторная работа № 2
Тема: Численные методы одномерной минимизации с использованием
производной.
Цель работы: Приобретение практических навыков для решения задач
одномерной минимизации численными методами.
Постановка задачи
Требуется найти безусловный минимум функции одной переменной
Y  F (x) , то есть, такую точку x*  R , что F ( x* )  min F ( x) .
xR
Методы, рассмотренные в лабораторной работе 1, используются при
минимальных требованиях к целевой функции Y  F (x) - она должна быть
унимодальной.
В данной работе предполагается, что целевая функция Y  F (x) является
выпуклой и дифференцируемой (один раз или дважды). Причем, производная
может быть вычислена в произвольно выбранных точках. Считается, что
эффективность методов, использующих информацию о производных при
поиске точки минимума можно существенно повысить.
Численные методы одномерной минимизации с использованием
производной
К основным численным методам одномерной
использованием производной относят:
- метод средней точки;
- метод хорд;
- метод Ньютона;
- метод кубической аппроксимации и др.
минимизации
с
1. Метод средней точки [1]
Метод средней точки направлен на повышение эффективности метода
деления отрезка пополам при использовании технологии исключения отрезков
за счет замены вычислений функции в трех точках на операцию вычисления
производной в средней точке x 
ab
.
2
Если F ( x)  0 , то точка x лежит на участке монотонного возрастания
F ( x) , поэтому x*  x и точку минимума следует искать на отрезке [a, x] .
Если F ( x)  0 , то точка x лежит на участке монотонного убывания F ( x) ,
поэтому x*  x и точку минимума следует искать на отрезке [ x, b] .
Равенство F ( x)  0 означает, что точка минимума найдена точно и x*  x .
Такое исключение отрезков требует на каждой итерации только одного
вычисления F ( x) и уменьшает отрезок поиска точки минимума ровно в два
раза.
Поиск заканчивается, если абсолютная величина производной меньше
заданной погрешности.
Алгоритм поиска точки минимума методом средней точки
Алгоритм поиска минимума функции сводится к выполнению следующих
этапов.
1 этап. Задается начальный интервал неопределенности L0  [a0 , b0 ] и   0 требуемая точность.
2 этап. Задать k  0 .
a  bk
, F ( x) .
2
3 этап. Вычислить среднюю точку x  k
4 этап. Проверить условие окончания:
- если F ( x)   , то процесс поиска завершается и x*  x, F *  F ( x* ) ;
- если F ( x)   , то сравнить F ( x) с нулем.
Если F ( x)  0 , то продолжить поиск на отрезке Lk  [ak , bk ] , положив
k  k  1 , ak  ak 1 , bk  xk 1 .
Если F ( x)  0 , то продолжить поиск на отрезке Lk  [ak , bk ] , положив
k  k  1 , ak  xk 1 , bk  bk 1 .
Перейти к этапу 3.
2. Метод хорд [1]
Метод хорд опирается на равенство F ( x)  0 , которое является
необходимым и достаточным условием глобального минимума выпуклой
дифференцируемой функции F ( x) .
Если на концах отрезка L  [a, b] производная имеет разные знаки, то на
интервале (a, b) найдется точка, в которой F ( x)  0 и
поиск точки
минимума F ( x) на отрезке [a, b] эквивалентен решению уравнения
F ( x)  0 , x [a, b] .
Таким образом, любой приближенный метод решения уравнения
F ( x)  0 , x [a, b] можно рассматривать как метод минимизации выпуклой
дифференцируемой функции F ( x) на отрезке [a, b] . Одним из таких методов
является метод хорд. Он основан на исключении отрезка путем определения
точки
xa
F (a )
(a  b)
F (a )  F (b)
пересечения с осью Ox хорды графика функции F ( x) на очередном отрезке.
.
Отрезок дальнейшего поиска определяется по следующему правилу.
Новыми точками отрезка [a, b] для осуществления следующей итерации
являются концы того из отрезков [a, x] и [ x, b] , который содержит точку x* . Его
определяют по знаку производной F ( x) .
Если F ( x)  0 , то точка x лежит на участке монотонного возрастания
F ( x) , поэтому x*  x и точку минимума следует искать на отрезке [a, x] , то есть
b x.
Если F ( x)  0 , то точка x лежит на участке монотонного убывания F ( x) ,
поэтому x*  x и точку минимума следует искать на отрезке [ x, b] , то есть a  x .
Равенство F ( x)  0 означает, что точка минимума найдена точно и x*  x .
На каждой итерации, кроме первой, следует вычислять одно новое
значение F ( x) .
Поиск заканчивается, если абсолютная величина производной меньше
заданной погрешности.
Алгоритм поиска точки минимума методом хорд
Алгоритм поиска минимума функции методом хорд сводится к
выполнению следующих этапов.
1 этап. Задается начальный интервал неопределенности L0  [a0 , b0 ] и   0 требуемая точность,   0 - малое положительное число.
2 этап. Задать k  0 . Вычислить F (ak ), F (bk ) .
Если F (ak )* F (bk )  0 , то перейти к этапу 3, иначе к этапу 5.
3 этап. Вычислить xk  ak 
F (ak )
(ak  bk ), F ( xk ) .
F (ak )  F (bk )
4 этап. Проверить условие окончания:
- если F ( xk )   , то процесс поиска завершается и x*  xk , F *  F ( x* ) ;
- если F ( xk )   , то сравнить F ( xk ) с нулем.
Если F ( xk )  0 , то продолжить поиск на отрезке Lk  [ak , bk ] , положив
k  k  1 , ak  ak 1 , bk  xk 1 , F (bk )  F ( xk 1 ) .
Если F ( xk )  0 , то продолжить поиск на отрезке Lk  [ak , bk ] , положив
k  k  1 , ak  xk 1 , bk  bk 1 , F (ak )  F ( xk 1 ) .
Перейти на этап 3.
5 этап. Если F (ak )  0, F (bk )  0 , то F ( x) возрастает на отрезке Lk  [ak , bk ] и,
следовательно, x*  ak .
Если F (ak )  0, F (bk )  0 , то F ( x) убывает на отрезке Lk  [ak , bk ] и,
следовательно, x*  bk .
Если F (ak )* F (bk )  0 , то x*  ak или x*  bk , в зависимости от того, на
каком из концов отрезка Lk  [ak , bk ] производная F ( x)  0 .
3. Метод Ньютона [1]
Предполагается, что функция F ( x) дважды дифференцируема, причем
F ( x)  0 . Тогда для поиска корня уравнения F ( x)  0 используется метод
касательных. Сущность метода заключается в том, что в очередной точке xk
строится линейная аппроксимация функции F ( x) (касательная к графику F ( x) ),
а точка, в которой линейная аппроксимирующая функция обращается в нуль,
используется в качестве следующего приближения xk 1 .
Координата точки xk 1 находится по формуле
xk 1  xk 
F ( xk )
, k  0,1,...,
F ( xk )
где
x0 - начальная точка выбирается пользователем. Вычисления по
приведенной формуле продолжаются до тех пор, пока не выполнится условие
F ( xk )   , после чего полагают x*  xk , F *  F ( x* ) .
Алгоритм поиска точки минимума методом Ньютона
Алгоритм поиска минимума функции методом Ньютона сводится к
выполнению следующих этапов.
1 этап. Задается начальный интервал неопределенности L0  [a0 , b0 ] и   0 требуемая точность.
2 этап. Задать k  0 и начальную точку xk [ak , bk ] .
3 этап. Вычислить F ( xk ) . Проверить условие окончания:
- если F ( xk )   , то процесс поиска завершается и x*  xk , F *  F ( x* ) ;
- если F ( xk )   , то вычислить F ( xk ) и если F ( xk )  0 перейти к этапу 4. В
противном случае закончить вычисление связи с нарушением обязательного
условия F ( xk )  0 .
4 этап. Вычислить xk 1  xk 
F ( xk )
.
F ( xk )
5 этап. Принять k  k  1 и перейти к этапу 3.
Примечание. В связи с выбором начального приближения x0 , удаленного
достаточно далеко от искомого решения x* , возможно, что последовательность
 xk  будет расходиться. В этом случае рекомендуется найти лучшее начальное
приближение x0 другим методом (метод золотого сечения и т. д.).
4. Метод кубической аппроксимации [1]
В этом методе полиномиальной аппроксимации в качестве
аппроксимирующего полинома используется многочлен третьей степени.
Предполагается, что F ( x) - выпуклая дифференцируемая функция и найден
интервал ( x1 , x2 ) , содержащий ее точку минимума x* . Это означает, что F ( x1 )  0 ,
а F ( x2 )  0 .
Аппроксимирующий кубический полином записывается в виде
q( x)  a0  a1 ( x  x1 )  a2 ( x  x1 )( x  x2 )  a3 ( x  x1 )2 ( x  x2 ) ,
где неизвестными являются коэффициенты a0 , a1 , a2 , a3 .
Для определения неизвестных коэффициентов предполагается, что в
точках x1 и x2 значения функции F ( x) и аппроксимирующего полинома q( x)
совпадают. Это позволяет найти два коэффициента. Для определения
недостающих двух коэффициентов дополнительно полагают, что в точках x1 и
x2 равны и их производные
q( x)  a0  a1  a2 (2 x  x1  x2 )  2a3 ( x  x1 )( x  x2 )  a3 ( x  x1 ) 2  F ( x) .
Тогда уравнения для определения коэффициентов аппроксимирующего
полинома примут вид
q ( x1 )  a0  F ( x1 ),  a0
q ( x2 )  a0  a1 ( x2  x1 )  F ( x2 ),  a1
q( x1 )  a1  a2 ( x1  x2 )  F ( x1 ),  a2
.
q( x2 )  a1  a2 ( x2  x1 )  a3 ( x2  x1 ) 2  F ( x2 ),  a3
Для определения точки минимума производная q( x) приравнивается
нулю. В результате получается квадратное уравнение, имеющее два корня. Из
двух корней выбирается тот, который принадлежит интервалу ( x1 , x2 ) . Этот
корень x является точкой минимума приближения q( x) на отрезке [ x1 , x2 ] и
используется в качестве приближения к точке минимума x* .
Новыми точками x1 и x2 для осуществления следующей итерации
являются концы того из отрезков [a, x] и [ x, b] , который содержит точку x* . Его
определяют по знаку производной F ( x) .
Если F ( x)  0 , то точка x лежит на участке монотонного возрастания
F ( x) , поэтому x*  x и точку минимума следует искать на отрезке [a, x] .
Если F ( x)  0 , то точка x лежит на участке монотонного убывания F ( x) ,
поэтому x*  x и точку минимума следует искать на отрезке [ x, b] .
Равенство F ( x)  0 означает, что точка минимума найдена точно и x*  x .
Алгоритм поиска точки минимума с кубической аппроксимацией [1]
Алгоритм поиска точки минимума с кубической интерполяцией [2]
Алгоритм поиска минимума функции с кубической интерполяцией
сводится к выполнению следующих этапов.
1 этап. Задать начальную точку x0 , величину шага x  0 , 1 ,  2 - малые
положительные числа, характеризующие точность ( F ( x)  1 ,
x  x1
  2 ).
x
2 этап. Вычислить производную F ( x0 ) .
3 этап. Проверить знак производной в точке x0 .
Если F ( x0 )  0 , то вычислить xk 1  xk  2k x, k  0,1,..., . до точки xm , в
которой F ( xm1 )* F ( xm )  0 .
Если F ( x0 )  0 , то вычислить xk 1  xk  2k x, k  0,1,..., . до точки xm , в
которой F ( xm1 )* F ( xm )  0 .
4
этап.
Положить
и
вычислить
x1  xm1 , x2  xm
F ( x1 )  F1 , F ( x1 )  F1, F ( x2 )  F2 , F ( x2 )  F2 .
5 этап. Найти точку минимума кубического интерполяционного полинома
по формуле
 x2 ,   0

x   x2   ( x2  x1 ), 0    1,
x ,   1
 1
2
1/ 2
F2  w  z
3( F1  F2 )
( z  F1* F2) , x1  x2
 F1 F2 , w   2
где  
, z
.
1/ 2
F2  F1  2w
x2  x1
( z  F1* F2) , x1  x2
Вычислить F ( x) .
6 этап. Проверить условие убывания.
Если F ( x)  F ( x1 ) , перейти к этапу 7.
1
2
Если F ( x)  F ( x1 ) , вычислить x по формуле x  x  ( x  x1 ) до тех пор, пока
не будет выполнено неравенство F ( x)  F ( x1 ) .
7 этап. Проверить выполнение условий окончания:
F ( x)  1 ,
x  x1
 2 .
x
Если оба условия выполнены, то процедура поиска точки минимума
закончена и x*  x .
Если хотя бы одно из условий не выполнено, то положить либо
x1  x, x2  x1 при F ( x)* F ( x1 )  0 , либо x1  x, x2  x2 при F ( x)* F ( x2 )  0 .
Перейти к шагу 5.
Примечание. На этапах 2-3 реализуется эвристическая процедура поиска
границ интервала неопределенности, где изменение знака производной
свидетельствует о переходе через точку минимума.
Варианты заданий
Варианты заданий приведены в таблице.
Таблица. Варианты заданий
№
F(X) =
Тип
экстрем
ума
max
Исходный
интервал
[4; 9]
0.02
Погрешность
1
ctg105
. x  x2  0
2
x 2  sin( x)
min
[-1; 0]
0.005
3
0.1  x  cos(x)
max
[4; 9]
0.02
4
exp( x)  x 2
exp( x)  1
x
 x  ( x  2) / x 2
x 1
ln( x)
x  ln(ln(x))
0.2  x  sin( 2 x)
5x 2  1
x
2
5 /( x  2 x  5)
exp(x  1)  1 / x
exp(1 / x)  ln( x)
x  exp(0.5x)
1  exp( x)
x
2  x  x2
exp( x)  1 /(1  x)
min
[-1; 0]
0.005
min
[0.5; 1]
0.001
min
[-2; 0]
0.01
min
[-1.5; 3]
0.01
min
[1.3; 3.0]
0.01
max
[0; 3]
0.02
min
[0; 2.5]
0.02
max
[0.8; 2.0]
0.008
min
[0; 1.5]
0.01
min
[1; 3]
0.012
max
[0; 3]
0.02
max
[-1; 0.5]
0.005
min
[0; 2]
0.01
min
[0; 2]
0.01
x 4  2x 2  4x
x 2  x  exp( x)
exp(x)  1 /( x  2)
min
[-1; 0]
0.002
min
[0; 1]
0.005
min
[-1; 1]
0.01
5 x 2 exp(0.5 x)
x lg(x)
max
[2; 6]
0.02
min
[0; 2]
0.01
min
[0.5; 2]
0.01
24
5/ x  x
exp(2 x)  x 2 / 2
min
[0; 1.5]
0.01
25
2  (ln( x)) 2  x / 2
min
[0.5; 2]
0.005
26
x 2  1 / arctg( x)
min
[0; 2]
0.005
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
Задание
1. Составить блок-схемы алгоритмов поиска точки экстремума заданной
функции.
2. Построить график функции для выбора границ первоначального интервала.
3. По разработанным алгоритмам составить программы поиска минимума
функции.
4. Найти координаты и значение функции в точке минимума всеми методами.
5. Найти точное значение координаты точки минимума, используя
необходимые и достаточные условия экстремума.
6. Проанализировать полученные результаты и сделать выводы по достигнутой
точности и количеству вычислений функции.
7. Дать письменные ответы на контрольные вопросы.
Контрольные вопросы
На основе полученных результатов решения задачи минимизации в работах
1 и 2 дать ответы на следующие вопросы:
1. Какие методы более эффективны?
2. Какие методы Вы рекомендуете для решения задачи минимизации Вашего
варианта? Ответ обосновать.
СОДЕРЖАНИЕ ОТЧЕТА
1. Цель работы.
2. Формулировка задачи.
3. Блок-схемы алгоритмов поиска минимума.
4. Графическое представление функции.
5. Листинги программ.
6. Результаты вычислений.
7. Сравнительная характеристика методов.
8. Выводы.
ЛИТЕРАТУРА
1. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации: Учебное пособие.
– СПб.: Издательство «Лань», 2011. – 352 с.
2. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах:
Учебное пособие. – М.: Высшая школа, 2002.- 544 с.
Временной ресурс:
- аудиторные занятия – 2 часа;
- самостоятельная работа – 8 часов.
Итоговая оценка защиты лабораторной работы
Всего: 8 баллов, в том числе:
- метод средней точки
- метод хорд
- метод Ньютона
- метод кубической аппроксимации
- 2 балла;
– 2 балла;
- 2 балла;
- 2 балла.
Численные методы одномерной минимизации с использованием
производной
Методические указания к выполнению лабораторной работы
Составитель – Юрий Владимирович Бабушкин
Подписано к печати ___._______. 2015 г.
Формат 60*84/16. Бумага офсетная.
Плоская печать. Усл. печ. л. _____. Уч. – изд. л. ____.
Тираж 150 экз. Заказ ____. Цена свободная.
ИПФ НИ ТПУ. Лицензия ЛТ № 1 от 18.07.94.
Типография НИ ТПУ. 634034, Томск, пр. Ленина, 30.