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.
14
questions
15
votes
2
answers
6k
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\\
&& \...
- 713
8
votes
5
answers
473
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 $\...
- 13.7k
7
votes
2
answers
689
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\\ & \...
- 71
4
votes
3
answers
2k
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 ...
- 53
4
votes
2
answers
586
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,371
3
votes
2
answers
3k
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?
- 145
2
votes
3
answers
2k
views
Solving a non-convex quadratically-constrained quadratic program
I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is ...
- 149
2
votes
1
answer
229
views
Minimizing quadratic objective under orthogonality constraints
The following problem is motivated from Generalized Procrustes Analysis. I am wondering if it is possible to obtain a closed form minimizer (which may involve SVD or some other decomposition of a ...
- 141
2
votes
0
answers
154
views
How to solve a QCQP where constraints are balls?
I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$
\begin{equation}
\begin{aligned}
& \underset{\theta}{\text{minimize}}
& & \...
1
vote
1
answer
433
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 ...
- 133
1
vote
1
answer
650
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 ...
- 13
1
vote
0
answers
389
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
0
votes
0
answers
30
views
Efficient algorithms to find the global minimum of a non-convex quadratically-constrained quadratic program
I am working on a problem involving a non-convex quadratically-constrained quadratic program and am seeking efficient algorithms to find its global minimum. The problem is structured as follows:
Fix ...
0
votes
0
answers
33
views
Find a complex matrix on a unit sub-spheres
I am new to optimization theory. I have a following question. For a given $X = [x_1 x_2 \ldots x_N] \in \mathbb{C}^{N \times N}$, where $x_i \in \mathbb{C}^{N\times 1}$ for $i \in \{1,\ldots,N\}$, $U =...
