Ограниченная задача оптимизации в матричной энтропии

10

У меня есть ограниченная проблема оптимизации в матрице (Шеннона) энтропии (sUм(еNTр(еяг(A)))) . Матрица может быть записана как сумма матриц ранга 1 вида где - заданный нормализованный вектор. Коэффициенты матриц ранга один - это неизвестные, в которых мы оптимизируем, и они должны быть больше нуля и суммировать до 1.[ V IAv i[vяvяT]vя

В CVX-подобном синтаксисе проблема заключается в следующем: заданная переменнаяс(N)

минимизироватьsUм(еNTр(еяг(A)))

при условииAзнак равноΣсяvяvяTΣсязнак равно1ся0
.

У кого-нибудь есть идеи, как решить это эффективно? Я уже знаю, что это, вероятно, нельзя рассматривать как проблему полуопределенного программирования (SDP).

Dries
источник

Ответы:

8

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

Овертон, Майкл Л. и Роберт С. Вомерсли. «Вторые производные для оптимизации собственных значений симметричных матриц». Журнал 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(с)знак равноΣязнак равно1NсяvяvяT
vяA

Во- вторых, так как любая , теряет ранг поэтому наименьшее собственное значение А стремится к нулю. То есть σ m i n ( A ( c ) ) 0 при c i0 . Поскольку производная - σ log ( σ ) взрывается при σ 0 , нельзя иметь последовательность последовательно лучших и лучших точек, приближающихся к границе допустимого множества. Таким образом, проблема хорошо определена и, кроме того, ограничения неравенствася0AAσмяN(A(с))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Λзнак равноя(UTdAU),
dUзнак равноUС(dA),
Сзнак равно{UяTdAUJλJ-λя,язнак равноJ0,язнак равноJ

Такие формулы выводятся путем дифференцирования уравнения собственных значений , и формулы выполняются всякий раз, когда собственные значения различны. Когда имеются повторяющиеся собственные значения, формула для d Λ имеет устранимый разрыв, который можно расширить, если тщательно выбирать неединственные собственные векторы. Подробнее об этом см. Следующую презентацию и статью .AUзнак равноΛUdΛ

Затем вторая производная находится путем дифференцирования,

d2Λзнак равноd(я(UTdA1U))знак равноя(dU2TdA1U+UTdA1dU2)знак равно2я(dU2TdA1U),

d2ΛdU2Сvя

Устранение ограничения равенства

Σязнак равно1Nсязнак равно1N-1

сNзнак равно1-Σязнак равно1N-1ся,

N-1

dезнак равноdС1TMT[я(ВTUВUTВ)]
ddезнак равноdС1TMT[я(ВT[2dU2ВaUT+UВбUT]В)],
Mзнак равно[111-1-1...-1],

Вaзнак равноdяaг(1+журналλ1,1+журналλ2,...,1+журналλN),

Вбзнак равноdяaг(d2λ1λ1,...,d2λNλN),

Метод Ньютона после устранения ограничения

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

Метод заключается в следующем (не включая детали поиска области доверия / линии)

  1. с~знак равно[1/N,1/N,...,1/N]
  2. сзнак равно[с~,1-Σязнак равно1N-1ся]
  3. Aзнак равноΣясяvяvяT
  4. UΛA
  5. гзнак равноMT[я(ВTUВUTВ)]
  6. ЧАСгзнак равноппЧАСЧАСδс~dU2ВaВб
    MT[я(ВT[2dU2ВaUT+UВбUT]В)]
  7. с~с~-п
  8. Перейти к 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

Ник Алджер
источник
Большое спасибо! Я решил это просто с градиентом, но это, вероятно, более надежно. Тот факт, что v должен иметь полный ранг в файле matlab - единственное, что беспокоит меня.
Высыхает
@NickAlger Предоставленная ссылка не работает, могу я попросить вас посмотреть?
Создатель
@Creator обновил ссылку в сообщении! github.com/NickAlger/various_scripts/blob/master/…
Ник Алджер
@NickAlger Есть ли ограничение на матрицу, что алгоритм может работать? Этот алгоритм подходит для матрицы со сложными элементами? В моем случае SVD выходит из строя через некоторое время, так как матрица имеет Nan.
Создатель
Я не думаю, что сложные числа должны быть проблемой. Одним из ограничений метода является то, что оптимальное решение не может иметь повторяющихся собственных значений, что я предполагаю, что происходит здесь. В этом случае метод сходится к чему-то, что делится на ноль в уравнении C. Вы можете попробовать немного помешать входам и посмотреть, поможет ли это. Есть способ обойти это в статье Овертона, на которую мы ссылаемся выше, но мой код не настолько продвинут.
Ник Алджер