Северин В.П. Методы ОП

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

го) выпукла (рис. 2.9, б). Для дифференцируемой строго вогнутой функции f (x) 0 .

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

31

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

f (v)

z

f (u)

y

Рис. 2.9. Выпуклая и вогнутая функции

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

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

2.4.Интервал неопределенности минимума унимодальной функции

Интервал [a, b] R , содержащий неизвестную точку минимума x функции f (x) , называется интервалом неопределенности.

Таким образом, если известно, что x [a, b] , но само значение x не известно заранее, то [a, b] – интервал неопределенности.

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

32

1)поиск интервала неопределенности;

2)уменьшение интервала неопределенности.

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

определению левее точки x функция монотонно убывает. Это означа-

33

ет, что для u v x должно выполняться неравенство fu fv , что противоречит условию. Аналогично доказывается утверждение для случая fu fv .

Эту теорему называют правилом исключения интервалов. Дей-

ствительно, из нее следует, что если выполняется неравенство fu fv ,

то полуоткрытый интервал (v, b] заведомо не содержит точку мини-

мума x и его следует исключить, приняв в качестве нового интервала неопределенности интервал [a, v] меньшей длины, чем исходный интервал [a, b] (рис. 2.11, а). Если же выполняется противоположное

неравенство fu fv , то заведомо не содержит точку минимума x полуоткрытый интервал [a, u) , и его следует исключить, приняв в ка-

честве нового интервала неопределенности меньший интервал [u, b]

(рис. 2.11, б).

f f

Рис. 2.11. Правило исключения интервалов

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

34

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

2.5. Поиск интервала неопределенности методом Свенна

Для поиска интервала неопределенности [a, b] унимодальной функции f (x) Свенном был предложен метод удвоения шага. Для начала работы метода задается начальная точка x0 и начальный шаг h 0 . В точке x0 вычисляется значение функции f0 f (x0 ) и выпол-

няется переход к следующей точке x1 x0 h с вычислением значения функции f1 f (x1) . Если f1 f0 , то выполняются итерации в поло-

жительном направлении относительно точки x0 по рекуррентной формуле удвоения шага

с вычислением значений функции fk f (xk ) до тех пор, пока не будет получена точка с не меньшим значением функции, чем значение функ-

35

fc fm . Таким образом, аналогично рис. 2.10 имеем интервал неопре-

свычислением

образом, будет определен интервал неопределенности со значениями

36

концов a xn 1 , b xn 1 , fa fn 1 , fb fn 1 и внутренняя точка интервала c xn со значением функции fc fn .

В результате работы метода Свенна устанавливаются значения границ интервала неопределенности. В любом случае интервал неопределенности [a, b] определяется тремя последними точками поис-

ка метода Свенна xn 1 , xn , xn 1 . При этом становятся известными значения функции на концах интервала неопределенности fa f (a) и fb f (b) , а также внутренняя точка интервала c и значение функции

вней fc f (c) (рис. 2.10).

Вметоде Свенна используются только значения целевой функции, поэтому это метод нулевого порядка. Метод Свенна с использованием формул (2.2) и (2.3) можно реализовать по следующему алгоритму.

А л г о р и т м м е т о д а С в е н н а .

Входные параметры: c – начальная точка поиска; h – начальный

шаг.

Выходные параметры: a и b – границы интервала неопределен-

4.Вычислить b c h , fb f (b) .

5.Если fb fc , то перейти к шагу 3, иначе перейти к шагу 11.

37

10.Если fa fc , то перейти к шагу 8.

11.Остановиться.

На шагах 1–5 выполняется поиск интервала в положительном направлении, а на шагах 6–10 – в отрицательном направлении.

Лабораторная работа

Т е м а л а б о р а т о р н о й р а б о т ы .

Разработка подпрограммы поиска интервала неопределенности. Ц е л ь л а б о р а т о р н о й р а б о т ы .

Разработать подпрограмму метода Свенна для поиска интервала неопределенности унимодальной целевой функции.

П о р я д о к в ы п о л н е н и я л а б о р а т о р н о й р а б о т ы .

ции f (x) и вычислить минимальное значение функции f f (x ) .

3.Написать подпрограмму вычисления значений функции f (x) с входным параметром x и выходным параметром f .

4.Протестировать подпрограмму вычисления функции f (x) при

1)за основу подпрограммы для поиска интервала неопределенности взять подпрограмму итерационного процесса из предыдущей лабораторной работы и модифицировать эту подпрограмму согласно алгоритму метода Свенна;

2)входные параметры подпрограммы: f (x) – целевая функция,

38

держащую номер точки поиска k , шаг поиска hk , значение функции

fk и значение переменной xk ;

5)итерации продолжаются до тех пор, пока выполняется неравенство k N ;

6)после окончания процесса оптимизации на экране должна отображаться таблица, имеющая соответствующий заголовок и представляющая процесс минимизации функции;

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

выходных параметров a , b , fa , fb , c , fc .

6. Написать общую программу для выполнения вычислительного процесса поиска интервала неопределенности и отображения на экране этого процесса в соответствии с требованиями:

1)за основу общей программы для поиска интервала неопределенности взять общую программу итерационного процесса из предыдущей лабораторной работы и модифицировать эту программу;

2)задать в программе значения x0 , x , h , , N ;

3)путем вызова подпрограммы метода Свенна с использованием подпрограммы вычисления функции f (x) и значений x0 , h , N реа-

лизовать итерационный процесс поиска интервала неопределенности с построением таблицы процесса на экране и получением массивов зна-

39

чений переменной X и функции F , границ интервала неопределенности a и b , значений функции на концах интервала fa и fb , внут-

ренней точки интервала c и значения в ней функции fc ;

4) с помощью подпрограммы графического отображения итерационного процесса, разработанной на предыдущей лабораторной рабо-

8. Выполнить анализ полученных результатов:

1) на основании табличной и графической информации о работе метода поиска интервала неопределенности определить конечные точки метода Свенна (a, fa ) , (b, fb ) , (c, fc ) и найденный этим методом интервал неопределенности [a, b] ;

2)на основании табличного и графического представления процесса поиска интервала неопределенности сделать вывод о верном нахождении границ интервала;

3)сделать вывод о правильности работы общей программы и всех используемых ею подпрограмм.

9. Ответить на вопросы преподавателя по теме лабораторной работы.

10. Оформить и сдать отчет о проведенной лабораторной работе.

С о д е р ж а н и е о т ч е т а :

1)титульный лист установленного образца с указанием организации, названия учебной дисциплины, темы работы, номера варианта, исполнителя и принимающего, города, года;

2)введение с кратким общим описанием предназначения методов

40