Курс: Методы оптимизации

Лемма 1 Пусть замкнутое выпуклое множество в . Тогда
1. Проекция любой точки существует и единственна;
2. Точка является проекцией точки a на множество X в том и только в том случае, если (3)
3. Для всех точек справедливо неравенство
(4)
т.е. оператор проектирования обладает свойством нерастяжения расстояний.
Доказательство леммы приведено в [Сухарев, с. 225].
Сформулируем необходимое и достаточное условие оптимальности для выпуклой задачи.


Лемма 2. Пусть множество X выпукло и замкнуто, функция f выпукла на X и дифференцируема в точке . Тогда является решением задачи (1) в том и только в том случае, если
(5)
при произвольном .
Доказательство леммы приведено в [Сухарев, с. 226].

Теперь рассмотрим алгоритм метода проекции градиента и его сходимость. В методе проекции градиента в качестве очередной точки приближения к решению задачи (1) выбирается проекция точки на множество X той точки, которая получается по градиентному методу:

, где (6)
Коэффициенты можно выбирать различными способами. (см. например, книги: Сухарев и др. или Реклейтис и др.). Рассмотрим теорему о сходимости проекции градиента с априорным выбором коэффициентов , то есть последовательность выбирают заранее, до начала вычислений (например, , где k=0,1,2,...).


Теорема 1. Пусть множество X выпукло и замкнуто, функция f сильно выпукла с константой и дифференцируема на X, причем ее градиент удовлетворяет условию Липшица:
(7)
Тогда последовательность , генерируемая по формуле (6), где произвольная точка из X, а сходится к решению задачи (1) со скоростью геометрической прогрессии:
(8)
где
Доказательство теоремы приведено в [Сухарев, с. 226].

Замечания:

0. 
   В рассмотренном методе на каждой k-ой итерации требуется производить операцию проектирования точки на множество X, то есть решать задачу вида (2) при . В некоторых случаях удается указать явный вид проекции, например, если множество X  шар, координатный параллелепипед, полупространство, гиперплоскость, аффинное множество. Однако, если X задается с помощью более или менее сложной системы равенств и неравенств, то метод проекции градиента практически неприменим, так как задача (2) оказывается не проще исходной.
   
1. 
   В большинстве практических задач константы из теоремы 1 обычно неизвестны, что затрудняет отыскание . Тогда можно использовать другие правила выбора длины шага, например, различные модификации метода наискорейшего спуска с приближенным решением задач одномерной минимизации по или правило дробления шага [Реклейтис и др.].
   
2. 
   Используя идею проектирования, можно модифицировать применительно к задачам условной оптимизации и другие методы безусловной оптимизации, в том числе метод Ньютона и метод сопряженных направлений.