- •Элементы выпуклого анализа.
- •Основная задача выпуклого программирования. Седловая точка и оптимальный план.
- •Теорема Куна-Таккера.
- •Критерий оптимальности для гладкой выпуклой задачи .
- •Теория двойственности в выпуклом программировании.
- •Решение одной задачи выпуклого программирования.
- •О существовании решения линейной задачи.
- •Задача на безусловный минимум.
- •3.2.1 Метод исключения
- •10. Задача с равенствами. Обобщенное правило Лагранжа.
- •Задача с равенствами. Метод исключения.
- •Задача с равенствами. Классическое правило множителей Лагранжа
- •Задача с равенствами. Лемма о включении
- •Задача с равенствами. Необходимое условие оптимальности первого порядка
- •Задача с равенствами. Другое доказательство принципа Лагранжа
- •Задача с равенствами. Случай линейных ограничений
- •Задача с равенствами. Условия оптимальности второго порядка
- •Задача с неравенствами. Необходимое условие оптимальности первого порядка
- •Задача снеравенствами. Обобщённое правило множителей Лагранжа
- •Задача с неравенствами. Классическое правило множителей Лагранжа
- •Задача с неравенствами. Условие оптимальности второго порядка
- •Векторная оптимизация. Эффективные планы. Усреднение целевых функций.
- •Принципы выбора
- •1. Введение весовых коэффициентов
- •2. Введение иерархии целевых функций
- •3. Установление гарантированных уровней
- •4. Минимизация расстояния до идеальной точки
Задача с равенствами. Случай линейных ограничений
(1)
Будем предполагать, что функции и имеют нужную гладкость.
Рассмотрим задачу
оптимизации:
(19)
Эта задача (1), у
которой
.
Теорема. Пусть
− локально-оптимальный план задачи
(19). Тогда для любого вектора
такого, что
(20)
выполняется неравенство
(21)
Доказательство.
Пусть
− локально-оптимальный план и пусть
удовлетворяет равенству (20). Построим
векторы
.
Докажем, что они являются планами задачи
(19). Действительно,
. Ясно,
что
лежат в сколь угодно малой окрестности
при малых
.
Допустим противное. Существует направление , подходящее для задачи на плане , то есть этот вектор будет удовлетворять (17), то есть .
По и , согласно лемме о включении найдутся такие планы , лежащие в окрестности точки , что .
Рассмотрим разложение
для некоторых малых , то есть получили неравенство . Это неравенство противоречит локальной оптимальности , то есть в любой малой окрестности точки найдутся планы лучшие, чем .
Ч.т.д.
Следствие. Применяя к (20), (21) теорему Фаркаша о неравенстве вследствие равенств, приходим к выводу, что для задачи (19) всегда справедливо классическое правило множителей Лагранжа (не требуется проверки на обыкновенность).
Задача с равенствами. Условия оптимальности второго порядка
(1)
Будем предполагать, что функции и имеют нужную гладкость.
Теорема 1
(Необходимое
условие оптимальности второго порядка).
Пусть
− обыкновенный локально-оптимальный
план задачи (1) и пусть
соответствующий ему вектор Лагранжа.
Тогда для любого вектора
допустимого по ограничениям
выполняется неравенство
.
Доказательство.
Пусть
− обыкновенный локально-оптимальный
план. Возьмём произвольный вектор
,
который удовлетворяет условию (12). По
и
,
согласно лемме о включении найдутся
планы
,
.
Рассмотрим функцию
.
Из локальной оптимальности
следует, что у задачи
оптимальным планом будет
.
Известно, что для
функции одной переменной достаточно
гладкой необходимым условием оптимальности
будет
.
Распишем условие неотрицательности:
(21)
Рассмотрим очевидное
тождество
.
.
Если это тождество продифференцировать дважды по , то получим снова тождественный нуль. А если потом рассмотреть это тождество при , то получим равное нулю выражение:
(22)
Если теперь сложить равенства (21) и (22), то с учётом вида функции Лагранжа придём к неравенству:
следовательно
.
Ч.т.д.
Теорема 2
(Достаточное условие оптимальности).
Пусть пара
− условно-стационарная точка задачи
(1). Тогда, если для любого вектора
удовлетворяющего условию (12) и
выполняется условие
,
то
− локально-оптимальный план задачи
(1).
