Сравнение методов и результаты вычислительных экспериментов

⇐ ПредыдущаяСтр 15 из 15

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

Химмельблау (см. [69, гл. 5]) приводит численные результаты реализации ряда методов. Полученные им данные представляют значительный интерес, поскольку Химмельблау не является сторонником того или иного метода. Он характеризует каждый метод (прямого поиска или градиентный) в соответствии с его устойчивостью, количеством требуемых вычислений значений функции и количеством необходимого для реализации алгоритма машинного времени при решении ряда тестовых задач. Устойчивость метода отражает успех в получении оптимального решения с заданной точностью для широкого круга задач. Химмельблау делает вывод, что методы Бройдена — Флетчера — Шэнно, Дэвидона — Флетчера — Пауэлла и метод прямого поиска Пауэлла лучше остальных методов. Более подробные сведения можно найти в книге Химмельблау.

Аналогичное, но менее полное исследование выполнено Сарджентом и Себастьяном в работе [70], где приведены результаты применения градиентных методов, в том числе алгоритмов Бройдена — Флетчера — Шэнно, Дэвидона — Флетчера — Пауэлла и Флетчера — Ривса. Они изучали влияние параметра сходимости для одномерного поиска, частоты возвратов к начальной итерации, положительной определенности матрицы Гессе для квазиньютоновских методов и точности вычисления компонент градиента. Полученные ими результаты указывают на превосходство квазиньютоновских методов (в частности, метода. Бройдена — Флетчера — Шэнно) при решении задач с функциями общего вида. Сарджент и Себастьян отмечают также, что точность расчетов на ЭВМ оказывает более заметное влияние на реализацию квазиньютоновских методов, чем на реализацию методов сопряженных градиентов. Это позволяет сделать вывод о том, что при расчетах на микро-ЭВМ (подобных тем, которые иногда используются в управлении технологическими процессами) метод Флетчера — Ривса может оказаться наиболее эффективным.

Карпентер и Смит [71] исследовали относительную эффективность вычислений по методу Ньютона для задач специальной структуры. Они сделали вывод, что для рассматриваемого круга задач методы Дэвидона — Флетчера — Пауэлла и метод Ньютона обладают преимуществом перед методом прямого поиска Пауэлла, а метод Дэвидона — Флетчера — Пауэлла превосходит метод Ньютона при решении задач большой размерности. Несколько позже Шэнно и Фуа [40, 56, 57] провели подробный анализ методов сопряженных градиентов и переменной метрики на основе вычислительных экспериментов. Полученные ими результаты весьма затруднительно изложить в краткой форме (читателю следует обратиться к указанным выше работам); однако можно отметить, что результаты указывают на преимущество метода Бройдена — Флетчера — Шэнно перед остальными методами.

Здесь, по-видимому, нецелесообразно уделять значительное внимание теоретическим вопросам проведения вычислительных экспериментов. С другой стороны, необходимо упомянуть о наличии определенных правил проверки алгоритмов [72], а также отметить, что числовые результаты, представленные в литературе примерно до 1977 г., следует использовать с известной осторожностью. Оценки эффективности тех или иных алгоритмов, полученные на основе анализа только количества вычислений значений функции, могут привести к неверным выводам, что подчеркивалось в работе Миля и Гонсалеса [73].

Авторы данной книги провели ряд вычислительных экспериментов для того, чтобы продемонстрировать относительные возможности реализации методов Коши, Флетчера — Ривса, Дэвидона — Флетчера — Пауэлла и Бройдена — Флетчера — Шэнно на ЭВМ CDC-6500 с обычной точностью. Возврат к начальной итерации по методу Флетчера — Ривса осуществлялся после каждой серии из N +1 шагов; критерии окончания поиска представлены в табл. 3.2.

Таблица 3.2. Критерии окончания поиска

1.k > M 3. ≤ ε

2. ≤ ε 4. f (x ) s(x ) ≥ 0

5.f (x ) > f (x )

В табл. 3.3 приведены результаты исследования функции Розен-брока (рис. 3.16):

f (x) = 100(x – x ) + (1 – x ) , (3.92)

которая обычно используется при анализе градиентных методов. Результаты получены с помощью различных методов поиска вдоль прямой; во всех случаях применялась процедура численной аппроксимации градиента. Заметим, что комбинация «метод Коши/метод деления интервала пополам» обеспечивает нахождение наиболее точного значения f, однако при этом требуются наибольшие затраты машинного времени. Самым эффективным по количеству вычислений значений функции оказывается метод Бройдена — Флетчера — Шэнно с использованием кубичной аппроксимации. Отметим, что метод Коггинса представляет собой один из вариантов метода квадратичной интерполяции [21].

Табл. 3.4 содержит результаты анализа задачи, связанной с минимизацией инерции зубчатой передачи [74]. Эта задача (рис. 3.17) была включена Изоном и Фентоном в число тестовых задач для сравнения различных алгоритмов. Ее целевая функция записывается в следующем виде:

f(x) = . (3.93)

f (x) = 100(x – x ) + (1 – x )

Рис. 3.16. Линии уровня функции Розенброка.

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

В табл. 3.5 приведены результаты исследования функции Вуда [75] (рис.3.18):

f (x) = 100(x – x ) + (1 – x ) + 90(x – x ) + (1– x ) + 10.1[(x – 1) + (x – 1) ]+

+19.8(x – 1)(x – 1). (3.94)

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

Таблица 3.3. Результаты исследования функции Розенброка (х⁽⁰⁾ = [–1.2, 1.0] )

Метод	Метод
Метод	деления интервала пополам	золотого сечения	Коггинса	кубической апроксимации
Коши	1.10E-10 / 7.47 / 38424^а)	1.25E-10 / 1.382 / 4066	8.30E-8 / 1.074 / 3570	6.19E-9 / 2.631 / 10685
Флетчера — Ривса	3.24E-6 / 0.18 / 988	5.91E-6 / 0.57 / 805	5.96E-5 / 0.109 / 370	2.77E-7 / 0.059 / 273
Дэвидона — Флетчера — Пауэлла	2.45E-8 / 0.173 / 977	2.39E-8 / 0.133 / 656	6.6E-8 / 0.115 / 331	4.3E-8 / 0.063 / 239
Бройдена — Флетчера — Шэнно	5.6E-8 / 0.169 / 932	3.6E-8 / 0.161 / 740	2.1E-8 / 0.115 /315	3.9E-9 / 0.065 / 204

^а) f (x*) / время / К.Ф., где К.Ф. количество вычислений значений функции при проведении поиска; время — количество секунд работы центрального процессора до окончания поиска.

Таблица 3.4. Результаты решения задач (№10) Изона и Фентона (х⁽⁰⁾ = [0,5, 0,5] )

Метод	Метод
Метод	деления интервала пополам	золотого сечения	Коггинса	кубической апроксимации
Коши	1.744 / 0,299 / 1026^а)	1.744 / 0,219 / 688	1.744 / 0,181 / 312	1.744 / 0.091 / 171
Флетчера — Ривса	1.744 / 0.066 / 249	1.744 / 0.053 / 199	1.744 / 12.21 / 28141	1.744 / 0.025 / 92
Дэвидона — Флетчера — Пауэлла	1.744 / 0.056 / 232	1.744 / 0.051 / 184	1.744 / 0.09 / 208	1.744 / 0.079 / 262
Бройдена — Флетчера — Шэнно	1.744 / 0.055 / 226	1.744 / 0.051 / 176	1.744 / 0.087 / 195	1.744 / 0.043 / 133

^а) f (x*) / время / К.Ф.

Таблица 3.5. Результаты исследования функции Вуда (х⁽⁰⁾ = [–3, –1, –3, –1] )

Метод	Метод
Метод	деления интервала пополам	золотого сечения	Коггинса	кубической апроксимации
Коши	3.74E-9 / 13.466 / 39503^а)	1.77E-8 / 10.70 / 29 / 692	2.95E-9 / 5.844 / 12.392	8.36E-6 / 7.89 / 20.007
Флетчера — Ривса	1.3E-10 / 0.401 / 1257	1.2E-8 / 0.311 / 942	2.9E-8 / 0.571 / 1468	2.0E-7 / 0.083 / 244
Дэвидона — Флетчера — Пауэлла	3.9E-9 / 0.810 / 2404	3.7E-9 / 0.684 / 1895	2.9E-9 / 0.403 / 747	9.5E-10 / 0.298 / 727
Бройдена — Флетчера — Шэнно	2.2E-9 / 0.759 / 2054	2,0E-9 / 0.652 / 1650	2.0E-8 / 0.444 / 723	2.3E-9 / 0.240 / 410

^а) f (x*) / время / К.Ф.

f(x) =

Рис. 3.17. Линии уровня функции Изона и Фентона.

Функция Вуда: (x = x = 1)

f (x) = 100(x – x ) + (1 – x ) + 90(x – x ) + (1– x ) + 10.1[(x – 1) + (x – 1) ]+ 19.8(x – 1)(x – 1).

Рис. 3.18. Линии уровня функции Вуда.

Заключение

В данной главе изложены методы исследования функций нескольких переменных в задачах оптимизации. Сформулированы необходимые и достаточные условия существования минимума функции нескольких переменных. Вместе с тем большая часть главы посвящена рассмотрению методов поиска оптимумов. Некоторые методы включены по причинам исторического характера, другие методы являются наиболее эффективными из разработанных к настоящему времени. Рассмотрены методы, в которых используются только значения f (x),значения f (x)и f (x)значения f (x), f (x) и ²f (x). Достаточно подробно освещены вопросы, связанные с важным понятием сопряженности направлений; изложены методы сопряженных градиентов и квазиньютоновские методы. Разумеется, проведенное обсуждение не является полным, и многие полезные методы не рассмотрены из-за ограниченного объема книги. Глава завершается кратким анализом алгоритмов и результатов вычислительных экспериментов.

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

3.1. Объясните, почему направления поиска, которые используются в алгоритме прямого поиска, например в алгоритме Хука — Дживса, должны быть линейно независимыми. Сколько направлений следует использовать в данном случае?

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

3.3. Почему квадратичные функции используются как основа для построения алгоритмов нелинейной оптимизации?

3.4. В чем состоит полезность свойства параллельного подпространства, которым обладают квадратичные функции?

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

3.6. Почему положительная определенность матрицы А⁽^k⁾ является необходимым условием при решении задач минимизации с помощью квазиньютоновских методов?

3.7. Поясните связь метода Марквардта с методами Коши и Ньютона. Какому из трех перечисленных методов следует отдать предпочтение?

3.8. Возможно ли получение одинаковых точек при использовании методов Дэвидона — Флетчера — Пауэлла и Флетчера — Ривса для решения задачи с квадратичной целевой функцией, если в обоих случаях начальная точка одна и та же? Если возможно, то при каких условиях? Если невозможно, то почему?

3.9. Поясните понятие квадратичной сходимости. Укажите один алгоритм, обладающий свойством квадратичной сходимости, и один алгоритм, который этим свойством не обладает.

3.10. Покажите, что функция

f (x) = 3x + 2x + x – 2x x – 2x x + 2x x – 6x – 4x – 2x

является выпуклой.

3.11. Найдите и классифицируйте стационарные точки функции

f (x) = 2x + 4x x – 10 x x + x

линии уровня которой изображены на рис. 3.19.

f (x) = 2x + 4x x – 10 x x + x

Риc. 3.19. Линии уровня функции из задачи 3.11.

3.12. Проведите анализ определенности следующих квадратичных форм:

Q (x) = x + 2x – 3x – 6x x + 8x x – 4x x ,

Q (x) = 2ax x + 2bx x + 2cx x ,

Q (x) = x +5x + 3x + 4x x – 2x x – 2x x .

3.13. Воспользуйтесь методом Гаусса — Жордана для преобразования следующей квадратичной формы к виду суммы полных квадратов:

Q (x) = x + 2x x + 4x x + 3x + 2x x + 5x .

Покажите, что эта квадратичная форма положительно определена.

3.14. Пусть в точке х= градиент f ( ) = 0. Что можно сказать о точке х,если

(а) f(x) — выпуклая функция?

(б) f(x) — вогнутая функция?

(в) ²f ( ) — неопределенная матрица?

(г) матрица ²f ( ) положительно определена?

(д) матрица ²f ( ) отрицательно определена?

3.15. Контрпример Пеано. Дана функция

f (х)= (x – a x )(x – a x ),

где a и a — постоянные коэффициенты.

(а) Охарактеризуйте точку х = [0, 0].

(б) Покажите, что максимальное значение f(x) на множестве точек кривой, заданной уравнением

x = ½ (a + a ) x ,

достигается в начале координат.

(в) Нарисуйте несколько линий уровня этой функции в окрестности начала координат.

3.16. В результате поиска минимума функции

f (х)= [x + (x + 1)²] [x + (x – 1)²]

найдены следующие точки:

(а) х⁽¹⁾ = [0, 0],

(б) х⁽²⁾ = [0, 1],

(в) х⁽³⁾ = [0, –1],

(г) х⁽⁴⁾ = [1, 1],

Классифицируйте полученные точки.

3.17. Пусть требуется переправить 400 ярд³ сыпучего материала через большую реку. Для перевозки груза необходимо построить контейнер. Известны следующие данные: стоимость каждого рейса на противоположный берег реки и обратно равна 4,2 долл.; стоимость материалов для изготовления дна контейнера составляет 20,00 долл./ярд²; боковых стенок контейнера — 5,00 долл./ярд², крышки контейнера — 20,00 долл./ярд².

Сконструируйте контейнер таким образом, чтобы минимизировать полные затраты на перевозку груза.

3.18. Рассматриваются функция Розенброка

f (х)= 100(x – x ) + (1– x )

и начальная точка

х⁽⁰⁾ = [–1.2, 0].

Найдите точку x*, которой соответствует минимальное значение f (x*), пользуясь:

(а) методом поиска по симплексу Нелдера и Мида (проведите четыре итерации), затем при начальной точке х⁽⁰⁾ проведите счет по программе SPX из библиотеки программ OPTLIB [22] или по другой подходящей программе по вашему выбору;

(б) методом Хука — Дживса (программа PS в OPTLIB);

(в) методом сопряженных направлений Пауэлла (программа PCD в OPTLIB).

3.19. На рис. 3.20 изображен бункер, для хранения зерна.

Требуется выбрать значения параметров h, d и φ таким образом, чтобы бункер имел заданный объем (v* = 10м³), а его стоимость была минимальной. Основание бункера изготавливается из деревянных плит стоимостью С₁ = l долл./м², а остальная часть бункера — из листового металла стоимостью С₂ = 1,5 долл./м². Воспользуйтесь ограничением на объем бункера для того, чтобы исключить одну переменную из целевой функции, и решите получаемую в результате задачу с двумя переменными с помощью метода поиска по образцу (θ = 30°). Указание. Полезно попытаться описать геометрическую форму бункера с помощью другого (эквивалентного) множества управляемых переменных.

Рис. 3.20. Бункер для хранения зерна.

3.20.На рис. 3.21 схематически изображена система подачи газа по трубам [76], в которой компрессорные станции расположены на расстоянии L миль друг от друга.

Рис. 3.21. Схема газопровода.

Суммарные затраты на эксплуатацию газопровода в течение года определяются

функцией

C (D, P_l, L, r) = 7,84D²P₁+ 450000 + 36900D + +

+ (r – 1) (долл./год), (1)

где D — внутренний диаметр труб, дюйм; P₁— давление на выходе компрессора, фунт/дюйм²; L — расстояние между компрессорными станциями, миля; r = P₁/P₂ — отношение .давлений на выходе и входе компрессора. Предположим, что расход газа в единицу времени можно описать функцией

Q = 3.39 (фут³/ч.), (2)

где f = 0,008D — коэффициент трения. Пусть расход газа составляет 100 10⁶ фут³/день. Воспользуйтесь формулой (2) для исключения переменной P₁из (1). Затем с помощью метода поиска по симплексу Нелдера и Мида и метода сопряженных направлений Пауэлла найдите такие значения параметров системы, которым соответствует минимум суммарных эксплуатационных затрат в единицу времени.

3.21. Найдите координаты точек минимума функции Химмельблау (рис. 3.1)

f (x) = ( + – 11) +( + – 7)

с точностью до трех десятичных знаков. Воспользуйтесь методом Хука — Дживса при поиске из следующих начальных точек:

х⁽¹⁾ = [5, 5]^T, х⁽²⁾ = [5, –5]^T, х⁽³⁾ = [0, 0]^T,

х⁽⁴⁾ = [–5, –5]^T, х⁽⁵⁾ = [–5, 0]^T

3.22. Заданы текущее приближение к решению х⁽^k⁾ и направление поиска s(x⁽^k⁾). Итерации проводятся по формуле (3.42). Покажите, что

α* = ,

если целевая функция квадратичная:

f (x) = q (x) = a + b²x + x Cx.

3.23. Определите размеры прямоугольного контейнера открытого типа (без крышки), стоимость которого минимальна. (Пусть v* = 10 м³.)

3.24. Заданы функция q (х) = 8x + 4x x + 5x , начальная точка x⁽⁰⁾ = [10, 10]^T и два линейно независимых направления

d⁽⁰⁾ = q (x⁽⁰⁾) = [200, 140]^T, d⁽¹⁾ = [7, – 10]^T.

Определите новое направление поиска (S⁽¹⁾ = d⁽¹⁾ + β ∆g⁽¹⁾), сопряженное с d⁽⁰⁾. Используйте эти направления при поиске точки х*: сначала проведите поиск в направлении S⁽⁰⁾ = d⁽⁰⁾, затем из полученной точки минимума проведите поиск в направлении S⁽¹⁾. Сравните S⁽¹⁾ с направлением, полученным по методу Флетчера — Ривса.

3.25. Найдите направление, ортогональное вектору

s = , x = [0, 0, 0]^T.

Найдите также направление s₂, сопряженное с s₁ в той же точке при условии, что целевая функция равна

f (x) = x + 2x – x x + 3x – 2x x + x .

3.26. Определите и классифицируйте стационарные точки функции

f (x) = x – x x + x – 2x + 3x – 4.

3.27. Изон показал, что задача выбора (с целью минимизации инерции передачи) передаточных отношений в понижающей зубчатой передаче, образованной тремя прямозубыми цилиндрическими колесами и имеющей суммарное передаточное число 10, эквивалентна задаче минимизации функции (3.93). Воспользуйтесь методами Хука — Дживса, Коши и Флетчера — Ривса для нахождения приближенных значений координат точки х* при х⁽⁰⁾ = [0.5, 0,5]^T.

3.28. Заданы функция

f (х)= 100(x – x ) + (1– x )

и две первые точки, полученные в процессе поиска точки минимума функции f:

х⁽⁰⁾ = [–1.2, 1], х⁽¹⁾ = [–1.3, 1.07].

Определите направление поиска из точки х⁽¹⁾ пользуясь следующими градиентными методами: (а) методом Коши, (б) модифицированным методом Ньютона, (в) методом Флетчера — Ривса, (г) методом Марквардта (λ⁽¹⁾ = 100).

3.29. Исследуйте влияние ε₂ — параметра сходимости для поиска вдоль прямой — на процедуры расчетов по методам Флетчера — Ривса, Дэвидона — Флетчера — Пауэлла и Бройдена — Флетчера — Шэнно. Используйте каждый из перечисленных методов для решения задачи минимизации функции Вуда (3.94) при х⁽⁰⁾ = [–3, –1, –3, –1]^T. Положите ε = αε , α = 0,01, 0,1, 1 и 10; при этом значение параметра сходимости алгоритма ε следует выбирать в зависимости от характеристик используемой ЭВМ. Примечание: для ЭВМ CDC–6500 можно выбрать ε = 10^–4.

3.30. Рассмотрите задачу 3.19, в которой речь шла об определении параметров геометрической формы бункера для хранения зерна. Исследуйте влияние отношения c /c на оптимальную форму бункера. В частности, найдите оптимальные решения при c /c = 0.5, 1.5 и 3 и проиллюстрируйте ответы рисунками. Какие общие выводы можно при этом сделать?

3.31. Проведите три итерации в соответствии с методом Коши, модифицированным методом Ньютона и методом Дэвидона — Флетчера — Пауэлла для минимизации функции Пауэлла

f (x) = (x + 10x ) + 5(x – x ) + (x – 2x ) + 10(x – x )

при х⁽⁰⁾ = [3, –1, 0, 1]^T.

3.32. В процессе проведения экспериментов инженер устанавливает наличие функциональной зависимости некоторой величины Q от переменной t. Он имеет определенные основания…

Дата добавления: 2018-06-01; просмотров: 400; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 6 7 8 9 10 11 12 13 1415

Мы поможем в написании ваших работ!