0
$\begingroup$

After reading n times the four first sections of the 4th Chapter of J.Dattorro's book (Convex Optimization & Euclidean Distance Geometry). I am confused between yes or no, every extreme point of $\mathbf K$ ( intersection of a polyhedron and the positive semidefinite cone), verifies the upper bound of Barvinok. (to get to that specific question I have a bunch of transitive questions, and it will be helpful if someone give me some clarification.)

Let : $$ \mathcal A \triangleq \{ X \in | \mathbb{S}^n \left\langle A_j,X \right\rangle = b_j \, \ j=1 \cdots m \} $$ So, $$\mathbf K \triangleq \mathcal A \cap \mathbb S_+^n =\{ X \in \mathbb S_+^n | \ \left\langle A_j,X \right\rangle = b_j \ , \ j=1 \cdots m \} $$

$ A_j \in \mathbb{S}^n $ and $ b_j $ are $m$ scalars, and $\mathbb{S}^n$ , $\mathbb S_+^n$ are the notation of symmetric matrices space and positive semidefinite cone respectively.

Theorem of Barvinok says that if $\mathbf K$ is not empty, it has an extreme point $X_0$ satisfies :

$$ \mathrm{rank}(X_0) \leq \left\lfloor \frac{\sqrt{8m+1}-1}{2} \right\rfloor $$

Dattorro introduces the following (SDP) :

\begin{array}{cc} Minimize & \left\langle C,X \right\rangle \\ S.t & X \in \mathbf K \end{array} C is an arbitrary symmetric matrix.

He shows by an example that a problem of this form may have a minimizer of rank that exceeds the bound given by Barvinok, So he introduced an algorithm that has a purpose to give an optimal solution that verifies the bound from a former minimizer that doesn't verify it ( perturbation technique). Thought, What relay does this algorithm is to locate an extreme point of $\mathbf K$ that has an optimal value.

( The existence of such matrix is not very clear for me, and it is not announced explicitly neither in that book, nor in others books and papers announcing the Barvinok Theorem*, [ this is my first question, does such minimizer that verifies the bound always exists ?])

To make things consistent in my head from what the algorithm does and what it should do, I think all extreme points that minimize the (SDP) must respect the Barvinok's bound. [Is That True?]

After some research in the book "Michel Deza & M.Laurent: Geometry of Cuts and Metrics" which Dattorro refers to, I find a theorem that can remove my confusion.

Theorem 31.5.3 :Let $A \in \mathbf K$ and let $\mathcal F_{\mathbf K} (A)$ be the smallest face of $ \mathbf K$ that contains $A$. Suppose that $A$ has rank $r$ and that $A = QQ^T$ , where $Q$ is an $n × r$ matrix of rank $r$. Then, $$ \mathrm{dim} \mathcal F_{\mathbf K} (A) =\frac{r(r+1)}{2} − \mathrm{rank} \{Q^T A_j Q | j = 1,\cdots,m \}.$$

I know that $A$ is an extreme point iff $\mathrm{dim} \mathcal F_{\mathbf K} (A) = 0$, so if $\mathrm{rank} \{Q^T A_j Q | j = 1,\cdots,m \} \leq m$ it is easy to prove that when $A$ is an extreme point it necessarily verifies the upper bound. the problme is that I don't know the meaning of the notation $\mathrm{rank} \{Q^T A_j Q | j = 1,\cdots,m \}$ [what is it?]

  • I have additional questions :

Does that (SDP) have always an extreme point as a minimizer? if yes, Does it have an other minimizer which is not an extreme point of $\mathbf K$?

Sorry, I tried my best to organize my question, but I know it still has ambiguities due to my poor language, but please let me know and I will try to reformulate any part of my question.

$\endgroup$
  • $\begingroup$ At least I got the Tumbleweed badge! -_-" $\endgroup$ – Aymane Fihadi Nov 3 '14 at 16:54
1
$\begingroup$

The existence of such matrix is not very clear for me, and it is not announced explicitly neither in that book, nor in others books and papers announcing the Barvinok Theorem*, [ this is my first question, does such minimizer that verifies the bound always exists ?]

Yes. A solution meeting Barvinok's upper bound on rank always exists.

Existence of a matrix satisfying Barvinok's upper bound on rank is guaranteed by Barvinok's theorem (section 2.9.3 of Convex Optimization Euclidean book). The perturbation technique in section 4.3.1 guarantees existence of a matrix satisfying Barvinok's upper bound while simultaneously optimizing the prototypical semidefinite program (SDP) with the same optimal objective value as that prior to perturbation.

$\endgroup$
1
$\begingroup$

${\rm rank}\{Q^TA_j\,Q~|~j=1,\ldots,m\}~$ means $~{\rm rank}\!\left[\,{\rm vec\,} Q^{\rm T}A_1Q ~~{\rm vec\,} Q^{\rm T}A_2Q\;\cdots\;{\rm vec\,} Q^{\rm T}A_mQ\,\right]~$ where $~{\rm vec}~$ means vectorization of a matrix by stacking columns.

$\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.