Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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 $

This was your original problem.

share|improve this answer
    
There are several software packages for solving such an SDP, including SDPA (written in C++) and CSDP (in C) –  Brian Borchers May 21 '13 at 3:23
    
As I recall, you can also get to this formulation using the S-lemma. –  Brian Borchers May 21 '13 at 3:35
    
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
    
See appendix B of "Convex Optimization" by Boyd and Vandenberghe. –  Brian Borchers May 21 '13 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.