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.


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.

  • $\begingroup$ Interestingly, what I've found in practice is that $x$ stays in the dual problem. The equation 2Qx + A^Tu = 0 stays in the dual problem as is. As long as the resulting problem remains convex there's nothing really "wrong" with this. Quadratic programs are unique in this fashion, because normally, if you don't eliminate $x$, the resulting model has non-convex expressions. $\endgroup$ – Michael Grant Nov 2 '17 at 15:36

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.


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.