3
$\begingroup$

Let $A$ be an $n \times n$ positive semidefinite matrix and $\forall k, x_k \in \mathbb{R}^n$. The distance with respect to this matrix is defined as

$ \|x_i -x_j\|_A := \sqrt{(x_i-x_j)^TA(x_i-x_j)} $.

Now, suppose we have the constraint $$\sum_{(x_i,x_j) \in D} \|x_i -x_j\|_A = \sum_{(x_i,x_j) \in D} \sqrt{(x_i-x_j)^TA(x_i-x_j)} \ge 1$$ I know (by reading in a paper), that this is a $\textbf{convex constraint in } \mathbf{A}$, but cannot verify that (because of the sqrt).

Can anyone help me please or give a hint? Why is it convex in $A$? Is it? More importantly, what type of convex constraint is that (linear, quadratic, SOC, SDP?)

$\endgroup$
5
  • $\begingroup$ Any thoughts can be helpful. $\endgroup$
    – user25004
    Oct 24, 2013 at 4:10
  • $\begingroup$ How is $D$ defined? $\endgroup$
    – triple_sec
    Oct 24, 2013 at 4:18
  • $\begingroup$ $D$ is just a set of pairs. Some domain. $\endgroup$
    – user25004
    Oct 24, 2013 at 4:28
  • $\begingroup$ This is equivalent to asking if $\|x\|_A$ is a concave function of $A$. $\endgroup$
    – user25004
    Oct 24, 2013 at 4:36
  • $\begingroup$ Maybe should compute the Hessian and prove it is negative semi-definite. $\endgroup$
    – user25004
    Oct 24, 2013 at 5:48

1 Answer 1

1
$\begingroup$

This is not an answer and it is just my thoughts on it. May be you can convert it into a set of equivalent constraints.

\begin{align} \sum_{i,j}t_{ij}&\geq 1 \\\ t_{ij} &\geq 0 \\\ \|x_i -x_j\|_A &\geq t_{ij} \end{align} You can square both sides of the third inequality.

$\endgroup$

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.