Why are constraints not met in this quadratic program?

Question

This question is a followup question of the question How to find a minimizer with only positive entries? answered by Rodrigo de Azevedo.

We have the quadratic program (QP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & x_1 = 1\\ & x_2, \dots, x_n \geq 0\end{array}$$

which can be written as the following QP in $\mathrm y \in \mathbb R^{n-1}$

$$\boxed{\begin{array}{ll} \text{minimize} & \mathrm y^{\top} \mathrm Q \, \mathrm y - 2 \, \mathrm r^{\top} \mathrm y + s\\ \text{subject to} & \mathrm y \geq 0_{n-1}\end{array}}$$

where

$$\mathrm x = \begin{bmatrix} 1\\ \mathrm y\end{bmatrix}$$

and

$$\mathrm A = \begin{bmatrix} s & -\mathrm r^{\top}\\ -\mathrm r & \mathrm Q\end{bmatrix}$$

The solution to new prog is $y^{*}:=\mathrm{Q^{-1}}\mathrm{r}$.

My problem is that this does not always result in $\mathrm y \geq 0_{n-1}$. Few entries turn out to be less than zero.

My questions are

1. Why are constraints not met in this case?
2. What do I need to do to ensure that $\mathrm y^{*} \geq 0_{n-1}$ always?

Answer 1

Let me define $$f(y)=y^TQy-2r^Ty+s$$Then the so-called primal problem is $$\min_{y}f(y) \\ s.t.~~y\geq 0_{n-1}$$Note that differentiating the objective and equating to zero gives you the solution (technically speaking the stationary points) only if there are no constraints involved and your objective is convex. If you have constraints, you need to look at the Lagrangian function. In your case, this will be $$L(y,\lambda)=y^TQy-2r^Ty+s-\lambda^Ty$$ where $\lambda>0_{n-1}$. We obtain this by subtracting (adding) the positive (negative) constraint from the objective with a multiplier vector called the lagrangian dual variable. Now you need to minimize this w.r.to $y$. Differentiating this and equating to zero, gives you the solution as $$y^*=Q^{-1}r-(1/2)Q^{-1}\lambda$$ Substitute this into $L(y,\lambda)$. Then the so-called Lagrangian dual problem is $$\max_{\lambda}g(\lambda)$$where $g(\lambda)=L(y^*,\lambda)$ is what you obtain after substitution in $L(y,\lambda)$. Now the theory is this, if $\lambda^*$ is the solution to the dual problem and $\hat{y}$ is the solution to the primal problem, then $$g(\lambda^*)\leq f(\hat{y})$$ where $f(y)$ is the value of your original objective and $\hat{y}$ is the true solution to your primal problem. If $f(y)$ is convex, then equality holds, and also $\hat{y}=y^*$. In your case, $f(y)$ is convex iff $Q$ is positive semi-definite.