How's this optimization problem simplified?

Question

I encountered this optimization problem: $$\min_S\sum_{i,j}\left [ -\sum_l w_lK_l(c_i,c_j)+\gamma (LL^T)_{ij} \right ]S_{ij}+\beta \left \| S \right \|_F^2$$ $$s.t \sum_jS_{ij}=1, S_{ij}\geq 0 \, \forall (i,j)$$ where $S$ is a matrix (each row is independant), the proposed approach to solve the problem is to parallel the solution by solving each row ( $s_1,...,s_N$) independently. The problem was then simplified to $N$ independant quadratic subproblems: $$\min_{s_i}\frac{1}{2}\|s_i-v_i\|_2^2 $$ $$s.t \,\,s_i^T1=1 \,,(s_i)_j\geq 0 \, \forall j $$ where $v_i$ (a $N$-length vector) defined as: $$(v_i)_j = -\frac{1}{2\beta}(\gamma (LL^T)_{ij}-\sum_l w_lK_l(c_i,c_j)) $$ The equivalence between the first and second equations remains unclear to me, is it a simple mathematical calculation that I miss or some kind of "trick" I can't see ?

Answer 1

You objective can (after dividing with $\beta$) be written as $\sum_i -2s_i v_i^T + \left\| s_i\right\|^2$, which you can complete the squares on to $\sum_i \left\| s_i-v_i \right\|^2 -v_iv_i^T$. The constraints are not coupled between rows of $S$, hence you can solve $N$ problems.