Методы оптимизации

 
А.В. АТТЕТКОВ
В.С. ЗАРУБИН
А.Н. КАНАТНИКОВ
МЕТОДЫ
ОПТИМИЗАЦИИ
УЧЕБНОЕ ПОСОБИЕ
Рекомендовано Министерством образования РФ
в качестве учебного пособия для студентов
высших учебных заведений
Москва
РИОР
ИНФРА-М

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11
УДК	 519.863(075.8)
ББК	 22.18я73
А92
Р е ц е н з е н т ы :
А.В. Манжиров — д-р физ.-мат. наук, профессор;
В.Ф. Формалев — заслуженный деятель науки РФ, д-р физ.-мат. наук, 
профессор 
Аттетков А.В.
Методы оптимизации : учебное пособие / А.В. Аттетков, В.С. Зарубин, 
А92
А.Н. Канатников. — Москва : РИОР : ИНФРА-М, 2021. — 270 с. — (Высшее образование: Бакалавриат). — DOI: https://doi.org/10.12737/11456
ISBN 978-5-369-01037-2 (РИОР)
ISBN 978-5-16-004876-5 (ИНФРА-М, print)
ISBN 978-5-16-103309-8 (ИНФРА-М, online)
Освещается одно из важнейших направлений математики — теория 
оптимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Описаны алгоритмы 
численного решения задач безусловной минимизации функций одного 
и  нескольких переменных, изложены методы условной оптимизации. 
Приведены примеры решения конкретных задач, дана наглядная интерпретация полученных результатов.
Предназначено для студентов, аспирантов и преподавателей технических, экономических и других вузов и факультетов.
УДК 519.863(075.8)
ББК 22.18я73
© 
Аттетков А.В., Зарубин В.С., 
Канатников А.Н.
ISBN 978-5-369-01037-2 (РИОР)
ISBN 978-5-16-004876-5 (ИНФРА-М, print)
ISBN 978-5-16-103309-8 (ИНФРА-М, online)

ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Список принятых обозначений . . . . . . . . . . . . . . . . . . .
7
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Г л а в а 1
Задачи оптимизации . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.1. Основные понятия . . . . . . . . . . . . . . . . . . . .
11
1.2. Примеры задач оптимизации . . . . . . . . . . . . . .
12
1.3. Классы задач оптимизации
. . . . . . . . . . . . . . .
19
Вопросы для самопроверки . . . . . . . . . . . . . . .
23
Г л а в а 2
Методы одномерной минимизации
. . . . . . . . . . . . . . . .
25
2.1. Предварительные замечания
. . . . . . . . . . . . . .
25
2.2. Методы прямого поиска . . . . . . . . . . . . . . . . .
27
2.3. Сравнение методов прямого поиска
. . . . . . . . . .
34
2.4. Методы полиномиальной аппроксимации . . . . . . .
37
Вопросы для самопроверки . . . . . . . . . . . . . . .
43
Г л а в а 3
Многомерная безусловная минимизация . . . . . . . . . . . . .
44
3.1. Методы спуска . . . . . . . . . . . . . . . . . . . . . .
47
3.2. Метод градиентного спуска . . . . . . . . . . . . . . .
50
3.3. Минимизация квадратичной функции . . . . . . . . .
59
3.4. Метод сопряженных направлений
. . . . . . . . . . .
68
3.5. Метод Ньютона и его модификации
. . . . . . . . . .
80
3.6. Квазиньютоновские методы . . . . . . . . . . . . . . .
89
3.7. Методы прямого поиска . . . . . . . . . . . . . . . . .
98
3.8. Методы случайного поиска . . . . . . . . . . . . . . .
119
Вопросы для самопроверки . . . . . . . . . . . . . . .
126

Оглавление
Г л а в а 4
Аналитические методы нелинейного программирования . . .
128
4.1. Минимизация целевой функции на заданном
множестве . . . . . . . . . . . . . . . . . . . . . . . . .
128
4.2. Минимизация при ограничениях типа равенства . . .
133
4.3. Общая задача нелинейного программирования . . . .
136
4.4. Седловая точка функции Лагранжа . . . . . . . . . . .
143
4.5. Двойственная функция . . . . . . . . . . . . . . . . . .
145
Вопросы для самопроверки . . . . . . . . . . . . . . .
149
Г л а в а 5
Численные методы нелинейного программирования . . . . . .
151
5.1. Метод условного градиента . . . . . . . . . . . . . . .
151
5.2. Использование приведенного градиента . . . . . . . .
158
5.3. Проектирование точки на множество . . . . . . . . . .
168
5.4. Метод проекции точки на множество . . . . . . . . . .
172
5.5. Метод проекции антиградиента . . . . . . . . . . . . .
178
5.6. Метод возможных направлений . . . . . . . . . . . . .
199
5.7. Методы последовательной безусловной
минимизации . . . . . . . . . . . . . . . . . . . . . . .
212
Вопросы для самопроверки . . . . . . . . . . . . . . .
221
Г л а в а 6
Методы линейного программирования . . . . . . . . . . . . . .
222
6.1. Виды задач линейного программирования . . . . . . .
223
6.2. Графический метод решения задач линейного
программирования . . . . . . . . . . . . . . . . . . . .
227
6.3. Основы теории линейного программирования . . . . .
230
6.4. Симплекс-метод
. . . . . . . . . . . . . . . . . . . . .
233
6.5. Построение начального допустимого базисного
решения . . . . . . . . . . . . . . . . . . . . . . . . . .
244
6.6. Двойственная задача линейного программирования . .
250
Вопросы для самопроверки . . . . . . . . . . . . . . .
258
Список рекомендуемой литературы . . . . . . . . . . . . . . . .
260
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . .
266

ПРЕДИСЛОВИЕ
Предлагаемое пособие посвящено конечномерным задачам оптимизации. В излагаемом материале основное внимание уделено прикладным и вычислительным аспектам, в первую очередь анализу
численных методов оптимизации и построению алгоритмов их реализации.
В книге опущены доказательства многих теоретических
положений, в частности теорем о сходимости методов.
По этим
вопросам есть обширная литература, и <математические тонкости>,
связанные с оценками сходимости методов, можно изучить самостоятельно. В практической деятельности более важно понимание сути
методов и алгоритмов их реализации, знание условий их применения. Большое количество примеров и разобранных задач, поясняемых
графическими иллюстрациями и интерпретацией полученных результатов, позволяет использовать данное издание не только как учебное
пособие, но и как методическое, предназначенное для проведения семинарских занятий и организации лабораторных работ.
В основу книги лег методический опыт авторов, которые в течение ряда лет в стенах МГТУ имени Н.Э. Баумана читают лекции
по методам оптимизации, ведут семинарские и лабораторные занятия. Этот опыт нашел свое отражение в учебнике авторов, изданном
ранее*. В предлагаемом издании методические наработки авторов получили дальнейшее развитие. Некоторые разделы переработаны. Так,
пересмотрена глава по одномерной оптимизации, три главы по методам многомерной оптимизации сокращены и собраны в одну. Глава
по оптимизации выпуклых функций не включена в пособие, поскольку
этот материал имеет в основном теоретическое значение. Авторы ограничились изложением минимальных сведений по выпуклым функциям
в первой главе.
В то же время в книгу включен новый материал:
методы случайного поиска в третьей главе, новая глава по методам
линейного программирования.
* Аттетков А.В. Методы оптимизации: учебник для вузов / А.В. Аттетков,
С.В. Галкин, В.С. Зарубин; под ред. В.С. Зарубина, А.П. Крищенко. { М.: Изд-во
МГТУ им. Н.Э. Баумана, 2001. { 440 с.

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

СПИСОК ПРИНЯТЫХ ОБОЗНАЧЕНИЙ
◀и ▶
| начало и окончание доказательства
#
| окончание примера, замечания
{a1, a2, ..., an} | конечное множество, состоящее из элементов a1,
a2, . . . , an
{x: P(x)} | множество, состоящее из тех и только тех элементов x,
которые обладают характеристическим свойством P(x)
k = 1, N | число k принимает последовательно все значения из
множества натуральных чисел от 1 до N включительно
N
| множество натуральных чисел
Z
| множество целых чисел
R
| множество действительных чисел
R+
| множество всех положительных действительных чисел
R∗
| множество всех неотрицательных действительных чисел
Rn
| n-я декартова степень множества R действительных чисел (также n-мерное евклидово арифметическое пространство)
Rn
+
| положительный ортант, т.е. n-я декартова степень множества R+ положительных действительных чисел
Rn
∗
| неотрицательный ортант, т.е. n-я декартова степень множества R∗неотрицательных действительных чисел
AB и |AB| | отрезок, соединяющий точки A и B, и его длина
x = (x1 ... xn)т | n-мерный арифметический вектор, т.е. элемент
n-мерного евклидова арифметического пространства Rn
|x|
| длина (модуль, евклидова норма) вектора x
k=1
ak
| сумма n слагаемых a1, a2, . . . , an
n
P
m=1
am
| произведение n сомножителей a1, a2, . . . , an
n
Q
D(f) и R(f) | область определения и область значений функции
f(x)

Список принятых обозначений
sgnx
| функция знака числа действительного числа x, т.е. sgnx =
= 1 при x > 0, sgnx = 0 при x = 0 и sgnx = −1 при x < 0
exp(x)
| экспоненциальная функция ex
diamX
| диаметр ограниченного множества X
∂X
| граница множества X
sup
x∈X
f(x) и inf
x∈X f(x) | точная верхняя грань и точная нижняя грань
функции f(x) на множестве X
max
x∈X f(x) и min
x∈X f(x) | максимальное и минимальное значения
функции f(x) на множестве X
f(x + 0) =
lim
x→a+0f(x) и f(x −0) =
lim
x→a+0f(x) | правосторонний
и левосторонний пределы функции f(x) одного действительного переменного в точке a
gradf(x) | градиент скалярной функции f(x) многих переменных
(a, b)
| скалярное произведение векторов a и b
Aт
| матрица, транспонированная к матрице A
RgA
| ранг матрицы A
detA
| определитель матрицы A
c(A)
| число обусловленности матрицы A
∥A∥
| евклидова норма матрицы A
I
| единичная матрица
f(x) →min, x ∈Ω, | задача минимизации функции f(x) на множестве Ω
f(x) →inf, x ∈Ω, | задача нахождения точной нижней грани функции f(x) на множестве Ω
a ⩾b, b ⩽a | каждая координата вектора a ∈Rn не меньше соответствующей координаты вектора b ∈Rn
wk
| антиградиент целевой функции в текущей точке xk−1
итерационной последовательности {xk}
uk и βk | направление спуска и шаг спуска на k-й итерации метода
спуска
H(x)
| матрица Гессе скалярной функции многих переменных

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

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