3
$\begingroup$

The problem to solve is

$\min_x \sum_i \sum_j C_{ij} x_i x_j$ $\,$ s.t. $\sum_i x_i = 1$.

for $C$ a symmetric and positive semidefinite matrix. Or equivalently

$\min_x x'Cx$ $\,$ s.t. $x'e = 1$.

This feels similar to a quadratic minimization onto the positive simplex (for a particular norm induced by C), although here the individual $x_i$ might take negative values. As already stated in How can I minimize a quadratic on the unit simplex? such problem can be solved with general quadratic programming methods, which also applies here. However, it seems that for this particular case a closed form solution can be found as

$x_i = \frac{\sum_j C_{ij}^{-1}}{\sum_k \sum_j C_{kj}^{-1}}$,

as stated (without proof) in the paper "When Networks Disagree: Ensemble Methods for Hybrid Neural Networks", section 4: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.3857


enter image description here


How can this result be obtained?

And furthermore, would still be possible to find a closed form solution if positivity constraints are enforced as $x \geq 0$, recovering the positive simplex problem but for a pure symmetric quadratic objective?

$\endgroup$
3
$\begingroup$

Using Lagrange multipliers, $x$ is a solution of your problem if there is $\mu$ such that $$ 2Cx + \mu e =0, \ x^Te =1. $$ Solving the first equation for $x$ gives $$ x = -\frac\mu2 C^{-1}e. $$ However, $x^Te=1$ is required, so $$ \mu = -2 (e^TC^{-1}e)^{-1}. $$ And we get $$ x= \frac{C^{-1}e}{e^TC^{-1}e}. $$

$\endgroup$
  • $\begingroup$ Great! This correctly addresses my first question. What about the second one? Would still be possible to get a similar result with positivity constraints on the x? $\endgroup$ – albarji Feb 16 '17 at 17:33
  • $\begingroup$ @albarji No, with additional non-negativity constraints this is much harder to solve. $\endgroup$ – daw Feb 16 '17 at 18:07

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.