в. Приложение в. МЕТОД КОПЕЧПО-СХОДЯЩИХ- СЯ АЛГОРИТМОВ РЕШЕНИЯ РЕКУРРЕНТНЫХ ЦЕЛЕВЫХ НЕРАВЕНСТВ

В 1966 г. В.А. Якубовичем было предложено приводить задачи распознавания образов и адаптации к задаче решения бесконечной системы рекуррентных целевых неравенств. Следуя [103], сформулируем ее в обш;ем виде.

Пусть {0} - некоторое евклидово пространство, элементы которого - векторы Ѳ G {0} называются векторами подстраиваемых параметров. Рассмотрим функции ф^(Ѳ,Ѳ^~^) G TZ,

G TZ, где к = 0,1,2,... - дискретное время, а через  обозначены последовательности векторов  =

0[О], 0[1], .. . , Ѳ[к — 1] . (Для краткости записи далее аргументы у функций ф{-), ф{-) опускаются).

Пусть имеются условные неравенства

и безусловные неравенства

В задачах управления неравенства (В.1) порождаются целью управления (отсюда и название метода), а неравенства (В.2)

- ограничениями.

Положим также, что имеются множество {0}° начальных значений вектора 0[О] подстраиваемых параметров и правило

сопоставляюш;ее набору и наборам функций

значение Ѳ[к + 1]. Тогда при заданных начальных условиях последовательно определяются Ѳ[к],ф^{Ѳ),фі;{Ѳ) к = 0,1,2, .. . . Заметим, что неравенства (В.1), (В.2) заранее не заданы (при всех к), а появляются на каждом шаге после вычисления Ѳ[к + 1] по (В.З). Поэтому они называются рекуррентными неравенствами.

Определение 1. [103] Правило (В.З) называется конечно- -сходящимся алгоритмом (КСА) решения рекуррентных неравенств (В.1) - условных и (В.2) - безусловных, если

а)   для всех к выполнено (В.2) при Ѳ = Ѳ[к]

б)   существует такой момент времени А;*, что для всех к > к^, выполняются неравенства (В.1) и векторы Ѳ[к] устанавливаются: Ѳ[к^,] = Ѳ[к^, -Ь 1] = Ѳ[к^, -Ь 2] = ... .

Если указанное свойство выполнено, но векторы Ѳ[к], возможно, не устанавливаются, то (В.З) называется конечнорешающим алгоритмом.

Число моментов времени г, для которых при Ѳ = Ѳ[к] не выполняется (В.1), называется числом ошибок (коррекций) алгоритма. □

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

1. Алгоритм ”Полоска-1”

Рассмотрим следующую систему условных рекуррентных неравенств в евклидовом пространстве {0}:

Здесь а[к] G TZ, е[к] G TZ, через {f,9) обозначено скалярное произведение векторов f, Ѳ (для конечномерного пространства можно записать {f[k],9) = f[k] Ѳ).

Для каждого (фиксированного) к неравенство (В.5) определяет полосу между двумя параллельными плоскостями в пространстве {0}.

Предположим, что:

1.   Существует такое е > О, что для любого А; > О выполнено

2.   Существуют вектор 0* и число /О, /О G [0,1) такие, что для всех А; > О выполнено неравенство

Эти условия означают, что ширина полос не меньше 2е и что все полосы (В.5) содержат некоторый шар с центром в точке 0*.

Имеется следующее утверждение [103].

Ири выполнении условий 1, 2 для произвольного к > min(l,2/o) и любого 0[О] алгоритм

где

является конечно-сходящимся алгоритмом решения безусловных неравенств (В.5).

Если положить к = оо, то второй случай будет всегда отсутствовать и алгоритм (В.8) принимает вид

Если р < 0.5, то можно взять к < 1; тогда алгоритм (В.8) имеет вид

Можно также использовать алгоритм, имеющий некоторый свободный параметр шага (усиления) р[к], О < р' < ji[k\ < р" < 2:

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

2. Алгоритм ”Полоска-2”

Рассмотрим условные рекуррентные неравенства вида

с некоторыми j3[k] G TZ, которые считаются неизвестными (в задаче адаптивного управления - зависящими от неизвестных параметров).

Предполагается, следующее.

1.   Существуют такие числа > О, е > О, что

2.   Существует такие вектор 0* G {0} и число /О, /О G [0,1), что при Ѳ = Ѳ^, рекуррентные неравенства (В.13) выполнены ”с запасом”, т.е.

Конечно-сходящийся алгоритм решения рекуррентных неравенств (В.13) имеет вид [103]

где:

а для jj', jj", jj[k] выполнено О < < р[к] < р" < 2(1 — р)Ср^.

Условия (В.6) или (В.14) в ряде задач могут и не выполняться. Это означает, что ширина полосок (В.5) или (В.13) может быть сколь угодно малой. Конечная сходимость алгоритмов в этом случае может нарушаться. Тем не менее эти алгоритмы будут конечно-решающими, а именно - справедливы следующие утверждения [103].

1. Пусть выполнено условие (В.7) и величина 5[А;] определена соотношением (В.9). Тогда для любого 0[О] любой из алгоритмов (В.8) (где к > тіп(1,2/о)), (В.10), (В.11) (при р < 0.5), (В.12) (где О < р' < р[к] < р" < 2) является конечнорешающим алгоритмом для неравенств

2. Пусть выполнено условие (В.15) и величины ѵ[к\, 5[А;] определены соотношениями (В.17). Тогда алгоритм (В.16) является конечно-решаюш;им алгоритмом для неравенств

где

3. Алгоритмы решения рекуррентных линейных неравенств Рассмотрим линейные условные неравенства

Пусть суш;ествует вектор 0*, для которого неравенства (В.20) выполнены ”в усиленном смысле”:

Тогда для любого 0[О] алгоритм

является конечно-сходяш;имся алгоритмом решения (В.20) [103]. Рассмотрим теперь условные неравенства

Пусть неравенства (В.23) выполнены ”в усиленном смысле”: суш;ествует вектор 0*, для которого

Тогда при |а[А;]| < Са, р[к] > О, р[к] —>■ О при к ^ оо, р[к] = оо, О < /3[/г] < 2 для любого 0[О] и г[0] алгоритм

является конечно-сходяш;имся алгоритмом решения (В.23) [103].

4. Алгоритм решения рекуррентных неравенств для обш;его

случая

Рассмотрим теперь более обш;ий случай, когда условные неравенства определяют (произвольные) выпуклые множества, а именно - пусть выполнены следуюш;ие условия:

1.   Функция ф{Ѳ) в (В.1) дифференцируема по векторному параметру Ѳ и

Сф не зависит от к, Ѳ.

2.   Суш;ествуют вектор 0* G {0} и число е* > О такие, что \/к при 0 = 0* имеет место

3.   \/к функция фк{Ѳ) вогнута по параметру 0. ^

4.   Числа р[к] удовлетворяют условиям:

Тогда для любого 0[О] и при г[0] = О алгоритм

является конечно-сходяш;имся алгоритмом решения условных рекуррентных неравенств (В.1) [103].

Значения р[к] можно вычислять, например, по формуле

где постоянные

Пусть наряду с условными (В.1) заданы также безусловные неравенства (В.2), которые определяют выпуклые множества Т>[к] С {0}, 0* G Т7[к] для всех к) и определена операция

проектирования Pv[k] на эти множества. ^ Тогда сунерно- зиция операции Рѵ[к] и алгоритма (В.24) является конечнорешающим алгоритмом для (В.1), (В.2), а если Ѵ[к\ = V, то данный алгоритм будет конечно-сходящимся.

Перечисленные алгоритмы и сформулированные условия их работоспособности могут применяться для решения самых разнообразных прикладных задач (см. п.п. 12.5, 13.4, а также примеры в [36, 103, 106]).