Численные методы решения задач многомерной безусловной минимизации. Часть 1. Методы первого и второго порядков

Московский государственный технический университет
имени Н.Э. Баумана
А.В. Аттетков, А.Н. Канатников, Е.С. Тверская
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ
ЗАДА
Ч МНОГОМЕРНОЙ
БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
Часть 1
Методы первого и второго порядков
Методические указания
по курсу «Методы оптимизации»
Под редакцией С.Б. Ткачева
Москва
Издательство МГТУ им. Н.Э. Баумана
2009

УДК 517.51
ББК 22.161
A92
Р е ц е н з е н т
Тимонин В.И.
A92
Аттетков А.В., Канатников А.Н., Тверская Е.С.
Численные методы решения задач многомерной безусловной минимизации. – Ч. 1: Методы первого и второго порядков: Методические указания по курсу «Методы оптимизации» /
Под ред. С.Б. Ткачева . – М.: Изд-во МГТУ им. Н.Э. Баумана,
2009. – 47 с.: ил.
Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной безусловной оптимизации. Много внимания уделено описанию алгоритмов численного решения задач безусловной минимизации дифференцируемых функций нескольких переменных. Приведены примеры решения конкретных задач, дана
наглядная интерпретация полученных результатов, способствующая
лучшему усвоению применяемых методов.
Для студентов старших курсов факультетов ФН, ИУ
.
УДК 517.51
ББК 22.161
c
⃝МГТУ им. Н.Э. Баумана, 2009

ВВЕДЕНИЕ
На практике часто возникает ситуация, когда из нескольких
возможных вариантов поведения необходимо выбрать один, наилучший. Такой выбор (принятие наилучшего решения) может быть
осуществлен по-разному. Один из подходов заключается в количественной оценке каждого возможного варианта поведения (решения) и выборе среди них того, у которого оценка наилучшая (максимальная или минимальная). Так мы приходим к задаче оптимизации, которую можно сформулировать следующим образом. Есть
некоторое множество возможных решений, называемых альтернативами. Каждой альтернативе можно дать некоторую количественную оценку на основе некоторого критерия оптимальности.
Решение задачи оптимизации состоит в определении той альтернативы, для которой критерий оптимальности дает наибольшую
(или наименьшую) количественную оценку.
Описанная задача — выбор наилучшей альтернативы на основе критерия оптимальности — возникает в самых разных ситуациях: при проектировании технических устройств и технологических
процессов, когда какие-либо параметры устройства или процесса
в определенной степени варьируются, причем за счет изменения
этих параметров можно повысить эксплуатационные характеристики устройства или экономичность технологического процесса,
при распределении материальных и финансовых ресурсов, встречающаяся во многих областях экономики и управления.
Разнообразны задачи оптимизации и по своему внутреннему
содержанию. Множество альтернатив может описываться одним
числовым параметром (в этом случае говорят об одномерной оптимизации) или некоторым набором параметров (многомерная оптимизация). Есть класс задач оптимизации, в которых каждая альтернатива характеризуется бесконечным числом параметров. Отделяя
3

этот класс задач, говорят о бесконечномерной оптимизации, противопоставляя ей конечномерную оптимизацию.
Если каждая альтернатива в задаче оптимизации характеризуется совокупностью из n числовых параметров, то естественно
альтернативы ассоциировать с элементами n-мерного арифметического пространства Rn. В этом случае множество всех альтернатив будет представлять собой некоторое подмножество Ω ⊂Rn,
а критерий оптимальности, который каждой альтернативе ставит
в соответствие некоторую числовую оценку, — функцию многих
переменных f(x1, x2, . . . , xn), определенную на множестве Ω.
Таким образом, с математической точки зрения задача конечномерной оптимизации заключается в определении наибольшего или наименьшего значения функции многих переменных
f(x1, x2, . . . , xn) на заданном множестве Ω и точки x∗∈Ω, в
которой это значение достигается. Сформулированную задачу называют задачей математического программирования, а f(x) =
= f(x1, x2, . . . , xn) — целевой функцией. Переменные x1, x2, . . . ,
xn называют параметрами оптимизации, каждую точку x =
= x1; x2; . . . ; xn ∈Ω — допустимым решением, а множество
Ω ⊂Rn — множеством допустимых решений или допустимым
множеством. Точку x∗∈Ω, в которой целевая функция принимает
наименьшее значение, называют оптимальным решением. Задачу
математического программирования будем записывать следующим
образом:
f(x) →min,
x ∈Ω.
Эта запись предполагает, что функция f0(x) определена всюду на
допустимом множестве Ω, т. е. область определения целевой функции включает в себя допустимое множество, хотя может и не совпадать с ним.
С математической точки зрения нет различий между поиском
наибольшего и наименьшего значений функции. Чтобы преобразовать одну задачу в другую, достаточно у целевой функции сменить знак. Учитывая это, в дальнейшем ограничимся рассмотрением только одной из двух задач, а именно задачи минимизации
функции, заключающейся в поиске наименьшего значения целевой
функции на допустимом множестве и точки, в которой это значение достигается.
4

Из курса математического анализа известно, что функция на
заданном множестве может не достигать наименьшего значения.
Причина в том, что она либо ограничена снизу, либо не ограничена, но тем не менее не достигает точной нижней грани множества
своих значений. В обоих случаях задача минимизации не имеет решения, что говорит о некорректной ее постановке и необходимости
вносить изменения в математическую модель изучаемого объекта
или явления. В некоторых случаях может решаться задача поиска
точной нижней грани mf функции f(x) на допустимом множестве
Ω и построения такой последовательности точек {xk} ⊂Ω, для
которой f(xk) →mf при k →∞. Такую задачу записывают в виде
f(x) →inf,
x ∈Ω.
Задачу поиска точной нижней грани можно рассматривать как
обобщение задачи минимизации. Методы решения такой задачи в
целом те же, что и методы решения задачи минимизации. Поэтому
мы на ней останавливаться не будем, считая, что исследуемая целевая функция на допустимом множестве достигает наименьшего
значения.
Если допустимое множество совпадает с Rn, то на изменение
параметров оптимизации (координат точки в Rn) не накладывается никаких ограничений. В этом случае задачу минимизации
называют задачей безусловной минимизации. Если же допустимое
множество не покрывает все арифметическое пространство Rn, то
задачу минимизации часто называют задачей условной минимизации.
В задачах безусловной оптимизации допустимое множество совпадает со всем линейным арифметическим пространством соответствующей размерности, а основным фактором, определяющим
сложность решаемой задачи, становится поведение целевой функции. Большие различия в поведении функций многих переменных
порождают и большое количество методов безусловной оптимизации. Общего метода поиска наименьшего значения функции многих переменных, который можно было бы использовать во всех
случаях, нет. Приступая к решению задачи безусловной оптимизации, нужно провести предварительный анализ целевой функции и
на основании этого анализа выбрать один из численных методов,
который в заданных условиях может обеспечить решение задачи.
5