Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be an $m$x$n$ real matrix. Let QP denote the problem: minimise $f(x,y) = \frac12 x^Tx$ such that $x \ge 0, y\ge 0$, and $Ax-y=b$.

I want to prove that the dual of this problem QP* is: maximise $ f^*(\lambda, \mu, x) = \lambda^Tb - \frac{1}{2} x^Tx$ such that $\lambda\ge 0, \mu \ge 0$ and $x = A^T \lambda + \mu$. I am having some trouble however and I was hoping somebody would point me in the right direction.

I started by defining the lagrange $L(x,y,\lambda) = \frac12 x^Tx - \lambda^T (Ax - y -b)$, and my goal is to find $g(\lambda):= \displaystyle\inf_{x,y}L(x,y,\lambda)$, and then maximise over such $\lambda$ where this $g(\lambda)$ has a finite minimum. I observed that since $L(x,y,\lambda) = \frac12 x^Tx - \lambda^T Ax + \lambda^T y +\lambda^T b$, then this only has a finite minimum if we ensure $\lambda^T y \ge 0$, i.e. that $\lambda \ge 0$. So to minimise the Lagrange, it makes sense to set $y=0$.

By partially differentiating the Lagrange, I get that the vector $(x,y) = (A^T \lambda, 0)$ (thinking of vectors within a vector here) minimises L, so I have $$g(\lambda) = -\frac12(A^T \lambda)^T (A^T \lambda) + \lambda^T b.$$

Is this analysis correct? How do I write it in the given form QP*? I am very confused about where the $x$ and the $\mu$ come from, as well as the constraints. Any help would be greatly appreciated with this!

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.