0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Johan Löfberg Sep 20 '17 at 13:25
  • $\begingroup$ @JohanLöfberg, you're right, I forgot an S term $\endgroup$ – Sofia693 Sep 20 '17 at 13:26
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Sofia693 Sep 20 '17 at 15:41
  • $\begingroup$ 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 $\endgroup$ – Johan Löfberg Sep 20 '17 at 15:59
  • $\begingroup$ 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 ) $$ $\endgroup$ – Sofia693 Sep 26 '17 at 11:37
  • $\begingroup$ $m = 0$ is trivially optimal as $m$ doesn't appear in any constraint $\endgroup$ – Johan Löfberg Sep 26 '17 at 11:47
  • $\begingroup$ 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. $\endgroup$ – Sofia693 Sep 26 '17 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.