Метод проекции градиента

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

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

Известный метод проекции градиента служит для поиска экстремума функции на области, заданной системой аффинных равенств или неравенств. В статье дается расширение алгоритма для решения задачи поиска минимума выпуклой, Липшиц-непрерывно дифференцируемой функции на области, заданной нелинейными ограничениями специального вида. Приведен итеративный алгоритм поиска минимума, доказана сходимость алгоритма в подпоследовательности к точке глобального минимума на допустимой области.

Утверждение 1

Пусть дифференцируемая по Липшицу с константой L функция; и Тогда:

1. 
2. Если для t>0 справедливо , то имеет место оценка

Доказательство

1. Из дифференцируемости следует:
   .
   Так как и , то существует , такой что
   , а следовательно
   
   
2. Мы имеем . Учитывая Липшиц-дифференцируемость , получаем :
   
   
   
   
   

Утверждение 2

Пусть дифференцируемая по Липшицу с константой L функция; ; и Тогда:

1. 
2. Если для t>0 выполняется , то справедливо

Доказательство

1. Из утверждения 1 следует, что для достаточно малых t справедливо
   , а следовательно , т.е.
   (*)      для достаточно малых t.
2. Пусть . Учитывая Липшиц-дифференцируемость , получаем :
   
   
   
   
   

Утверждение 3

Пусть дифференцируемая по Липшицу с константой L функция; ; . Тогда:

1. 
2. Если для t>0 справедливо , то имеет место оценка .

Доказательство

1. Из непрерывности ф-ции и отрицательности ее значения в точке x следует существование окрестности точки x, где значения ф-ции остаются отрицательными, т.е. .
2. Пусть . Случай исключен, так как , таким образом . Учитывая Липшиц-дифференцируемость , получаем:
   
   
   
   (**)     
   Уравнение
   (***)      , решаемое относительно t с учетом , имеет два действительных корня:
   , среди которых только один положительный: . Учитывая положительность коэффициента перед второй степенью t, наличие двух действительных и только одного положительного корня уравнения (**), приходим к выводу, что положительное решение неравенства (**) должно быть больше корня уравнения (***) , т.е.
   
   

Утверждение 4

Пусть - матрица ; Ran(A) = m, т.е. строки A линейно независимы, тогда матрица инвертируема.

Доказательство

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



. Так как вектора линейно независимы, то получаем, что , т.е. - инъективна, из чего вследствии квадратности следует биективность, то есть инвертируемость.

Обозначения

1. Пусть - матрица ; . Обозначим - матрица состоящая из соответствующих индексам из I столбцов матрицы A.
2. Если строки линейно независимы, то по утверждению 4 матрица инвертируема и можно определить

Утверждение 5

Пусть - матрица ; ; . Тогда справедливо:

1. , т.е.
2. 
3. 
4. 

Доказательство

Обозначения

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

Утверждение 6

Пусть , -матрица градиентов -активных ограничений в точке x, т.е. , - проекция градиента функции f в точке x на ядро A(x), т.е. .
Если , то существует и , такое что:

1. ,
2. 
3. 
4. , где >0, константы, а

Доказательство

Итак, определим направление: , где .
, так как .
Определим

(1)

(2)

Из утверждения 5 следует, что

(3)

и, таким образом
Из определения (1) следует, что , если и в любом случае, поэтому
, т.е.

(4)

Далее,

.
Из чего следует, что и ортогональны, а следовательно,

Т.е.

(5)

С другой, стороны, так как , то

(6)

Из (4), (5) и (6) следует, что пункт 1. утверждения 6 доказан.

(7)

(8)

(9)

• Эти условия выполняются для первоначального значения
• Для эти условия не выполняются, но выполняются для максимального , полученного путем последовательного делением единицы на два. В этом случае для хотя бы одно из условий (7), (8) или (9) не выполняются. Из вторых частей утверждений 1, 2 и 3 следует, что для шага должно выполняться одно из неравенств:

  (10)

  (11)

  (12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(пункт 2. утверждения 6)

(пункт 3. утверждения 6)

(пункт 4. утверждения 6)

Утверждение 7

Пусть , итеративно определим следующие величины для k=0,1,2…:

1. -матрица -активных ограничений в точке .
2. - проекция градиента функции f в точке x на ядро , т.е.
   . Если , то останавливаемся.
3. Если , то определяем , где ,
   ,
   
4. Из утверждения 6 следует, что существует
   
   при этом справедлива оценка
   
5. Определяем
6. k:=k+1
   Тогда либо алгоритм останавливается для определенного k, для которого , либо существует сходящаяся к подпоследовательность последовательности , для предела которой справедливо .

Доказательство

Пусть для всех k справедливо .
Так как по 4 пункту алгоритма по построению следует , то все элементы последовательности находятся в допустимой области G.
Также из пункта 4 и утверждения 6 следует, что , т.е. последовательность строго монотонно убывающая. Эта последовательность ограничена снизу, так как G компактно, а f непрерывна, следовательно, сходится. В частности из этого следует, что - последовательность Коши (фундаментальная последовательность) и поэтому
, т.е.

(1)

Определим .
Предположим, что , тогда из (1) следует:

(2)

С другой стороны из пункта 4 и утверждения 6 следует, что

(3)

Из (2) и (3) следует, что

(4)

Так как число индексов конечно, а число элементов последовательности
бесконечно, то существует хотя бы один индекс на котором принимает минимум бесконечное число раз, т.е. существует подпоследовательность индексов , такая что
для всех .
С учетом этого получаем из (4):

(5)

Из (5) следует, что , т.е. , таким образом, мы пришли к противоречию с предположением, что .
Мы получили: , а так как , то , а следовательно, существует подпоследовательность , такая что или

(6)

Последовательность бесконечна, а набор возможных активных индексов конечен, следовательно, существует набор активных индексов , встречающийся на бесконечном количестве элементов последовательности, т.е. для бесконечного числа . Следовательно, существует подпоследовательность , такая что множество активных индексов для нее постоянна .
Так как G компактное множество, , то существует сходящаяся к подпоследовательность . Учитывая непрерывную дифференцируемость функций и то, что матрицы состоят из одних и тех же строк получаем:

(7)

Если , т.е. множество активных индексов в точке совпадает с множеством активных индексов в точках из окрестности , то , и, очевидно, , т.е. с учетом (7)

(8)

Предположим, что . Но множество не может быть меньше чем так как если , то , значит в пределе , а следовательно, , т.е. . Таким образом, если , то . В этом случае матрица содержит больше (линейно независимых) строк, чем , поэтому проектор на ядро равен проектору на ядро умноженному на проектор на ядро , т.е.
.
Следовательно

Но норма проекции вектора не может быть больше нормы самого вектора, поэтому

Таким образом

(9)

Из (8) и (9) мы получаем, что в любом случае .

Утверждение 8

Пусть и проекция градиента на ядро матрицы градиентов активных ограничений равно 0, т.е. .
Обозначим , где .
Если существует такое, что , то для набора индексов , полученного из I путем удаления этого -ого индекса справедливо:

1. - проекция градиента на ядро матрицы градиентов активных ограничений с удалением -ого индекса отлична от нуля.
2. , где - -ая строка матрицы градиентов ограничений в точке x.

Доказательство

1. Из имеем:
   

   (1)

   Предположим, что , тогда для получаем:

   (2)

   Вычитая (2) из (1) получаем:

   (3)

   Из линейной независимости градиентов активных ограничений, т.е. из (3) следует, что что противоречит условию. Т.е. мы доказали, что .
2. Сначала докажем, что вектор . Действительно, предположим, что , следовательно . Т.е. представляет собой линейную комбинацию строк из , а следовательно строки линейно зависимы, что противоречит условию линейной независимости градиентов активных ограничений. Таким образом, мы доказали, что

   (4)

   Далее из утверждения 5 следует:

   (5)

   Из имеем: , умножаем на :

   (6)

   Так как - проектор на ядро , то , следовательно из (6) с учетом (5) получаем:

   (7)

   что доказывает последнее утверждение.

Утверждение 9

Пусть ,
-матрица градиентов -активных ограничений в точке x, т.е. ,
- равная нулю проекция градиента функции f в точке x на ядро A(x), т.е.
.
Обозначим , где .
Пусть существует такое, что . Определим набор индексов , полученный из I путем удаления этого -ого индекса.
Определим

, где

Отметим, что так как по утверждению 8 , то

Тогда найдется такое положительное число t, что будет справедливы следующие неравенства:


где >0, константы, а

Доказательство

Из утверждения 8 следует, что .
Из ортогональности и следует, что .
Из определения следует, что .
Далее, так как , то из утверждения 1 следует, что для достаточно малых , будет выполнено

(1)

Из определения и следует, что Так как для всех индексов , и , то условия утверждения 2 выполнены и, следовательно, для достаточно малых справедливо

(2)

Для индекса справедливо вследствие утверждения 8:

(3)

Из определения следует если и следовательно

Т.е.

(4)

Итак, мы имеем: , , т.е. условия утверждения 2 для тоже выполнены и, следовательно, для достаточно малых справедливо

(5)

Для множества неактивных индексов на основании утверждения 3 найдутся достаточно малые , такие что

(6)

Таким образом, последовательно деля единицу пополам, мы через конечное число шагов придем на основании первых частей утверждений 1, 2 и 3 к такой величине шага , что условия (1), (2), (5) и (6) будут выполнены.
Если для эти условия не выполняются, но выполняются для максимального , полученного путем последовательного делением единицы на два, то в этом случае для хотя бы одно из условий (1), (2), (5) или (6) не выполняются. Из вторых частей утверждений 1, 2 и 3 следует, что для шага t должно выполняться одно из неравенств:

(7)

(8)

(9)

(10)

Так как, - компактное множество, функции , непрерывны, то существуют положительные константы, такие что

(11)

(12)

(13)

(14)

Поэтому

(15)

Из (11) и (12) следует:

(16)

Если справедливо (8), то из (15) и (16) следует:

(17)

Если справедливо (9), то из (16) следует:

(18)

Если справедливо (10), то из (16) следует:

(19)

Из (7), (17), (18), (19) следует:

(20)

где >0, константы, а

Утверждение 10

Пусть , .
По алгоритму, описанному в утверждении 7 итеративно определим следующие величины для k=0,1,2…:

1. -матрица -активных ограничений в точке .
2. - проекция градиента функции f в точке x на ядро , т.е. . Если , то переходим к пункту 7.
3. Если , то определяем , где ,
   ,
   .
4. Из утверждения 6 следует, что существует
   
   при этом справедлива оценка
   .
5. Определяем .
6. k:=k+1 , переходим к пункту 1.
   Тогда по утверждению 7 либо мы выходим из цикла последовательности действий 1-6 алгоритма с определенным k , для которого , либо существует сходящаяся к подпоследовательность последовательности , для предела которой справедливо .

7. Обозначим , где - матрица градиентов -активных ограничений в точке .
8. Если , то алгоритм завершается.
9. Если существует такое, что , то для набора индексов , полученного из I путем удаления этого -ого индекса со свойством определим:
   
   , где
   
   
   
   По утверждению 9 найдется такое положительное число , что будет справедливы следующие неравенства:
   

   (1)

   
   

   (2)

   
   

   (3)

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

Доказательство

Рассмотрим случай, когда последовательность для которой и , бесконечна. Из компактности G и следует, что существует и сходящаяся к ней подпоследовательность , т.е.

(4)

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

(5)

, так как если , то , значит в пределе , а следовательно, . Множество , таким образом, отличается от на множество индексов

(6)

Из (1) следует, что последовательность строго монотонно убывает, поэтому сходится, а, следовательно,

(7)

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

(8)

и будут принимать самые малые значения из всех . Тогда на каждом шаге p из множества активных индексов будет удаляться именно индекс , т.е. множество будет, начиная с , постоянно.
Учитывая получаем из (1), (2), (3), что:

(9)

(10)

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

(11)

Определим .
Предположим, что , тогда из (11) следует:

(12)

Но с учетом (10) выражение (12) возможно только если

(13)

или

(14)

Из (14) следует , что противоречит предположению , таким образом, случай (14) исключен.
Если выполняется условие (13), то с учетом (8) получаем , что

(15)

Учитывая непрерывную дифференцируемость получаем из (4) и (15):

следовательно, строки линейно зависимы, что противоречит условию о линейной независимости градиентов активных ограничений . Таким образом, случай (13) тоже исключен, поэтому , переходя к подпоследовательности , получаем:
.
Учитывая непрерывную дифференцируемость и того, что
, где матрицы состоят из одних и тех же строк, переходя к пределу, получаем:

(16)

Из (5) и (16) получаем:

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

(17)

Резюмируя (16) и (17), получаем:
последовательность, сгенерированная в ходе выполнения алгоритма, имеет сходящуюся к точке подпоследовательность, для которой для некого набора индексов выполняются следующие условия:

(18)

(19)

(20)

Утверждение 11

Пусть для сходящейся к нулю последовательности , по алгоритму, описанному в утверждении 10, сконструирована последовательность , такая что

(1)

(2)

(3)

Тогда существует сходящаяся к подпоследовательность , набор индексов и числа для которых выполняются условия:





Точка является глобальным минимумом функции f на G.

Доказательство

Все элементы последовательности находятся в компактном множестве G, следовательно, содержит сходящуюся к подпоследовательность .
Число наборов индексов конечно, а число элементов последовательности бесконечно, следовательно, существует набор индексов , повторяющийся в последовательно бесконечное число раз. Следовательно, можно выделить подпоследовательность для которой будет справедливо:
.
Учитывая непрерывную дифференцируемость функций , а также тот факт, что все состоят из одинаковых строк, то, переходя к пределу с учетом (1), (2), (3), получим:

(4)

(5)

(6)

Определим , тогда из (5) мы получим:

(7)

Из (4)

(8)

Из (6)

(9)

Определим функцию
Для каждого фиксированного функция L является выпуклой по x, так как - выпуклые функции, а . L также дифференцируемая функция, поэтому .
Если , то , следовательно

(10)

Т.е. - минимум f на G.

В формате PDF