Business Data Analytics. Технологии добычи знаний и интеллектуального анализа данных. Data mining Сайт www.BusinessDataAnalytics.ru
предлагает актуальные материалы
об алгоритмах и технологиях
добычи знаний и интеллектуального
анализа данных.
Документ: Businesss Data Analytics / Статьи / Метод проекции градиента /

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

Максим Гончаров
© spellabs it.company
Москва, март 2009 года
http://www.spellabs.ru/
http://www.businessdataanalytics.ru/

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

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

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

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

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

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

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

  1. Из дифференцируемости следует:
    .
    Так как и , то существует , такой что
    , а следовательно

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




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

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

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

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

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




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

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

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

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

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



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

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

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

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

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



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

Обозначения

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

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

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

  1. , т.е.

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





Обозначения

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

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

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

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

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

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

(2)

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

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

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

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

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



Так как , то из утверждения 1 следует, что для достаточно малых , будет выполнено
(7)
Из определения и следует, что , так как - строки матрицы A(x) для i из I(x).
Так как для всех активных индексов , и , то условия утверждения 2 выполнены и, следовательно, для достаточно малых справедливо
(8)
Для множества неактивных индексов на основании утверждения 3 найдутся достаточно малые , такие что
(9)
Таким образом, последовательно деля единицу пополам, мы через конечное число шагов придем на основании первых частей утверждений 1, 2 и 3 к такой величине шага , что условия (7), (8) и (9) будут выполнены.
Возможны два варианта:
  • Эти условия выполняются для первоначального значения
  • Для эти условия не выполняются, но выполняются для максимального , полученного путем последовательного делением единицы на два. В этом случае для хотя бы одно из условий (7), (8) или (9) не выполняются. Из вторых частей утверждений 1, 2 и 3 следует, что для шага должно выполняться одно из неравенств:
    (10)
    (11)
    (12)
Так как (4), а также (6), то из (10) следует
(13)

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

Таким образом, из (1), (15) и (16) следут
(17)

С учетом (16) и (17), из неравенства (11) можно получить следующую оценку:

Т.е.
(18)

С учетом (14) из (12) можно получить оценку
(19)

Таким образом, для шага t(x) мы получаем: либо t(x)=1 либо справедливо одно из неравенств (13), (18) или (19), а следовательно

где , , .
Таким образом, для t(x) справедливо:
(пункт 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 , для которого , либо существует сходящаяся к подпоследовательность последовательности , для предела которой справедливо .
Обозначим полученную в результате последовательности действий 1-6 алгоритма (возможно предельную) точку в которой .
  1. Обозначим , где - матрица градиентов -активных ограничений в точке .
  2. Если , то алгоритм завершается.
  3. Если существует такое, что , то для набора индексов , полученного из 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

в начало страницы