Функции релаксации градиентных методов

Последний, кстати, фактически использует данное представление, поскольку в нем осуществляется векторное сложение расширенных неопределенностей. Метод статистического моделирования (называемый также методом статистических испытаний, методом Монте-Карло) учитывает автоматически как положение на числовой оси, так и рассеяние значений физической величины, т. к. представляет ее случайной совокупностью, но требует для своей реализации резкого увели-

чения вычислительного ресурса.

На вопрос, что практически дает «угловое» представление свойств физических объектов, также ответить сложно. Здесь причина в радикальном расширении понятия «физическая величина».

В целом представляется, что вопрос о практическом использовании приведенных соображений выходит за рамки данной статьи и нуждается в отдельном рассмотрении.

СПИСОК ЛИТЕРАТУРЫ

1. Тарбеев, Ю.В. Пути развития фундаментальных исследований в области теоретической метрологии [Текст] / Ю.В. Тарбеев // III Всесоюз. совещ. по теорет. метрологии: тез. докл. -Л., 1986. -С. 4-7.

2. Математическая энциклопедия: В 5 т. [Текст] / -М., 1977. -Т. 1. -1152 с.

3. Шутц, Б. Геометрические методы математической физики [Текст] / Б. Шутц. -М., 1984. -303 с.

4. Мазин, В.Д. Описание свойств физических объектов в кусочно-евклидовых и кусочно-римановых пространствах [Текст] / В.Д. Мазин // Вычисл., измер. и управл. системы. -Л.: Изд-во СПбГТУ, 1993.

5. Новицкий, П.В. Оценка погрешностей резуль-

татов измерений [Текст] / П.В. Новицкий, И.А. Зограф; 2-е изд. перераб. и доп. -Л., 1991. -303 с.

6. Рашевский, П.К. Риманова геометрия и тензорный анализ [Текст] / П.К. Рашевский; Изд. 4-е, стер. -М.: УРСС, 2002. -664 с.

7. Корн, Г. Справочник по математике для научных работников и инженеров [Текст] / Г. Корн, Т. Корн; 5-е изд. -М., 1984. -831 с.

8. Mazin, V. Properties and application technology of a vector-analytical method for an estimation of uncertainty in measurement [Text] / V. Mazin, A. Chepushtanov // Proc. of the 56-th International Scientific Colloquium of the TU Ilmenau. -Ilmenau, 2008.

УДК 681.3.06

И.Г. Черноруцкий

ФУНКЦИИ РЕЛАКСАЦИИ ГРАДИЕНТНЫХ МЕТОДОВ

Введено понятие функции релаксации (ФР) для класса матричных градиентных методов, включающего в себя такие классические процедуры, как метод простого градиентного спуска, метод Ньютона, метод Маркуардта-Левенберга. Показано, что ФР является своеобразным «паспортом» метода и полностью определяет его локальные свойства подобно областям устойчивости методов численного интегрирования систем обыкновенных дифференциальных уравнений. ФР является не только средством анализа заданного матричного градиентного метода, но и средством синтеза новых оптимизирующих процедур, обладающих необходимыми свойствами.

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

J(x) ^ min, x е Rn, J e C2 (Rn).

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

= xk - Hk (Ak, hk) J'(xk), hk e R1,

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

Дх)=1/2

где Лк - симметричная, не обязательно положительно определенная матрица. Без существенного ограничения общности можно считать, что Ък = 0, ск = 0. Действительно, принимая detЛкФ 0, х = = х* + 2, где х* = Лк1Ък, получаем представление

№) = Ах* + 2) = 1/2 (Лк2, 2) + Ск.

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

Формула

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

д (хк)=1 £ х.

2/ ,=1

1

Д (хк+1) =Ж

2 / ^ +1

х, = ^ х,я2

имеем:

= х - них - Ъ\

1

,=1 2 =1 следует, что при выполнении (7) каждое слагаемое суммы в представлении ДХ) не возрастает. Достаточность доказана. Докажем необходи-(5) мость. Пусть существует такой индекс , = ,0, для

Принимая X = хк - х*, получаем из

которого Х. < 0, Я(Х. ) < 1.

к\ А СЛ ^ °Х.к+К

Выберем

х = и.

Х+1 = X - Н,Лкгк. Это запись метода (2) для функ- Тогда Д(х ) = 0,5Х, < Д(х + ) = 0,5Х Я , что про-

ционала Д1.

Ставится задача построения таких матричных функций нк, чтобы выполнялись условия релак-сационности процесса ДХ+1) < ДХ).

Определение. Скалярная функция Як(Х) = = 1 - Н(Х, к)Х; X, к е Я1 называется функцией релаксации метода (2), а ее значения Як(Х,) на спектре матрицы Ак - множителями релаксации для точки X.

В некоторых случаях для сокращения записей индекс «к» в выражении функции релаксации будет опускаться.

Здесь Н(Х, к) означает скалярную зависимость, отвечающую матричной функции Н(Лк,кк) в представлении (2).

Напомним, что если А - симметричная матрица и Л = Тdiag (Х1, Х2, ... , Хп) Т, где Т- ортогональная матрица, столбцы которой есть собственные векторы матрицы А, то F(Л) = Т diag [^(Х1), ^(Х2), ... , ^Х)] Г.

Матричная функция имеет смысл, если порождающая скалярная функция ^(Х) определена в точках Х., Х., ..., Х .

1' 2' ' п

Теорема. Для выполнения условия

дх+о < ДХ)

при Ухк е Яп необходимо и достаточно, чтобы

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

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

хк = £ ЪкЧ; хк+1 = хк - Нк (Лк, кк)Д '(хк) =

=1

= (Е - НкЛк) хк =£ (1 - Нк (Х,, кк) Х,) и, =

=1

= £ ^,,кЯ(Х,) и,.

тиворечит условию релаксационности (6). Аналогично рассматривается второе неравенство (7). Теорема доказана.

З амечания.

1. Для строгого выполнения неравенства (6) необходимо и достаточно, кроме выполнения условий (7), потребовать, чтобы существовал такой индекс , = ,0, для которого к Ф 0, и соответствующее неравенство (7) было строгим.

2. Выражения (8) позволяют оценить скорость убывания функционала Дв зависимости от «запаса», с которым выполняются неравенства (7). Действительно, обозначим через Х.+, Х- положительные и отрицательные собственные числа матрицы Ак. Эти же индексы присвоим соответствующим собственным векторам. Суммирование по соответствующим , будем обозначать £+, £-. Тогда

2ДХ)-Дх+1)| = 2 ,

ХД1 - Я2 (Х,+)) +

+ 2,,к |Х-| (Я2 (Хг) - 1).

Из полученного выражения следует, что наибольшее подавление будут испытывать слагаемые, для которых значение множителя релаксации наиболее существенно отличается от единицы (при выполнении условий (7)).

Далее будут рассматриваться в основном зависимости Як(Х), обладающие свойством Як(Х) ^ 1 (к ^ 0).

В этом случае из равенства

-хк|| = [Я, (Х,)-1]2

следует, что для УЕ,к е Я1 всегда можно выбрать такой кк, что ||хк+1 - Х\\ < Таким образом, с помощью параметра кк можно регулировать норму вектора продвижения в пространстве управляемых параметров с целью предотвращения выхода из области справедливости локальной квадратичной модели (3).

х

Иногда для ограничения нормы (10) параметр к может вводиться в схему оптимизации как множитель в правой части (2):

хк+1

При этом Цхк+1(к) - хк|| = к||х^+1(1) - хк||, а второе равенство (11) трансформируется к виду

г (хк+1) = 1/2]Г ^2,к ), 1=1

где R('kj) = (1 - к) + кЯ(к.). Таким образом, новые множители релаксации R(hi) принимают промежуточные значения между единицей и R(^i), что и требуется для обеспечения свойства релаксаци-онности, определяемого требованиями (7).

Введенное понятие функции релаксации позволяет с единых позиций оценить локальные свойства различных градиентных схем поиска. Удобство такого подхода заключается также в возможности использования наглядных геометрических представлений.

Для любого метода (2) можно построить функцию релаксации, характеризующую область его релаксационности в множестве собственных чисел. Требуемый характер функции релаксации представлен на рис. 1. Заштрихована запрещенная область, где условия релаксационности (7) не выполняются.

Очень важное свойство функций релаксации заключается в возможности использования соответствующих представлений для синтеза новых процедур из класса (2), обладающих некоторыми желательными свойствами при решении конкретных классов задач оптимизации.

Важный класс прикладных задач конечномерной оптимизации составляют плохо обусловленные

(жесткие) задачи [1]. Локальная характеристика (индекс) жесткости для некоторого функционала 3(х) в точке х задется выражением

П(x) = ^i(x)/

min k

Рис. 1. Области релаксационности градиентного метода

Здесь ki (x) - собственные числа невырожденной матрицы J''(x), удовлетворяющие по предположению неравенствам вида

При наличии указанного «разброса» собственных чисел в некоторой окрестности точки х возникают существенные вычислительные трудности при минимизации функционала J(x) в этой окрестности. Для вырожденных матриц J"(x) индекс жесткости полагается равным бесконечности. Легко видеть, что жесткие матрицы J"(x) (матрицы с высокими индексами жесткости) являются частным случаем матриц с большими спектральными числами обусловленности. Если высокий индекс жесткости для функционала J(x) сохраняется в некоторой области пространства поиска, то поверхности уровня функционала приобретают характерную «овражную» структуру, хорошо известную специалистам по компьютерной оптимизации. Обычно замедление сходимости поисковых методов оптимизации возникает в области, называемой «дном оврага» и аппроксимируемой подпространством, натянутом на собственные векторы, отвечающие «малым» собственным числам.

С помощью понятия ФР можно вполне наглядно (геометрически) оценить вычислительные возможности конкретной градиентной схемы при минимизации жестких функционалов.

Классические градиентные схемы

Рассмотрим некоторые конкретные методы (2) и отвечающие им функции релаксации.

Простой градиентный спуск (ПГС). Формула метода ПГС имеет вид

xk+1 = xk- hJ'

Соответствующая функция релаксации

R

линейна и представлена на рис. 2.

Пусть собственные значения матрицы Ak расположены в замкнутом интервале [m, M], причем 0 < m < M так, что n(x) = M/m >>1. В этом случае условие (9), очевидно, выполняется, а неравенства (7) сводятся к требованию R(ki )| < 1, / = 1, п или

Рис. 2. Функция релаксации метода простого градиентного спуска

|1 - hk\< 1,/ = \п.

Из неравенства

||xk+1 _ xk|| = 4 j (X/ / X1)2 < 4a_.......

-2I X

что может быть существенно меньше С>к.

В результате соответствующие малым собственным значениям из окрестности X = 0 слагаемые в выражении (8) почти не будут убывать, а продвижение будет сильно замедленным. Это и определяет низкую эффективность метода (12).

В области X < 0 функция (13) удовлетворяет условиям релаксации при любом значении параметра к. Параметр к в методе ПГС выбирается из условия монотонного убывания функционала на каждом шаге итерационного процесса. При отсутствии убывания величина к уменьшается до восстановления релаксационности процесса. Существуют различные стратегии выбора к, однако при больших п все эти методы, включая и метод наискорейшего спуска

хк+1 = а^ттЫ[/ - Ы'(/)], малоэффективны даже при минимизации сильно

выпуклых функционалов. Так же как и в методе покоординатного спуска, здесь возможна ситуация заклинивания, представленная на рис. 3.

Метод ПГС представляет определенный интерес как средство оценки локальной степени жесткости в окрестности точки замедления алгоритма. Выведем соответствующие соотношения.

Пусть замедление метода ПГС при минимизации некоторого функционала Ы(х) произошло в окрестности некоторой точки х0. Тогда можно предположить, что достаточно длинный отрезок последовательности {хк}, построенный из точки х0, будет оставаться в области ||х - х0|| < и для Ы(х) справедлива квадратичная аппроксимация:

Ах) = 1/2

Метод (12) для аппроксимации (15) примет

вид

xk+1 = xk- h(Axk - b) = Bxk + g,

где В = E - hA; g = hb .

Записывая (16) для двух последовательных номеров к и вычитая полученные равенства, приходим к соотношению

ук = хк + - хк = B(хк - хк-1) =

= Вк (х1 - х0) = Вку0.

Согласно степенному методу определения максимального собственного числа симметричной матрицы в результате проведения процесса (17) может быть получена оценка максимального собственного числа матрицы В:

Цук+1И|уЦ ^ тах X

Пусть шаг h в итерационном процессе (12) выбирается из условия релаксационности, тогда можно заключить, что h = 2/M. Пусть X (A)e[-m, M],

Рис. 3. Заклинивание метода простого градиентного спуска: J

M > m > 0. В результате имеем max |à.(8)| = 1 + mh. Следовательно, для достаточно больших k

„ 'К 'У„" =

= | J '( хк+1)||/| J '( хк ) = ц« 1 + mh.

Приходим к требуемой оценке степени овраж-ности функционала J(x) в окрестности точки х0:

п(х0) = M/m = 2/(цк - 1).

Рассуждая аналогично, для случая à.(A)e[m, M] получаем вместо (19) равенство

« 1 - mh <1 и соответствующую оценку п(х0) « 2/(1 - цк). Общая оценка может быть записана в виде п(х°) « 2/ |1 - цк|, причем, сравнивая цк с единицей, можно установить характер выпуклости /х) в окрестности точки х°, что дает дополнительную полезную информацию.

Метод Ньютона основан на построении квадратичной аппроксимации функционала /х) в окрестности текущей точки хк:

/х) = /х) = /(хк) + <х - хк, /'(хк)> +

+ 1/2 {Г(хк) (х - хк), х - хк>.

В качестве хк+1 выбирается точка, удовлетворяющая уравнению /'(х) = 0. В результате приходим к формуле

хк+1 = хк - hkAkl /'

С помощью дополнительно введенного параметра hk, как указывалось ранее, осуществляется регулировка нормы вектора продвижения ||хк+1 - хк||.

Таким образом, по построению метод Ньютона является оптимальным для квадратичных функционалов при условии положительной определенности матрицы Ak. Минимум сильно выпуклого квадратичного функционала находится за один шаг при hk = 1.

Главный недостаток метода заключается в следующем. Если функционал /х) не является выпуклым в окрестности точки хк, то это может послужить причиной расходимости. Действительно, допустим, что функционал /х) аппроксимируется невыпуклым квадратичным функционалом. В этом случае ньютоновское направление рк = A-J'(хк) указывает на точку х', удовлетворяющую условию / ' (х ' ) = 0. Такой точкой может оказаться, например, седловая точка, а не точка минимума, как в выпуклой ситуации. В результате направление р будет указывать «наверх», а не «вниз» (рис. 4).

Рис. 4. Расходимость метода Ньютона

Заметим, что полная потеря работоспособности алгоритма Ньютона в невыпуклых экстремальных задачах происходит независимо от наличия или отсутствия овражной ситуации. Такая особенность методов ньютоновского типа существенно ограничивает область их практического применения, т. к. уже простейшие задачи оптимизации могут приводить к невыпуклым критериям.

На языке функций релаксации это обстоятельство проявляется в попадании графика функции релаксации метода

R(x) = 1 - И(х, к)Х = 1 - кк

в запрещенную область, где не выполняются неравенства (7). Действительно, при кк = 1, что соответствует классическому варианту метода Ньютона без регулировки шага, имеем R(x) = 0 при ух ф 0. И аналогично при любых значениях кк прямая релаксации 1 - кк параллельна оси абсцисс и захватывает запрещенную область либо при x > 0, либо при x < 0. Положение ее при к = 0 соответствует остановке процесса. В указанных условиях эффективный выбор кк оказывается затруднительным.

Аналогичным недостатком обладают многие из аппроксимирующих метод Ньютона квазиньютоновских алгоритмов и совпадающих с ними при минимизации квадратичных функционалов методов сопряженных направлений. Все эти методы по эффективности приближаются к методу ПГС, если функционал 3(х) в окрестности хк не является выпуклым.

Традиционное возражение против метода Ньютона, связанное с необходимостью выполнения операции вычисления вторых производных целевого функционала, для реальных задач оптимизации оказывается менее существенным.

Рис. 5. Функция релаксации ЛМ-метода

Метод Левенберга-Маркуардта

Я

удовлетворяющую требованиям (7) при УХ е [-т, М], если к' > т.

Соответствующий метод предложен Левен-бергом и имеет функцию Н (X, к) = [1 - ^(Х)] / X = = (к' + X)-1.

Схема метода (2) с указанной функцией Н имеет вид

хк+1 = хк - [к'Е + 3'

Скаляр к' на каждом шаге итерационного процесса подбирается так, чтобы матрица к'Е + + Ы'(хк) была положительно определена и чтобы ||хк+1 - хк || < ск, где ск может меняться от итерации к итерации.

Из последнего выражения следует, что мы имеем регуляризованную форму метода Ньютона с параметром регуляризации к'. Данная форма метода Ньютона применялась Левенбергом для решения задач метода наименьших квадратов. Существенно позже данный метод применялся Маркуардтом для решения общих задач нелинейной оптимизации и иногда встречается его описание в литературе под названием «метод Марку -ардта».

Реализация метода (22) сводится к решению на каждом шаге линейной алгебраической системы:

[ к' Е + 3"

= - 3'(хк )(Дхк = хк+1 - хк).

Главный недостаток метода легко увидеть на

графике ФР. Он заключается в необходимости точного подбора параметра к', что сопряжено с известными вычислительными трудностями. Значение т, как правило, неизвестно и не может быть вычислено с приемлемой точностью. При этом оценка для т существенно ухудшается при возрастании размерности п. Лучшее, что обычно можно сделать на практике, это принять

к' > шах{8мП3к 1|,|тпX,Ы и)|}.

Правая часть неравенства (24) обусловлена тем, что абсолютная погрешность представления любого собственного числа матрицы 3''к ввиду ограниченности разрядной сетки равна

^ ^ пХ18М ~ пЫ"^м.

При невыполнении условия к > т система (23) может оказаться вырожденной. Кроме этого, слева от точки X = -к' функция релаксации быстро входит в запрещенную область и метод может стать расходящимся. Попытки использования алгоритмического способа более точной локализации к' приводят к необходимости многократного решения плохо обусловленной линейной системы (23) с различными пробными значениями к'.

Число обусловленности матрицы к'Е + 3"(хк) может превышать спектральное число со^[3''(хк)]. Действительно, потребуем, например, чтобы Я(-т) = 10 для обеспечения заданной скорости убывания 3(х). Определим необходимое значение параметра к'. Имеем 1/(1-кт) = 10 или к' = 1/к = т/0,9. В этом случае ХтП(к'Е + 3''к) = = -т + т/0,9 = т/9 > 0. Принимая А™ах(к'Е + 3"к) ~ ~ Хтах(3'"), получаем, что со^(к'Е + 3'") ~ ~ 9 (3'")/\\ . (3'").

тах ^ к' 1 тт^ к

При выборе заведомо больших значений к', что реализуется, например, когда определяющим в (24) является первое выражение в скобках, имеем т << к' и \^(-т)\ ~ 1, что приводит к медленной сходимости. Ограничение к' снизу не позволяет также уменьшить до желаемого значения множитель релаксации для X > 0.

Эти трудности возрастают при аппроксимации производных конечными разностями, т. к. при малых значениях 3'(х") для точек хк, расположенных на дне оврага, приходим к необходимости получать компоненты вектора градиента как малые разности относительно больших величин порядка 3(х"). В результате компоненты вектора Ахк будут находиться с большими относительными погрешностями порядка п(хк)|ем 3(хк)\ / \\3'(хк)\\.

Индекс овражности п в этом случае играет роль своеобразного коэффициента усиления погрешности. Для метода Ньютона справедливо аналогичное замечание. В то же время для метода ПГС точность задания J'(xk) может оказаться достаточной для правильного указания направления убывания J(x).

Несмотря на отмеченные недостатки, метод (23) часто оказывается достаточно эффективным и его присутствие в библиотеке методов оптими-

зации следует признать весьма желательным.

Аппарат функций релаксации позволяет производить полный анализ любой матричной градиентной схемы компьютерной оптимизации. Аналитическая связь между ФР и матричным множителем в градиентном методе позволяет по заданной ФР строить соответствующий метод оптимизации с заданными релаксационными свойствами. По существу предложен «генератор» новых методов градиентного типа.

СПИСОК ЛИТЕРАТУРЫ

1. Черноруцкий, И.Г. Методы оптимизации. Компьютерные технологии [Текст] / И.Г. Черноруцкий. -СПб.: БХВ - Петербург, 2011. -384 с.

2. Гилл, Ф. Практическая оптимизация [Текст] / Ф. Гилл, У Мюррей, М. Райт. -М.: Мир, 1985. - 509 с.

УДК 510.67

В.Г. Бурлов, Е.А. Зенина, А.В. Матвеев

СИНТЕЗ МОДЕЛИ И СПОСОБОВ ФУНКЦИОНИРОВАНИЯ СИСТЕМЫ

В УСЛОВИЯХ КОНФЛИКТА

При моделировании сложных систем необходимо учитывать, что объекты различной физической природы функционируют в какой-то среде или вступают с другими объектами в определенные отношения [1]. Поэтому в ходе моделирования требуется учитывать, что в исследуемом процессе принимают участие как минимум две стороны (А, В). Их взаимодействие рассматривается как конфликт с несовпадающими, в общем случае, интересами. Конфликт возникает при столкновении интересов, при желании сторон занять несовместимые позиции и т. п.

В целом проблема конфликта имеет богатую литературу и немалые научные традиции. В монографии [2] рассмотрены вопросы построения математических моделей трудно формализуемых конфликтных ситуаций, не относящихся к стандартной теории игр и статистических решений. Определяются цели и задачи урегулирования конфликтов, исследуются пути стабилизации и равновесия в условиях неполной информации. Приводятся некоторые математические модели оценивания взаимного контроля конфликтующих сторон. Формализуются процедуры формирования соглашений в конфликтных ситуациях.

В [3] конфликт рассмотрен как способ взаимодействия сложных систем. Формируются математические структуры и функциональные пространства описания конфликтов, учитывающие многомерность и разномерность процессов, их нелинейность, большое число степеней свободы, память и взаимную рефлексию конфликтующих сторон. Разработана математическая модель конфликта и исследованы ее свойства.

В ряде работ конфликт исследовался на основе математической теории игр, отыскивался путь к достижению «оптимального» решения [4]. Конечно, методы решения задач теории игр обладают значительными возможностями для количественного оценивания результатов разрешения конфликтов. Это широкий спектр методов решения задач матричных игр [5], методов решения непрерывных игр [6], методов решения позиционных игр [7].

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