How can I minimize a quadratic function which some of the quadratic terms have a coefficient of zero?

e.g. $$\min x_1^2 + x_1 + x_2$$

(subject to some linear constraints on $$x_i$$)

As a quadratic programming problem, this is

$$\min q^\intercal x + \frac{1}{2}x^\intercal Q x$$

with

$$Q = \begin{pmatrix}2 & 0 \\0 & 0\end{pmatrix}, q = \begin{pmatrix}1 \\ 1 \end{pmatrix}$$

However $$Q$$ is not positive-definite and therefore a standard QP solver cannot be used. What other methods can I use?

• What are the linear constrains? – Vasily Mitch Oct 8 '19 at 8:55
• I wrote this example without constraints thinking they do not matter for the question, but perhaps I'm mistaken-would they? – njd42 Oct 8 '19 at 9:18
• Yes, they do. Depending on the constrains, the problem can have on have not a reasonable answer – Vasily Mitch Oct 8 '19 at 9:20
• $x_1 - x_2 \le 0$ and $-x_1 - x_2 \le 0$ and $|x_1| < c$ for some $c>0$ – njd42 Oct 8 '19 at 9:25
• A standard QP solver will handle a semidefinite $Q$. In practice it is very rare that all optimiziation variables appear in the quadratic term. – Michal Adamaszek Oct 8 '19 at 10:54

Matrix $$Q$$ has zero eigenvector that isn't orthogonal to $$q$$. That means that without constraints the function has no global minimum.
For boundaries $$x_1=\pm c$$ there is no minimum. For boundary $$x_1-x_2=0$$, there is minimum $$f=-1$$ at $$(-1,-1)$$, which lies outside of condition $$x_1+x_2\ge0$$. For boundary $$x_1+x_2=0$$ there is minimum $$f=0$$ at $$(0,0)$$ which coincides with one vertex. For other two vertices $$(-c,c)$$ and $$(c,c)$$, $$f=c^2>0$$ and $$f=c^2+2c>0$$.
Thus, we conclude that the minimum $$f=0$$ is achieved at vertex $$(0,0)$$.