- •Глава 6. Постановки задачи нелинейного программирования (знп) и основные определения…………………………...3
- •Глава 7. Задача одномерной оптимизации…………………………………….13
- •Глава 8. Графический метод решения знп…………………………………...33
- •Глава 10. Выпуклое программирование……………………………………....62
- •Глава 11. Квадратичное программирование…………………………………74
- •Глава 12. Задача безусловной оптимизации (збо)…………………………………………………………………..81
- •Глава 13. Задача условной оптимизации (зуо)……………………….……127
- •Глава 6.
- •6.1. Задача нелинейного программирования (знп) и ее постановки.
- •6.2. Основные определения.
- •6.3. Классификация знп.
- •6.4. Классическая оптимизация.
- •Глава 7. Методы одномерной оптимизации
- •Постановка задачи. Основные понятия
- •7.2. Поиск отрезка, содержащего точку максимума Алгоритм Свенна
- •Методы нулевого порядка.
- •Дихотомический поиск (метод деления отрезка пополам)
- •Метод золотого сечения
- •Метод дск-Пауэлла
- •7.4. Методы первого порядка.
- •Метод средней точки
- •Метод хорд (секущих)
- •Метод кубической аппроксимации
- •7.5. Методы второго порядка. Метод Ньютона-Рафсона
- •Итерация 1
- •Глава 8. Графический метод решения знп.
- •8.1. Алгоритм графического метода решения знп
- •8.2. Решение примеров.
- •Выпуклые и вогнутые функции
- •9.1. Определения
- •9.2. Свойства вогнутых (выпуклых) функций
- •9.3. Критерии вогнутости (выпуклости) гладких функций
- •9.4. Экстремальные свойства вогнутых (выпуклых) функций
- •9.5. Сильно вогнутые (выпуклые) функции
- •9.5.1. Определение. Примеры
- •9.5.2. Свойства сильно вогнутых (выпуклых) функций
- •9.5.3. Критерии сильной вогнутости (выпуклости)
- •9.5.4. Экстремальные свойства сильно вогнутых (выпуклых) функций
- •Глава 10. Выпуклое программирование
- •10.1. Постановка задачи
- •10.2. Функция Лагранжа. Седловая точка функции Лагранжа, условия ее существования Определение 10.1. Функция , (10.10)
- •10.3. Достаточные условия оптимальности
- •10.4. Условия регулярности выпуклого множества
- •10.5. Теорема Куна-Таккера. Общий случай
- •10.6. Теорема Куна-Таккера. Случай линейных ограничений
- •Глава 11. Квадратичное програмирование.
- •11.1. Постановка задачи квадратичного программирования (зкп)
- •11.2. Применение теории Куна-Таккера к решению зкп.
- •11.3. Решение задач.
- •Глава 12. Методы безусловной оптимизации
- •12.1. Постановка задачи
- •Алгоритм метода спуска
- •. Методы нулевого порядка (прямого поиска)
- •Метод Хука-Дживса
- •Алгоритм метода Хука-Дживса, использующий одномерный поиск
- •Метод покоординатного спуска
- •Первый вариант
- •Второй вариант
- •Методы первого и второго порядков
- •Градиентные методы. Метод скорейшего спуска – метод Коши
- •Метод Ньютона
- •Модифицированный метод Ньютона
- •Методы, использующие сопряженные направления
- •Определение сопряженных направлений
- •Оптимизация квадратичной функции. Конечная сходимость алгоритмов, использующих сопряженные направления
- •12.4.4. Метод Дэвидона-Флетчера-Пауэлла Шаг 1.Метод Дэвидона-Флетчера-Пауэлла (дфп) принадлежит к классу квазиньютоновских методов, в которых направление поиска задаётся в виде
- •Алгоритм метода дфп
- •Итерация 1
- •Шаг 2. Вычислим , тогда .
- •Шаг 2. Вычислим , тогда .
- •12.4.5. Метод сопряжённых градиентов Флетчера-Ривса
- •Алгоритм метода Флетчера-Ривса
- •Глава 13. Методы условной оптимизации
- •13.1. Постановка задачи. Классификация методов
- •Общая схема методов условной оптимизации
- •Шаг 2.Шаг 1. Выбрать ( -я итерация) – возможное направление подъёма функции в точке . Если такого направления нет, то - решение задачи. В противном случае перейти к шагу 2.
- •13.2. Методы возможных направлений
- •13.2.1. Метод Зойтендейка
- •Пример 13.2
- •Итерация 3
- •Шаг 4.Рисунок 13.6
- •13.2.2. Метод Топкиса-Вейнотта
- •Пример 13.3
- •Итерация 1
- •Шаг 5.Рисунок 13.7
- •Алгоритм метода Топкиса-Вейнотта
- •13.2.3. Метод Франка-Вульфа
- •Алгоритм метода Франка-Вульфа
- •Шаг 5. Находим шаг в направлении новой точки . Решение этой задачи (одномерной): .
- •Шаг 3. Так как , переходим к шагу 4.
- •Шаг 5. Решаем задачу: .
- •Литература
9.5.4. Экстремальные свойства сильно вогнутых (выпуклых) функций
Теорема 9.20. Пусть функция сильно вогнута и непрерывна на выпуклом замкнутом множестве . Тогда:
множество не пустое и состоит из единственной точки ;
имеет место неравенство (9.27) для любого ;
любая максимизирующая последовательность , , , сходится к точке .
Эта теорема является обобщением теоремы Вейерштрасса, т.к. от множества не требуется ограниченности. В частности, в теореме возможно .
Доказательство. Если ограничено, то все утверждения теоремы 9.20, кроме (9.27), следуют из теоремы Вейерштрасса.
1. Рассмотрим множество , где . Оно замкнуто и ограничено в силу теоремы 9.16.
В силу теоремы 9.14 функция ограничена на множестве , а следовательно, и на , тогда по теореме Вейерштрасса существует точка , такая что , но из определения множества следует, что , т.е. .
Так как сильно вогнутая функция является и строго вогнутой (теорема 9.13), то в силу теоремы 9.11 множество состоит из единственной точки .
2. Из определения сильной вогнутости функции (9.14) для следует
(9.28)
В силу неравенства из соотношения (9.28) получим условие (9.27) теоремы:
или или
(9.29)
для любого .
3. Пусть существует максимизирующая последовательность , т.е. .
Полагая в (9.29) , получим
Отсюда при следует, что .
Глава 10. Выпуклое программирование
10.1. Постановка задачи
Задачей выпуклого программирования называется следующая задача
, (10.1)
, (10.2)
где – заданное выпуклое множество из , определены и выпуклы на , определена и вогнута на .
В дальнейшем под множеством будем понимать положительный октант
, (10.3)
т.е. будем рассматривать следующую задачу выпуклого программирования
(10.4)
, (10.5)
В силу теоремы 9.4. множество выпукло.
Пример 10.1. Задача квадратичного программирования
, (10.6)
, (10.7)
где – отрицательно определенная матрица, – заданный вектор из , – заданная матрица, представляет собой задачу выпуклого программирования.
Пример 10.2. Основная задача линейного программирования
, (10.8)
, (10.9)
где – заданная матрица порядка , – заданный вектор из , – заданный вектор из , является частным случаем задачи выпуклого программирования.
10.2. Функция Лагранжа. Седловая точка функции Лагранжа, условия ее существования Определение 10.1. Функция , (10.10)
где , называется функцией Лагранжа для задачи выпуклого программирования (10.4), (10.5).
Определение 10.2. Точка называется седловой точкой функции Лагранжа (10.10) на множестве , , если
, , (10.11)
для всех , .
Соотношение (10.11) можно переписать следующим образом:
(10.12)
В задачах выпуклого (и, в частности, квадратичного и линейного программирования) функция Лагранжа играет важную роль, а именно при довольно общих предположениях задача выпуклого программирования сводится к отысканию седловых точек функции Лагранжа. “Простые” же ограничения задачи (10.12) позволяют применять для ее решения методы, схожие с численными методами безусловной оптимизации.
Следующая теорема дает другое, равносильное (10.11), определение седловой точки.
Теорема 10.1. для того чтобы точка была седловой точкой функции Лагранжа, необходимо и достаточно, чтобы выполнялись следующие условие:
(10.13)
для всех , , , . (10.14)
Доказательство.
Необходимость. Пусть – седловая точка. Тогда условие (10.13) представляет собой левое неравенство (10.11). Получим условия (10.14). Перепишем правое неравенство (10.11), подставив в него (10.10):
, (10.15)
отсюда , , . (10.16)
Рассмотрим точки , , где и при всех остальных , .
Из (10.16) при получим , , т.е. .
Теперь рассмотрим точки , , и из (10.16) получим при ,
или (10.17)
для всех .
Но , при , поэтому неравенство (10.17) возможно только при для всех , т.е. соотношения (10.14) получены.
Достаточность. Пусть для некоторой точки выполняются условия (10.13), (10.14). Покажем, что – седловая точка. Необходимо доказать выполнение правого неравенства из (10.11). По условию (10.14) точка , т.е. для всех . Если для некоторого , то . Если для некоторого , то из условия (10.14) следует, что и для любого . Таким образом, для всех , откуда и , или для всех , т.е. доказано выполнение правого неравенства (10.11).
Теорема 10.2. Устанавливает условия существования седловой точки. Предположим, что в задаче выпуклого программирования (10.4), (10.5) функции , , являются непрерывно-дифференцируемыми при . Тогда, для того чтобы точка была седловой точкой функции Лагранжа в области , , необходимо и достаточно выполнение условий
, (10.18)
, (10.19)
, (10.20)
, (10.21)
, (10.22)
, (10.23)
где
(10.24)
(10.25)
Запишем условия (10.18)-(10.23) в эквивалентной форме:
, (10.26)
, (10.27)
, (10.28)
, (10.29)
, (10.30)
, (10.31)
Необходимость. Пусть выполняется условие (10.110 в области , . В частности, отсюда следует, что для всех , т.е. точка является точкой максимума функции одного переменного на полупрямой . Условия (10.26)-(10.28) являются необходимыми условиями локального максимума при для функции одного переменного (если , то , если , то ).
Аналогично доказывается справедливость условий (10.29)-(10.31) (функция линейная по ).
Достаточность. Пусть для некоторой точки выполняются условия (10.18)-(10.23). Так как функция вогнута, а функции – выпуклы, , то функция вогнута по при .
Пользуясь неравенством (9.3), получим ,
откуда из (10.18) и (10.19) получаем
т.е. для любого , т.е. доказано выполнение левого неравенства (10.11).
Функция линейная и, следовательно, выпуклая по при любом . Пользуясь для выпуклой функции неравенством, аналогичным (9.3), получим , откуда из (10.21) и (10.22) получаем правое неравенство в (10.11)
для любого .