Нелинейное программирование в примерах и задачах

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное автономное образовательное  
учреждение высшего образования  
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
 
Институт математики, механики и компьютерных наук 
им. И. И. Воровича 
 
 
 
И. А. Землякова 
 
НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ  
В ПРИМЕРАХ И ЗАДАЧАХ 
Учебное пособие 
 
 
 
 
Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 
2024 

 
УДК 519.853(075.8) 
ББК 22.185.42я73 
 
З-53 
 
Печатается по решению кафедры методов оптимизации и машинного  
обучения Института математики, механики и компьютерных наук  
Южного федерального университета (протокол № 6 от 11 июня 2024 г.) 
 
 
Рецензенты: 
д-р техн. наук, профессор кафедры методов оптимизации 
и машинного обучения Института математики, механики и компьютерных 
наук  Южного федерального университета Г. И. Белявский; 
д-р физ.-мат. наук, доцент, заведующий кафедрой информатики 
и информационных таможенных технологий 
Ростовского филиала Российской таможенной академии О. Е. Кудрявцев  
 
Землякова, И. А. 
З-53  
Нелинейное программирование в примерах и задачах : учебное пособие / И. А. Землякова ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2024. – 126 с.   
ISBN 978-5-9275-4738-8 
Учебное пособие содержит систематическое изложение раздела «Нелинейное 
программирование», снабжённое теоретическим материалом, множеством примеров и заданий для самостоятельного закрепления материала. Целью данного 
пособия является подробное изучение такого раздела математического программирования, как нелинейное программирование. 
Предназначено для студентов бакалавриата, обучающихся по направлению 
01.03.02 Прикладная математика и информатика, студентов других специальностей, изучающих курс «Методы оптимизации и исследование операций».  
УДК 519.853(075.8) 
ББК 22.185.42я73 
ISBN 978-5-9275-4738-8 
© Южный федеральный университет, 2024 
© Землякова И. А., 2024 
© Оформление. Макет. Издательство  
Южного федерального университета, 2024

Оглавление 
1. Постановка задачи нелинейного программирования ............................... 4 
2. Задача безусловной минимизации ....................................................................... 5 
3. Задача условной оптимизации. Графический метод решения ............... 12 
4. Выпуклые функции. Проверка функции на выпуклость ...................... 22 
5. Задача выпуклого программирования ............................................................ 27 
6. Задача нелинейного программирования с ограничениямиравенствами. Метод множителей Лагранжа ................................................ 14 
7. Задача нелинейного программирования  с ограничениямиравенствами и неравенствами.  Метод множителей Лагранжа ........ 48 
8. Численные методы оптимизации функции одной   
и нескольких переменных ...................................................................................... 62 
8.1. Безусловная нелинейная оптимизация  функции  
одной переменной ...................................................................................... 62 
8.1.1. Метод перебора .................................................................................. 62 
8.1.2. Метод дихотомии (деления отрезка пополам) ................ 64 
8.1.3. Метод золотого сечения ................................................................ 66 
8.2. Градиентные методы решения  
оптимизационных задач ......................................................................... 70 
8.2.1. Метод градиентного спуска ........................................................ 70 
8.2.2. Метод Ньютона ................................................................................... 76 
8.2.3. Метод субградиентного спуска ................................................. 79 
8.2.4. Метод проксимального градиента .......................................... 80 
8.2.5. Метод стохастического градиентного  
спуска (SGD) ................................................................................................ 81 
8.3. Численные методы решения оптимизационных задач,  
позволяющие не использовать градиент ...................................... 83 
8.3.1. Метод покоординатного спуска ................................................ 84 
8.3.2. Метод штрафных и барьерных функций ............................. 91 
8.4. Эвристические алгоритмы решения  
оптимизационных задач ......................................................................... 93 
8.4.1. Генетические алгоритмы ............................................................. 94 
8.4.2. Метод муравьиных колоний ....................................................... 99 
8.4.3. Алгоритм имитации отжига .................................................... 105 
Список литературы ........................................................................................................ 114 
Приложение ....................................................................................................................... 117 
  
 

1. Постановка задачи нелинейного программирования 
Нелинейное программирование (НЛП) представляет собой раздел математического программирования. Задача математического программирования заключается в отыскании экстремальных значений функции 
(целевая функция, или функция цели) среди множества её допустимых 
значений, которое задаётся рядом ограничений. 
Например: 
𝑓(𝑥, 𝑦) →max, 
𝑔(𝑥, 𝑦) ≤𝐶, 
𝑥, 𝑦≥0. 
В задаче нелинейного программирования (ЗНЛП) нелинейными 
являются целевая функция и (или) ограничения.  
Задачи нелинейного программирования можно разделить на два 
больших класса: задачи безусловной оптимизации и задачи условной 
оптимизации. В задачах безусловной оптимизации происходит поиск 
минимума или максимума нелинейной целевой функции при отсутствии 
дополнительных ограничений. Задача условной оптимизации предполагает наличие дополнительных ограничений на переменные. 
Решение задачи нелинейного программирования, в отличие от задачи 
линейного программирования, является более сложным процессом. Это 
связано с тем, что область допустимых решений задачи имеет сложную 
структуру и не обязана быть выпуклым множеством с конечным циклом 
угловых точек, как в задаче линейного программирования; оптимальное 
значение целевой функции может достигаться не только в угловой точке 
области допустимых решений, но и внутри данной области; возможно 
наличие нескольких локальных решений. 
Определение 1. Вектор 𝑥= (𝑥1, 𝑥2, … , 𝑥𝑛), удовлетворяющий ограничениям задачи, называется допустимым решением. 
Определение 2. Множество допустимых решений задачи называется 
областью допустимых решений (ОДР). 
Определение 3. Допустимое решение, доставляющее оптимальное 
значение целевой функции, называется оптимальным решением и обозначается 𝑥∗.  
Решить задачу нелинейного программирования – это означает 
найти оптимальное решение 𝑥∗ и оптимальное значение целевой функции, т. е. 𝑓(𝑥∗). 

2. Задача безусловной минимизации 
Если в задаче нелинейного программирования ограничения отсутствуют, то данная задача является задачей безусловной минимизации и 
может быть сформулирована в виде [8]: 
𝑓(𝑥) →min, 𝑥∈𝑆, 𝑆⊂ℝ𝑛, 
где 𝑓(𝑥) − функция многих переменных. 
Определение 4 [16]. Точка 𝑥∗∈𝑆 называется точкой глобального 
минимума функции 𝑓(𝑥) на множестве 𝑆, если 𝑓(𝑥∗) ≤𝑓(𝑥) при всех 
𝑥∈𝑆. 
Определение 5 [16]. Точка 𝑥∗∈𝑆 называется точкой строгого глобального минимума функции 𝑓(𝑥) на множестве 𝑆, если 𝑓(𝑥∗) < 𝑓(𝑥) 
при всех 𝑥∈𝑆, 𝑥≠𝑥∗. 
Определение 6 [16]. Точка 𝑥∗∈𝑆 называется точкой локального 
минимума функции 𝑓(𝑥) на множестве 𝑆, если 𝑓(𝑥∗) ≤𝑓(𝑥) при всех 
𝑥∈𝑆∩𝑉𝜀(𝑥∗), где 𝑉𝜀(𝑥∗) = {𝑥∈𝑅𝑛: ‖𝑥−𝑥∗‖ ≤𝜀} − шар радиуса 𝜀> 0 с 
центром в точке 𝑥∗ (𝜀− окрестность точки 𝑥∗). 
Определение 7 [16]. Точка 𝑥∗∈𝑆 называется точкой строгого локального минимума функции 𝑓(𝑥) на множестве 𝑆, если 𝑓(𝑥∗) < 𝑓(𝑥) 
при всех 𝑥∈𝑆∩𝑉𝜀(𝑥∗), где 𝑉𝜀(𝑥∗) = {𝑥∈𝑅𝑛: ‖𝑥−𝑥∗‖ ≤𝜀} − шар радиуса 
𝜀> 0 с центром в точке 𝑥∗ (𝜀− окрестность точки 𝑥∗). 
Определение 8 [17]. Градиентом функции 𝑓(𝑥) называется вектор 
𝑓′(𝑥), своим направлением указывающий направление наибольшего возрастания функции. 
Определение 9 [17]. Матрицей Гессе (гессианом) 𝐻(𝑥) дважды 
непрерывно дифференцируемой в точке 𝑥 функции 𝑓(𝑥) называется симметричная квадратная матрица, описывающая поведение функции во 
втором порядке: 
𝐻(𝑥) = { 𝜕2𝑓
𝜕𝑥𝑖𝜕𝑥𝑗
(𝑥)} , 𝑖, 𝑗= 1, … , 𝑛; 
𝐻=
(
 
 
 
 
 
𝜕2𝑓
𝜕𝑥1
2
𝜕2𝑓
𝜕𝑥1𝜕𝑥2
…   
𝜕2𝑓
𝜕𝑥1𝜕𝑥𝑛
𝜕2𝑓
𝜕𝑥2𝜕𝑥1
  𝜕2𝑓
𝜕𝑥2
2 
…   
𝜕2𝑓
𝜕𝑥2𝜕𝑥𝑛
…
…
…
𝜕2𝑓
𝜕𝑥𝑛𝜕𝑥1
    
𝜕2𝑓
𝜕𝑥𝑛𝜕𝑥2
    …   𝜕2𝑓
𝜕𝑥𝑛2 )
 
 
 
 
 
. 

Далее сформулируем некоторые теоремы, необходимые для решения 
задач безусловной оптимизации.  
Теорема 1 (необходимое условие локального минимума) [16]. 
Пусть 𝑓(𝑥) − дифференцируемая в точке 𝑥∗∈ℝ𝑛 функция, если 𝑥∗― 
точка локального минимума, то 𝑓′(𝑥∗) = 0. 
Теорема 2 (достаточное условие локального минимума) [16]. 
Пусть 𝑓(𝑥) − дважды дифференцируемая в точке 𝑥∗∈ℝ𝑛 функция, если 
𝑓′(𝑥∗) = 0 и матрица Гессе 𝐻(𝑥) положительно определена, то 𝑥∗− точка 
локального минимума. 
Напомним критерий положительной определённости матрицы. 
Теорема 3 (критерий Сильвестра) [20]. Для того чтобы матрица 
была положительно определённой, необходимо и достаточно, чтобы все 
угловые миноры матрицы были положительны. 
Определение 10 [43]. Угловым минором 𝑘-го порядка является 
определитель, составленный из элементов матрицы квадратичной 
формы, находящихся на пересечении первых 𝑘 строк и 𝑘 столбцов данной матрицы. 
Таким образом, сформулируем алгоритм нахождения безусловного 
минимума. 
Алгоритм нахождения безусловного минимума 
1. Применить необходимое условие локального минимума: составить вектор 𝑓′(𝑥) первых производных функции 𝑓(𝑥) и решить систему 
𝑓′(𝑥) = 0. В результате получим вектор стационарных точек 𝑥∗. 
2. Применить достаточное условие локального минимума: проверить, является ли матрица 𝐻(𝑥𝑖
∗), 𝑖= 1, … , 𝑘 положительно определённой, используя критерий Сильвестра. В случае положительного ответа 
сделать вывод о том, что 𝑥𝑖
∗− точка локального минимума. 
3. Если 𝑥𝑖
∗ не является точкой локального минимума, проверить, является ли эта точка точкой локального максимума. Для этого следует 
определить, является ли матрица −𝐻(𝑥𝑖
∗), 𝑖= 1, … , 𝑘 положительно 
определённой, используя критерий Сильвестра. В случае положительного ответа сделать вывод о том, что 𝑥𝑖
∗− точка локального максимума. 
Рассмотрим примеры. 
 
Пример 1. Найти локальный минимум функции  
𝑓(𝑥) = 𝑥1
3 −2𝑥1𝑥2 + 𝑥2
2 −3𝑥1 −2𝑥2. 

Воспользуемся алгоритмом, описанным выше. Найдём частные производные первого порядка функции 𝑓(𝑥) по всем переменным: 
𝜕𝑓(𝑥)
𝜕𝑥1 = 3𝑥1
2 −2𝑥2 −3; 
𝜕𝑓(𝑥)
𝜕𝑥2 = −2𝑥1 + 2𝑥2 −2. 
Составим систему, приравняв найденные производные к нулю: 
{ 3𝑥1
2 −2𝑥2 −3 = 0,
−2𝑥1 + 2𝑥2 −2 = 0. 
Для решения данной системы прибавим к первому уравнению второе 
и решим полученное квадратное уравнение:  
3𝑥1
2 −2𝑥1 −5 = 0, 
𝑥1,1 = −1, 
𝑥1,2 =
5
3. 
Продолжим решение системы и для 𝑥1,1 = −1 получим 𝑥2,1 = 0. Для  
𝑥1,2 =
5
3 получим 𝑥2,2 =
8
3. 
Таким образом, получили две стационарные точки: 𝐴(−1; 0); 𝐵(
5
3 ;
8
3). 
Далее находим частные производные функции 𝑓(𝑥) второго порядка 
и составляем матрицу Гессе: 
𝜕2𝑓(𝑥)
𝜕𝑥1
2
= 6𝑥1; 𝜕2𝑓(𝑥)
𝜕𝑥1𝑥2
= −2; 𝜕2𝑓(𝑥)
𝜕𝑥2
2
= 2; 𝜕2𝑓(𝑥)
𝜕𝑥2𝑥1
= −2; 
𝐻(𝑥) = (6𝑥1
−2
−2
2 ). 
Рассмотрим стационарную точку A(–1; 0) и составим 𝐻(𝐴) = 
= (−6
−2
−2
2 ). Вычислим угловые миноры матрицы 𝐻(𝐴): Δ1 = |𝑎11| = 
= −6 < 0; Δ2 = |𝐻(𝐴)| = −16 < 0. Положительной определённости матрицы нет, значит, точка 𝐴 не является точкой локального минимума.  
Проверим эту точку на локальный максимум. Составим −𝐻(𝐴) =
=  (6
2
2
−2).  Вычислим угловые миноры матрицы 𝐻(𝐴): Δ1 = |𝑎11| =
=  6 > 0; Δ2 = |𝐻(𝐴)| = −16 < 0. Положительной определённости матрицы нет, значит, точка 𝐴 не является точкой локального максимума. 
Следовательно, точка 𝐴− седловая точка.  

Рассмотрим стационарную точку 𝐵(
5
3 ;
8
3) и составим 𝐻(𝐵) = 
= (10
−2
−2
2 ). Вычислим угловые миноры матрицы 𝐻(𝐵): Δ1 = |𝑎11| = 
= 10 > 0; Δ2 = |𝐻(𝐴)| = 16 > 0. Матрица положительно определённая, значит, точка 𝐵−  точка локального минимума.  
Ответ: 𝐵(
5
3 ;
8
3) −точка локального минимума. 
Проиллюстрируем полученный результат. Построим двумерные 
линии уровня функции 𝑓(𝑥) и отметим точки 𝐴 и 𝐵. Построение будем 
выполнять в системе компьютерной алгебры Maple [11; 39]. Для этого 
сначала зададим функцию: 
> f := (x1, x2) -> x1^3 - 2*x1*x2 + x2^2 - 3*x1 - 2*x2 
Подключим пакет расширения plots и построим контурный график с 
помощью команды contourplot: 
> with(plots): 
> contourplot(f(x, y), x1 = -2.5 .. 2.5, x2 = -2.5 .. 5.0, axes = frame, filled = 
= true, contours = 25, coloring = [yellow, green]);   
Здесь опция contours задаёт количество линий уровня на поверхности. 
Первое значение цвета (yellow) соответствует наименьшему значению 
функции, второе (green) – наибольшему (рис. 1). 
 
Рис. 1. Двумерные линии уровня функции 𝑓(𝑥) 
Построенные линии уровня подтверждают результат, полученный 
аналитически. 

Пример 2. Найти локальный минимум функции  
𝑓(𝑥) = 𝑥1
4 + 𝑥2
4 −(𝑥1 + 𝑥2)2. 
Найдём частные производные первого порядка функции 𝑓(𝑥) по всем 
переменным: 
𝜕𝑓(𝑥)
𝜕𝑥1 = 4𝑥1
3 −2(𝑥1 + 𝑥2); 
𝜕𝑓(𝑥)
𝜕𝑥2 = 4𝑥2
3 −2(𝑥1 + 𝑥2). 
Составим систему, приравняв найденные производные к нулю: 
{4𝑥1
3 −2(𝑥1 + 𝑥2) = 0,
4𝑥2
3 −2(𝑥1 + 𝑥2) = 0; 
{2𝑥1
3 −(𝑥1 + 𝑥2) = 0,
2𝑥2
3 −(𝑥1 + 𝑥2) = 0. 
Решим 
данную 
систему 
и 
получим 
стационарные 
точки 
𝐴(0; 0); 𝐵(1; 1); 𝐶(−1; −1). 
Далее найдём частные производные функции 𝑓(𝑥) второго порядка и 
составим матрицу Гессе: 
𝜕2𝑓(𝑥)
𝜕𝑥1
2
= 12𝑥1
2 −2; 𝜕2𝑓(𝑥)
𝜕𝑥1𝑥2
= −2; 𝜕2𝑓(𝑥)
𝜕𝑥2
2
= 12𝑥2
2 −2; 𝜕2𝑓(𝑥)
𝜕𝑥2𝑥1
= −2; 
𝐻(𝑥) = (12𝑥1
2 −2
−2
−2
12𝑥2
2 −2). 
Рассмотрим стационарную точку 𝐴(0; 0) и составим 𝐻(𝐴) = 
= (−2
−2
−2
−2). Вычислим угловые миноры матрицы 𝐻(𝐴): Δ1 = |𝑎11| = 
= −2 < 0; Δ2 = |𝐻(𝐴)| = 0. Положительной определённости матрицы 
нет, значит, точка 𝐴 не является точкой локального минимума.  
Проверим эту точку на локальный максимум. Составим −𝐻(𝐴) = 
= (2
2
2
2).  Вычислим угловые миноры матрицы 𝐻(𝐴): Δ1 = |𝑎11| = 2 > 
> 0; Δ2 = |𝐻(𝐴)| = 0. Положительной определённости матрицы нет, 
значит, точка 𝐴 не является точкой локального максимума. Следовательно, точка 𝐴− седловая точка.  
Рассмотрим стационарную точку 𝐵(1; 1) и составим 𝐻(𝐵) =
=  (10
−2
−2
10). Вычислим угловые миноры матрицы 𝐻(𝐵): Δ1 = |𝑎11| =
=  10 > 0; Δ2 = |𝐻(𝐴)| = 96 > 0. Матрица положительно определённая, 
значит, точка 𝐵−  точка локального минимума.  

Рассмотрим стационарную точку 𝐶(−1; −1) и составим 𝐻(𝐶) = 
= (10
−2
−2
10). Матрица положительно определённая, значит, точка 
𝐶−  точка локального минимума.  
Ответ: 𝐵(1; 1), 𝐶(−1; −1) −точки локального минимума. 
Проиллюстрируем полученный результат. Построим двумерные 
линии уровня функции 𝑓(𝑥) и отметим точки 𝐴, 𝐵 и 𝐶. Построение будем выполнять в системе компьютерной алгебры Maple. Для этого сначала зададим функцию: 
> f := (x1, x2) -> x1^4 +x2^4-(x1+x2)^2 
Подключим пакет расширения plots и построим контурный график 
с помощью команды contourplot:  
> with(plots): 
> contourplot(f(x1, x2), x1 = -2.0 .. 2.0, x2 = -2.0 .. 2.0, axes = frame, filled = 
true, contours = 25, coloring = [yellow, green]); 
Здесь опция contours задаёт количество линий уровня на поверхности. Первое значение цвета (yellow) соответствует наименьшему значению функции, второе (green) – наибольшему (рис. 2). 
 
Рис. 2. Двумерные линии уровня функции 𝑓(𝑥) 
Построенные линии уровня подтверждают результат, полученный 
аналитически.