1
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ You determine $y^*$ via differentation, forgetting about the nonnegativity constraints, which is why you end up with negative numbers. There is no direct formula for $y^*$. Try to use a QP solver. $\endgroup$ – LinAlg Dec 12 '16 at 20:08
  • $\begingroup$ @ LinAlg...By QP solver you mean inbuilt functions in Matlab like mathworks.com/help/optim/ug/quadprog.html ? $\endgroup$ – NAASI Dec 12 '16 at 20:18
  • $\begingroup$ Yes, quadprog is a good solution method. $\endgroup$ – LinAlg Dec 12 '16 at 20:42
0
$\begingroup$

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.

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