- •Глава 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. Решаем задачу: .
- •Литература
6.2. Основные определения.
Начнём с того, что уточним постановку задачи (6.1)-(6.4) .
Определение 6.2. Точку , удовлетворяющую всем ограничениям (6.2)-(6.3), назовем допустимым решением или планом ЗНП. Совокупность всех планов обозначим через P. Таким образом, ЗНП можно записать в виде:
(6.5)
Для уточнения постановки ЗНП необходимы такие понятия как: точка минимума и максимума, наименьшее и набольшее значение, нижняя и верхняя грань функции на множестве P, минимизирующая и максимизирующая последовательность, точка локального и глобального минимума и максимума, сходимость последовательности к заданному множеству и т.д., известные из классического математического анализа.
Определение 6.3. Точку называют точкой глобального минимума (максимума) функции на множестве Р, если ( ) для всех . Величину называют наибольшим или максимальным (наименьшим или минимальным) значением на Р.
Множество всех точек максимума на Р будем обозначать через P* . В зависимости от свойств множества Р и функции множество P* может содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когда P* пусто (см.пример 6.3).
В тех случаях, когда , естественным обобщением понятия наименьшего (наибольшего) значения функции является понятие нижней (верхней) грани функции.
Определение 6.4. Функция называется ограниченной снизу (сверху) на множестве Р, если существует такое число М, что ( ) для всех . Функция не ограничена снизу (сверху) на Р, если существует последовательность , для которой ( ).
Определение 6.5. Пусть функция ограничена сверху на множестве Р. Тогда f* называют верхней гранью на Р, если:
а) при всех ;
б) для любого сколь угодно малого числа найдётся точка
для которой .
Верхнюю грань на Р обозначают через .
Если функция не ограничена сверху на Р, то в качестве верхней грани на Р принимается .
Определение 6.6. Пусть функция ограничена снизу на множестве Р. Тогда число называют нижней гранью на Р, если:
a) при всех
б) для любого сколь угодно малого числа найдется точка , для которой .
Нижнюю грань на Р обозначают через .
Если функция не ограничена снизу на Р, то в качестве нижней грани на Р принимается .
Таким образом, запись ЗНП в форме (6.5) означает:
либо 1) найти точку такую что, или , данная форма записи возможна только в случае 1;
либо, если не существует такой точки ( ), то 2) найти ;
либо 3) убедиться, что не ограниченная сверху (снизу) на Р функция, т.е. ; ;
либо 4) убедиться в том, что Р пусто ( ).
Пример 6.3.
Пусть при и .
В ЗНП
и т.е. множество P* состоит из единственной точки.
В ЗНП
множество P* содержит 3 точки:
и .
В ЗНП
множество P* содержит счетное число точек:
и
В ЗНП
не имеет наименьшего значения на Р.
В самом деле, какую бы точку ни взять, найдётся точка (например, при достаточно большом k) такая, что .
Это значит, что пусто.
Пример 6.4.
Пусть при и . На множествах или эта функция не имеет наименьшего значения, т.е. , но
Пример 6.5.
В ЗНП , . , так как во всех точках из P функция принимает конечные значения, а для последовательности имеем , т.е. .
В примерах 6.3, 6.4 функции ограничены снизу на рассматриваемых множествах, а в примере 6.5 функция не ограничена.
Если , то, очевидно, нижняя грань совпадает с наименьшим значением этой функции на Р, т.е . В этом случае говорят, что функция на Р достигает своей нижней грани. Подчеркнем, что всегда существует, а , как мы видели из примеров 6.3, 6.4, не всегда имеет смысл.
Определение 6.7. Последовательность называется минимизирующей для функции на множестве Р, если
Из определения и существования нижней грани следует, что минимизирующая последовательность всегда существует.
Пример 6.6. Рассмотрим . Очевидно, здесь и множество Р* состоит из единственной точки x*=0. последовательность является минимизирующей , так как , но не стремится к нулю.
Определение 6.8. Функция достигает на замкнутом множестве в точке локального максимума, если существует число такое, что для всех , где