3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you assuming $ H$ is symmetric positive semidefinite? $\endgroup$ – littleO Mar 28 '16 at 11:23
  • $\begingroup$ Yes, I am. Sorry. I'll put it in there $\endgroup$ – ANYN11 Mar 28 '16 at 11:32
  • $\begingroup$ Thanks. I think it would help also if you write down the primal problem. $\endgroup$ – littleO Mar 28 '16 at 11:36
1
$\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$
  • $\begingroup$ You are right. The constraint on lambda is not correct. I'll delete it. Further I've come up with some answers for some of the question myself. Thanks for your reply though :) $\endgroup$ – ANYN11 Mar 29 '16 at 16:12
  • $\begingroup$ @littleO I'm working on a problem similar to this, where I have posted a question here: math.stackexchange.com/questions/2571031/… Would you be willing and/or able to take a look and possibly help me out? Thanks so much! :) $\endgroup$ – ALannister Dec 17 '17 at 21:53

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.