# Dual problem of quadratic program general theory

At the moment I'm studying constrained optimization. Recently we had a lecture concerning dual problems. I have a few questions regarding this.

The primal problem is given as \begin{align} \min_x \quad & \frac{1}{2} x^THx+g^Tx \\ \text{s.t.} \quad & A^Tx = b . \end{align} The Lagrange dual program of the equality constrained QP is given as \begin{align} \max_{x,\lambda} & \qquad - \frac{1}{2} x^THx+b^T \lambda, \\ \text{s.t} & \qquad Hx+g-A\lambda = 0. \\ \end{align} It's assumed that the matrix H is positive definit.

My questions are as follows?

1. How is this maximization problem derived?
2. What are the optimality conditions for the dual problem and how are they related to the primal problem?
3. When does the primal and dual problem have the same solution?
4. Can one use KKT for the solution of this problem?
5. How are the variables in the primal and dual problem related in general?
6. What are the advantage of solving the dual instead of the primal problem?

I have a few suggestions myself.

Q1: I've read that we define the dual objective as the infimum of the Lagrange, that is $q(\lambda) = \inf_x L(x, \lambda)$. The dual problem is then the maximization of q. However I'm in doubt about the constraints in the dual problem.

Q2: Don't know.

Q3: Is it when the primal problem is strictly convex (meaning a positive definite hessian in the primal objective function)?

Q4: Don't know. Guess it depends on the optimality conditions somehow.

Q5: Don't know.

Q6: Don't know.

• Are you assuming $H$ is symmetric positive semidefinite? – littleO Mar 28 '16 at 11:23
• Yes, I am. Sorry. I'll put it in there – ANYN11 Mar 28 '16 at 11:32
• Thanks. I think it would help also if you write down the primal problem. – littleO Mar 28 '16 at 11:36

I'll assume that $H$ is symmetric positive definite (as stated in the question).
The dual problem is to maximize $g(\lambda)$ (with no constraints on $\lambda$). Is this equivalent to the dual problem given in the question? From the constraint $Hx + g - A \lambda = 0$, it follows that $x = H^{-1}(A \lambda - g)$. Plugging into the objective function, the stated dual problem reduces to \begin{align} \text{maximize} & \quad -\frac12 (A \lambda - g)^T H^{-1}(A \lambda - g) + b^T \lambda \\ \text{subject to} & \quad \lambda \geq 0. \end{align} This is similar to the dual problem I derived, except that we have $-g$ in place of $g$ and we have an extra constraint $\lambda \geq 0$.