0
$\begingroup$

Consider the quadratic programming problem $$\min \frac{1}{2}\langle x, Qx \rangle + \langle c, x \rangle \\ \text{s.t.}\, Ax \geq b $$

where $Q$ is a positive definite matrix of dimension $n$, $A$ is a matrix of dimension $m \times n$, $c \in \mathbb{R}^{n}$, and $b \in \mathbb{R}^{m}$.

I need to derive the dual problem.

To that effect, I have formulated the Lagrangian:

$$L(x,\lambda) = \frac{1}{2}\langle x, Qx \rangle + \langle c, x \rangle + \langle \lambda, b-Ax\rangle $$

And after applying the rules of inner products, I get that $$ = \frac{1}{2}\langle x, Qx \rangle + \langle c, x \rangle + \langle \lambda, b \rangle - \langle \lambda, Ax \rangle \\ = \frac{1}{2}\langle x , Qx \rangle + \langle c, x \rangle - \langle A^{T}\lambda, x \rangle + \langle \lambda, b \rangle \\ = \langle \frac{1}{2}Q^{T}x,x \rangle + \langle c - A^{T}\lambda, x \rangle + \langle b, \lambda \rangle \\ = \frac{1}{2}Q^{T}x + c - A^{T}\lambda, x \rangle + \langle b, \lambda \rangle $$

So, the dual function should have the form $L_{D}(\lambda) = \langle b, \lambda \rangle + \inf \langle \frac{1}{2}Q^{T}x + c - A^{T}\lambda, x \rangle$

Usually, however, the $\inf$ is taken over the set of all $x$ in some set, and I'm not sure what that set should be in this case. All the problems I have seen thus far have a nonnegativity condition that $x \geq 0$, so this not only helps in figuring out what to take the infimum over, but also in formulating the dual problem.

Since I do not have the $x \geq 0$ condition in my problem, I am not sure what to do. Could somebody please help me finish it?

Thank you.

$\endgroup$
1
$\begingroup$

Note: I have assumed that $Q$ is symmetric below. Since $\langle x, Q x \rangle = \langle x, {1 \over 2} (Q + Q^T) x \rangle$, there is no loss of generality in doing so (just replace $Q$ by ${1 \over 2} (Q + Q^T)$ in the resulting formulae).

Informally, we have the primal $\inf_x \sup_{\lambda \ge 0} L(x,\lambda)$ and we swap the $\inf, \sup$ to get the dual $\sup_{\lambda \ge 0} \inf_x L(x, \lambda)$.

Since $Q>0$ we can solve $\inf_x L(x, \lambda)$ by solving for the first order conditions $Qx+c-A^T \lambda = 0$ to get $x = Q^{-1} (A^T \lambda -c)$.

Then the dual is $\sup_{\lambda \ge 0} L(Q^{-1} (A^T \lambda -c), \lambda)$.

$\endgroup$
  • $\begingroup$ isn't it $Q^{T}x+c-A^{T}\lambda = 0$, though? $\endgroup$ – ALannister Dec 4 '17 at 18:34
  • $\begingroup$ Usually $Q$ is symmetric in these sorts of problems, otherwise replace $Q$ by ${1 \over 2} (Q+Q^T)$. The cost function remains the same. $\endgroup$ – copper.hat Dec 4 '17 at 18:41
  • $\begingroup$ In fact, if we keep the $\frac{1}{2}$ in so that we let the first order conditions be $\displaystyle \frac{1}{2}Q^{T}x+c-A^{T}\lambda = 0$, then $x = (Q^{-1})^{T}(2A^{T}\lambda -2c)$. Why isn't it? Also, how then do you get the dual problem? $\endgroup$ – ALannister Dec 4 '17 at 18:42
  • $\begingroup$ No, the derivative of the cost function is ${1 \over 2}(Q+Q^T) x + c-A^T \lambda$. $\endgroup$ – copper.hat Dec 4 '17 at 18:43
  • $\begingroup$ But assuming that $Q$ is symmetric in the first place is simpler, and usual for these sorts of things. $\endgroup$ – copper.hat Dec 4 '17 at 18:44

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.