Курс: Методы оптимизации
Download 326 Kb.
|
31. Метод проекции градиента. (1)
Лемма 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]. Замечания:
Download 326 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2025
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling