Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



 

В соответствии с рассматриваемым методом подлежащая мини­мизации функция f аппроксимируется полиномом третьего порядка. Логическая схема метода аналогична схеме методов с использовани­ем квадратичной аппроксимации. Однако в данном случае построе­ние аппроксимирующего полинома проводится на основе меньшего числа точек, поскольку в каждой точке можно вычислять значения как функции, так и ее производной.

Работа алгоритма начинается в произвольно выбранной точке x1. находится другая точка х2, такая, что производные f '(x1) и f '(х2) имеют различные знаки. Другими словами, необходимо заключить стационарную точку `х, в которой f '(х)=0, в интервал между х1и х2. Аппроксимирующая кубичная функция записывается в следующем виде:

`f (Х)=а01(х—х1)+а2(х—х1) (х—х2} +а3(х—х1)2(х—х2). (2.8)

Параметры уравнения (2.8) подбираются таким образом, чтобы зна­чения `f (х) и ее производной в точках х1и х2 совпадали со значениями f (х) и f '(x) в этих точках. Первая производная функции `f(x) равна

Коэффициенты а0, a1, a2 и a3 уравнения (2.8) определяются по из­вестным значениям f(x1), f(x2), f '(x1) и f '(х2) путем решения следую­щей системы линейных уравнений:

Заметим, что данная система легко решается рекурсивным ме­тодом. После того как коэффициенты найдены, действуя по анало­гии со случаем квадратичной аппроксимации, можно оценить коор­динату стационарной точки функции f с помощью аппроксимирую­щего полинома (2.8). При этом приравнивание к нулю производной (2.9) приводит к квадратному уравнению. Используя формулу для вычисления корней квадратного уравнения, запишем решение, определяющее стационарную точку аппроксимирующего кубичного полинома, в следующем виде:

Формула для w обеспечивает надлежащий выбор одного из двух корней квадратного уравнения; для значений m, заключенных в ин­тервале от 0 до 1, формула (2.10) гарантирует, что получаемая точка `х расположена между х1и х2. Затем снова выбираются две точки для реализации процедуры кубичной аппроксимации — `х, и одна из точек x1или х2, причем значения производной исследуемой функции в этих точках должны быть противоположны по знаку, и процедура кубичной аппроксимации повторяется.

Приведем формализованное описание алгоритма. Пусть заданы начальная точка х0, положительная величина шага D и параметры сходимости e1 и e2.

Шаг 1. Вычислить f ‘0).

Шаг 2. Вычислить значения f '(x) в точках хк+1при K=0, 1, 2, ... вплоть до точки хM, в которой f '(xM-l) f '(xM)≤ 0. Затем положить xl=xM-1, х2M. Вычислить значения f1 f2, f 1и f ’2.

Ш а г 3. Найти стационарную точку `х аппроксимирующего ку­бичного полинома, пользуясь формулой (2.10).

Ш а г 4. Если f(x)< f(x1 ), перейти к шагу 5. В противном слу­чае вычислять `х по формуле `x=`x+1/2(`xх2) до тех пор, пока не будет выполняться неравенство f(`x)≤ f(xl).

Ш а г 5. Проверка на окончание поиска.

Затем перейти к шагу 3.

Заметим, что шаги 1 и 2 реализуют процедуру поиска границ интервала по эвристическому методу, причем изменение знака про­изводной используется в качестве критерия перехода через точку оптимума. На шаге 3 проводятся вычисления координаты точки оптимума аппроксимирующего полинома. Шаг 4 ассоциирован с проверкой того факта, что полученная оценка действительно явля­ется улучшенным приближением к точке оптимума. В случае когда значения производной вычисляются непосредственно, метод поиска с использованием кубичной аппроксимации, безусловно, оказыва­ется более эффективным по сравнению с любым из представленных выше методов поиска. Однако если значения производной вычисля­ются путем разностного дифференцирования, то предпочтение сле­дует отдать методу Пауэлла, основанному на квадратичной аппрок­симации.

Пример 2.12. Поиск с использованием кубичной аппроксимации и производных

 

Опять рассмотрим задачу, в которой требуется

минимизировать f(x)=2x2+16/x.

Пусть начальная точка х0=1 и длина шага D = 1. В качестве пара­метров сходимости используем

 

Поиск закончен.

Заметим, что при тех же самых исходных точках x1=l и х2=2 метод Пауэлла в примере 2.9 позволил получить оценку `х=1, 714, тогда как метод с использованием кубичной аппроксимации привел к оценке `х=1, 5657. Точная координата точки минимума равна 1, 5874, что указывает на преимущество полиномиальной аппрок­симации более высокого порядка.

Сравнение методов

 

С помощью теоретических выкладок можно показать, что такие методы точечного оценивания, как метод Пауэлла или метод поиска с использованием кубичной аппроксимации и производных, су­щественно эффективнее методов исключения интервалов, среди ко­торых выделяется метод золотого сечения. В частности, известно, что применение схемы поиска с использованием квадратичной ап­проксимации позволяет достигнуть асимптотически суперлинейной скорости сходимости к точке истинного минимума, т. е. отклонение (k+1)-й оценки от истинной координаты точки минимума пропорционально отклонению k-й. оценки, возведенному в степень a> 1 (как показано в [6], a=1, 3). Для сравнения отметим, что если при реализации метода золотого сечения в качестве k-й оценки коорди­наты точки истинного минимума берется координата средней точки интервала, полученного в результате k вычислений значения функ­ции, то отклонение этой оценки от точной координаты линейно убывает при переходе от k-й к (k+1)-й итерации. Это означает, что в случае, когда интервалы сходимости сравнимы между собой, метод, основанный на квадратичной аппроксимации, сходится быстрее, чем любой из методов исключения интервалов. Разумеется, сделанный вывод справедлив лишь в предположении, что интервалы сходи­мости сравнимы между собой, а исследуемая функция является достаточно гладкой и унимодальной.

Результаты численных экспериментов, представленные в спе­циальной литературе, не подтверждают преимущества методов с ис­пользованием производных и квадратичной аппроксимации или метода исключения интервалов над остальными методами. Если для вычисления значений целевой функции требуется значительное машинное время, то, по мнению авторов работы [7], предпочтитель­нее использовать стратегию поиска, основанную на модификации метода Пауэлла. Это мнение подтверждается результатами вычис­лительных экспериментов, проведенных Химмельблау [8], который сравнил указанную стратегию поиска со схемой поиска по методу золотого сечения и показал, что модифицированный метод Пауэлла требует меньшего количества вычислений значения функции для достижения заданной точности при оценивании координаты точки минимума. Если необходимо получить решение с очень высокой степенью точности, то лучшими оказываются методы поиска на основе полиномиальной аппроксимации. С другой стороны, известно, что при исследовании мультимодальных или быстро изменяю­щихся функций метод Пауэлла сходится значительно медленнее, чем методы исключения интервалов. Таким образом, если очень важно добиться надежной работы алгоритма, то целесообразно выбрать метод золотого сечения. Поэтому поисковые методы типа метода Пауэлла следует использовать совместно с методом золотого сечения, переход к алгоритму которого осуществляется в тех слу­чаях, когда реализация соответствующих итераций на ЭВМ свя­зана с определенными трудностями. Читатель также может обра­титься к книге Брента [9], в которой проведен анализ относительной эффективности различных методов поиска.

Сравнительное исследование трех методов точечного оценива­ния, а именно метода средней точки, метода Пауэлла и метода по­иска с использованием кубичной аппроксимации, было проведено в соответствии с учебной программой по университетскому (Purdue University) курсу теории оптимизации. Перечисленные методы ис­пользовались для решения задачи минимизации функции f(x) =sink x при различных значениях k. Кроме того, для сравнения был также использован метод золотого сечения как наилучший из методов исключения интервалов.

Для оценки эффективности выбранных методов использовались три характеристики: время, затраченное на получение решения, точность решения и чувствительность к изменениям параметра схо­димости. Первые две характеристики исследовались путем варьи­рования значений, показателя степени k на множестве нечетных чисел от 1 до 79. Следует отметить, что для всех значений k минимум функ­ции достигается в точке х* =4, 71239; при этом f(x*)=—1, 0. Однако с увеличением k степень гладкости функции, которая обладает уз­кими впадинами в окрестности точки минимума, уменьшается. Это обстоятельство приводит к понижению точности и замедлению схо­димости методов точечного оценивания.

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

Заключение

 

В этой главе были представлены необходимые и достаточные условия оптимальности решения задач безусловной оптимизации с целевыми функциями одной переменной. Показано, что необходи­мое условие наличия оптимума в данной точке заключается в том, что данная точка должна быть стационарной, т. е. первая производ­ная функции должна обращаться в нуль в этой точке. Для того чтобы проверить, соответствует ли стационарная точка минимуму, мак­симуму или является точкой перегиба, используются производные второго и более высоких порядков. Затем были рассмотрены вопро­сы, связанные с получением оптимальных решений на основе мето­дов поиска, которые носят название методов исключения интервалов и ориентированы на нахождение точки оптимума в заданном интер­вале. Показано, что алгоритм поиска по методу золотого сечения, вообще говоря, является наиболее предпочтительным вследствие высокой вычислительной эффективности и простоты реализации. Методы исключения интервалов основаны на процедуре простого сравнения значений функции в двух пробных точках; при таком сравнении используется только отношение порядка на множестве значений функции. Для того чтобы учесть величину разности между значениями функции, разработан ряд так называемых методов то­чечного оценивания, позволяющих определить точку оптимума с помощью квадратичной или кубичной аппроксимации целевой функции. В условиях, когда выполняется предположение о том, что интервалы сходимости сравнимы между собой, а исследуемая функ­ция является достаточно гладкой и унимодальной, методы точечного оценивания сходятся значительно быстрее, чем методы исключения интервалов. Однако при исследовании мультимодальных или быстро изменяющихся функций наиболее надежным оказывается метод зо­лотого сечения. В заключение сформулированы рекомендации, в со­ответствии с которыми методы поиска с использованием квадратич­ной аппроксимации типа метода Пауэлла, вообще говоря, следует применять совместно с методом золотого сечения, переход к алго­ритму которого реализуется в тех случаях, когда выполнение соот­ветствующих итерационных циклов на ЭВМ сопряжено с определен­ными трудностями.

Контрольные вопросы и задачи

 

2.1. Что такое точка перегиба, и как ее идентифицировать?

2.2. Как проверить, является ли функция выпуклой или вогнутой?

2.3. В чем состоит свойство унимодальности функций и в чем заключается важное значение этого свойства при решении задач оптимизации с одной переменной?

2.4Пусть данная точка удовлетворяет достаточным условиям существования локального минимума. Как установить, яв­ляется ли этот минимум глобальным?

2.5. Сформулируйте условие, при выполнении которого метод поиска, основанный на полиномиальной интерполяции, может не привести к получению правильного решения.

2.6. Являются ли методы исключения интервалов в целом более эффективными, чем методы точечного оценивания? Почему?

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

2.8. Заданы следующие функции одной переменной:

(а) f(x)=x5+x4(x /3)+2,

(б) f(х)=(2х + 12(x-4).

Для каждой из заданных функций найдите

(1) интервал(ы) возрастания, убывания;

(2) точки перегиба (если таковые имеются);

(3) интервал(ы), в котором (в которых) функция вогнута, выпукла;

(4) локальные и глобальный максимумы (если таковые име­ются);

(5) локальные и глобальный минимумы (если таковые име­ются).

2.9. Паром, который должен курсировать через канал, конструи­руется с таким расчетом, чтобы с его помощью можно было перевозить заданное количество груза в тоннах (L) в течение дня (рис. 2.17). Пусть стоимость парома без двигателей прямо

пропорциональна грузоподъемности парома (l), а стоимость двигателей прямо пропорциодальна произведению грузоподъ­емности на скорость движения парома (u) в кубе. Покажите, что полная стоимость парома минимальна в том случае, когда стоимость парома без двигателей в два раза превышает стои­мость двигателей. (Временем погрузки и разгрузки можно пренебречь, т. е. считается, что паром курсирует без остано­вок.)

2.10. Лесной пожар распространяется в узкой долине шириной 2 мили со скоростью 32 фут/мин (рис. 2.18). Содержать на­ступление огня можно путем построения заградительной противопожарной перегородки, пересекающей лес по всей ширине долины. Один рабочий может построить 2 фута пере­городки в минуту. Затраты на транспортировку каждого ра­бочего к месту событий и обратно составляют 20 долл.; оплата труда каждого рабочего составляет 6 долл. в час. Стоимость квадратной мили леса равна 2000 долл. Сколько рабочих

следует послать на борьбу с огнем, чтобы полные издержки были минимальны?

2.11. Рассмотрите задачу безусловной оптимизации с целевой функ­цией одной переменной f(x). Пользуясь приведенными в таб­лице данными о значениях производных порядка 1, 2, 3, 4 в точках xi (i=1, 2, ..., 10), идентифицируйте каждую из точек (установите, оказывается ли она точкой максимума, минимума, перегиба или не является точкой оптимума; ука­жите случаи, когда нельзя сделать определенный вывод и т. д.).

xi f ‘(xi ) f ''(xi ) f ‘’’(xi) f ”” (xi )
x1 + Нет данных Нет данных
x2 + Нет данных
x3 - Нет данных Нет данных
x4 - - Нет данных Нет данных
x5 - - Нет данных
x6 - -
x7 -
x8 - +
x9 + + Нет данных Нет данных
x10 - + -

 

2.13. Исследуйте функцию

f(x)=x3—12х+3 в интервале —4≤ x≤ 4

Найдите локальные минимумы, локальные максимумы, гло­бальный минимум и глобальный максимум f в заданном интер­вале.

2.14. Установите области, в которых следующая функция выпукла

или вогнута:

f (x) = e-x2

Найдите глобальный максимум и глобальный минимум этой функции.

2.15. Рассмотрите модель одного цикла управления запасами скоро­портящихся товаров, в которой спрос описывается случайной величиной с плотностью вероят­ности f, т.е. P (величина спроса ≤ x) = ò x0 f(x) dx; отсутствие запасов влечет за собой экономические потери;

С — стоимость единицы товара;

p — величина потерь, обусловленных отсутствием запасов (включая потери дохода и так называемого неосязаемого основного капитала);

r — продажная цена единицы товара;

l— ликвидационная стоимость единицы товара, не продан­ного к концу периода.

Задача заключается в том, чтобы определить оптимальный размер заказа Q, который максимизирует ожидаемую величи­ну чистого дохода за период. Ожидаемый чистый доход равен

(а) Покажите, что П(Q) — выпуклая функция Q(≥ 0).

(б) Объясните, как определить оптимальный размер заказа, пользуясь результатом, полученным в п. (а).

(в) Вычислите оптимальный размер заказа для следующего конкретного примера:

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

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

2.17. Реализуйте процедуру одномерного поиска точки оптимума функции

f(x)=3x2+(12/x3)—5 в интервале 1/2≤ x≤ 5/2,

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

2.18. Найдите точку минимума функции

f (х)=(10x3x2+x+5)2:

Заданы начальная точка х=2и длина шага D=0, 5.

(а) Воспользуйтесь методом исключения интервалов: поиск границ интервала эвристическим методом и шесть итераций по методу золотого сечения.

(б) Воспользуйтесь методом оценивания на основе квадратич­ной аппроксимации: три итерации по методу Пауэлла.

2.19. Найдите вещественные корни уравнения (с точностью до одного знака после запятой)

f (x)=3000— 100x2—4x5—6х6=0,

используя (а) метод Ньютона — Рафсона, (б) метод средней точки, (в) метод секущих. Полезно также написать программу для мини-ЭВМ, реализующую перечисленные методы поиска.

2.20. (а) Объясните, как можно преобразовать задачу 2.19 в нели­нейную задачу безусловной оптимизации с одной переменной, (б) Напишите программу для ЭВМ, реализующую поиск по методу золотого сечения, и используйте ее для решения задачи оптимизации, о которой идет речь в п. (а). Сравните получен­ное решение с решением задачи 2.19.

2.21. В результате экспериментов установлено, что траектория дви­жения космического тела описывается следующим уравнением [10]:

f (Х)=4х3+2х—3х2х/2.

Найдите корень уравнения f(х)=0 с помощью любого из мето­дов с использованием производных.

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

2.23. В структуре капитальных вложений на развитие химического завода важное место занимают затраты на приобретение и монтаж труб, а также затраты на установку насосного обо­рудования. Рассмотрите проект трубопровода длиной L фут., который должен обеспечивать подачу жидкости со скоростью Q галлон/мин. Выбор наиболее экономичного диаметра трубы D (дюйм.) осуществляется на основе минимизации функции затрат на приобретение труб, насосов и прокачивание жид­кости. Известно, что функция затрат в единицу времени в случае, когда, трубопровод состоит из труб, изготовленных из углеродистой стали, и центробежного насоса с электродвига­телем, может быть описана следующим выражением:

Сформулируйте соответствующую задачу оптимизации с од­ной переменной для проектирования трубопровода длиной 1000 фут., который должен обеспечивать подачу жидкости со скоростью 20 галлон/мин. Диаметр трубы должен быть заключен в пределах от 0, 25 до 6 дюйм. Решите эту задачу с помощью метода золотого сечения.


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 1454; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.061 с.)
Главная | Случайная страница | Обратная связь