0
$\begingroup$

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 some natural numbers $I,J\geq2$ and let $K=I+J+2IJ$. Fix some $(c_1,\ldots,c_I)\in(0,1)^I$ such that $\sum_{i=1}^{I}c_i<1$. The problem is given by \begin{align*} \underset{\mathbf{x}\in\mathbb{R}^K}{\text{minimize}}&\quad\frac{1}{2}\mathbf{x}^T\mathbf{P}_0\mathbf{x}+\mathbf{q}_0^T\mathbf{x}\\ \text{subject to}&\quad\frac{1}{2}\mathbf{x}^T\mathbf{P}_m\mathbf{x}+\mathbf{q}_m^T\mathbf{x}+r_m\leq0,\quad\forall m\in\mathcal{M}\subseteq\mathbb{N} \\ &\quad\mathbf{A}\mathbf{x}=\mathbf{b} \end{align*} where the index set for the inequality constraints $\mathcal{M}$ can be partitioned into four cells, denoted $\mathcal{M}_1$, $\mathcal{M}_2$, $\mathcal{M}_3$, and $\mathcal{M}_4$, respectively. The properties of the coefficients are as follows.

  1. For the objective function, we have $$ \mathbf{P}_0= \begin{pmatrix} \mathbf{I}_J & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{pmatrix} $$ positive semi-definite, and $$ \mathbf{q}_0=-(q_{01},\ldots,q_{0J},0,\ldots,0)^T $$ where $(q_{01},\ldots,q_{0J})\in\Delta(\{1,\ldots,J\})$.

  2. We have four sets of inequality constraints.

    • For $m_{1k}\in\mathcal{M}_1$ with $k\in\{1,\ldots,K\}$, we have $$ \mathbf{P}_{m_{1k}}=\mathbf{0}, \quad \mathbf{q}_{m_{1k}}=-\mathbf{e}_k, \quad\text{and}\quad r_{m_{1k}}=0, $$ where $\mathbf{e}_k$ denotes the $k$-th standard unit vector for $\mathbb{R}^K$.
    • For $m_{2i}\in\mathcal{M}_2$ with $i\in\{0,1,\ldots,I\}$, we have $$ \mathbf{P}_{m_{2i}}=\mathbf{0}, \quad \mathbf{q}_{m_{2i}}= \begin{pmatrix} \mathbf{e}_{i+1}\otimes\mathbf{\iota}_J \\ \mathbf{0} \end{pmatrix}, \quad r_{m_{20}}=-1, \quad\text{and}\quad r_{m_{2i}}=-c_i\ \forall i>0, $$ where $\mathbf{e}_{i+1}$ denotes the $(i+1)$-th standard unit vector for $\mathbb{R}^{I+1}$, and $\mathbf{\iota}_J$ denotes the $J$-vector of ones.
    • For $m_{3ij}\in\mathcal{M}_3$ with $i\in\{1,\dots,I\}$ and $j\in\{1,\ldots,J\}$, we have $$ \mathbf{P}_{m_{3ij}}=\mathbf{E}_{s(i,j),t(i,j)}, \quad \mathbf{q}_{m_{3ij}}=\mathbf{0}, \quad\text{and}\quad r_{m_{3ij}}=0, $$ where $\mathbf{E}_{st}$ denotes the matrix unit with the nonzero entry at the $s$-th row and $t$-th column, with $s(i,j)=j+iJ$ and $t(i,j)=j+iJ+I+J+IJ$. $\mathbf{E}_{s(i,j),t(i,j)}$ is indefinite for all $i,j$.
    • For $m_{4i}\in\mathcal{M}_4$ with $i\in\{1,\ldots,I\}$, we have $$ \mathbf{P}_{m_{4i}}= \begin{pmatrix} \mathbf{e}_{i+1}\otimes\mathbf{\iota}_J \\ \mathbf{0} \end{pmatrix} \mathbf{e}_{i+(I+1)J}^T, \quad \mathbf{q}_{m_{4i}}=-c_i\mathbf{e}_{i+(I+1)J} \quad\text{and}\quad r_{m_{4i}}=0, $$ where $\mathbf{e}_{i+(I+1)J}$ denotes the $(i+(I+1)J)$-th standard unit vector for $\mathbb{R}^K$, and $\mathbf{e}_{i+1}$ denotes the $(i+1)$-th standard unit vector for $\mathbb{R}^{I+1}$.

  3. For the equality constraints, we have $$ \mathbf{A}= \begin{pmatrix} \mathbf{\iota}_I\otimes\mathbf{I}_J & \mathbf{0} & \mathbf{I}_I\otimes\mathbf{\iota}_J & -\mathbf{I}_{IJ} \end{pmatrix} \in\mathbb{R}^{IJ\times K} \quad\text{and}\quad \mathbf{b}= \begin{pmatrix} \mathbf{b}_1 \\ \vdots \\ \mathbf{b}_I \end{pmatrix} $$ where $\mathbf{b}_i\in\Delta(\{1,\ldots,J\})$ for all $i=1,\ldots,I$.

Any pointers to relevant literature and algorithms would be very helpful. Thanks a lot!

Improve this question
$\endgroup$

0

Reset to default

You must log in to answer this question.