Questions tagged [qcqp]

A quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic functions.

Filter by
Sorted by
Tagged with
8
votes
5answers
315 views

Nearest matrix orthogonally similar to a given matrix

Given $A,B\in\Bbb R^{n\times n}$ is there technique find $$\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_F\mbox{ or }\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$$ within additive approximation error in $\...
7
votes
2answers
232 views

Eigenvalue problem with two quadratic constraints

I would like to solve the following problem: $$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \mathbf{x}^T\mathbf{B}\mathbf{x} = 0\\ & \...
4
votes
3answers
1k views

Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres

For $X = (x_1^T,\ldots,x_N^T)^T \in \mathbb{R}^{Nm \times 1}$, where $x_i \in \mathbb{R}^{m \times 1}$ for $i \in \{1,\ldots,N\}$, $A \in \mathbb{R}^{r \times Nm}$, and $r \geq Nm$, I want to obtain a ...
1
vote
0answers
222 views

Is this QCQP convex or nonconvex?

\begin{equation} \begin{split} \min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x \end{split} \end{equation} s.t. $$ g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\} $$ $$ g_i(x)=\frac{...
11
votes
2answers
3k views

Linearly constrained eigenvalue problem

Suppose I'd like to: \begin{align} \mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\ && \...
1
vote
1answer
588 views

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 ...
3
votes
2answers
459 views

A certain type of quadratic constrained quadratic program (QCQP)

Let $P_1$, $P_2$ be two Hermitian matrices. Can anyone comment on the following QCQP? $$\begin{array}{ll} \text{minimize} & z^{H} z\\ \text{subject to} & z^{H} P_1 z +1 \leq 0\\ & z^{H} ...
1
vote
1answer
347 views

Solving a QCQP problem with sparse regularization

I want to solve the follong QCQP problem: $$ \mbox{Minimize}\quad\beta^TA\beta+\mu\Omega(\beta)$$ $$ \mbox{s.t.}\quad\beta^TB\beta=1 \quad\mbox{and}\quad\beta\ge0 $$ where $A$ and $B$ are both ...
2
votes
2answers
835 views

Complexity of convex quadratically constrained quadratic programming (QCQP)

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP)? Any references?