1
$\begingroup$

$$\begin{array}{ll} \text{minimize} & \beta^{T} A \beta\\ \text{subject to} & \beta^{T} C \beta=1\\ & \beta \geqslant 0\end{array}$$

where $A, C\in \mathbb{R}^{M\times M}$ and $\beta \in \mathbb{R}^{M}$. I saw in one paper 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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ There are several software packages for solving such an SDP, including SDPA (written in C++) and CSDP (in C) $\endgroup$ Commented May 21, 2013 at 3:23
  • $\begingroup$ As I recall, you can also get to this formulation using the S-lemma. $\endgroup$ Commented May 21, 2013 at 3:35
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 21, 2013 at 4:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Journey
    Commented May 21, 2013 at 7:10
  • 1
    $\begingroup$ See appendix B of "Convex Optimization" by Boyd and Vandenberghe. $\endgroup$ Commented May 21, 2013 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .