$\min_{\beta}\beta^{T} A \beta$

$s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$

Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$

I saw in one paper saying that it could be solved via its semidefinite programming relaxation by adding an auxiliary variable $B \in \mathbb{R}^{M \times M}$ like this:

$\min_{\beta ,B}trace(AB)$

$s.t.trace(CB)=1$,

$\beta \geqslant 0$,

$\begin{bmatrix} 1 & \beta^{T}\\\\ \beta& B \end{bmatrix}\succeq 0$

where $\succeq 0$ means left matrix is positive semidefinite.

I don't get how this is done, and besides, how to solve such a problem using any possible C/C++ software?

Thanks. $;)$

-

It's helpful if you cite the paper in which you saw something that you're asking a question about- we could provide a better answer if we knew where the question came from.

First, assume without loss of generality that $A$ and $C$ are symmetric matrices. It's easy to take these quadratic forms and write them in terms of symmetric matrices.

I believe that this problem transformation requires that $A$ be a positive semidefinite matrix- see below.

We'll begin with your second problem and show that it is equivalent to the original problem. We begin with

$\min \mbox{tr}(AB)$

subject to

$\mbox{tr}(CB)=1$

$\beta \geq 0$

$\left[ \begin{array}{cc} 1 & \beta^{T} \\\ \beta & B \end{array} \right] \succeq 0$

By Schur's theorem, the constraint

$\left[ \begin{array}{cc} 1 & \beta^{T} \\\ \beta & B \end{array} \right] \succeq 0$

is equivalent to

$B \succeq \beta \beta^{T}$

Note that we've implicitly restricted $B$ to being a symmetric matrix.

Next, write $B$ as

$B= \beta \beta^{T} + LL^{T}$

where $L$ is the (slightly generalized) Cholesky factor of $B- \beta \beta^{T}$. If $B-\beta \beta^{T}$ is singular, then $L$ would be singular or even $0$.

Then our problem is equivalent to

$\min \mbox{tr}( A ( \beta \beta^{T} + LL^{T} ) )$

subject to

$\mbox{tr}(CB)=1$

$\beta \geq 0$

$B=\beta \beta^{T} + LL^{T}$

By the property $\mbox{tr}(DEF)=\mbox{tr}(FDE)$, this problem is equivalent to

$\min \mbox{tr}(\beta^{T}A\beta + L^{T}AL)$

subject to

$\mbox{tr}(CB)=1$

$\beta \geq 0$

$B=\beta \beta^{T} + LL^{T}$

Note that because $A \succeq 0$, $\mbox{tr}(L^{T}AL) \geq 0$ for all $L$, and the term is minimized when $L=0$.

Thus our problem is equivalent to:

$\min \mbox{tr}(\beta^{T}A\beta)$

subject to

$\mbox{tr}(CB)=1$

$\beta \geq 0$

$B=\beta \beta^{T}$

Since $B=\beta \beta^{T}$, and by the cyclic property of $\mbox{tr}()$, this is equivalent to

$\min \mbox{tr}(\beta^{T}A\beta)$

subject to

$\beta^{T}C\beta=1$

$\beta \geq 0$

On second thought, although approach I sketched out is sufficient to show that the SDP is a relaxation of the original problem, it's not enough to show that the relaxation is exact (I forgot to account for the $L^{T}CL$ term in the constraint. I'm afraid that you need the machinery of the S-lemma to show that the relaxation is exact. –  Brian Borchers May 21 '13 at 4:02
Thank you very much for your detailed answer!$:-)$ I read it carefully and basically understand your proof. The paper I quote is Yen-Yu Lin, Multiple Kernel Learning for Dimensionality Reduction.In fact I need this relaxation to be exact, but I don't quite get what S-lemma is, Could you please show some links or pdfs? And how to use it to make the relaxation exact is also new to me. –  Journey May 21 '13 at 7:10