- •Введение
- •1. Основы математического программирования
- •1.1. Постановка задачи математического программирования
- •1.2. Разновидности змп
- •1.3. Базовые понятия и терминология математического программирования
- •1.4. Производная по направлению. Градиент
- •1.5. Касательные гиперплоскости и нормали
- •1.6. Разложение Тейлора
- •1.7. Задача нелинейного программирования и условия существования ее решения
- •1.8. Задачи
- •2. Решение задачи нелинейного программирования без ограничений
- •2.1. Необходимые условия существования безусловного экстремума функции
- •2.2. Достаточные условия существования безусловного экстремума функции
- •2.3. Классический метод поиска безусловного экстремума
- •2.4. Задачи
- •3. Решение задачи нелинейного программирования при ограничениях-равенствах
- •3.1. Метод множителей Лагранжа
- •3.1.1. Назначение и обоснование метода
- •3.1.2. Схема реализации метода множителей Лагранжа
- •3.1.3. Интерпретация множителей Лагранжа
- •3.2. Метод подстановки
- •3.3. Задачи
- •4. Решение задачи нелинейного программирования при ограничениях-неравенствах
- •4.1. Обобщенный метод множителей Лагранжа
- •4.2. Условия Куна-Таккера
- •4.2.1. Необходимость условий Куна-Таккера
- •4.2.2. Достаточность условий Куна-Таккера в задачах выпукло-вогнутого программирования
- •4.2.3. Метод Куна-Таккера решения задачи выпукло-вогнутого программирования
- •4.3. Задачи
- •5. Численные методы решения знлп
- •5.1. Понятие алгоритма
- •5.3.2. Метод сопряженных градиентов
- •Описание алгоритма
- •5.3.3. Метод Ньютона
- •5.3.4. Метод Ньютона-Рафсона
- •Литература
- •Оглавление
1.3. Базовые понятия и терминология математического программирования
Множество называется ограниченным множеством, если расстояние между любыми двумя его точками меньше некоторого числа :
.
Эпсилон-окрестностью точки называется множество точек, отстоящих от точки на расстоянии меньшем, чем :
.
Точка называется предельной точкой множества , если существует последовательность принадлежащих точек , сходящаяся к , то есть если выполняется условие
. (1.10)
Множество называется замкнутым множеством, если оно содержит все свои предельные точки.
Множество называется компактным множеством, если оно ограничено и замкнуто.
Точка называется внутренней точкой множества , если существует такое, что . В противном случае точка называется граничной точкой множества .
Точка называется точкой условного локального максимума (локального минимума) функции в области , если существует окрестность такая, что для любой точки из этой окрестности значение не больше (не меньше), чем :
( для минимума). (1.11)
Точка называется точкой условного глобального максимума (глобального минимума) функции в области , если значение не меньше (не больше), чем для любого :
( для минимума).
Говорят, что функция имеет в точке условный локальный (глобальный) экстремум на множестве , если точка является точкой локального (глобального) максимума или минимума.
Говорят, что функция имеет в точке локальный (глобальный) безусловный экстремум, если точка является точкой локального (глобального) максимума или минимума на всем пространстве .
Говорят, что функция дифференцируема в точке , если в этой точке существуют все ее частные производные первого порядка
.
Говорят, что функция непрерывно дифференцируема в точке , если все ее частные производные первого порядка непрерывны в этой точке.
Точка , в которой равны нулю все частные производные первого порядка функции , называется стационарной точкой этой функции.
Точка называется седловой точкой (седлом) функции , если она является стационарной точкой, но не является точкой безусловного экстремума.
Говорят, что функция дважды дифференцируема в точке , если в этой точке существуют все ее частные производные второго порядка
.
Замечание 1.1. Значение частной производной второго порядка не зависит от порядка дифференцирования по переменным, то есть
.
Квадратная матрица , элементы которой определяются значениями частных производных второго порядка функции в точке , то есть
,
называется матрицей Гессе функции в точке .
Выражение , где – квадратная матрица, , называется квадратичной формой матрицы .
Квадратная матрица называется положительно (неотрицательно) определенной, если справедливо
. (1.12)
Квадратная матрица называется отрицательно (неположительно) определенной, если справедливо
. (1.13)
Квадратная матрица называется неопределенной матрицей, если она не является ни положительно, ни отрицательно определенной.
Установить тип определенности матрицы Гессе в стационарной точке позволяет следующая теорема.
Теорема об условиях определенности матрицы (критерий Сильвестра). Справедливы следующие утверждения:
1) квадратная матрица положительно определена тогда и только тогда, когда значения всех ее главных миноров положительны.
2) квадратная матрица отрицательно определена тогда и только тогда, когда знак ее k-го главного минора определяется знаком .
Пример 1.1. Матрицы , определены положительно; матрицы , определены отрицательно.
Функция называется m-мерной вектор-функцией, если она представляет собой m-мерный вектор, компоненты которого суть вещественные функции, то есть
.
Матрицей Якоби m-мерной вектор-функции называется матрица размера , элементы которой определяются формулами
.
Функция называется выпуклой в области , если
, .
Функция называется вогнутой в области , если
, .
Замечание 1.2. Функция является вогнутой в области , если функция выпукла в этой области.
Свойства выпуклых функций
1. Сумма выпуклых функций является выпуклой функцией.
2. Если выпукла и , то тоже выпукла.
3. Если выпукла и , то вогнута.