<<
>>

11.1. Общая схема градиентных методов. Понятие функции релаксации

Классические градиентные схемы, основанные на применении антигра­диентов в качестве направлений спуска, непосредственно не приспособ­лены для минимизации овражных функционалов и по этой причине не позволяют получить решение сколько-нибудь сложной задачи конечно­мерной оптимизации.
Однако далее будет показано, что на их основе мо­гут быть построены методы, обладающие существенно лучшими показа­телями сходимости в овражной ситуации независимо от характера выпуклости минимизируемых функционалов. С учетом представленных в главе 9 моделей явления овражности эффективность алгоритмов оценива­ется по свойствам специально вводимых для этих целей функций релакса­ции, полностью определяющих локальные характеристики методов.

Пусть решается задача

/(*)-> пип; хеД"; С2(Л"). (11.1)

X

Рассмотрим класс матричных градиентных методов вида

хА+1 = - Нкк, К)Г(хк) (кк е Л1), (11.2)

где Ак = Т\хк), Нк — матричная функция Ак. Предполагается, что в неко­торой ^.-окрестности {х е Я" | \\х - хА|| < точки хк функционал 7(х) достаточно точно аппроксимируется квадратичным функционалом

/(х)=1/2 (Акх, х) - (Ък, х> + с*, (11.3)

где Ак — симметричная, не обязательно положительно определенная матрица. Без существенного ограничения общности можно считать, что bk - 0, ск = 0. Действительно, принимая &е\Ак * 0, х = х* + z, где х* = = АкчЬк, получим представление

ш =f(x + Z) = 1/2 (Akz,z) + Ck. (11.4)

При этом константу ck =ck -1/2^Акх*, х*^ можно не учитывать как не влияющую на процесс оптимизации.

Формула (11.2) обладает свойством инвариантности относительно сме­щения начала координат. Будучи записанной для /(х), она преобразуется в аналогичное соотношение для f\(z). Для f(x) имеем:

хмкккхкк). (11.5)

Принимая zk = хк — х*, получаем из (11.5): zA+1 = zk - HkAkzk. А это есть запись метода (11.2) для функционала/,.

Ставится задача построения таких матричных функций Нк, чтобы вы­полнялись условия релаксационности процесса/(хА+1) 0) (11.7)

для всех собственных чисел I = 1,п матрицы

Доказательство. Пусть {ц} — ортонормированный базис, составленный из собственных векторов матрицы Ак. Тогда, разлагая хк по векторам ба­зиса, получаем

** = Е Ъ»,' (Л. к )/\хк)=

/=1

= (Е- НкАкк = 2 ^ (1 - Нк (А,, Ък )к, =

/=1

/=1

Из сравнения выражений

1 = 1

/

<< | >>
Источник: Черноруцкий И. Г.. Методы принятия решений. — СПб.: БХВ-Петербург, — 416 с.. 2005 {original}

Еще по теме 11.1. Общая схема градиентных методов. Понятие функции релаксации:

  1. 11.3. Методы с экспоненциальной функцией релаксации
  2. 11.4. Реализация и область применимости методов с экспоненциальной функцией релаксации
  3. ГРАДИЕНТНЫЕ МЕТОДЫ
  4. Методы спуска. Приближенное решение задач выпуклого программирования градиентным методом
  5. 9.1. Понятие финансового результата деятельности организации и общая схема его формирования
  6. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА
  7. 6. ГРАДИЕНТНЫЕ МЕТОДЫ
  8. 6. Градиентные методы
  9. МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМ
  10. 1.3. Общая схема
  11. 11.3. Общая схема сложных процентов
  12. ОБЩАЯ СХЕМА ПРОВЕРКИ ГИПОТЕЗЫ
  13. 5.2. Принципы и общая схема оценки эффективности ИП
  14. 4.4. Общая схема оценки эффективности
  15. Общая схема объяснений
  16. Общая концептуальная схема действия
  17. 7.3. Общая схема простых процентов
  18. 11.2. Классические градиентные схемы
  19. 8.1. Понятие и общая характеристика функций государства