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?
- How is this maximization problem derived?
- What are the optimality conditions for the dual problem and how are they related to the primal problem?
- When does the primal and dual problem have the same solution?
- Can one use KKT for the solution of this problem?
- How are the variables in the primal and dual problem related in general?
- 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.
$\endgroup$ 32 Answers
$\begingroup$I'll assume that $H$ is symmetric positive definite (as stated in the question).
The Lagrangian is \begin{align} L(x,\lambda) &= \frac12 x^T Hx + g^T x + \lambda^T (A^Tx - b) \\ &= \frac12 x^T H x+ x^T (A \lambda + g) - \lambda^T b. \end{align} The dual function is \begin{align} g(\lambda) &= \inf_x \, L(x,\lambda) \\ &= -\frac12 (A \lambda + g)^T H^{-1} (A \lambda + g) - \lambda^T b. \end{align}
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$.
It seems like the dual problem given in the question is wrong.
$\endgroup$ 5 $\begingroup$I searched some literature. It appears this duality is from the paper Duality in Quadratic Programming by W. S. Dorn. Here is a link to that paper: .
$\endgroup$
