Minimize Sum of a Quadratic Matrix Form

187 Views Asked by At

For given PSD symmetric Matrix $Q$ and two real $a$ and $b$ i want to minimize the non linear form defined as:

$$\mathop {\min }\limits_{{\alpha _i},{u_i}} \sum\limits_{i = 1}^{n = N} {{\alpha _i}u_i^TQ{u_i}}$$

st: $$\begin{array}{l} U = [{u_1},{u_2}...,{u_N}]\\ U{U^T} = I\\ 0 < a < {\alpha _i} < b \end{array}$$

1

There are 1 best solutions below

0
On

According to @Surb comments, we need $\alpha_i = a$ for all $i$. Thus I reformulate the problem here: \begin{equation} \begin{array}{cl} {\min_{U}} & {a \cdot \operatorname{tr} (U^TQU)} \\ {\mathrm{s.t.}} & {U^TU = I} \end{array} \end{equation} where $$U = \begin{pmatrix} u_1 \\ \vdots \\ u_N\end{pmatrix}$$.

This is a non-convex problem. Applying the Lagrangian Multiplier Method, we have \begin{equation} \max_{V} \min_{U} a \cdot \langle U, QU \rangle - \langle V, U^TU-I \rangle. \end{equation} The optimal solution is \begin{equation} a \cdot Q\bar{U} = \bar{U}\bar{V}, \quad \bar{U}^T\bar{U} = I. \end{equation} Thus $V$ is a diagonal matrix formed from the eigenvalues of $Q/a$. And $U$ is the matrix formed from the eigenvector of $Q$.

In conclusion, if $N < n$, then $V$ is a diagonal matrix formed from the largest $N$ eigenvalues of $Q/a$, and $U$ is the matrix formed from its corresponding eigenvector.