Алгоритм построения последовательности

1. Выбирается начальная точка . Общего правила выбора начальной точки не имеется.

2. Вычисляется градиент функционала . Методы вычисления градиента функционала приведены в главе 3.

3. Следующее приближение определяется так: . В общем случае

, (2) где – шаг градиентного метода.

4. Существуют различные способы выбора величины . Ниже приведены некоторые из них:

а) в методе скорейшего спуска число выбирается из условия

; (3)

б) можно принять – заданная величина, так, чтобы выполнялось неравенство . Если данное неравенство не выполняется, то дробят число до тех пор, пока не выполнится данное неравенство (например, и т.д.);

в) если функционал , то величину можно выбрать из условий , где – постоянная Липшица из неравенства ;

г) можно задать последовательность по алгоритму .

(например, ). Необходимо проверять неравенства .

Теорема 1. Пусть функционал определен в гильбертовом пространстве H, принадлежит классу , ограничен снизу, т.е. . Пусть последовательность построена по алгоритму (2), (3). Тогда:

1) числовая последовательность строго убывает;

2) .

Доказательство. Из (3) следует, что . Тогда имеет место неравенство . Отсюда, с учетом того, что , имеем

. (4)

Поскольку , то, согласно лемме 4 (лекция 2), выполняется неравенство

.

Следовательно,

.

Из правого неравенства следует, что

.

Отсюда при имеем

. (5)

Теперь неравенство (4) с учетом соотношения (5) запишется в виде

. (6)

Из (6) следует, что

, (7) где максимум достигается при . Если для некоторого конечного n градиент , то и , так что . Представляет интерес случай, когда для конечного n. Поскольку величина, то из (7) следует, что числовая последовательность строго убывает (). Так как функционал ограничен снизу, то числовая последовательность ограничена снизу. Следовательно, существует предел , а из существования предела следует, что . Переходя к пределу при из (9), имеем .Теорема доказана.

Теорема 2. Пусть выполнены условия теоремы 1, и пусть, кроме того:

1) функционал выпуклый на H;

2) множество ограничено.

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

, (8) где – диаметр множества .

Доказательство. Покажем, что множество слабо бикомпактно. Поскольку выпуклый функционал, то для любых и при всех . Следовательно, точка . Это означает, что множество выпукло.

Пусть – предельная точка множества . Тогда существует последовательность такая, что при . Так как , то . Тогда в силу того, что непрерывен в H, имеем , т.е. точка . Таким образом, – ограниченное выпуклое замкнутое множество в банаховом пространстве H. Тогда согласно теореме 6 (лекция 10) множество слабо бикомпактно.

Выпуклый функционал слабо полунепрерывен снизу на и достигает нижней грани на множестве . Так как , то последовательность , построенная по алгоритму (2), (3), принадлежит множеству .

Покажем, что последовательность из (2), (3) является минимизирующей, т.е. , где по доказанному выше. В самом деле, так как – выпуклый функционал, то согласно теореме 3 (лекция 6) выполняется неравенство . Тогда , . Отсюда, в частности, при получим

, (9) где – диаметр множества . Переходя к пределу при из (9), с учетом того, что при , имеем

.

Тогда . Следовательно, последовательность минимизирующая.

Поскольку , , множество слабо бикомпактно, то последовательность слабо сходится к множеству .

Пусть . Тогда неравенства (7), (9) запишутся так

. (10)

Отсюда следует, что последовательностьудовлетворяет условиям: . Верна следующая лемма: если числовая последовательность такая, что при всех , то справедливо неравенство .

Применяя данную лемму, из (10) получим ()

.

Итак, доказана оценка (8). Теорема доказана.

Теорема 3. Пусть выполнены условия теоремы 1, и пусть, кроме того, сильно выпуклый функционал на H. Тогда:

1) последовательность сходится к единственной точке ;

2) справедливы следующие оценки скорости сходимости

, (11)

, (12) где – постоянная сильной выпуклости, .

Доказательство. Свойства сильно выпуклых функционалов приведены в лекции 7. Как следует из теоремы 4 (лекция 7), множество – выпукло, ограничено и замкнуто, где . Множество слабо бикомпактно и остаются верными все утверждения теоремы 2. Так как сильно выпуклый функционал является строго выпуклым, то согласно теореме о глобальном минимуме (лекция 8) множество содержит единственную точку .

Как следует из теоремы 1 (лекция 7), верно неравенство

.

Тогда

.

Отсюда при имеем

–,

где . Таким образом, величина

. (13)

Как было доказано выше, верно неравенство (см. (10))

. (14)

Из (13), (14) следует, что последовательность удовлетворяет условиям

. (15)

Как следует из теоремы 2 (лекция 7), верно неравенство

, . (16)

Так как , то

(17)

Из (16), (17) следует, что . Тогда . Из (15) имеем

.

Отсюда имеем

.

Следовательно, . Оценка (11) доказана.

Из теоремы 4 (лекция 7) следует, что

.

Отсюда при , получим

Тогда .

Теорема доказана.

Пример 1. Рассмотрим задачу оптимального управления (1) – (3) из лекции 11, когда :

, (18)

, (19)

. (20)

Как показано в лекциях 11, 12, если выполнены условия теоремы 1 (лекция 11) и теоремы 1 (лекция 12), то функционал , причем

,

где – решение дифференциального уравнения

.

Последовательность определяется по формуле

, где – решение дифференциального уравнения

,

а функция – решение сопряженной системы

,

.

Величины определяются из условия

.

Для задачи оптимального управления (18) – (20) применима теорема 1. Следовательно, значение функционала (18) при условиях (19), (20) строго убывает и

.

ЛЕКЦИЯ 17. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА

Рассмотрим оптимизационную задачу

, (1) где U – выпуклое замкнутое множество гильбертова пространства H, .

Алгоритм построения последовательности. 1. Выбирается начальная точка . 2. Вычислим градиент функционала . 3. Определяется точка . 4. Находим проекцию точки на множестве U. В результате находим следующее приближение . В общем случае

, (2) где число выбирается из условия .

5. Существуют различные способы выбора . В частности:

а) если , то может быть выбрано из условий

. (3)

В случае имеем .

б) определяется из условия .

в) .

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

1) , т.е. ;

2) , т.е. функционал ограничен снизу;

3) последовательность определяется по формулам (2), (3). Тогда:

1. ; (4)

2. . (5)

Доказательство. Поскольку точка является проекцией на множество, то согласно теореме 6 (лекция 8) имеем

. (6)

Отсюда получим

. (7)

Согласно лемме 4 (лекция 2) справедливо неравенство

. (8)

Из соотношений (7), (8) с учетом неравенства (3) имеем

, (9)

,

где . Из неравенства (9) следует, что числовая последовательность строго убывает, из-за ограниченности снизу значения функционала она сходится. Следовательно, при . Тогда из (9), переходя к пределу при , имеем при . Теорема доказана.

Теорема 2. Пусть выполнены условия теоремы 1, и пусть, кроме того, – выпуклый функционал, множество ограничено.

Тогда:

1) последовательность является минимизирующей ;

2) последовательность слабо сходится к множеству ;

3) справедлива следующая оценка скорости сходимости

. (10)

Доказательство. Как и в доказательстве теоремы градиентного метода, можно показать, что: 1) – ограниченное выпуклое замкнутое множество; 2) функционал достигает нижней грани на множестве ; 3) последовательность .

Покажем, что последовательность минимизирующая. Поскольку – выпуклый функционал, то

.

Отсюда при получим

. (11)

Как следует из соотношения (7), справедливо неравенство (при )

. (12)

Тогда из (11), (12) следует, что

.

Отсюда с учетом того, что

,

где D – диаметр множества , получим

. (13)

Так как по доказанному выше (см. (5)) при , то из (13) следует, что . Это означает, что последовательность является минимизирующей.

Заметим, что слабо бикомпактное множество, , следовательно, все слабо предельные точки принадлежат множеству .

Из неравенств (9), (13) следует, что

.

Отсюда, в силу леммы о числовой последовательности , получим оценку (10), где . Теорема доказана.

Теорема 3. Пусть выполнены условия теоремы 1, и пусть, кроме того, – сильно выпуклый функционал на U. Тогда последовательность сходится к единственной точке минимума , верна оценка

. (14)

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

Как следует из теоремы 4 (лекция 7), верно неравенство

.

Тогда . Следовательно, верна оценка (14). Теорема доказана.

Пример 1. Рассмотрим задачу оптимального управления

, (15)

, (16)

, (17) где – заданные непрерывные функции (см. (1) – (3), лекция 11). Построим последовательность для задачи (15) – (17). Полагаем, что выполнены условия теоремы 1 (лекция 11) и теоремы 1 (лекция 12). Как показано в лекции 17, функционал и в любой точке градиент

, (18)

. (19)

Согласно формуле (2), последовательность определяется так

, где – i-я компонента вектора. (20)

Пример 2. Рассмотрим задачу оптимального управления для линейных систем (см. лекцию 13)

, (21)

, (22)

. (23)

Градиент функционала в любой точке определяется по формуле (см. лекцию 12, формулы (24), (25))

, (24)

. (25)

Последовательность определяется по формуле (20), где градиент вычисляется по алгоритму (24), (25).

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

Пример 3. Рассмотрим задачу оптимального управления (1) – (4) (лекция 14)

, (26)

, (27)

, (28)

. (29)

Градиент функционала . Тогда последовательность строится по алгоритму

,

.

Согласно результатам лекции 8 (проекция точки на множество) имеем

(30)

(31)

Для задачи (26) – (29) последовательности (30) – (31) являются минимизирующими.

Пример 4. Рассмотрим задачу оптимального управления (1) – (5) (лекция 15)

(32)

, (33)

, (34)

, (35)

. (36)

Градиент функционала (32) при условиях (33) – (36) определяется по формуле . Последовательность строится по алгоритму

,

.

Тогда

(37)

(38)

Для задачи (32) – (36) последовательности (37), (38) являются минимизирующими.

ЛЕКЦИЯ 18. МЕТОД УСЛОВНОГО ГРАДИЕНТА

Рассмотрим оптимизационную задачу

, (1) где U – выпуклое замкнутое ограниченное множество из гильбертова пространства H.

Алгоритм построения последовательности. 1. Выбирается начальная точка . 2. Вычисляется градиент функционала . 3. Определяется вспомогательная точка как решение оптимизационной задачи

.

4. Следующее приближение . Поскольку U – выпуклое множество, то . В общем случае

, (2) где – решение оптимизационной задачи

. (3)

Поскольку множество U слабо бикомпактно, – слабо полунепрерывен снизу на U, то точка существует (см. лекцию 10).

5. Существуют различные способы выбора . В частности:

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

; (4)

б) выбрать и проверить выполнение условия . Если данное условие не выполняется, то необходимо дробить до тех пор, пока не выполняется данное неравенство;

в) если , то

,

– параметры метода. В частности, .

Теорема 1. Пусть функционал определен на выпуклом ограниченном замкнутом множестве U из гильбертова пространства H, и пусть, кроме того:

1) , т.е. ;

2) последовательность определяется соотношениями (2) – (4).

Тогда

. (5)

Доказательство. Покажем, что функционал ограничен на множестве U. В самом деле, из включения следует, что (см. лемма 4, лекция 2)

. (6)

Отсюда имеем

.

В частности, при получим

,

где – ограниченное множество. Отсюда следует, что , т.е. функционал ограничен снизу на U.

Из (3) следует, что значение . Тогда . Так как , то выполняется неравенство

. (7)

Поскольку величина выбирается из условия (4), то . Отсюда следует, что . Тогда

. (8)

Из (6) имеем

.

Тогда

. (9)

Из (8) и (9) при получим

, (10) где в силу неравенства (7), D – диаметр множества U. Заметим, что если , то выполнено неравенство (5) и теорема доказана. Интерес представляет случай, когда . Так как , то из неравенства следует, что . Значит, числовая последовательность не возрастает. Тогда из ограниченности снизу значения функционала, т.е. , следует, что числовая последовательность сходится. Следовательно, при .

Теперь, переходя к пределу при , из (10) имеем

.

Отсюда при получим

.

Следовательно, , т.е. верно соотношение (5). Теорема доказана.

Теорема 2. Пусть выполнены условия теоремы 1, и пусть, кроме того, выпуклый функционал. Тогда:

1) последовательность является минимизирующей, т.е. ;

2) последовательность слабо сходится к множеству ;

3) справедлива следующая оценка скорости сходимости

. (11)

Доказательство. Поскольку U – слабо бикомпактное множество и выпуклый функционал слабо полунепрерывен снизу, то множество .

Покажем, что последовательность минимизирующая. В этом случае, как в доказательстве предыдущих теорем, справедливо неравенство

,

где . Отсюда, в силу того, что

,

получим

. (12)

Отсюда, в силу доказанного при , имеем . Это означает, что последовательность минимизирующая.

Так как множество U слабо бикомпактно, , то минимизирующая последовательность слабо сходится к .

Покажем справедливость оценки (11). Поскольку , то найдется номер такой, что при всех . Как следует из (10),

. (13)

Заметим, что

,

где при . Тогда неравенство (13) запишется так

. (14)

Из (12), (14) получим

. (15)

Далее, применяя лемму о числовой последовательности (см. лекцию 16), из (15) получим

.

Отсюда следует оценка (11). Теорема доказана.

Теорема 3. Пусть выполнены условия теоремы 1, и пусть, кроме того, – сильно выпуклый функционал на U. Тогда:

1)последовательность сходится к единственной точке минимума ;

2) справедлива следующая оценка скорости сходимости

. (16)

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

В лекции 7 было доказано, что для сильно выпуклого функционала верно неравенство

.

Отсюда при имеем

. (17)

Из утверждения теоремы 2 следует, что . Тогда из (17) получим

.

Отсюда следует оценка (16), где . Теорема доказана.

Пример 1. Рассмотрим задачу оптимального управления

, (18)

, (19)

. (20)

Покажем алгоритм решения задачи (18) – (20) методом условного градиента. Заметим, что U – выпуклое ограниченное замкнутое множество из гильбертова пространства , градиент функционала в точке равен

,(21)

, (22)

, (23)

. (24)

По формулам (21) – (24) можно найти градиент функционала . Итак, – известная функция.

Функцию находим из решения задачи оптимального управления

, (25)

, (26) где – известные функции, – известное число, минимизируется линейный функционал

. (27)

Из (25) – (27) следует, что компоненты вектор функции определяются следующим образом

Функция

.

Величину находим из условия . Следующее приближение . Аналогичным путем может быть построена последовательность для линейной системы.

Пример 2. Рассмотрим задачу оптимального управления

, (28)

, (29)

, (30)

. (31)

Для задачи (28) – (31) последовательность строится по следующему алгоритму, где U – выпуклое ограниченное замкнутое множество из , градиент функционала

, (32)

, (33)

, (34)

, (35)

, (36)

. (37)

По формулам (32) – (37) можно найти градиент функционала . Функцию находим из решения задачи оптимального управления

. (38)

Решением задачи (38) является

(39)

. (40)

Величина определяется из условия , где

. (41)

Из (39) – (41) следует, что , .

Последовательность является минимизирующей в силу того, что функционал выпуклый.

ЛЕКЦИЯ 19. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ. МЕТОД НЬЮТОНА

Метод сопряженных направлений. Рассмотрим оптимизационную задачу

, (1) где H – гильбертово пространство, .

Алгоритм построения последовательности. 1. Выбирается начальная точка . 2. Вычислим градиент функционала . 3. Строится последовательность по правилу

, (2) где

. (3)

4. Числовые последовательности выбираются следующим образом:

, (4)

. (5)

Теорема 1. Пусть функционал определен на гильбертовом пространстве H, принадлежит классу и сильно выпуклый на H, последовательность определяется по правилу (2) – (5). Тогда:

1) последовательность сходится к точке ;

2) справедливы следующие оценки скорости сходимости

, (6)

, (7) где – постоянная Липшица для , т.е. – коэффициент сильной выпуклости.

Доказательство. Поскольку – сильно выпуклый функционал, то существует единственная точка , где . Заметим, что функция – сильно выпукла по и – определяется однозначно. Полагаем, что .

Из условия (5) следует, что . Так как , то

. (8)

Можно показать, что

. (9)

В самом деле, при имеем , поэтому . Из (5) при следует, что . Таким образом, равенства (9) при верны. Докажем равенства (9) методом математической индукции. Пусть при верны равенства . Тогда Равенства (9) доказаны.

Из (8), (9), имеем

. (10)

Так как функционал сильно выпуклый, то (см. лекцию 7)

.

Отсюда при имеем

.

Тогда с учетом того, что , получим

.

Отсюда с учетом равенства (9) имеем

. (11)

Из (4) следует, что

в силу неравенства (11). Отсюда имеем

. (12)

Так как , то

, (13) в силу равенств (9). Из (12) и (13) следует, что

. (14)

Докажем оценки (6), (7). Из (10), (14) следует, что

,

где .

Тогда

, (15) где . Как следует из теоремы 1 (лекция 7),

.

Тогда

.

Отсюда при имеем

.

Следовательно,

. (16)

Из (15), (16) следует, что

, (17) где .

Из (17) следует, что

.

Следовательно, , т.е. верна оценка (6). Из теоремы 4 (лекция 7) следует, что

.

Отсюда при