69899

Безусловная одномерная оптимизация

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

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

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

Русский

2014-10-12

503.5 KB

16 чел.

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

Тема: Безусловная одномерная оптимизация

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

1. Краткие теоретические сведения

1.1 Постановка задачи одномерной безусловной

оптимизации

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

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

x*=arg min f(x), xX, 

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

Другая распространенная запись задачи минимизации

        .

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

В методах одномерной оптимизации вместо X=R рассматривается отрезок X=[a,b], содержащей искомое решение x*. Такой отрезок называется отрезком неопределенности, или отрезком локализации. Относительно целевой функции f(x) часто предполагается, что она унимодальная.

Определение: Функция f(x) называется унимодальной на X=[a,b], если существует такая точка x*X, что

f(x1)>f(x2), если x1<x2<x*, x1,x2X,

f(x1)<f(x2), если x*<x1,x2, x1,x2X.

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

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

Определение: Функция f(x) называется выпуклой на x=[a,b], 

если f(x1+(1-)x2)f(x1)+(1-)f(x2) 

при любых x1,x2,X и всех , 01.

Если при любых x1,x2,X неравенство будет строгим, то функция f(x) называется строго выпуклой.

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

1.2 Алгоритм пассивного поиска минимума

Отрезок [a,b] исходный отрезок неопределенности. Пусть N - число точек, в которых необходимо провести вычисления целевой функции f(x), т.е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:

Среди вычисленных значений {f(xi)} (i=1,N), ищется точка xj , в которой достигается минимум:

f(xj)= min f()

        1iN

Найденная точка принимается за приближенное решение задачи . Исходный отрезок неопределенности [a,b] после экспериментов в N точках сужается до [xj-1,xj+1], длина которого равна:

Точность найденного решения равна половине отрезка неопределенности, т.е. , где  и x* - точное решение.

1.3 Алгоритмы активного поиска минимума

В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начнем с методов блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно ni экспериментов), общее число экспериментов будет ), т.е. блок – это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {xij (j=1,2,…,ni}(последовательный поиск). Если размеры блоков равны единице, т.е. ni=1, то мы имеем обычный последовательный алгоритм поиска.

1.3.1 Алгоритм равномерного блочного поиска

Схема алгоритма

Шаг 1.  Задаются исходный отрезок неопределенности [a,b], - точность приближенного решения , число экспериментов в блоке – n (нечетное, n=2k-1). Проводим эксперимент в середине отрезка [a,b], т.е. вычисляем yk=f(xk), где xk=(a+b)/2.

Шаг 2.  Проводим эксперименты в остальных точках блока: yi=f(xi), где xi=a+i*(b-a)/(n+1), i=1,2,..,n, ik. Находим точку xj, в которой достигается минимум среди вычисленных значений: f(xj)=min f(xi), следовательно, точное значение минимума x* содержится на отрезке [xj-1,xj+1].

Шаг 3.  Полагаем a=xj-1, b=xj+1, xk=xj, yk=yj. Если b-a2, то ,  и поиск заканчивается. Иначе перейти к шагу 2. Если заданная точность достигнута после т итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех N вычислений (N=n+(m-1)(n-1)=(n-1)m+1) будет:

и  

1.3.2 Алгоритм деления интервала пополам

Это вариант предыдущего алгоритма при n=3.

Схема алгоритма.

Шаг 1. Задаются a,b,. Производим эксперимент в точке x2=(a+b)/2, т.е. вычисляем y2=f(x2).

Шаг 2.  Проводим эксперименты в остальных точках блока: x1=(a+x2)/2, y1=f(x1), x3=(x2+b)/2, y3=f(x3).

Находим  такую, что f(xj)=min {f(xi)}.

                                                                      

 Тогда точное решение x* содержится на отрезке [xj-1,xj+1]. Предполагается .

Шаг 3. Полагаем a=xj-1, b=xj+1, x2=xj, y2=yj. Если b-a2, то   и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число проведенных экспериментов равно N=2к+1, а длина получившегося отрезка неопределенности будет , где [z] – целая часть числа z. Следовательно, достигнутая точность будет , =1/2LN.

1.3.3 Метод дихотомии

Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента. Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек , в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и, соответственно, расположение точек равномерным. Если блок содержит два эксперимента, то оптимальное (дельта оптимальное) расположение точек, в которых будут проводится эксперименты, это как можно ближе к середине отрезка. Такое расположение точек позволяет получить наименьший отрезок неопределенностей после экспериментов в блоке.

Схема алгоритма.

Шаг 1.  Задаются a,b, и - малое положительное число, значительно меньшее чем .

Шаг 2.  Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках близких середине: y1=f(x-), y2=f(x+).

Шаг 3.  Определяется следующий отрезок локализации, т.е. определяется какой из отрезков [a,x+] или [x-,b] содержит точное решение x*. Если y1y2, то это отрезок [a,x+] и b=x+, иначе это отрезок [x-,b] и a=x-, т.е. выбранный отрезок локализации мы снова обозначили как [a,b].

Шаг 4.  Если b-a2, то x=(a+b)/2,  и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N=2к, а длина получившегося отрезка неопределенности . Следовательно, .

А теперь перейдём к рассмотрению чисто последовательных методов поиска.

1.3.4 Метод золотого сечения

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

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [] или []. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки  и  должны быть симметричны относительно середины отрезка []. В этом случае длины отрезков [] и [] будут равны. Таким образом, остаётся вопрос как выбрать точку .

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

т.е. точка делит отрезок [] по правилу «золотого сечения», где  - есть «золотое отношение». Точка  определяется как точка симметричная к  относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости [], содержащий точку , или отрезок неопределённости [], содержащий точку . Оказывается, что остающаяся точка на суженном отрезке неопределённости делит его вновь по правилу «золотого сечения». Следовательно, чтобы, в свою очередь, уменьшить новый отрезок неопределённости, нам не достаёт одного эксперимента, а именно, вычисления целевой функции в точке, симметричной к оставшейся точке относительно середины этого нового отрезка. Всё продемонстрировано на рисунке,

а) 

б) 

где буквы со штрихами обозначают новый отрезок неопределённости. Вариант а) соответствует случаю, если новым отрезком неопределённости будет [], а вариант б) – отрезку [].

В приводимой ниже схеме алгоритма остающиеся отрезки неопределённости переименовываются каждый раз как [], а точки, в которых проводятся эксперименты на этом отрезке, обозначается через  и , причём . Кроме того,  и  имеют следующие значения:  и .

Схема алгоритма

Шаг1. Задаются  и . Вычисляют .

Шаг2.  а) Если , то полагают  и вычисляют .

б) Если , то полагают  и вычисляют .

Шаг3.  Если , то переходят к шагу 2. Иначе если , то полагают  и  если , то полагают  и

Закончить поиск.

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

.

  1.  Метод чисел Фибоначчи

Этот метод применяется, когда число экспериментов  заранее задано. Метод чисел Фибоначчи, также как и метод золотого сечения относится к симметричным методам, т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка. Вот только выбор точки  происходит на основе других соотношений. Для этого используются числа Фибоначчи: , где   и .

Точка  определяется из соотношения:

т.е. . Точка  делит  на две неравные части. Отношение малого отрезка к большему равно . Точка  определяется как точка, симметричная к  относительно середины отрезка . Поэтому . При этом будет выполняться условие .

В результате экспериментов в точках  и  у нас получится отрезок неопределённости , содержащий точку , или отрезок неопределённости , содержащий точку . Остающаяся точка делит новый отрезок неопределённости на две неравные части в отношении:

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

а)

                                                                                   

                                                                                             

б)

 

Для того чтобы в свою очередь уменьшить получившийся отрезок неопределённости, надо определить симметричную точку относительно середины отрезка и произвести эксперимент в ней. Этот процесс продолжается, пока не будет проведено  экспериментов.

Схема алгоритма

Шаг 1.  Задаются  Вычисляются числа Фибоначчи . Определяется:

Шаг 2.  а) Если , то полагают  и вычисляют .

б) Если , то полагают  и вычисляют .

Повторить шаг 2  раза.

Шаг 3.  Если , то полагают  и . Если , то полагают  и .

Закончить поиск.

Длина отрезка неопределённости в методе Фибоначчи .

1.4 Методы поиска, основанные на аппроксимации

целевой функции

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

1.4.1 Метод касательных

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

Полученная аппроксимирующая функция есть ломанная состоящая из прямой  на  и  на , где с – точка пересечения касательных. Легко заметить, что при  и  минимум аппроксимирующей функции достигается в точке с. Значение точки пересечения с можно определить по формуле

В точке с производятся вычисления  и . Если , то решением задачи будет . Если же , то в качестве следующего отрезка неопределённости будет . Если же , то – отрезок . Процесс повторяется до тех пор, пока  или отрезок неопределённости не достигнет заданной точности.

Схема алгоритма

Шаг 1.  Заданы . Вычислить .

Шаг 2.  Если , то полагаем . Поиск окончен. Если , то вычислить . Если z=0, то полагаем  и поиск окончен. Если , то . Если , то . Повторить шаг 2.

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

Рассмотрим алгоритм квадратичной интерполяции или метод парабол, т.е. в качестве аппроксимирующей функции используется парабола. Для однозначного задания параболы необходимы три точки. Пусть имеются три точки, для которых выполняется   a<c<b,  f(c)f(a),  f(c)f(b). Так как [a,b] – отрезок неопределенности и f(x) – унимодальная функция, то найти такую точку c  нетрудно. Парабола, проходящая через три точки (a,f(a)), (c,f(c)), (b,f(b)), имеет вид

Поскольку f – унимодальная функция, то хотя бы одно из неравенств    f(c)f(a), f(c)f(b) строгое и, следовательно, коэффициент при старшем члене P(x) положителен. Тогда P(x) достигает минимума в точке

,

причем (a+c)/2t(c+b)/2. Эта точка и выбирается в качестве точки очередного вычисления значения функции.

Если оказалось, что t=c, условимся в качестве точки очередного вычисления выбирать точку (a+c)/2. Итак, следующее вычисление проводится в точке

Определим новый отрезок неопределенности с лежащей внутри него точкой, для которой выполняются условия аналогичные условиям, которым удовлетворяла точка c. В силу унимодальности функции f и  в зависимости от выполнения или невыполнения условий x<c, f(x)<f(c), f(x)=f(c) это будут отрезки с точкой внутри: [a,c] и x; [x,b] и c; [x,c] и (x+c)/2; [a,x] и c; [c,b] и x; [c,x] и (x+c)/2. Смотри рисунок. Далее строится парабола, определяется ее минимум, и т.д., до тех пор, пока длина отрезка неопределенности не удовлетворяет заданной точности.

Схема алгоритма

Шаг 1. Задаются a,c,b и . Вычислить ya=f(a), yc=f(c), yb=f(b).

Шаг 2. Вычислить , y=f(x), где

Шаг 3. А) При x<c.

Если y<yc, то b=c, c=x, yb=yc, yc=y.

Если y>yc, то a=x, ya=y.

Если y=yc, то a=x, b=c, c=(x+c)/2, ya=y, yb=yc, yc=f(c).

Б) При x>c.

Если y<yc, то a=c, c=x, ya=yc, yc=y.

Если y>yc, то b=x, yb=y.

Если y=yc, то a=c, b=x, c=(x+c)/2, ya=yc, yb=y, yc=f(c).

Шаг 4. Если b-a, то закончить поиск, положив , иначе перейти к шагу 2.

2. Задание на лабораторную работу

2.1. Изучить предлагаемые методы одномерной безусловной оптимизации.

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

а) Если в варианте задания указано число экспериментов N, то сравнить заданные  в варианте методы по получаемой длине отрезка неопределенности.

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

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

3. Варианты заданий

3.1 Методы одномерной безусловной оптимизации:

а) пассивный оптимальный алгоритм;

б) алгоритм блочного равномерного поиска;

в) алгоритм деления интервала пополам;

г) метод дихотомии;

д) метод золотого сечения;

е) метод Фибоначчи;

ж) метод касательных;

з) метод парабол.

3.2 Варианты задач

Целевая функция

Отрезок [a,b]

Точность или число экспериментов N

1

[-1,0]

N=22

2

[0,1]

N=23

3

[-1,0]

N=20

4

[0,1]

N=21

5

[-2,0]

=10-3

6

[0,2]

=1.5*10-3

7

[0,2]

=5*10-3

8

[-1,0]

N=18

9

[-1,0]

=10-3

10

[0,3]

=5*10-4

9


 

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

13855. Dangerous minds 40 KB
  Копысова Е.А. Dangerous minds Приступая к анализу политикоэтических интенции в вышеобозначенном фильме стоит определить как мы будем интерпретировать политическое в данном контексте. Учитывая специфику выбранной картины целесообразно понимать политическое как ...
13856. Профессиональная учительская этика в романе Белл Кауфман «Вверх по лестнице, ведущей вниз» 52.5 KB
  Роман Белл Кауфман Вверх по лестнице ведущей вниз опубликованный в 1960х годах заслужил признание не только в США роман обрел известность стал популярным без преувеличения во всем мире. Действие романа происходит в школе им. Кальвина Куллинджа в НьюЙорке. Главный г
13857. «Белая гвардия» Булгаков. Эссе 43 KB
  Вадим Матвеев Белая гвардия Булгаков. Эссе. Роман Булгакова наполнен историческими событиями от начала и до конца. 1918 год. Украина объявила независимость провозгласив гетмана в связи с чем обострились националистические настроения и рядовые украинцы сразу ра
13858. Джордж Оруэлл «1984» 32.58 KB
  Мосогутова Евгения Политология 4 курс Джордж Оруэлл 1984 Роман антиутопия Оруэлла1984 отражает настроения царившие в ХХ веке. Автор берет за основу реалии современного ему мира и возводит их в гроте
13859. Эссе Анализ романа Шодерло де Лакло «Опасные связи» 55.5 KB
  Эссе Анализ романа Шодерло де Лакло Опасные связи. Опасные связи единственный роман генерала Шодерло де Лакло основанный по утверждению автора на реальных событиях. Роман эпистолярного жанра что должно убедить читателя в подлинности излагаемого повествовани...
13860. Креативный анализ фильма « Последний урок» 24.46 KB
  Петрова Регина Креативный анализ фильма Последний урок Политическая целесообразность В основе сюжета фильма лежит история учительницы которая работает во французской школе для трудных подростков. Основная часть учеников это иммигранты из арабских стран...
13861. Анализ фильма «Конформист» 46 KB
  Ромазанов Д.М. Политология 4 курс. Анализ фильма Конформист Фильм Конформист режиссера Бернардо Бертолуччи снят в 1970 году по роману Альберто Моравиа. Главный герой Марчелло Клеричи интеллектуал о чем можно судить из его диалого
13862. Мультфильм «Персеполис» 41 KB
  абиров Д.Р. Задание по курсу Политическая этика Мультфильм Персеполис Персеполис французский полнометражный анимационный фильм режиссёра Маржана Сатрапии французской писательницы иранского происхождения. Сюжет в кратце: Бойкая Марьян восьми л
13863. Анализ фильма «Молитвы за Бобби» с точки зрения этики и морали 27.34 KB
  Анализ фильма Молитвы за Бобби с точки зрения этики и морали. Место действия. Действия фильма разворачивается в небольшом городе Walnut Creek в Соединенных Штатах Америки штат Калифорния 60 тысяч населения. Город представляет собой американскую мечту с красивыми уло...