Ograniczony problem optymalizacji w Entropii macierzy

Mam ograniczony problem optymalizacji w entropii macierzy (Shannona) $\mathtt{(sum(entr(eig(A))))}$ . Macierz $A$ można zapisać jako sumę macierzy rangi 1 w postaci gdzie jest danym znormalizowanym wektorem. Współczynniki macierzy pierwszego stopnia to niewiadome, w których optymalizujemy i muszą być większe od zera i sumować do 1.v $[v_i\,v_i^T]$$v_i$

W składni podobnej do CVX problem wygląda następująco: podana zmienna$\mathtt{c(n)}$

$$\text{minimize} \qquad \mathtt{sum(entr(eig(A)))}$$

$$\begin{align} \text{subject to} \qquad A &= \sum c_i v_i v_i^T\\ \sum c_i &= 1\\ c_i &\ge 0\end{align}$$ .

Czy ktoś ma pomysł na skuteczne rozwiązanie tego problemu? Wiem już, że prawdopodobnie nie można go traktować jako problemu programowania pół-określonego (SDP).

Edycja: kolega poinformował mnie, że moja metoda poniżej jest przykładem metody ogólnej w poniższym artykule, gdy jest ona wyspecjalizowana w funkcji entropii,

Overton, Michael L. i Robert S. Womersley. „Drugie pochodne do optymalizacji wartości własnych macierzy symetrycznych”. SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Przegląd

W tym poście pokazuję, że problem optymalizacji jest dobrze postawiony i że ograniczenia nierówności są nieaktywne w rozwiązaniu, a następnie oblicz pierwszą i drugą pochodną Frecheta funkcji entropii, a następnie zaproponuję metodę Newtona dotyczącą problemu z wyeliminowanym ograniczeniem równości. Na koniec prezentowany jest kod Matlab i wyniki numeryczne.

Dobrze postawiony problem optymalizacji

Po pierwsze, suma dodatnio określonych macierzy jest dodatnia, więc dla suma macierzy rangi 1 jest dodatnia. Jeśli zbiór ma pełną rangę, wówczas wartości własne są dodatnie, więc można przyjąć logarytmy wartości własnych. Zatem funkcja celu jest dobrze zdefiniowana we wnętrzu wykonalnego zestawu.A ( c ) : = N ∑ i = 1 c i v i v T $c_i > 0$

$$A(c):=\sum_{i=1}^N c_i v_i v_i^T$$ $v_i$$A$

Po drugie, jak każdy , traci pozycję, więc najmniejsza wartość własna spada do zera. Tj. as . Ponieważ pochodna wysadza się jako , nie można mieć sekwencji kolejnych coraz lepszych punktów zbliżających się do granicy wykonalnego zbioru. Zatem problem jest dobrze zdefiniowany, a ponadto ograniczenia nierówności są nieaktywne.$c_i \rightarrow 0$$A$$A$$\sigma_{min}(A(c)) \rightarrow 0$$c_i \rightarrow 0$$-\sigma \log(\sigma)$$\sigma \rightarrow 0$$c_i \ge 0$

Pochodne Frecheta funkcji entropii

We wnętrzu wykonalnego regionu funkcją entropii jest wszędzie różnicowalność Frecheta i dwukrotność różnicowania Frecheta wszędzie tam, gdzie wartości własne nie są powtarzane. Aby wykonać metodę Newtona, musimy obliczyć pochodne entropii macierzy, które zależą od wartości własnych macierzy. Wymaga to obliczenia czułości rozkładu wartości własnej macierzy w odniesieniu do zmian w macierzy.

Przypomnijmy, że dla macierzy z rozkładem wartości własnej pochodną macierzy wartości własnej w odniesieniu do zmian w oryginalnej macierzy jest: i pochodną macierzy wektorów własnych jest gdzie jest iloczynem Hadamarda , o macierzy współczynników $A$$A = U \Lambda U^T$

$$d\Lambda = I \circ (U^T dA U),$$ $$dU = UC(dA),$$ $\circ$ $$C = \begin{cases} \frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\ 0, &i=j \end{cases}$$

Takie formuły wyprowadza się przez różnicowanie równania wartości własnej , a formuły zachowują się, gdy wartości własne są różne. Gdy powtarzane są wartości własne, formuła dla ma usuwalną nieciągłość, którą można przedłużyć, o ile nietypowe wektory własne zostaną starannie wybrane. Aby uzyskać szczegółowe informacje na ten temat, zobacz następującą prezentację i artykuł .$AU=\Lambda U$$d\Lambda$

Następnie można znaleźć drugą pochodną, ​​różnicując ponownie:

$$\begin{align} d^2 \Lambda &= d(I \circ (U^T dA_1U)) \\ &= I \circ (dU_2^T dA_1 U + U^T dA_1 dU_2) \\ &= 2 I \circ (dU_2^T dA_1 U). \end{align}$$

Podczas gdy pierwsza pochodna macierzy wartości własnych mogłaby być ciągła przy powtarzanych wartościach własnych, druga pochodna nie może, ponieważ zależy od , która zależy od , który wysadza się, gdy wartości własne ulegają degeneracji względem siebie. Jednak dopóki prawdziwe rozwiązanie nie ma powtarzających się wartości własnych, jest OK. Eksperymenty numeryczne sugerują, że tak jest w przypadku generycznego , chociaż nie mam na to dowodu. Jest to naprawdę ważne, aby to zrozumieć, ponieważ maksymalizacja entropii zazwyczaj próbowałaby przybliżyć wartości własne, jeśli to możliwe.$d^2 \Lambda$$dU_2$$C$$v_i$

Eliminacja ograniczenia równości

Możemy wyeliminować ograniczenie , pracując tylko na pierwszych współczynnikach i ustawiając ostatni na $\sum_{i=1}^N c_i = 1$$N-1$

$$c_N = 1-\sum_{i=1}^{N-1} c_i.$$

Ogólnie, po około 4 stronach obliczeń macierzowych, zredukowane pierwsze i drugie pochodne funkcji celu w odniesieniu do zmian pierwszych współczynników są podane przez gdzie $N-1$

$$df = dC_1^T M^T [I \circ (V^T U B U^T V)]$$ $$ddf = dC_1^T M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)],$$ $$M = \begin{bmatrix} 1 & \\ & 1 & \\ &&\ddots& \\ &&&1\\ -1 & -1 & \dots & -1 \end{bmatrix},$$

$$B_a = \mathrm{diag}(1+\log \lambda_1, 1 + \log \lambda_2, \ldots, 1 + \log \lambda_N),$$

$$B_b = \mathrm{diag}(\frac{d_2\lambda_1}{\lambda_1},\ldots,\frac{d_2\lambda_N}{\lambda_N}).$$

Metoda Newtona po wyeliminowaniu ograniczenia

Ponieważ ograniczenia nierówności są nieaktywne, zaczynamy po prostu od wykonalnego zestawu i uruchamiamy dokładny region zaufania lub wyszukiwanie liniowe z dokładnym newtonem-CG dla kwadratowej zbieżności z maksimami wewnętrznymi.

Metoda jest następująca (bez uwzględnienia szczegółów przeszukiwania regionu zaufania / linii)

1. Zacznij od .$\tilde{c} = [1/N,1/N,\ldots,1/N]$
2. Skonstruuj ostatni współczynnik, .$c = [\tilde{c},1 - \sum_{i=1}^{N-1} c_i]$
3. Skonstruować .$A = \sum_i c_i v_i v_i^T$
4. Znajdź wektorów własnych i wartości własne od .$U$$\Lambda$$A$
5. Konstruuj gradient .$G = M^T [I \circ (V^T U B U^T V)]$
6. Rozwiąż dla za pomocą gradientu sprzężonego ( potrzebna jest tylko umiejętność zastosowania , a nie rzeczywiste wpisy). stosuje się do wektora , znajdując , i a następnie podłączając do formuły, p H H δ ˜ $H G = p$$p$$H$$H$$\delta \tilde{c}$B a B b M T [ I ∘ ( V T [ 2 d U 2 B a U T + U B b U T ] V ) $dU_2$$B_a$$B_b$ $$M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)]$$
7. Ustaw .$\tilde{c} \leftarrow \tilde{c} - p$
8. Idź 2.

Wyniki

W przypadku losowego , przy przeszukiwaniu linii dla długości kroku metoda bardzo szybko się zbiega. Na przykład typowe są następujące wyniki dla (100 ) - metoda jest zbieżna kwadratowo. N = 100 v $v_i$$N=100$$v_i$

>> N = 100;
>> V = randn (N, N);
>> dla k = 1: NV (:, k) = V (:, k) / norma (V (:, k)); koniec
>> maxEntropyMatrix (V);
Iteracja Newtona = 1, norma (stopień f) = 0,67748
Iteracja Newtona = 2, norma (stopień f) = 0,03644
Iteracja Newtona = 3, norma (stopień f) = 0,0012167
Iteracja Newtona = 4, norma (stopień f) = 1,3239e-06
Iteracja Newtona = 5, norma (stopień f) = 7,7114e-13

Aby zobaczyć, że obliczony punkt optymalny jest w rzeczywistości maksimum, oto wykres, w jaki sposób entropia zmienia się, gdy punkt optymalny jest zaburzony losowo. Wszystkie zaburzenia powodują zmniejszenie entropii.

Kod Matlab

Funkcja wszystko w 1, aby zminimalizować entropię (nowo dodana do tego postu): https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m