Численные методы решения задач нелинейного программирования

Московский государственный технический университет
имени Н. Э. Баумана
А. В. Аттетков, А. Н. Канатников,
Е. В. Пилявская
Численные методы решения задач
нелинейного программирования
Учебное пособие

УДК 517.51(075.8)
ББК 22.18я.73
А92
Издание доступно в электронном виде на портале ebooks.bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/93/book1346.html
Факультет «Фундаментальные науки»
Кафедры «Прикладная математика» и «Математическое моделирование»
Рекомендовано Редакционно-издательским советом
МГТУ им. Н.Э. Баумана
в качестве учебного пособия
Рецензент
д-р физ.-мат. наук, профессор В.И. Тимонин
Аттетков, А. В.
А92
Численные методы решения задач нелинейного программирования: учебное пособие / А. В. Аттетков, А. Н. Канатников,
Е. В. Пилявская. — Москва : Издательство МГТУ им. Н.Э. Баумана, 2016. — 87, [3] c.: ил.
ISBN 978-5-7038-4300-0
Рассмотрены теоретические, вычислительные и прикладные аспекты методов решения задач нелинейного программирования. Приведены примеры решения конкретных задач, дана наглядная интерпретация
полученных результатов, способствующая лучшему усвоению применяемых методов.
Для студентов МГТУ им. Н.Э. Баумана, изучающих методы конечномерной оптимизации.
УДК 517.51(075.8)
ББК 22.18я.73
ISBN 978-5-7038-4300-0
c
⃝МГТУ им. Н. Э. Баумана, 2016
c
⃝Оформление. Издательство
МГТУ им. Н. Э. Баумана, 2016

ПРЕДИСЛОВИЕ
В основу учебного пособия положен курс лекций по методам
оптимизации, который авторы читают на протяжении ряда лет
студентам различных специальностей МГТУ им. Н.Э. Баумана, а
также опыт проведения семинарских и лабораторных занятий по
этому курсу.
Учебное пособие целиком посвящено методам решения общей
задачи нелинейного программирования. В излагаемом материале
основное внимание уделено прикладным и вычислительным аспектам, в первую очередь анализу численных методов нелинейного
программирования и построению алгоритмов их реализации. В пособии опущены доказательства многих теоретических положений,
в частности теорем о сходимости методов. По этим вопросам есть
обширная литература, и «математические тонкости», связанные
с оценками сходимости методов, можно изучить самостоятельно.
В практической деятельности более важно понимание сути методов и алгоритмов их реализации, знание условий их применения.
Большое количество примеров и разобранных задач, поясняемых
графическими иллюстрациями и интерпретацией полученных результатов, позволяет использовать данное издание не только как
учебное пособие, но и как методическое, предназначенное для проведения семинарских занятий и организации лабораторных работ.
Содержание пособия относится к специальным разделам высшей математики, для работы с ним требуется хорошее знание
базового курса. В частности, предполагается, что читатель умеет
оперировать основными понятиями линейной алгебры, аналитической геометрии, теории матриц и математического анализа.

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

ческого пространства 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∗∈Ω, в которой целевая функция
принимает наименьшее значение, — оптимальным решением.
С математической точки зрения нет различий между поиском
наибольшего и наименьшего значения функции. Чтобы преобразовать одну задачу в другую, достаточно у целевой функции изменить
знак.
Учитывая это, в дальнейшем ограничимся рассмотрением
только одной из двух задач — задачи минимизации функции, заключающейся в поиске наименьшего значения целевой функции на
допустимом множестве и точки, в которой это значение достигается.
Если допустимое множество совпадает с Rn, то на изменение
параметров оптимизации (координат точки в Rn) не накладывается
никаких ограничений. В этом случае задачу минимизации называют задачей безусловной минимизации.
Если же допустимое
множество не покрывает все арифметическое пространство Rn, то
имеет место задача условной минимизации.
Допустимое множество может описываться разными способами. В наиболее типичной ситуации допустимое множество описывается системой уравнений и неравенств, связывающих возможные
значения параметров оптимизации. При этом уравнения называют
ограничениями типа равенства, а неравенства — ограничениями
типа неравенства.
5

Если в задаче минимизации либо целевая функция нелинейна,
либо есть нелинейное ограничение (т. е. функция в левой части
этого ограничения нелинейная), то эту задачу называют задачей
нелинейного программирования.
Задача нелинейного программирования может быть сложной вследствие того, что допустимое
множество, описываемое системой ограничений типа равенства и
неравенства, может иметь очень сложную структуру. На это указывает и отсутствие универсального метода решения, пригодного для
любой задачи нелинейного программирования.
Общую задачу нелинейного программирования можно записать
следующим образом:
f0(x) →min,
x ∈Ω⊂Rn,
(В1)
где f0(x) — целевая функция, определенная на допустимом множестве
Ω=

x ∈X: fl(x) = 0, l = 1, k, gi(x) ⩽0, i = 1, m
	
.
(В2)
При этом предполагается, что хотя бы одна из фигурирующих в
задаче функций не является линейной. Считаем, что все функции
fl(x), l = 0, k, и gi(x) ⩽0, i = 1, m, определены на некотором
открытом множестве X ⊂Rn. Упрощая изложение, далее ограничимся случаем X = Rn. В конкретной ситуации можно добиться
выполнения этого ограничения, доопределив все функции вне множества X, например, большим постоянным значением, которое не
повлияет на процесс минимизации целевой функции.
Среди задач нелинейного программирования выделяется достаточно широкий класс задач выпуклого программирования. В таких
задачах допустимое множество Ωявляется выпуклым множеством,
а целевая функция f(x) — выпуклой функцией. Дадим определение того и другого.
Множество X ⊂Rn называется выпуклым, если для любых
точек x и y из X и любого действительного числа α ∈(0, 1)
выполняется условие αx + (1 −α)y ∈X. Выпуклые множества
обладают важным свойством: пересечение любого семейства таких
множеств есть выпуклое множество.
6

Функция f(x), определенная на выпуклом множестве X называется выпуклой (в математическом анализе в этом случае говорят
о функции, выпуклой вниз), если для любых точек x и y из множества X и действительного числаα ∈(0, 1) выполняется неравенство
f

αx + (1 −α)y


⩽αf(x) + (1 −α)f(y).
Если это неравенство для любых x, y ∈X строгое, то и функцию
f(x) называют строго выпуклой функцией.
Для выпуклой функции любая точка локального минимума есть
точка наименьшего значения. Для выпуклой и дифференцируемой
функции любая стационарная точка (точка с нулевым значением
градиента) есть точка наименьшего значения.
Строго выпуклая
функция может иметь только одну точку наименьшего значения.
Сильно выпуклая функция, т. е. функция, которая для любых точек
x, y ∈X удовлетворяет условию
f

αx + (1 −α)y


⩽αf(x) + (1 −α)f(y) −α(1 −α)γ|x −y|2
с некоторой постоянной γ > 0, всегда достигает наименьшего
значения.
В математическом программировании важную роль играет теорема Куна — Таккера, которая является обобщением принципа
Лагранжа и учитывает как ограничения типа равенства, так и ограничения типа неравенства.
Теорема В1. Если точка x∗∈Ωявляется точкой локального
минимума функции f0(x) на множестве Ωвида (В2), причем
функции fl(x) = 0, l = 0, k, и gi(x) ⩽0, i = 1, m, непрерывно
дифференцируемы в окрестности точки x∗, то существуют такие
числа λ0 ⩾0, λl, l = 1, k, и µi ⩾0, i = 1, m, одновременно не
равные нулю, что для функции
i=1
µigi(x)
l=1
λlfl(x) +
k
X
m
X
e
L(x) = λ0f0(x) +
выполняются необходимое условие экстремума
7
grad e
L(x∗) = 0

и, кроме того, условия дополняющей нежесткости
µigi(x∗) = 0,
i = 1, m.
#
Функцию e
L(x) принято называть функцией Лагранжа. Хотя
эта функция определена для любых значений параметров λl, l =
= 0, k, и µi, i = 1, m, мы, учитывая утверждение теоремы Куна —
Таккера, будем рассматривать ее лишь при µi ⩾0, i = 1, m.
Отметим особую роль в этой теореме условий дополняющей
нежесткости. В рассматриваемой точке x∗локального минимума
функции f0(x) на множестве Ωкаждое из ограничений gi(x) ⩽0,
i = 1, m, выполняется либо в виде равенства gi(x∗) = 0, либо в
виде строгого неравенства gi(x∗) < 0. Ограничения первого вида
называют активными, в то время как остальные — неактивными (пассивными). Для активных ограничений соответствующее
условие дополняющей нежесткости выполнено. Неактивные ограничения в силу непрерывности фигурирующих в задаче функций
выполняются в виде строгого неравенства не только в точке x∗, но
и в некоторой окрестности этой точки. Поэтому после удаления
этих ограничений из задачи точка x∗останется точкой локального минимума.
Полагая для таких ограничений µi = 0, мы, с
одной стороны, обеспечиваем выполнение условия дополняющей
нежесткости, а с другой — удаляем соответствующее слагаемое из
функции Лагранжа.
Общей чертой многих численных методов решения задач оптимизации является рассмотрение такой последовательности {xk}
точек в Rn, что значения fk = f(xk), k ∈N, целевой функции в точках последовательности удовлетворяют неравенствам
fk ⩽fk−1, k ∈N. Подобную последовательность можно строить по-разному, но, как правило, путем выполнения некоторого
ряда операций, в котором используют ранее вычисленные точки
xi, i < k. Первую точку последовательности (начальную), а иногда и несколько первых точек (в зависимости от алгоритма) можно
выбирать произвольно.
Упомянутая последовательность операций составляет одну
итерацию в численном методе, а сам численный метод называют
8

итерационным. Последовательность {xk} часто называют итерационной, отражая в названии характер ее построения. Однако в
задачах оптимизации более существенным является убывание значений функции в точках последовательности {xk}, т. е. выполнение
условия fk ⩽fk−1, k ∈N. В этом случае последовательность {xk}
называют релаксационной. Численные методы оптимизации, основанные на построении такой последовательности, относят к классу
методов спуска.
Процесс построения релаксационной последовательности {xk}
в методах спуска обычно описывают рекуррентным соотношением
xk = xk−1 + βkuk, k ∈N,
(В3)
где uk ∈Rn — единичный вектор, определяющий направление
спуска на k-й итерации; βk ⩾0 — шаг спуска, т. е. расстояние от
точки xk−1 до новой точки xk.
Построение последовательности {xk} начинается с выбора
начальной точки x0, входящей в правую часть равенства (В3) при
k = 1.
Методы спуска различаются способами выбора направления и
шага спуска. Выбор на каждой итерации единичного вектора спуска uk, сонаправленного антиградиенту wk = −grad f(xk−1), т. е.
uk = wk
|wk|, характерен для метода градиентного спуска. Основное
рекуррентное соотношение для этого метода можно записать в виде
xk = xk−1 + βk
wk
|wk|, k ∈N.
(В4)
Построение релаксационной последовательности в методах
спуска обычно прекращают, если на очередной k-й итерации
выполнено одно или оба неравенства
|xk −xk−1| < ε1,
|f(xk) −f(xk−1)| < ε2,
(В5)
где ε1 и ε2 — заданные достаточно малые положительные числа,
называемые параметрами точности поиска.
9