Eingeschränktes Optimierungsproblem in der Matrixentropie

Ich habe ein constrainted Optimierungsproblem in der (Shannon) -Matrix Entropie . Die Matrix A kann als die Summe der Rang-1-Matrizen der Form [ v $\mathtt{(sum(entr(eig(A))))}$$A$ wobei v i ein gegebener normalisierter Vektor ist. Die Koeffizienten der Rang-1-Matrizen sind die Unbekannten, in denen wir optimieren, und sie müssen größer als Null sein und sich zu 1 summieren.$[v_i\,v_i^T]$$v_i$

In einer CVX-ähnlichen Syntax lautet das Problem wie folgt: gegebene Variable $\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}$$

Hat jemand eine Idee, wie man das effizient löst? Ich weiß bereits, dass es wahrscheinlich nicht als semi-definitives Programmierproblem (SDP) angesehen werden kann.

Bearbeiten: Ein Kollege informierte mich, dass meine Methode unten eine Instanz der allgemeinen Methode im folgenden Artikel ist, wenn sie auf die Entropiefunktion spezialisiert ist.

Overton, Michael L. und Robert S. Womersley. "Zweite Ableitungen zur Optimierung der Eigenwerte symmetrischer Matrizen." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697 & ndash; 718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Überblick

In diesem Beitrag zeige ich, dass das Optimierungsproblem gut gestellt ist und dass die Ungleichheitsbeschränkungen bei der Lösung inaktiv sind. Berechnen Sie dann die erste und zweite Frechet-Ableitung der Entropiefunktion und schlagen Sie dann Newtons Methode für das Problem vor, wobei die Gleichheitsbeschränkung beseitigt ist. Abschließend werden Matlab-Code und numerische Ergebnisse vorgestellt.

Gut gestelltes Optimierungsproblem

Erstens ist die Summe der positiv definierten Matrizen positiv definit, so dass für die Summe der Rang-1-Matrizen A ( c ) : = N ∑ i = 1 c i v i v T i positiv definit ist. Wenn die Menge von v i den vollen Rang hat, sind die Eigenwerte von A positiv, so dass die Logarithmen der Eigenwerte genommen werden können. Somit ist die Zielfunktion im Inneren des realisierbaren Satzes genau definiert.$c_i > 0$

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

Zweitens, wie jedes , A verliert Rang so kleinsten Eigenwert von A auf Null geht. Dh σ m i n ( A ( c ) ) → 0 als c i → 0 . Da die Ableitung von - σ log ( σ ) als σ → 0 explodiert , kann man keine Folge von immer besseren Punkten haben, die sich der Grenze der realisierbaren Menge nähern. Somit ist das Problem genau definiert und darüber hinaus die Ungleichheitsbeschränkungen$c_i \rightarrow 0$$A$$A$$\sigma_{min}(A(c)) \rightarrow 0$$c_i \rightarrow 0$$-\sigma \log(\sigma)$$\sigma \rightarrow 0$ sind inaktiv.$c_i \ge 0$

Frechet-Ableitungen der Entropiefunktion

Im Inneren des realisierbaren Bereichs ist die Entropiefunktion überall Frechet-differenzierbar und zweimal Frechet-differenzierbar, wo immer die Eigenwerte nicht wiederholt werden. Um Newtons Methode anzuwenden, müssen wir Ableitungen der Matrixentropie berechnen, die von den Eigenwerten der Matrix abhängen. Dies erfordert die Berechnung der Empfindlichkeiten der Eigenwertzerlegung einer Matrix in Bezug auf Änderungen in der Matrix.

Recall , daß für eine Matrix mit Eigenwertzerlegung A = U Λ U T , die Ableitung der Eigenwertmatrix in Bezug auf Änderungen in der ursprünglichen Matrix ist, d Λ = I ∘ ( U T D A U ) , und die Ableitung der Die Eigenvektormatrix ist d U = U C ( d A ) , wobei ∘ das Hadamard-Produkt ist , mit der Koeffizientenmatrix C = { $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}$$

$AU=\Lambda U$$d\Lambda$

$$\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}$$

$d^2 \Lambda$$dU_2$$C$$v_i$

Beseitigung der Gleichheitsbeschränkung

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

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

$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}).$$

Newtons Methode nach Beseitigung der Einschränkung

Da die Ungleichheitsbeschränkungen inaktiv sind, beginnen wir einfach in der realisierbaren Menge und führen eine ungenaue Newton-CG-Vertrauensregion oder Liniensuche durch, um eine quadratische Konvergenz mit den inneren Maxima zu erreichen.

Die Methode ist wie folgt (ohne Angaben zur Vertrauensregion / Zeilensuche)

1. $\tilde{c} = [1/N,1/N,\ldots,1/N]$
2. $c = [\tilde{c},1 - \sum_{i=1}^{N-1} c_i]$
3. $A = \sum_i c_i v_i v_i^T$
4. $U$$\Lambda$$A$
5. $G = M^T [I \circ (V^T U B U^T V)]$
6. $H G = p$$p$$H$$H$$\delta \tilde{c}$$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. $\tilde{c} \leftarrow \tilde{c} - p$
8. Gehe zu 2.

Ergebnisse

$v_i$$N=100$$v_i$

>> N = 100;
>> V = Randn (N, N);
>> für k = 1: NV (:, k) = V (:, k) / Norm (V (:, k)); Ende
>> maxEntropyMatrix (V);
Newton-Iteration = 1, Norm (Grad f) = 0,67748
Newton-Iteration = 2, Norm (Grad f) = 0,03644
Newton-Iteration = 3, Norm (Grad f) = 0,0012167
Newton-Iteration = 4, Norm (Grad f) = 1,3239e-06
Newton-Iteration = 5, Norm (Grad f) = 7,7114e-13

Um zu sehen, dass der berechnete optimale Punkt tatsächlich das Maximum ist, ist hier ein Diagramm, wie sich die Entropie ändert, wenn der optimale Punkt zufällig gestört wird. Alle Störungen verringern die Entropie.

Matlab-Code

All-in-1-Funktion zur Minimierung der Entropie (neu zu diesem Beitrag hinzugefügt): https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m