# A quadratic program with non-negativity constraints

Is there any closed form solution for the optimal value of the folowing optimization problem?

$$\begin{array}{ll} \text{minimize} & (\mathbf{x} - \mathbf{y})^{\mathrm{T}}\mathbf{B}(\mathbf{x} - \mathbf{y}) + \mathbf{1}^{\mathrm{T}} \mathbf{y} \\ \text{subject to} & \mathbf{x}, \mathbf{y} \geq \mathbf 0\end{array}$$

where $$\mathbf{1}$$ is an all-one vector and $$\mathbf{B}$$ is a symmetric indefinite matrix.

• B is indifinite. Dec 21 '19 at 20:43
• Suppose $\mathbf{B}$ is a negative semidefinite matrix, the objective value must be $-\infty$. Dec 26 '19 at 7:33

Is the problem well-defined in case $$B$$ has a negative eigenvalue?
Consider an unit eigenvector $$v$$ corresponding to a negative eigenvalue $$\lambda$$ of $$B$$. Since any vector $$v$$ can be written as the difference of two vectors each having non-negative elements, we have $$v=x_v-y_v$$ where $$x_v\geq 0, ~y_v\geq 0$$. The cost function will then evaluate at $$\{x_v, y_v\}$$ to: $$\lambda + 1^\top y_v$$. Scaling $$v$$ by $$K>0$$ would then yield: $$K^2\lambda + K\left(1^\top y_v\right)$$, which is clearly not bounded below.