Let $\mathcal{X} = \{x_1,\dots,x_N\}$ be a finite set in $\mathbb{R}^d$ and let $S$ and $D$ be two subsets of $\mathcal{X}\times \mathcal{X}$, with $S \cap D = \emptyset$. If $M$ is a positive semidefinite matrix of dimension $d$, we denote it $M \succeq 0$, and the norm associated to $M$, $\|x\|_M := \sqrt{x^TMx}$ (assuming that vectors are represented as column matrices).

I'm studying the following optimization problem:

\begin{align} \min_M &\quad \sum_{(x_i,x_j) \in S} \|x_i-x_j\|_M^2 \\ \text{s.t.: } &\quad \sum_{(x_i,x_j)\in D}\|x_i-x_j\|_M \ge 1 \\ &\quad M \succeq 0. \end{align}

It's my first time working with this kind of problems and I think I don't know many of the tools to approach (formally) this problem, so I'm having many doubts. I would like to know, if possible, how are the techniques to solve the questions I'm going to ask, in order to be able to apply them to new similar problems.

1- My first question is about convexity. I have read that this problem is convex, but I'm not used to the concept of convex problem. I'm supposing that this means that the objective function and all the restrictions are convex. If this is true, which are the techniques to prove the convexity of each item? At the moment, the only tool I have is the definition. Also I would like to know if there is any way to detect (intuitively) the convexity of a problem.

Finally, also about convexity, in which cases a convex problem guarantees the existence and uniqueness of a minimum? Because not all convex functions reach a minimum, so I would like to be able to rigorously show this too.

2- My second question is about the equivalence of this kind of problems. I have read that the previous problem is equivalent to the following one:

\begin{align} \max_M &\quad \sum_{(x_i,x_j) \in D} \|x_i-x_j\|_M \\ \text{s.t.: } &\quad \sum_{(x_i,x_j)\in S}\|x_i-x_j\|_M^2 \le 1 \\ &\quad M \succeq 0. \end{align}

First of all, in which sense are the two problems equivalent? Where I read this there wasn't any description of the 'equivalent' concept. Can that mean that both problems reach their minimum/maximum at the same point, or at proportional points, or just there is a correspondence between the solutions of both problems? And once the definition is cleared up, which are the ways to prove that equivalence?

Thanks in advance.

  • $\begingroup$ your problem is not convex due to the constraint function; should be straightforward to find a counterexample using the definition of convexity $\endgroup$ – LinAlg Jul 5 '18 at 12:38
  • $\begingroup$ I forgot to add the sqrt in the definition of the norm, sorry. $\endgroup$ – gtf Jul 5 '18 at 12:47
  • $\begingroup$ did you appreciate my answer? $\endgroup$ – LinAlg Jul 26 '18 at 19:05
  • $\begingroup$ Yes, I +1-ed it. But I'm still confused about the equivalence. Even trying with examples in $1\times 1$ matrices I don't find in which way can we say the problems are equivalent. $\endgroup$ – gtf Jul 27 '18 at 10:50
  • $\begingroup$ The problems are not equivalent in the sense that they find the same solution, but equivalent in the sense that find a solution that is good to both objectives (in Pareto sense). If you replace 1 in the second problem with the objective value of the first problem, you may find the same solution in both problems. $\endgroup$ – LinAlg Jul 27 '18 at 12:33
  1. a convex optimization requires the functions themselves to be convex (not just the sets defined by those functions). The functions are $$f_0(M) = \sum_{(x_i,x_j) \in S} x_i^T M x_j \text{, and } f_1(M) = 1 - \sum_{(x_i,x_j) \in D} \sqrt{ x_i^T M x_j}.$$ The first function is linear and hence convex. For the second function, the negative square root is convex, sums of convex functions are convex, and convex functions of linear functions are also convex. A solution is guaranteed unique if the objective is strictly convex (which yours is not). However, all solutions have the same value (no local optima). Your solution set is closed, so if an infimum exists, it is attained. Your problem appears feasible (as long as there is an $(x_i,x_j) \in D$ such that $x_i-x_j \neq 0$) and is bounded below by 0, so an optimal solution exists.

  2. you could look at your problem as finding a trade-off between $\sum_{(x_i,x_j) \in S} \|x_i-x_j\|_M^2$ and $\sum_{(x_i,x_j)\in D}\|x_i-x_j\|_M$. Both problems find a point on the pareto curve.


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.