Изменить: коллега сообщил мне, что мой метод ниже является примером общего метода в следующей статье, когда специализируется на функции энтропии,
Овертон, Майкл Л. и Роберт С. Вомерсли. «Вторые производные для оптимизации собственных значений симметричных матриц». Журнал SIAM по матричному анализу и приложениям 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf
обзор
В этом посте я покажу, что задача оптимизации хорошо поставлена и что ограничения неравенства неактивны при решении, затем вычисляем первую и вторую производные Фреше функции энтропии, а затем предлагаем метод Ньютона для задачи с устранением ограничения равенства. Наконец, код Matlab и числовые результаты представлены.
Хорошо поставленная задача оптимизации
Во-первых, сумма положительно определенных матриц положительно определена, поэтому для сумма матриц ранга 1
A ( c ) : = N ∑ i = 1 c i v i v T i
положительно определена. Если множество v i имеет полный ранг, то собственные значения A положительны, поэтому можно взять логарифмы собственных значений. Таким образом, целевая функция четко определена внутри допустимого множества.ся> 0
A ( c ) : = ∑я = 1NсяvяvTя
vяA
Во- вторых, так как любая , теряет ранг поэтому наименьшее собственное значение А стремится к нулю. То есть σ m i n ( A ( c ) ) → 0 при c i → 0 . Поскольку производная - σ log ( σ ) взрывается при σ → 0 , нельзя иметь последовательность последовательно лучших и лучших точек, приближающихся к границе допустимого множества. Таким образом, проблема хорошо определена и, кроме того, ограничения неравенствася→ 0AAσм я н( A ( c ) ) → 0ся→ 0- σжурнал( σ)σ→ 0 неактивны.ся≥ 0
Производные Фреше энтропийной функции
Внутри выполнимой области энтропийная функция везде дифференцируема по Фреше и дважды дифференцируема по Фреше, где собственные значения не повторяются. Чтобы сделать метод Ньютона, нам нужно вычислить производные энтропии матрицы, которая зависит от собственных значений матрицы. Это требует вычисления чувствительности разложения по собственным значениям матрицы относительно изменений в матрице.
Напомним, что для матрицы с разложением по собственным значениям A = U Λ U T производная матрицы собственных значений по изменениям в исходной матрице имеет вид
d Λ = I ∘ ( U T d A U ) ,
а производная от Матрица собственных векторов имеет вид
d U = U C ( d A ) ,
где ∘ - произведение Адамара с матрицей коэффициентов
C = { uAA = UΛ UT
dΛ = I∘ ( UTdA U) ,
dU= UС( дА ) ,
∘С= { тыTяdА тыJλJ- λя,0 ,я = jя = j
Такие формулы выводятся путем дифференцирования уравнения собственных значений , и формулы выполняются всякий раз, когда собственные значения различны. Когда имеются повторяющиеся собственные значения, формула для d Λ имеет устранимый разрыв, который можно расширить, если тщательно выбирать неединственные собственные векторы. Подробнее об этом см. Следующую презентацию и статью .A U= Λ UdΛ
Затем вторая производная находится путем дифференцирования,
d2Λ= д( Я∘ ( UTdA1U) )= Я∘ ( дUT2dA1U+ UTdA1dU2)= 2 я∘ ( дUT2dA1U) .
d2ΛdU2Сvя
Устранение ограничения равенства
ΣNя = 1ся= 1N- 1
сN= 1 - ∑я = 1N- 1ся,
N- 1
dе= дСT1MT[ Я∘ ( VTUB UTВ) ]
ddе= дСT1MT[ Я∘ ( VT[ 2 дU2ВaUT+ UВбUT] V) ] ,
M=⎡⎣⎢⎢⎢⎢⎢⎢⎢1- 11- 1⋱...1- 1⎤⎦⎥⎥⎥⎥⎥⎥⎥,
Вa= d i a g ( 1 + logλ1, 1 + журналλ2, … , 1 + журналλN) ,
Вб= d i a g ( d2λ1λ1, ... , d2λNλN) .
Метод Ньютона после устранения ограничения
Поскольку ограничения по неравенству неактивны, мы просто начинаем с допустимого набора и запускаем поиск в области доверия или неточный ньютон-CG в области поиска для квадратичной сходимости к внутренним максимумам.
Метод заключается в следующем (не включая детали поиска области доверия / линии)
- с~= [ 1 / N, 1 / N, … , 1 / N]
- с = [ с~, 1 - ∑N- 1я = 1ся]
- A = ∑ясяvяvTя
- UΛA
- G = MT[ Я∘ ( VTUB UTВ) ]
- ЧАСG = pпЧАСЧАСδс~dU2ВaВб
MT[ Я∘ ( VT[ 2 дU2ВaUT+ UВбUT] V) ]
- с~← с~- р
- Перейти к 2.
Результаты
vяN= 100vя
>> N = 100;
>> V = рандн (N, N);
>> для k = 1: NV (:, k) = V (:, k) / норма (V (:, k)); конец
>> maxEntropyMatrix (V);
Итерация Ньютона = 1, норма (градус f) = 0,67748
Итерация Ньютона = 2, норма (градус f) = 0,03644
Итерация Ньютона = 3, норма (градус f) = 0,0012167
Итерация Ньютона = 4, норма (град. F) = 1.3239e-06
Итерация Ньютона = 5, норма (градус f) = 7.7114e-13
Чтобы увидеть, что вычисленная оптимальная точка на самом деле является максимумом, приведем график изменения энтропии при случайном возмущении оптимальной точки. Все возмущения уменьшают энтропию.
Код Matlab
Функция «все в 1» для минимизации энтропии (недавно добавлена в этот пост):
https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m