# How to formulate the (Lagrangian) dual problem in this case?

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.

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

• isn't it $Q^{T}x+c-A^{T}\lambda = 0$, though? – ALannister Dec 4 '17 at 18:34
• 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. – copper.hat Dec 4 '17 at 18:41
• 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? – ALannister Dec 4 '17 at 18:42
• No, the derivative of the cost function is ${1 \over 2}(Q+Q^T) x + c-A^T \lambda$. – copper.hat Dec 4 '17 at 18:43
• But assuming that $Q$ is symmetric in the first place is simpler, and usual for these sorts of things. – copper.hat Dec 4 '17 at 18:44