I'm working on the following (convex) optimization problem:
Let $Q$ be an $n \times n$ positive semidefinite matrix, $A$ an $m\times n$ matrix and $b\in \mathbb{R}^m$. Determine the Lagrange dual of \begin{align} \min\{x^TQx \ | \ Ax\leq b , \ x\in\mathbb{R}^n \} \end{align} My problem is especially what if $Q$ is not invertible? There is where I get stuck.
Attempt:
I have calculated the Lagrangian $\phi(x,u)$ and that is: \begin{align} \phi(x,u)=x^TQx + u(Ax-b) \end{align} The Lagrange dual function $\Theta(u)$ is: \begin{align} \Theta(u) = \inf_{x\in\mathbb{R}^n} \phi(x,u) \end{align} To have an explicit form for it I minimized $\phi$ w.r.t. $x$. So I differentiated and equated to zero: \begin{align} \nabla_x \phi(x,u) = 2x^TQ + uA = 0 \end{align} That gives: \begin{align} x^TQ= -\frac{u}{2}A \end{align} Now two cases:
Case I: $Q$ invertible, then it is easy. I get $x=-\frac{1}{2}(Q^{-1})^TA^Tu^T$. Then I put it in $\phi(x,u)$ and get expression for $\Theta(u)$ what automatically gives me the Lagrange dual.
Case II: $Q$ is not invertible, then I really do not know how to proceed.
The primal model is \begin{array}{ll} \text{minimize} & x^T Q x \\ \text{subject to} & A x \leq b \end{array} The Lagrangian is $$L(x,u) = x^TQx - u^T(b-Ax)$$ where the Lagrange multiplier $u$ is nonnegative. The dual function is $$g(u) = \inf_x x^TQx - u^T(b-Ax)$$ The optimality conditions for the infimum are indeed $$2Qx+A^Tu=0$$ as you have pointed out. Because the infimum expression is convex, all values of $x$ that satisfy the optimality conditions must result in the same value of $g(u)$. Therefore, $$g(u) = \begin{cases} x^TQx - u^T(b-Ax) & \exists x ~\text{s.t.}~ 2Qx+A^Tu=0 \\ -\infty & \not\exists x~\text{s.t.}~2Qx+A^Tu=0 \end{cases}$$ The key is to realize that when the optimality condition is satisfied, we have \begin{aligned} x^TQx - u^T(b-Ax) &= x^TQx - b^T u + (A^Tu)^Tx \\&= x^TQx-b^Tu-2x^TQx \\&= -b^Tu - x^TQx \end{aligned} This last form of the expression is useful to us because it is concave in both $x$ and $u$! Therefore, we can write the dual as follows: \begin{array}{ll} \text{maximize} & -b^T u - x^T Q x \\ \text{subject to} & 2Qx + A^T u = 0 \\ & u \geq 0 \end{array} It might seem strange to leave the primal variable in the Lagrange dual, but this is exactly what the Wolfe dual does for general NLP. But unlike the general Wolfe dual, the objective function is jointly concave in $x$ and $u$, so it can be solved as-is.