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!


  • $\begingroup$ Are you minimizing with respect to both $M $ and $w $? $\endgroup$ – littleO Jul 17 '16 at 1:39
  • 1
    $\begingroup$ "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 $. $\endgroup$ – littleO Jul 17 '16 at 1:51
  • $\begingroup$ @littleO thanks for clarifying, It is a function of M, not x. And the w's are not variable, I already have them. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – dragon12321 Jul 18 '16 at 21:57
  • $\begingroup$ 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). $\endgroup$ – littleO Jul 18 '16 at 23:19
  • $\begingroup$ You are right. Makes sense! Thanks for clarifying! $\endgroup$ – dragon12321 Jul 19 '16 at 2:32

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.