Consider the following optimization problem:
$$\begin{array}{ll} \text{minimize} & \mathbf{x}^{T} \mathbf{A} \mathbf{x}\\ \text{subject to } & \mathbf{x}^{T} \mathbf{P}_i \mathbf{x} > 0, \quad i \in \{1, \dots, n-1\}\\ & \mathbf{x}^{T} \mathbf{e}_1 = 1\end{array} $$
where $\mathbf{x} \in \mathbb{R}^{n \times 1}$, $\mathbf{A} \in \mathbb{R}^{n \times n}$ is positive semidefinite. The matrix $\mathbf{P}_i \in \mathbb{R}^{n \times n}$ is an all-zero matrix except $1$ at its $i^{\text{th}}$ diagonal entry and $-1$ at its $(i+1)^{\text{th}}$ diagonal entry. The vector $\mathbf{e}_1$ is the first column of the identity matrix.
It turns out that this problem is a non-convex QCQP since $\mathbf{P}_i$'s are not definite.
This problem is to minimise a quadratic function, where $\mathbf{x}_1 = 1$ and $1 > \vert \mathbf{x}_2 \vert > \ldots > \vert \mathbf{x}_n \vert$.
Any suggestions on how to solve this problem are highly appreciated.
Thanks a lot.
I would cast this as a mixed-integer quadratic program. To do so, we first define new continuous variables $y_2,\dots,y_n$ and introduce these constraints: $$-y_k\leq x_k\leq y_k, \quad k=2,3,\dots, n, \quad y_2=1$$ Then we define new binary variables $z_2,\dots,z_{n-1}\in\{0,1\}$: $$x_k \geq y_{k+1} - 2 z_k, \quad -x_k \geq y_{k+1} - 2 ( 1 - z_k ), \quad k=2,3,\dots, n-1$$ This implies that, for any feasible solution, $$ x_k \geq y_{k+1} \geq |x_{k+1}| \quad \text{or} \quad - x_k \geq y_{k+1} \geq |x_{k+1}| \quad\Longrightarrow\quad |x_k| \geq |x_{k+1}|$$ These additional variables and constraints replace the quadratic constraints, leaving you with this: \begin{array}{ll} \text{minimize} & \sum_{ij} A_{ij} x_ix_j \\ \text{subject to} & -y_k \leq x_k \leq y_k, \quad k=2,3,\dots, n \\ & x_k + 2 z_k \geq y_{k+1}, \quad k=2,3,\dots, n-1 \\ & -x_k + 2(1-z_k) \geq y_{k+1}, \quad k=2,3,\dots, n-1 \\ & x_1 = y_2 = 1 \\ & z_2, z_3, \dots, z_{n-1} \in\{0,1\} \end{array} This can be solved with any mixed-integer quadratic programming solver.