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

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

Химмельблау (см. [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. Он имеет определенные основания…

 

 

⇐ Предыдущая1234567

Поделиться:

Популярное:

1. III. РЕЗУЛЬТАТЫ ПРОИЗВОДСТВЕННОЙ ПРАКТИКИ ПО ПРОФИЛЮ СПЕЦИАЛЬНОСТИ
2. THE GERUND AND THE PARTICIPLE. СРАВНЕНИЕ ГЕРУНДИЯ И ПРИЧАСТИЯ
3. В то время как использование одного Laetrile во многих случаях оказывается эффективным, все же лучшие результаты обычно достигаются вместе с побочной терапией.
4. Влияние кривизны Земли и рефракции на результаты нивелирования
5. Влияние управления оборотными средствами на конечные результаты хозяйственной деятельности предприятия
6. Другой путь приносит результаты
7. ДС.1. Администрирование вычислительных систем
8. Интенсивность (степень), устойчивость и распределение внимания: методы и результаты исследований.
9. К методам эмпирического уровня научного познания относят такие методы, как наблюдение, описание, измерение, сравнение и эксперимент.
10. Классификация вычислительных машин
11. Классификация вычислительных сетей
12. Лекция 5. Основные результаты развития теории защиты информации.