# What is the easiest way to optimize the weighted sum of L2 norms?

I have the following cost function (solving for $M$ - the $x_i$s are known):

minimize $\sum_i\sum_j(w_{ij} \cdot (x_i-x_j)^T\cdot M\cdot(x_i-x_j))$

($w_{ij} \in [-1,1]$)

subject to: $M \succeq 0$ ($M$ is positive semi definite)

Here is where I m having trouble:

The $(x_i-x_j)^T\cdot M\cdot(x_i-x_j)$ part is convex (since it is essentially squared L-2 norm in a space transformed by M). And the weighted sum of convex functions is also convex as long as the weights are positive. But since the $w_ij$s can be negative, I think the overall cost function is non-convex.

I was wondering if there is a better way to formulate this to make is convex or if there is a way to solve this problem as is?

I am fairly new to convex optimization. Any help would be appreciated!

Thanks!

• Are you minimizing with respect to both $M$ and $w$? – littleO Jul 17 '16 at 1:39
• "Essentially a squared 2-norm" suggests you are thinking of the objective as a function of $x$. You should think of it as a function of $M$. It's just a linear function of $M$. – littleO Jul 17 '16 at 1:51
• @littleO thanks for clarifying, It is a function of M, not x. And the w's are not variable, I already have them. – dragon12321 Jul 18 '16 at 21:54

Assuming that the numbers $w_{ij}$ are not variables, each term in the objective function is a linear function of $M$. That's true even if $w_{ij} < 0$ for some $i,j$. So the objective function is convex.
• Thank you. Just as a follow up, wouldn't having a negative $w_{ij}$ make that part of the summation concave (since it is negative convex)? Making the entire summation non-convex? In addition, would you have any ideas on how to stop it from collapsing to 0? I m getting M as a zero matrix. – dragon12321 Jul 18 '16 at 21:57
• Do you agree that the $ij$th term in the objective is a linear function of $M$, even if $w_{ij}$ is negative? Any linear function is convex (and also concave). – littleO Jul 18 '16 at 23:19