Оглавление:
Метод проекции градиента
Естественны и другие попытки применить методы безусловной оптимизации для решения задач математического программирования. Одним-из них является метод проекции градиента (МПГ), базирующийся на биоритме градиентного спуска безусловной оптимизации. Другими словами, МПГ — численный метод условной оптимизации для нелинейных задач. Рассмотрим задачу:
где 
— замкнутое выпуклое множество в 
— дифференцируемая функция на множестве .
Проекцией точки а на множество называется точка 
, ближайшая к а среди всех точек , т.е. является решением задачи проектирования:
Свойства проекции точки на множество определяются следующими леммами и теоремой.
Лемма 1. Пусть — замкнутое выпуклое множество в 
. Тогда:
1) проекция а любой точки 
существует и единственна;
2) точка 
является проекцией точки а на множество 
в том и только в том случае, если
при всех
3) для любых точек
справедливо неравенство
оператор проектирования обладает свойством нерастяжения.
Доказательство. 1. Функция 
есть строго выпуклая функция, поэтому решение задачи (5.30) существует и единственно.
На выпуклом множестве и при выпуклой функции , если 
есть локальное решение задачи (5.29), должно выполняться условие
при всех 
.
Производная
В силу утверждения 2 имеем
Сложив эти неравенства, получим
что в силу неравенства Коши-Буняковского дает
Необходимые и достаточные условия оптимальности в выпуклой задаче на языке проекций формулируются следующим образом.
Лемма 2. Пусть множество выпукло и замкнуто, функция 
выпукла на и дифференцируема в точке 
. Тогда является решением задачи (5.29) в том и только в том случае, если 
при произвольном 
.
Доказательство. Согласно п. 2 леммы 1 приведенное равенство эквивалентно условию
при всех . Поэтому
при всех . А это и есть условие решения задачи (5.29).
В методе градиентного спуска определяется последовательность точек
в методе проекции градиента на каждой k-й итерации требуется производить операцию проектирования точки на множество т.е. решать задачу (5.30) при
В качестве очередной точки приближения к решению задачи (5.29) выбирается точка
Сходимость последовательности (5.31) к решению задачи (5.29) гарантируется следующей теоремой.
Теорема. Пусть множество выпукло и замкнуто, функция строго выпукла на c константой 
и дифференцируема на , причем ее градиент удовлетворяет условию Липшица
Тогда последовательность, генерируемая по правилу (5.31), где 
— произвольная точка из множества , а
сходится к решению задачи (5.29) со скоростью геометрической прогрессии:
где
(без доказательства).
Конкретных рекомендаций для выбора значений 8 нет, поэтому значения а выбирают из опыта. В общем случае на каждой итерации надо решать задачу (5.30). Но для некоторых множеств удается получить явный вид проекций:
А линейно независимы,
Если множество 
задается с помощью более или менее сложной системы равенств и неравенств, то метод проекции градиента практически не применим — задача (5.30) не проще исходной задачи.
Пример:
Найти
при ограничениях
Здесь множество — круг радиуса 
с центром в начале координат 
, т.е. это шар. Последовательность точек в методе проекции градиента задается формулой
Пусть нулевое приближение
Производные
Тогда, согласно (5.31),точка
длина вектора
согласно (5.32) проекция
значение целевой функции
На следующем шаге имеем
значение целевой функции
т.е. движение идет в правильном направлении: оптимальное решение имеет координаты (0,75; 1,85) и значение целевой функции равно (—2,8).
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
