Optimizing quadratic form with respect to inner positive definite matrix with a trace constraint

lagrange multipliermatrix decompositionmatrix-calculusoptimization

Let $\{z_i\}_{i=1}^n$ and $\{w_i\}_{i=1}^n$ be two collections of vectors in $\mathbb R^p$. Let $A$ be a real positive definite $p\times p$ matrix, with Cholesky factorization $LL^T$, where $L$ is also $p\times p$.

I want to solve the following optimization:

$$\min_L F(L) \rightarrow \min_L \sum_{i=1}^p z^T_i LL^T z_i – w^T_i LL^T w_i$$
subject to the constraint
$$\text{tr}(LL^T) = 1.$$

My approach: Lagrange multipliers. I thought that $\frac{d}{dL} \left(zLL^Tz – wLL^Tw\right) = 2(zz^T-ww^T)L$, and $\frac{d}{dL}\text{Tr}(LL^T) = 2L$, but this doesn't seem to lead to a solution.

Edited: Rewrote problem to include a positive semi-definite constraint, via the Cholesky factorization.

Best Answer

Rather than solve for the Cholesky factor directly, find a solution in terms of a less structured matrix, $M$. Let a colon denote the matrix inner product, i.e. $$\eqalign{ A:B &= {\rm Tr}(AB^T) \cr M:M &= {\rm Tr}(MM^T) &= \frac{1}{\mu^2} \cr }$$ Also, for typing convenience let $$\eqalign{ A &= \frac{MM^T}{M:M},\quad\; Y &= Y^T = \sum_kz_kz_k^T - w_kw_k^T \cr }$$ Calculate the gradient of $F$. $$\eqalign{ F &= Y:A \cr dF &= Y:dA \cr &= Y:\Bigg(\frac{dM\,M^T+M\,dM^T}{M:M} - \frac{MM^T\big(dM:M+M:dM\big)}{(M:M)^2}\Bigg) \cr &= 2\mu^2\Big(YM-FM\Big):dM \cr \frac{\partial F}{\partial M} &= 2\mu^2\big(YM-FM\big) \cr }$$ Set the gradient to zero and solve for $M$. $$\eqalign{ &YM = F M \cr }$$ Thus it appears that the columns of $M$ are equal to the eigenvector $\{v_k\}$ of $Y$ associated with its minimum eigenvalue $\{\lambda_k\}$, i.e. $$k = \arg\min_j \lambda_j,\quad F = \lambda_k,\quad M = (\,v_k\;v_k\;v_k\;\ldots\,) \,=\, v_k{\large\tt 1}^T $$

Given the solution in terms of $M$, recover a solution in terms of $L$. $$\eqalign{ L &= {\rm cholesky}\bigg(\frac{MM^T}{M:M}\bigg) \cr A &= LL^T = \frac{MM^T}{M:M},\quad\quad {\rm Tr}(LL^T) = \frac{M:M}{M:M} = 1 \cr }$$

Related Question