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

ВЫСШЕЕ ОБРАЗОВАНИЕ

серия основана в 1 996 г.




> 00 >
X о 00

. АТТЕТКОВ
. ЗАРУБИН
. КАНАТНИКОВ





МЕТОДЫ ОПТИМИЗАЦИИ

УЧЕБНОЕ ПОСОБИЕ





                     Рекомендовано Министерством образования РФ в качестве учебного пособия для студентов высших учебных заведений

znanium.com

Москва РИОР ИНФРА-М

УДК 519.863(075.8)
ББК 22.18я73
      А92




   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

Рецензенты:

      А.В. Манжиров — д-р физ.-мат. наук, профессор;
      В.Ф. Формалев — заслуженный деятель науки РФ, д-р физ.-мат. наук, профессор





       Аттетков А.В.
А92      Методы оптимизации : учебное пособие / А.В. Аттетков, В.С. Зарубин,
       А.Н. Канатников. — Москва : РИОР : ИНФРА-М, 2023. — 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 с.

Предисловие

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

        СПИСОК ПРИНЯТЫХ ОБОЗНАЧЕНИЙ





◄ и ►   — начало и окончание доказательства
#       — окончание примера, замечания
{a 1, a2, ..., an} — конечное множество, состоящее из элементов a 1, а2, • • •, an
{x: P(x)} — множество, состоящее из тех и только тех элементов x, которые обладают характеристическим свойством P(x)
к = 1, N — число к принимает последовательно все значения из

    множества натуральных чисел от 1 до N включительно            
N   --- множество натуральных чисел                               
Z   --- множество целых чисел                                     
R   --- множество действительных чисел                            
R+  --- множество всех положительных действительных чисел         
R * --- множество всех неотрицательных действительных чисел       
Rn  --- n-я декартова степень множества R действительных чи-      
    сел (также n-мерное евклидово арифметическое про-             
    странство)                                                    
R+  --- положительный ортант, т.е^ n-я декартова степень множе-   
    ства R । положительных действительных чисел                   
Rn  --- неотрицательный ортант, т.е^ n-я декартова степень мно-   
*   жества R* неотрицательных действительных чисел                
AB  и | AB\ --- отрезок, соединяющий точки A и B, и его длина     
x = (x 1 ... xn)т --- n-мерный арифметический вектор, т.е^ элемент
    n-мерного евклидова арифметического пространства Rn           
|x| --- длина (модуль, евклидова норма) вектора x                 

n
^2 ak  — сумма n слагаемых а 1, а2, • • •, aₙ
k =1

 n
 1 am — произведение n сомножителей a 1, a2, • • •, aₙ
m =1
D (f) и R (f) — область определения и область значений функции f⁽x⁾

Список принятых обозначений

sgn x   — функция знака числа действительного числа x, те. sgn x =
           = 1 при x > 0, sgn x = 0 при x = 0 и sgn x = — 1 при x < О exp(x) — экспоненциальная функция ex diam X — диаметр ограниченного множества X дХ — граница множества X
sup f (x) и inf f (x) — точная верхняя грань и точная нижняя грань xtx       xex         ч
           функции f (x) на множестве X
max f (x) и min f (x) — максимальное и минимальное значения x- X      xGX
           функции f (x) на множестве X
f (x + 0) = lim f (x) и f (x — 0) = lim f (x) — правосторонний x^a+0                           x^a+0
           и левосторонний пределы функции f (x) одного действительного переменного в точке a
grad f (x) — градиент скалярной функции f (x) многих переменных (a, b)  — скалярное произведение векторов а и b
Aт      — матрица, транспонированная к матрице A
Rg A — ранг матрицы A
det A — определитель матрицы A
c(A)    — число обусловленности матрицы A
|| A || — евклидова норма матрицы A
I — единичная матрица
f (x) ^ min, x G Q, — задача минимизации функции f (x) на множестве Q
f (x) ^ inf, x G Q, — задача нахождения точной нижней грани функции f (x) на множестве Q
а ^ b, b ^ а — каждая координата вектора a G Rⁿ не меньше соответствующей координаты вектора b G Rⁿ
wk — антиградиент целевой функции в текущей точке xk-¹ итерационной последовательности {xk}
uk и вк — направление спуска и шаг спуска на к-й итерации метода спуска
H (x)   — матрица Гессе скалярной функции многих переменных

        ВВЕДЕНИЕ





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

Введение

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