Skip to main content

solve A non-convex quadraticquadratically constrained quadratic programmingprogram

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

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

Herewhere $A,C\in \mathbb{R}^{M\times M}$,$A, C\in \mathbb{R}^{M\times M}$ and $\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. $;)$

solve non-convex quadratic constrained quadratic programming

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

A non-convex quadratically constrained quadratic program

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

Source Link

solve non-convex quadratic constrained quadratic programming

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