quadratic programming with a fourth power term

128 Views Asked by At

I've the following modified Quadratic Program (QP) with an additional fourth power term. Suppose $X\in\mathbb{R}^{k \times n}$

$$ X^{\text{opt}} = \arg\min_{X \geq \mathbf{0}} \,\,\,\,tr(X^{\intercal} Q X)+ \dfrac{1}{2} \| X^TX\|^2$$

where $Q\in Sym(n)$ is positive-definite. I wish to find an efficient solution for this problem that converges fastly. My idea is to write $X$ as

$$ X = (x_1, x_2, x_3, .. x_n)$$

where each $x_i \in \mathbb{R}^{k}$ is the column vector of $X$. Then by doing some algebra, the problem is essentially

$$ X^{\text{opt}} = \arg\min_{x_i \geq \mathbf{0}} \,\,\,\,\sum_{i,j} \alpha_{i,j} x_i^Tx_j + \frac{1}{2}(x_i^Tx_j)^2$$

where $\alpha_{i,j} = e_i^T Q e_j$ is the entry $Q_{ij}$.

I wonder if I can iteratively solve this problem in a stochastic gradient descent manner. For example, fixing $i $ I update $x_i$ by treating it like the problem $b^Tx_i + x_i^TAx_i$ and update the value $x_i$ accordingly

where $b = \sum_j \alpha_{i,j}x_j$ and $ A = \frac{1}{2} \sum_j x_jx_j^T$.

The question is, would such a strategy converge? And is there any better solution?