# How's this optimization problem simplified?

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 ?

• There has to be some $S$-terms missing in the objective. As it is now, the problem is trivial to solve as the first term with sums doesn't depend on $S$ – Johan Löfberg Sep 20 '17 at 13:25
• @JohanLöfberg, you're right, I forgot an S term – Sofia693 Sep 20 '17 at 13:26

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.
• doesn't this lead us to $\min_{s_i}\|s_i-v_i\|_2^2$ why is there $\frac{1}{2}$ in the simplified objective function ? – Sofia693 Sep 20 '17 at 15:41
• The factor 1/2 is completely arbitrary. You can multiply with $\pi$ if you want to. It is just very common to have 1/2 before quadratics – Johan Löfberg Sep 20 '17 at 15:59
• What if we add another term to the objective quadratic term ($\|m_i-m_j\|_2^2$), the problem becomes:$$\min_S\sum_{i,j}\left [ -\sum_l w_lK_l(c_i,c_j)+\gamma (LL^T)_{ij}+\|m_i-m_j\|_2^2 \right ]S_{ij}+\beta \left \| S \right \|_F^2$$ can we still solve it the same way ? and we just define$v_i$ as $$(v_i)_j = -\frac{1}{2\beta}(\gamma (LL^T)_{ij}-\sum_l w_lK_l(c_i,c_j)+\|m_i-m_j\|_2^2 )$$ – Sofia693 Sep 26 '17 at 11:37
• $m = 0$ is trivially optimal as $m$ doesn't appear in any constraint – Johan Löfberg Sep 26 '17 at 11:47
• I don't get you, why $m= 0$ ? it represents something and $S$ depends of it. The other terms don't appear in constraints too and S was solved in regards to them. PS: please don't get bored of my questions, I am totally new to the field. – Sofia693 Sep 26 '17 at 12:24