0
$\begingroup$

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?

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

Matrix $Q$ has zero eigenvector that isn't orthogonal to $q$. That means that without constraints the function has no global minimum.

So the minimum of the problem is achieved on a boundary. We have 4 linear boundaries and 3 points (vertices). We solve boundary problems with Lagrange multipliers.

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.