69899

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

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

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

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

Русский

2014-10-12

503.5 KB

13 чел.

Лабораторная работа №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


 

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

39147. Управление процессами технической эксплуатации изделий ЛА, заменяемых по состоянию 3.12 MB
  Лабораторная работа №2 Тема: Управление процессами технической эксплуатации изделий ЛА заменяемых по состоянию. Цель: Использование моделей экранов и замены изделий подверженных износу и старанию для управления процессами технической эксплуатации.Сформировать модель процесса технической эксплуатации изделий заменяемых по состоянию; 2.Определить характеристики процесса технической эксплуатации изделий заменяемые по состоянию; 2.
39149. Программное обеспечение вычислительной техники и автоматизированных систем 100.5 KB
  Техникум-интернат, как учреждение среднего профессионального образования получает право на общеобразовательную деятельность и льготы, представляемые законодательством Российской Федерации через лицензию, выданную Министерством социальной защиты населения Российской Федерации.
39150. РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ «УЧЕТ СОЦИАЛЬНЫХ ДАННЫХ СТУДЕНТОВ» НА ПРИМЕРЕ ФКОУ СПО «КАЛАЧЕВСКИЙ ТЕХНИКУМ-ИНТЕРНАТ» 70.8 KB
  Цель данной работы – создание программного модуля учета социальных данных студентов для ФКОУ СПО «Калачевский техникум-интернат». Заказчиком данного программного модуля является социально-педагогическая служба техникума, которой требуется полный и точный контроль над социальными данными всех студентов техникума. Лучшее решение этой задачи – внедрение программного модуля, который автоматизирует данный процесс учета данных.
39152. Философия для аспирантов 1.73 MB
  Основное внимание уделено философскому анализу науки как специфической системы знания формы духовного производства и социального института. Рассмотрены общие закономерности развития науки ее генезис и история структура уровни и методология научного исследования актуальные проблемы философии науки роль науки в жизни человека и общества перспективы ее развития и ряд других проблем. Рассчитано прежде всего на аспирантов и соискателей готовящихся к экзаменам кандидатского минимума а также всех желающих составить собственное представление...
39153. КОНКУРЕНТОСПОСОБНОСТЬ ТОВАРА: АНАЛИЗ И УПРАВЛЕНИЕ 164 KB
  Целью данной работы и является 1) Определение и анализ тех факторов, за счет которых формируется конкурентоспособность товара, 2) Определить, что же это собственно такое – конкурентоспособность товара и 3) Каковы пути повышения конкурентоспособности товаров, выпускаемых предприятием.
39154. Оценка конкурентоспособности товаров и услуг на ООО «сервис-техника» 237.5 KB
  Самое главное в экономике любой страны – это малый бизнес. Во многих экономически развитых странах, по словам электронных СМИ, доля продукции, производимой малыми предприятиями в годовом ВВП, доходит до 60%. В этих странах на малых предприятиях работает минимум половина всего населения. Новые предприятия успешно создаются и функционируют, производят качественную и конкурентоспособную продукцию.
39155. Классификация компьютеров 496.94 KB
  Специалисты а таковыми являются в наш век все подростки старше десяти лет не преминут заметить что компьютер это не мозг по крайне мере пока уточнят особенно талантливые. Это простонапросто еще один инструмент еще одно устройство придуманное для того чтобы облегчить наш труд или усилить нашу власть над природой. Именно поэтому я и решил что моя будущая специальность будет связана с компьютерами: вопреки опасениям писателейфантастов человек не стал придатком машины а получил возможность лучше проявить свои...