1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Are you minimizing with respect to both $M $ and $w $? $\endgroup$
    – littleO
    Commented Jul 17, 2016 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
    Commented Jul 17, 2016 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$ Commented Jul 18, 2016 at 21:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented Jul 18, 2016 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
    Commented Jul 18, 2016 at 23:19
  • $\begingroup$ You are right. Makes sense! Thanks for clarifying! $\endgroup$ Commented Jul 19, 2016 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .