# How to solve this non-convex optimization problem?

We have the following non-convex optimization problem in $t \times m$ matrix $N$

$$\begin{array}{ll} \text{minimize} & \|W - N^{T}H N \|_F\\ \text{subject to} & N \geq 0\end{array}$$

where $W$ and $H$ are given symmetric, non-negative matrices of sizes $m \times m$ and $t \times t$, respectively. $H$ is also Toeplitz and positive semidefinite.

$$H = \begin{bmatrix} 2a_{1} & a_{2} & a_{3} \dots &a_{t} \\ a_{2} & 2a_{1} & \dots &a_{t-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{t} & a_{t-1} & \dots &2a_{1} \end{bmatrix}$$

where $a_{1}$ > $a_{2}$ > $\cdots$ > $a_{t}$.

Any suggestions for this problem? Thanks a lot.

• Are you looking for an exact solution (that might take exponential time)? Some kind of fast heuristic? How big are $T$ and $M$? (tens, hundreds, thousands, millions, billions)? – Brian Borchers May 6 '18 at 1:32
• Yes, I am looking for the exact solution. T could be thousands and M could be hundreds. Do you have any suggestions? Any website link or paper link could be very useful. Thank you very much! – Jin May 6 '18 at 1:35
• Is $H$ positive semi-definite or can it be any symmetric matrix? – VHarisop May 6 '18 at 1:42
• @VHarisop Thanks for helping me modify my problem, I also attach the additional information. So, assume that H is positive semi-definite, what will the optimization be? – Jin May 6 '18 at 18:02

$\min_{N} \| W- N^{T}HN \|_{F}^{2}$
$N \geq 0$
you've got a problem with nonnegativity constraints and quartic polynomial objective function. This can be minimized to any desired tolerance by branch and bound methods, but these are exponential time algorithms, and with $T$ in the thousands and $M$ in the hundreds, this is most likely to be impractical.